安徽工程大学课程设计(论文)
4.2详细设计
自顶向下语法分析方法
语法分析方法是编译程序的核心部分。语法分析的作用是识别由词法分析给出的单词符号序列是否是给定文法的正确句子（程序），目前语法分析方法有自顶向下分析和自底向上分析两大类。自顶向下分析包括确定分析和不确定分析，自底向上分析又包括算符优先分析和LR分析这些分析方法各有优缺点。然而除了自顶向下的不确定分析方法外，都是当今编译程序构造的使用方法。 自顶向下的分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推到出一输入的单词串完全像匹配的句子，若输入串是给定文法的句子，则必能退出，反之必然出错。自顶向下的确定分析方法需对文法有一定的限制，但由于实现方法简单、直观，便于手工构造或自动生成语法分析器，因而仍是目前常用的方法之一。
确定的自顶向下分析方法，是从文法的开始符号出发，考虑如何根据当前的输入符号（单词符号）唯一地确定选用哪个产生式替换相应非终结符一往下推导，或如何够着一颗相应的语法树。
当我们需选用自顶向下分析技术时，首先必须判别所给文法是否是LL（1）文法。因而对任给文法需计算FIRST、FOLLOW、SELECT集合，进而判别文法是否是ＬＬ（１）文法。
有关ＦＩＲＳＴ已有其他同学详细叙述，在这里就不在赘述。在此详细叙述关于ＦＯＬＬＯＷ集的定义及有关算法。
预测分析方法是自顶向下分析的另一种方法，一个预测分析器是由三个部分组成。
１预测分析程序 ２先进后出栈 ３预测分析表
其中只有预测分析表与文法有关，而分析表有可用一个矩阵Ｍ（或二维数组）表示。矩阵的元素Ｍ［Ａ，ａ］中的下表Ａ表示非终结符，ａ为终结符或句子括号“＃”，矩阵元素Ｍ［Ａ，ａ］中的内容是一条关于Ａ的产生式，表明当用非终结符Ａ向下推导时，面临输入符ａ时，所应采取的候选产生式，当元素内容物产生式时，则表明用Ａ为左部向下推导遇到了不该出现的符号，因此元素内容为转向出错处理的信息。
预测分析程序的工作过程用下图表示。 图中符号说明如下：
“＃”句子括号集输入串的括号 “Ｓ”文法的开始符号
“Ｘ”存放当前栈顶符号的工作单元 “ａ”存放当前输入符号ａ的工作单元
第 21 页
安徽工程大学课程设计(论文)
若产生式为 X→x1x2? xn按逆序即 xn?x2x1入 栈 是 M[X,a]是产生式 吗？ 否 出错
开始 '#' 'S' 进栈，当前终结符送a 上托栈顶符号放入X 是 是X=a X?VT? X=a ? 读入下一符号 否 否 X='#' ? 是 否 X=a ? 出错 否 是 结束 预测分析程序的框图
1.FOLLOW集的定义
设G=（VT，Vn，S，P)是上下文无关文法，A∈VN，S是开始符号 FOLLOW(A)={a|S?* μAβ且a∈FIRST（β），μ∈V*T，β∈V+}
若有S?* μAβ，且β?*ε，则#∈FOLLOW(A)。其中‘#’作为输入串的结束符，或称输入串括号。 2.计算FOLLOW集
第 22 页
安徽工程大学课程设计(论文)
(1)根据定义计算
对文法中每一A∈VT计算FOLLLOW（A） ①设S为文法的开始符号，把{#}加入FOLLOW（S)中（这里“#”为句子括号）。 ②若A→αBβ是一个产生式，则把FIRST（β）的非空元素加入FOLLOW（B）中。
如果β?*ε则把FOLLOW（A)也加入FOLLOW（B）中。 ③反复使用②直到每个非终结符的FOLLOW集不再增大为止。 （2）用关系图法球非终结符的FOLLOW集 ①文法G中的每一个符号和“#”对应图中的一个结点，对应终结符和“#”的结点用符号本身标记。对应终结符的结点（如ACVT）则用FOLLOW（A)标记。 ②从开始符号S的FOLLOW（S)结点到“#”号的结点连一条箭弧。
*
③如果文法中有产生式A→αBβX，且β?ε，则从FOLLOW（B)结点到FIRST（X)结点连一条弧，当X∈VT时，则与X相连。 ④如果文法中有产生式A→αBβ且β?*ε则从FOLLOW（Ｂ）结点到FOLLOW（A)结点连一条弧。
*
⑤对每一FIRST（Ａ）结点如果有产生式 A→αXβ，且α?ε，则从FIRST（Ａ）到FOLLOW（Ｘ）连一条箭弧。 ⑥凡是从FOLLOW（A)结点有路径可以到达的终结符或“#”号的结点，其所标记的终结符或“#”号即为FOLLOW（A)的成员。
如文法Ｇ［Ｓ］为 Ｓ→ＡＢ Ｓ→ｂｃ Ａ→ε Ａ→ｂ Ｂ→ε Ｂ→ａＤ Ｃ→ＡＤ Ｃ→ｂ Ｄ→ａＳ Ｄ→ｃ 得
ＦＯＬＬＯＷ（Ｓ）＝｛＃｝
ＦＯＬＬＯＷ（Ａ）＝｛ａ，ｃ，＃｝ ＦＯＬＬＯＷ（Ｂ）＝｛＃｝ ＦＯＬＬＯＷ（Ｃ）＝｛＃｝ ＦＯＬＬＯＷ（Ｄ）＝｛＃｝
第 23 页
安徽工程大学课程设计(论文)
# FOLLOW(B) FOLLOW(S) FOLLOW(D) FOLLOW(A) FIRST(B) FOLLOW(C) FIRST(D) c a
计算ＦＯＬＬＯＷ集的关系图
3.求解FOLLOW集合的算法
⑴ 逐一扫描代码中的产生式, 将产生式右部赋给γ 串,γ[j]表示γ 串中的第j 个字符。
⑵ 逐一扫描产生式的右部, 若γ[j]为非终结符X, 找出γ[j]后继的第一个字符γ[k]。
①若γ[k]为终结符, 则将该终结符加入到FOLLOW 集合, 结束, 跳出⑵; ②若γ[k]为非终结符, 则FIRST 集合‘- ε’, 执行⑶。 ⑶ 逐一扫描X 后的字符串,分为下面两种情况:
a.若非终结符γ[k]能推出空字符串, 则k++, 继续执行①、②两步;
b.若非终结符γ[k]为产生式最后一个字符, 则将该产生式的左部非终结符的FOLLOW 集合加入该非终结符的FOLLOW集合。
⑷ 若扫描完全部的产生式, 则求得所有非终结符的FOLLOW 集合。
在计算FOLLOW 集中也存在“ 环”和重复的终结符的问题, 解决的办法与FIRST 集的相同。
第 24 页
安徽工程大学课程设计(论文)
计算FOLLOW集的流程图
产生式为：X→x1x2?xn X=S? N Y {#}∈FOLLOW(X) 0