编译原理语法分析一节中的一些疑问与思考

编译原理语法分析一节中的一些疑问与思考

“向前看”符号是啥

输入中当前被扫描的终结符号通常被称为“向前看”符号；

在开始时，向前看符号是输入串中的第一个(即最左的)终结符号；

向前看符号被用以确定应该使用哪个产生式，如果向前看符号在FIRST(α)中，就使用α，如果向前看符号在FIRST(β)中，就使用β；

个人理解，向前看符号只是被拎出来，备着解释后面的避免回溯时用到的“消除公共左因子法”用的，当然，在这里来看，向前看符号是一种分割，表示现在只处理向前看符号后面的非终结符，不管前面的部分了；

预测分析法相比一般的自顶向下分析法，其无需回溯的优点是如何获取的？

“回溯”本身就是因为备选的产生式集合中各个产生式具有公共左因子导致的，当不确定应该对一个非终结符号使用哪一个产生式的时候，就只能猜测着一个个地试过去，假如试错了，那就只能回溯，最后要么有一个产生式可以与之对应，要么完全找不到，假如没有任何产生式能解释这个字符串，那么就只能认为输入的字符串有语法错误；

预测分析法用了一个“消除公共左因子”的技巧，经过这个处理之后，构建的产生式集合中任意两个不同的产生式不再会含有公共左因子，那么编译的时候遇到这种情况就不再需要试错了，直接用那个对应的产生式就可以了，于是就消除了回溯的问题；

消除公共左因子的方法是，将含有公共左因子的产生式体集合中，所有的产生式体最左侧的那个终结符号单独提出来，让剩下的部分构成另一些产生式的体，这样就将含有公共左因子的产生式集合拆分成了逻辑上的两部分，其中一部分负责让外部原本犹豫的挑选者进入这个集合，另一部分向挑选者给出真正有区分度的选项以供选择；

举个例子说明，

对于

1

A→αβ|αγ

1
2

A→αA'
A'→β|γ

语法分析树 VS 抽象语法树

这又是一个Versus问题；

语法分析树

先说语法分析树，因为这个是最先接触到的；

语法分析树用图形方式展现了从文法开始符号推导出相应语言中的符号串的过程，如果非终结符号A有一个产生式A→XYZ，那么在语法分析树中就可能有一个标号为A的内部结点，该结点有三个子结点，从左到右的标号分别是X、Y、Z；

插图画不出来，自行想象一个有三个叶子的树，根结点是A，叶子结点分别是X，Y，Z

当然，留意原文说的是“内部结点”和“子结点”，并没有说这就是一棵树，因为它可能仅仅是一棵树内部的一部分；

正式地讲，给定一个上下文无关文法，该文法的一棵语法分析树是具有以下性质的树

1. 根结点的标号为文法的开始符号；

2. 每个叶子结点的标号为一个终结符号或ε；

3. 每个内部结点的标号为一个非终结符号；

4. 如果非终结符号A是某个内部结点的标号，...

第四条可以自己去找本CPTT，翻到P28去看，我懒得把原文那么长一段话打上去了，大意就是，树长什么样那么产生式就是啥样，假如说某非终结符号A的产生式仅仅有一个A→ε，那么这个树就有一个内部结点A的叶子是ε；

最后，语法分析树又被称作具体语法树

抽象语法树

抽象语法树是那个经常被简称为“语法树”的树，而且也正是那个大名鼎鼎的“AST”

抽象语法树是一种数据结构，在设计一个翻译器时，抽象语法树是一个很好的起点。

在一个表达式的抽象语法树中，每个内部结点代表一个运算符，该结点的子结点代表这个运算符的运算分量。

一棵语法树中的每个结点代表一个程序构造，这个结点的子结点代表这个构造中有意义的组成部分，表达式E₁+E₂的语法树根结点的标号为+，且两个子结点分别代表子表达式E₁和E₂；

我们将使用具有适当数量的字段的对象来实现一棵语法树的各个结点；每个对象将有一个op字段，也就是这个结点的标号，这些对象将具有如下所述的其他字段：

• 如果结点是一个叶子，那么对象将有一个附加的域来存放这个叶子结点的词法值，构造函数leaf(op,val)创建一个叶子对象，我们也可以把结点看做记录，那么leaf就会返回一个指向与叶子结点对应的新记录的指针；

• 如果结点是一个内部结点，那么它的附加字段的个数和该结点在语法树中的子结点个数相同，构造函数Node带有两个或更多参数：Node(op,c₁,c₂,...,ck)，该函数创建一个对象，第一个字段的值为op，其余k各字段的值为c₁,...,ck

简单来说

简单来说：

在抽象语法树中，内部结点代表的是程序构造；

在语法分析树中，内部结点代表的是非终结符号；

Knighthana

2023/04/09