BUAACT-Chap04-语法分析
第四章 语法分析
4.1 语法分析概述
功能：根据文法规则，从原单词程序符号串中识别出语法成分，并进行语法检查。
基本任务：识别符号串 S 是否为某语法成分。
两大分析方法：
- 自顶向下分析
- 自底向上分析
4.2 自顶向下分析
4.2.1 自顶向下分析的一般过程
给定符号串 \(S\)，若预测他是某语法成分，那么可根据该语法成分的文法，设法为 \(S\) 构造一棵语法树。
- 如成功，则 \(S\) 最终被识别为某一语法成分。即 \(S\in L(G[Z])\)，其中 \(G[Z]\) 为某语言成分的文法；
- 若不成功，则 \(S \notin L(G[Z])\)。
4.2.2 自顶向下分析的特点
- 分析过程是带有预测的。即要根据输入符号串中下一个单词，来预测之后的内容属于什么语法成分，然后用相应语法成分的文法建立语法树；
- 分析过程是一种试探过程，是尽一切办法（选用不同规则）设法建立语法树的过程。由于是试探过程，故难免有失败，所以分析过程需进行回溯，因此我们也称这种方法是带回溯的自顶向下分析方法。
- 最左推导可以编出程序来实现，但在实际上价值不大，效率低，代价高。
4.2.3 自顶向下分析存在的问题及解决方法
1. 左递归文法
有如下文法：
令 \(U\) 是文法的任一非终结符，文法中有规则：
则这个文法是左递归的。
自顶向下分析不能处理具有左递归性的文法。要实行自顶向下分析，必须要消除文法的左递归。
消除直接左递归的规则
规则一（提因子）
若：\(U::=xy|xw|...|xz\)
则可以改写为：\(U::=x(y|w|...|z)\)
其中再若：\(y=y_1y_2, w=y_1w_2\)，
则 \(U::=x(y_1(y_2|w_2)|...|z)\)
若有规则：\(U::=x|xy\)
则可以改写为：\(U::=x(y|\varepsilon)\)
注意：不应写成 \(U::=x(\varepsilon|y)\)，总要把 \(\varepsilon\) 安置成最后的选择。
规则二
若有文法规则：\(U::=x|y|...|z|Uv\)
可以改写为 \(U::=(x|y|...|z)\{v\}\)
特点是：具有一个直接左递归的右部并位于最后，这表明该语法类 \(U\) 是由 \(x\) 或 \(y\) 等打头，期后跟随零个或多个 \(v\) 组成。
规则三（将左递归改写为右递归）
若：\(P::=P\alpha|\beta\)
则可改写为：
\(P::=\beta P'\)
\(P'::=\alpha P'|\varepsilon\)
2. 回溯问题
文法中，对于某个非终结符号的规则其右部有多个选择，并根据所面临的输入符号不能准确地确定所要的产生式，就可能出现回溯。
避免回溯的手段
设文法 \(G\)（不具左递归性），\(U \in V_n\)
\(U::= \alpha_1| \alpha_2 | \alpha_3\)
定义头符号集 \(FIRST(\alpha_i) = \{a |\alpha_i\Rightarrow a…, a\in V_t\}\)
为避免回溯，对文法的要求是 \[FIRST(\alpha_i)\cap FIRST(\alpha_j)=\varnothing\]
改写文法
对多个右部的规则反复提取左因子。例如：
\(U::=xV|xW,(U,V,W\in V_n, x\in V_t)\)
改写为 \(U ::= x(V|W)\)
更清楚的表示：
\(U::=xZ\)
\(Z::=V|W\)
超前扫描
当文法不满足避免回溯的条件时，即各选择的首符号相交时，可以采用超前扫描的方法，即向前侦察各输入符号串的第二个、第三个符号来确定要选择的目标。
文法的两个条件
为了在不采取超前扫描的前提下实现不带回溯的自顶向下分析，对文法需要满足两个条件：
- 文法是非左递归的；
- 对文法的任一非终结符，若其规则右部有多个选择时，各选择所推出的终结符号串的首符号集合要两两不相交。
4.2.4 递归子程序法（递归下降法）
对语法的每一个非终结符都编一个分析程序。当根据文法和当时的输入符号预测到要用某个非终结符去匹配输入串时，就调用该非终结符的分析程序。
具体操作鸽了，有时间补上~