编译原理笔记9：语法分析树、语法树、二义性的消除
具体语法树和抽象语法树是两个不同的概念。通常情况下，前者被称为“具体语法树”，它能够展现推导的步骤；而后者则被称为“抽象语法树”，它只关注最终的结果，并不涉及推导过程。
具体语法树是语言推导过程的图形化表示，它反映了语言的本质和推导过程。
对于上下文无关文法（CFGG）的句型，分析树被定义为一棵具有特定性质的树，它能够展示推导过程，包括最左推导和最右推导。
虽然这两种推导方式在推导过程中的分析树可能不同，但最终得到的句子是相同的，因此最终的分析树是一样的。
分析树能够反映句型的推导过程和结构。
然而，实际上我们更关心的是推导的结果，而不是过程。
因此，我们需要对分析树进行改造，得到抽象语法树。
在抽象语法树中，只包含终结符，不包含非终结符，并且没有括号。
抽象语法树的特点是：叶子节点都是操作数，内部节点都是操作符，树中不包含非终结符和括号。
抽象语法树表达了操作符作用于操作数的关系。
例如，对于表达式-(id+id)和-id+id，它们的抽象语法树能够直观地展示运算顺序。
然而，有时候一个句子可能对应多个抽象语法树，这就是二义性问题。
例如，对于文法G：E→E+E|EE|(E)|-E|id，句子id+idid和id+id+id可能的分析树有多种情况。
虽然对于id+id+id，无论“+”是左结合还是右结合都不会影响结果，但如果“+”的含义变成了减法，那么左结合和右结合就会导致不同的结果。
在这里，我们所说的“二义性”指的是一个句子对应多个分析树，而不是语义上的歧义。
二义性的产生是由于句子产生过程中的某些推导有多种选择。
例如，悬空else问题就是一个很好的例子，它展示了超过一种选择导致的二义性问题。
在二义文法中，由于else可以与多个then配对，因此会导致二义性。
为了解决这个问题，我们可以规定else右结合，即与左边最靠近的then结合。
为了消除二义性，我们可以使用改写的方法，将二义文法改写为非二义文法。
改写的关键是将优先级和结合性明确说明白，确保每个非终结符只负责一个优先级的运算符号，避免出现歧义。
改写后的非二义文法具有以下特点：优先级由低到高分别是+、-，距离开始符号越近，优先级越低；每个符号对应一层的非终结符；根据所需的结合性，确定是左递归还是右递归。
我们已经掌握了改写这个工具，可以用来消除二义性。
接下来，我们将使用这个工具来解决悬空else问题。
悬空else问题出现的原因是then数量多于else，导致else有多个可以结合的then。
在二义文法中，由于可以选择不同的then和else配对，因此会导致二义性。
在这里，我们规定else右结合，即与左边最靠近的then结合。
为了改写此文法，我们可以将S分为完全匹配（MS）和不完全匹配（UMS）两类。
在MS中，then和else数量相等，且else右结合；在UMS中，then和else数量不匹配，且else右结合。
通过改写后的文法，我们可以消除二义性。
虽然二义文法会导致二义性，但它也有一些优点。
例如，在Yacc中，我们可以直接指定优先级和结合性，而无需自己重写文法。
left表示左结合，right表示右结合，越往下的算符优先级越高。
实际上，我们可以将语言本身定义成没有优先级和结合性的，然后通过括号来控制运算顺序。
例如，在Ada中，通过明确的标志来标记过程的结束；在Pascal中，通过给表达式加括号来实现运算顺序的控制。
AST抽象语法树原理与创建
AST抽象语法树的构成与构建概述 概念阐述：抽象语法树（AST）是对源代码语法结构的抽象化表示，采用树形结构直观地展示代码的组织形式。每个节点映射源代码的特定元素，如指令、表达式和变量等。
通用性：AST不拘泥于特定编程语言的语法细节，如规则和实现方式，它提供了一种普遍适用的、跨语言的表示手段。
功能价值：AST在编译器各个阶段，包括前端和后端，充当了沟通的桥梁，促进了编译流程的高效执行和优化。
构建步骤： 1 . 词法分析：对源代码进行解析，分解为基本元素（词素），并清除无关的空白和注释，这是构建AST的初始步骤，为后续的语法分析打下基础。
2 . 语法分析：将词法分析的结果组织成树形结构，并检查语法是否合规。
生成的AST与源代码不完全相同，因为分析器会剔除一些冗余的标识，例如未闭合的括号。
3 . 语义分析：对AST进行深入审查，确保程序遵循语言的语义规则，并搜集类型数据。
类型验证是语义分析的关键环节，它确认运算符与操作数是否兼容，并允许进行适当的类型转换。
此阶段为生成中间代码提供必要的语义和类型信息。
具体实施：在特定开发环境中，可利用相应的API生成有效的AST。
随后，借助编译器对象添加引用和AST，并通过GetSemanticModel方法获取语义模型，以支持后续的语义分析。
总结：AST作为源代码的抽象表示，其构建过程包括词法、语法和语义分析等多个环节，为代码的生成和优化提供了清晰的框架和类型信息。
计算机自制解释器Pascal（七）：抽象语法树AST
抽象语法树（AST）在Pascal解释器中扮演着核心角色，其构建方式如下所述： AST概述：简称为AST，它是以树形结构展示源代码语法结构的抽象表示。在Pascal的编译或解释阶段，AST充当一个中间层，用来保存源代码的语法信息，便于进一步的代码处理。
解析器模块在AST构建中的角色：解析器是构建AST的核心部分，它通过递归调用多个函数，依据语法规则，将词法分析器输出的TOKEN组织成树形结构。
这些函数各自负责处理特定的语法元素，如数字、括号、运算符等，逐步构建出完整的AST。
以“6 /3 2 +4 5 ”表达式为例，解析器首先用factor函数识别出6 、3 、2 、4 作为树的叶子节点。
随后，term函数处理乘除运算，将乘法运算符与数字节点连接，形成子树。
expr函数最终处理加减运算，将加号与之前的子树结合，形成整个表达式的AST。
AST的深度遍历：在解释器执行阶段，需要对AST进行深度遍历。
这意味着从expr节点开始，递归访问每个节点，直到达到数字或运算符节点，确保解释器能按正确顺序执行计算，得出正确结果。
从代码到AST的转变过程：Token类与词法分析器协同工作：词法分析器扫描源代码，识别出TOKEN，为AST的构建打下基础。
解析器的动作：解析器接手TOKEN，依据语法规则，通过递归调用和树形组合函数，逐步构建出完整的AST。
解释器的角色：解释器遍历AST，按照既定顺序执行计算，并输出最终的执行结果。
通过这一过程，Pascal源代码被转换成易于理解和执行的AST结构，实现了对Pascal代码的解释和执行。
