从字符变成层级结构

源程序是一串字符,抽象语法树则把其中的表达式、语句和声明组织成节点。一个二元运算节点可以保存操作符和左右输入,函数调用节点保存被调用对象及实参。分析程序因此能够沿结构访问组成部分,而不必在每次检查时重新从字符中猜测它们属于哪条规则。

参考:[1]

优先级体现在树形中

同一行里的运算符并不一定按书写顺序执行。分析器把优先级和括号确定的组合方式写进树里,例如让乘法节点成为加法节点的一个子节点。LLVM教程用递归下降处理基本语法,再用运算符优先级分析处理表达式,使后续阶段得到明确的计算结构。

参考:[2]

抽象会略去部分写法

抽象语法树通常不保存所有标点和排版细节;不同写法只要形成相同结构,就可能得到相近的树。注释、空白与原始括号是否保留,取决于工具的表示设计。需要原样重写文件的格式化器,往往还需额外保存这些信息,不能只依赖语义结构重建原来的全部文本。

参考:[1]

检查与转换的中间表示

树可以供类型检查、静态分析和代码生成使用,也可以由程序修改后重新生成代码。Python的ast模块提供解析、遍历和节点变换工具,但生成可执行代码仍要满足节点规则与位置信息要求。语法树表达了程序怎样组成,名字指向什么对象和程序会产生什么效果,还需要其他分析配合。

解析出树也不等于程序已经通过全部合法性检查。Python的ast.parse可以为单独的return 42构造返回语句节点,但把它作为独立程序编译时仍会报语法错误,因为返回语句需要处于函数内部。解析阶段没有完成的作用域检查,会在编译阶段继续进行。这个例子把“输入能组成语法节点”“节点在当前位置合法”和“程序运行结果正确”分成了不同问题。

参考:[2] [3]