02 Syntactic Analysis

语法分析

在词法分析以后，我们希望能够得到表达式和程序语句的抽象语法树。例如对于(1+x)*y，我们希望根节点为*，左儿子为+，右儿子为y，+的儿子分别是1和x。

上下文无关语法

对抽象语法树的构建是基于一套“上下文无关语法”完成的。一套上下文无关语法是一系列“产生式”，它规定了表达式和程序语句的基本单元（终结符）、包含关系（产生式、非终结符）以及一个初始符号。例如

S -> S ; S E -> ID L -> E S -> ID := E E -> NAT L -> L , E S -> PRINT ( L ) E -> E + E E -> ( E )

就是一套上下文无关语法，S是初始符号，表示程序语句。这套语法允许程序语句的顺序执行、赋值语句、打印语句。E表示表达式，这套语法允许表达式的加法运算。L是表达式的参数列表。

如果能把一个程序语句，例如ID := ID + NAT; PRINT(ID, ID)按以上规则一步一步缩减到初始符号S，我们就完成了抽象语法树的构建。这个过程称之为“归约”。与之相反的称为“派生”，是从S出发按照语法规则展开得到具体的程序语句。规约是派生的反向，我们先来考察派生。

派生

我们规定在派生时每次都展开最左侧的非终结符，这称为最左派生（当然也可以有最右派生）。例如对上述语法，我们有如下最左派生：

S -> S; S -> ID := E; S -> ID := E + E; S -> ID := ID + E; S -> ID := ID + NAT; S -> ID := ID + NAT; PRINT(L) -> ID := ID + NAT; PRINT(L, E) -> ID := ID + NAT; PRINT(E, E) -> ID := ID + NAT; PRINT(ID, E) -> ID := ID + NAT; PRINT(ID, ID)

有了派生过程以后，我们就得到了抽象语法树。树的根节点是S，它有三个子节点S，;，S……以此类推。

我们希望对于一个标记串只对应唯一的抽象语法树。并不是所有上下文无关语法都有这样的唯一性的。如果一个标记串对应的抽象语法树不唯一，我们就称它出现了“歧义”。例如：E -> ID, E -> E + E, E -> E * E, E -> ( E ) 这一上下文无关语法没有规定乘法和加法的优先级，因此对于E+E*E这样的标记串就能对应两个完全不同的抽象语法树。为此，我们要重新设计语法消除歧义：E -> F, E -> E + E, F -> F * F, F -> ( E ), F -> ID 。如果一个标记串没有歧义，那么只有唯一的最左派生可以生成这一标记串。

规约

规约是派生的反过程。由于规约和派生的过程是相反的，最左派生对应着最右规约，最右派生对应着最左规约。现在我们要讨论，在给定一个标记串时，如何对它做最左规约。

我们采用一个称为“移入规约分析”的方法。从左到右扫描标记串，每一时刻我们可以选择做两个操作中的一个：移入或者规约。移入是指把扫描线向右移动一格；规约是指对紧贴扫描线左侧的标记串根据语法规则做一步代换。以下是一个在E -> F, E -> E + E, F -> F * F, F -> ( E ), F -> ID语法下对ID+ID+ID做移入规约分析的例子：

| ID + ID + ID -> ID | + ID + ID -> G | + ID + ID -> F | + ID + ID -> E | + ID + ID -> E + | ID + ID -> E + ID | + ID -> E + G | + ID -> E + F | + ID -> E | + ID -> E + | ID -> E + ID | -> E + G | -> E + F | -> E |

移入判断

要判断某一时刻能否做移入，就是要分析扫描线左侧的结构。如果在移入一个字符后形成的新的结构是可行的，我们就认为移入是可行的。对于任何一个扫描线左侧结构，它都应当可以被拆分成若干段，使得每一段是某个产生式右侧符号串的一个前缀，而这个产生式一定是前一段中缺失的那个非终结符对应的产生式。只有这样才是一个可行的结构。于是我们可以从初始状态出发，写出产生式，在产生式右侧和当前标记串前缀第一个不匹配的地方截断，然后写出截断后的第一个非终结符对应的所有产生式，在所有产生式与标记串不匹配的地方截断，再依次写出新的产生式……如果进行到某一步以后，发现没有可以匹配的产生式了，就意味着当前扫描线左侧结构是不可行的。例如，在E->F, E->E+E, F->F*F, F->(E), F->ID语法下判定E+F+|是否是可行的扫描线左侧结构：

初始状态是.E，句号表示截断点。由于截断点后的第一个非终结符为E，因此要考虑所有E的产生式，E又有右侧紧跟F的产生式，所以又要写出F的产生式，然后又要写出G的，至此不再有非终结符了。因此初始时我们要考虑以下产生式：

START -> . E E -> . F E -> . E + F F -> . G F -> . F * G G -> . ( E ) G -> . ID

得知第一个字符为E以后，截断点向右移动一位，只需考虑以下产生式：

START -> E . E -> E . + F

下一个是+：

E -> E + . F F -> . G F -> . F * G G -> . ID G -> . ( E )

然后是F：

E -> E + F . F -> F . * G

然后是+。但此时截断点后面没有能匹配加号的了，由此可得E+F+不是一个可行的扫描线左侧结构。

上面这个过程可以用一个NFA来完成，一个标记串是否是一个扫描线左侧的可行结构就看它能否被这个NFA接受。

规约判断

我们已经看到，能否规约依赖的是标记串对应的右侧产生式前缀之间的包含关系。我们可以采用一个基于First集合和Follow集合的方法来判断规约。对于终结符X和任意的标记Y，定义X 是Follow(Y) 的元素当且仅当... Y X ...是可能被完全规约的。X是First(Y) 的元素当且仅当X ...是可能被规约为Y的。X $\in$ Follow(Y)意味着考虑规约时X被允许follow在Y以后；X $\in$ First(Y)意味着考虑规约时X被允许作为Y中的第一个标记；

我们可以这样计算First集合
• 对任意终结符 X ， X $\in$ First(X) 。
• 对任意产生式 Y -> Z ... ， First(Z) $\subseteq$ First(Y) 。
这样计算Follow集合：
• 对任意产生式 U -> ... Y Z ... ， First(Z) $\subseteq$ Follow(Y) 。
• 对任意产生式 Z -> ... Y ， Follow(Z) $\subseteq$ Follow(Y) 。

如果紧贴扫描线左侧的标记没有落在其左侧标记的Follow集合中，那么此时一定不可以进行规约操作。

冲突

在移入规约分析中，如果某一时刻只能选择移入，那么自然选择移入；如果只能选择规约并且只有唯一的规约方式，那么自然选择这样规约；如果既不能移入也不能规约，那么说明表达式不合语法，失败。

问题是：如果某一时刻又可以选择移入又可以选择规约，或者只能规约但是存在多种不同的规约方式，这时怎么办呢？前者称为移入/规约冲突，后者称为规约/规约冲突。冲突并不是移入规约分析能解决的问题，而是语法设计的问题。一个好的上下文无关语法设计应当不容许冲突的发生，使得移入规约分析能顺利的完成，抽象语法树得到顺利的构建。