美文网首页
初识抽象语法树(AST)

初识抽象语法树(AST)

作者: madeirak | 来源:发表于2020-01-01 20:13 被阅读0次
    • 基本概念
    1. 基本字:阿拉伯数字、大小写拉丁字母、其他字符(~、!、%、&、_、-、+、=、{}、[]、:、;、<、>、,、.、?、/、|、\)、空格符、换行符、制表符等。
    2. 关键字(keyword):提前被定义,并赋予有特殊的含义的单词
    3. 保留字: 提前被定义,但还未被赋值(保留字与关键字有时等价)
    4. 标识符(identifier): 由数字、字母、下划线组成,且不能以数字开头,用于给变量、常量、函数、语句块等命名。
    • c语言中标识符包括:关键字(如int、while)、预定义标识符(如printf)和用户自定义标识符。

    当下的编译器都做了纯文本转AST的事情。

    一款编译器的编译流程是很复杂的,但我们只需要关注词法分析语法分析,这两步是从代码生成AST的关键所在。

    • 词法分析器(scanner)
    词法分析器结构

    在扫描器的驱动下,预处理子程序将到输入缓冲区中源代码的字符处理后由
    扫描缓冲区读入。扫描器在扫描缓冲区中识别单词符号,然后输出。

    其中预处理子程序的作用是:

    1. 剔除源代码中的空格、回车符、换行符等编辑性字符
    2. 区分标号区、捻接续行,给出句末符等等

    现代程序设计语言在最初设计时就遵循了一些规则:

    1. 所有基本字都是保留字,不可再作为标识符
    2. 基本字作为特殊的标识符处理
    3. 基本字、标识符和常数间若没有确定的运算符或界符作间隔,必须使用一个空白符作间隔,一方面避免了超前搜索、方便编译程序进行词法分析,另一方面增加代码的可读性

    • 词法分析器设计:
    1. 确定语言单词规范——单词表
    2. 有单词表得到该语言所有字的状态转换图
    3. 根据状态转换图实现词法分析器

    词法分析器会读取代码,它会一个一个字母地读取代码,所以很形象地称之为扫描(scanner)。然后把它们按照预定的规则合并成一个个的标识(tokens),当它遇到空格、操作符,或者特殊符号的时候,它会认为一个话已经完成了。同时,它会移除空白符、注释等。最后,整个代码将被分割进一个 tokens 列表(或者说一维数组)

    //词法分析器典型输入输出
    const a = 5;
    // 转换成
    [{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]
    

    • 语法分析器(parser)

    语法分析会将词法分析出来的列表转换成树形的形式,同时验证语法。语法如果有错的话,抛出语法错误。

    [{value: 'const', type: 'keyword'}, {value: 'a', type: 'identifier'}, ...]
    // 语法分析后的树形形式
    {
       type: "VariableDeclarator", //变量声明
       id: {
           type: "Identifier",//标识符
           name: "a"
       },
       ...
    

    当生成树的时候,解析器会删除一些没必要的标识 tokens(比如:不完整的括号),因此 AST 不是 100% 与源码匹配的。


    • 语法分析相关概念
    1. 巴克斯范式(EBNF)【巴克斯范式(Backus Form)简单例子-from知乎
    EBNF元符号 含义
    ::= 可解释为,可推导为
    |
    () 一项,一次重复
    [] 0次和1次重复
    {} 0次或任意多次重复
    . 一条生成规则的结束
    <> 非终结符
    “” 终结符
    1. 翻译单元: 什么是翻译单元?

    酷文章: ==C实现词法分析及语法分析==


    现在,我们拆解一个简单的add函数

    function add(a, b) {
        return a + b
    }
    

    首先,我们拿到的这个语法块,是一个FunctionDeclaration(函数定义)对象。

    用力拆开,它成了三块:

    • 一个id,就是它的名字,即add
    • 两个params,就是它的参数,即[a, b]
    • 一块body,也就是大括号内的一堆东西
    {
        name: 'add'
        type: 'identifier'
        ...
    }
    

    params继续拆下去,其实是两个Identifier组成的数组。之后也没办法拆下去了。

    [
        {
            name: 'a'
            type: 'identifier'
            ...
        },
        {
            name: 'b'
            type: 'identifier'
            ...
        }
    ]
    
    • 接下来,我们继续拆开body,我们发现,body其实是一个BlockStatement(块状域)对象,用来表示是\color{blue}{\{return\ a + b\}}

    • 打开Blockstatement,里面藏着一个ReturnStatement(Return域)对象,用来表示\color{blue}{return\ a + b}

    • 继续打开ReturnStatement,里面是一个BinaryExpression(二项式)对象,用来表示\color{blue}{a + b}

    • 继续打开BinaryExpression,它成了三部分,\color{blue}{left}\color{blue}{operator}\color{blue}{right}

    • \color{blue}{operator }\color{blue}{+}

    • \color{blue}{left} 里面装的,是Identifier对象 \color{blue}{a}

    • \color{blue}{right }里面装的,是Identifer对象 \color{blue}{b}

    就这样,我们把一个简单的add函数拆解完毕,用图表示就是

    "add" `s AST

    酷文章:

    词法分析器中的预处理程序部分
    词法分析器中的词法分析程序部分
    词法分析器

    相关文章

      网友评论

          本文标题:初识抽象语法树(AST)

          本文链接:https://www.haomeiwen.com/subject/jtmwoctx.html