编译原理 第四章 语法分析—自上而下分析
入分析工作栈中。若M[Xm，ai]=“Error”，则调用出错处理程序。
②若Xm?VT并且Xm=ai，则表明分析工作栈顶的符号与当前输入符号相匹配，将工作栈顶的符号Xm退出，输入符号指针向右移一位。
③若Xm=#，则表明输入符号串已完全匹配，分析成功结束分析工作。
3、分析程序的算法（P77）
例：对输入串 # i*i+i #的预测分析过程 P78
第四节 递归下降分析程序的构造
一、递归下降分析程序的构造方法
对文法的每个非终结符号，根据各侯选式的结构，编写一个对应的子程序，完成非终结符相应的语法成分的识别和分析任务。 二、递归下降分析程序的功能
对某个非终结符，用产生式规则的右部符号进行匹配。 三、递归下降分析程序的特点
1、程序结构清晰，易于手工操作。
2、对语义处理灵活。 四、递归下降分析法的必要条件
必须是不包含左递归和回溯的上下文无关文法。 五、递归下降分析程序的设计
P74
制作人：李明新 共28页第16页 13-3-24
编译原理 第四章 语法分析—自上而下分析
第五节 预测分析法的错误处理 一、出错情况
1、工作栈顶终结符与输入符号不匹配。
2、对应M[A，a]中为空(Error)。 二、出错处理
1、报告出错（出错位臵，出错性质）。 2、处理出错情况，使语法分析继续下去：
⑴若M[A，a]中为空(Error),跳过输入符号a，若该项为同步(synch)，则退出工作栈顶的非终结符A。
⑵工作栈顶的终结符无法与输入符号匹配，则弹出该符号。
第六节 学习与理解
一、填空题
⑴自上而下语法分析方法的基本思想是：从文法的开始符号出发。不断建立最左直接推导，试图构造一个推导序列，最终由它推导出与输入符号串相同的符号串。
⑵自上而下分析方法会遇到的主要问题有回溯和左递归。 ⑶在语法分析中，最常见的两种方法一定是自上而下分析法，另一种是自下而上分析法。 二、选择题
⑴编译过程中，语法分析器的任务是B，C，D。
A、分析单词是怎样构成的 B、分析单词串是如何构成语句的
制作人：李明新 共28页第17页 13-3-24
编译原理 第四章 语法分析—自上而下分析
C、分析语句是如何构成程序的 D、分析程序结构
⑵高级语言编译程序常用的语法分析方法中，递归下降分析法属于B分析方法。
A、自左至右 B、自上而下 C、自下而上 D、自右至左
三、解答题
⑴已知文法G： A?aAa??
①该文法是LL（1）文法吗？为什么？
②若采用LL（1）方法进行分析，如何得到该文法的LL（1）分析表。
③若输入串“aaaa”，请给出语法分析过程。 解：
①因为FOLLOW（A）＝FOLLOW（A）?FIRST（A）={a，#}，造成FOLLOW（A）?FIRST（A）={a，#}?{a，?}??，所以该文法不是LL（1）文法。
②若采用LL（1）方法进行语法分析，必须修改该文法。因该文法产生偶数（可以为0）个a，所以得到文法G`：A?aaA??。
此时 FOLLOW（A）={#}，因此
FOLLOW（A）?FIRST（A）={#}?{a，?}=?
所以文法G`是LL（1）文法。该文法的LL（1）分析表：
制作人：李明新 共28页第18页 13-3-24
编译原理 第四章 语法分析—自上而下分析
VT a # VN A A?aaA A?? ③对符号串“aaaa”的分析过程：
步骤 1 2 3 4 5 6 7 8 分析栈 输入串 产生式/动作 #A aaaa# A?aaA #Aaa aaaa# 匹配 #Aa aaa# 匹配 #A aa# A?aaA #Aaa aa# 匹配 #Aa a# 匹配 #A # A?? # # 接受 ⑵设文法G(A)：
A?aABc?aA B?Bb?d
①试给出文法G(A)等价的LL（1）文法G`(A)。
②构造G`(A)的LL（1）分析表，给出输入串aadc#的分析过程。
解答：
①由于该文法G(A) A?aABc?a 存在回溯 B?Bb?d 存在左递归
所以不是LL(1)文法。
②改写文法G(A)
制作人：李明新 共28页第19页 13-3-24
编译原理 第四章 语法分析—自上而下分析
A?aABc?a
提取最左公共因子使得：A?a（ABc??），定义A`?ABc?? 改写后的产生式：
A?aA` A`?ABc??
又因为：B?Bb?d存在左递归，消除左递归后的产生式：
B?dB` B`?bB`??
③构造文法每一个非终结符号FIRST和FOLLOW的集合。 a、构造文法每一个非终结符号FIRST的集合 FIRST（A）={a} FIRST（A`）={a，?} FIRST（B）={d} FIRST（B`）={b,?}
b、构造文法每一个非终结符号FOLLOW的集合 因为A?aA`和A`?ABc??，所以:
FOLLOW（A）={#}?FIRST（B）\\{?}={#,d}
因为A?aA`，所以FOLLOW（A`）= FOLLOW（A）={#,d} 因为A`?ABc，所以FOLLOW（B）={c}
因为B?dB`,所以FOLLOW（B`）=FOLLOW（B）， 最终结果:
FOLLOW（A）= FOLLOW（A`）={#，d}。
制作人：李明新 共28页第20页 13-3-24