程序设计语言 编译原理(第三版)第4章.ppt

第四章语法分析—自上而下分析§4.1语法分析器的功能§4.1语法分析器的功能§4.2自上而下面临的问题§4.2自上而下面临的问题§4.2自上而下面临的问题§4.2自上而下面临的问题§4.2自上而下面临的问题§4.3LL(1)分析法§4.3LL(1)分析法§4.3LL(1)分析法§4.3LL(1)分析法解答:令非终结符排序为R、Q、S
i=1， 无法执行for
i=2，j=1 QRb|b
RSa|a QSab|ab|b返回二、消除回溯,提取公共左因子例：Ａα１｜α２｜…｜αｎ
设Ａ所面临的第一个输入符号为ａ，若Ａ能根据不同的输入符号指派相应的候选αｉ作为全权代表去执行任务，那就肯定无需回溯。在这里Ａ已不再是让某个候选去试探性地执行任务，而是根据所面临的输入符号ａ准确地指派唯一的一个候选。２.当不得回溯时，对文法有什么要求？
∀非终结符Ａ的各个候选的首符集的交集均为空。3.提取公共左因子
A.事实上，许多文法均存在这样的非终结符，
其所有候选的终结首符集并非两两不相交。
例如：语句if条件then语句else语句
if条件then语句
代价:大量引进新的非终结符和ℇ_产生式.三、分析条件例：文法
EE+T|T
TT*F|F
F（E）|i２.由上分析是不是就意味着：当非终结符Ａ面临输入符号ａ，且ａ不属于Ａ的任意候选首符集，但Ａ的某个候选首符集包含ℇ时，就一定可以使Ａ自动匹配？Follow(A)={a|A⇒…Aa…,a∈VT}
若S⇒…A,则规定#∈follow(A)3.LL(1)文法4.LL(1)文法的自上而下分析(有效的无回溯的)一.实现思想
对应文法中每个非终结符编写一个递归过程,每个过程
的功能是识别由该非终结符推出的串,当某非终结符的产生
式有多个侯选时能够按LL(1)形式可唯一地确定选择某个侯
选进行推导.2.子程序的功能
对某个非终结符,用规则的右部符号串去匹配输入串.分析
过程是按文法规则自上而下一级一级地调用有关子程序来完成.§4.4递归下降分析程序构造预测分析器模型§4.5预测分析程序§4.5预测分析程序一、预测分析程序工作过程(1)初始化:依次把’#’和文法开始符号压入分析栈,
将输入串第一个符号读入a;
下面用预测分析方法对输入串i+i*i#进行分析，给出栈的变化过程如下：3步骤预测分析器模型§4.5预测分析程序§4.5预测分析程序1.A→a......例：求下题的FIRST集
E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i2.Follow(A)集合构造，A∈VN(2)B→αAβ
E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i练习：求下题的FIRST和FOLLOW集合。
S→a|(T)
T→ST’
T’→,ST’|ε
3.LL(1)分析表的构造例：
E→TE'E'→+TE'|εT→FT'T'→*FT'|εF→(E)|i4.6LL（1）中的错误处理第4章总结将‘#’和文法开始符号依次进栈STACK；
§4.5预测分析程序§4.5预测分析程序2.Follow(A)集合构造，A∈VN