资源描述：
《15西安电子科技大学《编译原理》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、《编译原理》西安电子科技大学软件工程研究所刘坚3.4自上而下语法分析对任何一个输入序列ω，从S开始进行最左推导，直到得到一个合法的句子或发现一个非法结构。在推导的过程中试图用一切可能的方法，自上而下、从左到右为输入序列建立分析树。分析是一种试探的过程，是反复使用不同产生式谋求与输入序列匹配的过程。主要内容：自上而下分析对文法的限制预测分析方法递归下降子程序方法（结合上机作业）LL(1)：文法、语言、分析器自上而下分析对文法的限制有哪些限制如何将一个不满足限制的文法改造为满足限制的文法文法G产生句子的基本方法－推导：从S开始反复用产生式的右部替换其左部（父亲长出儿子）分析树从左
2、到右的叶子序列－句型用推导的方法分析输入序列（记号流）：3.4.1自上而下分析对文法的限制例3.20用下述文法分析输入序列ω=cad：(G)：S→cAdA→ab
3、a问题：若有A→αβ1
4、αβ2(公共左因子)，则会虚假匹配(回溯)；从而造成分析效率低、语义动作难以恢复、以及出错位置的报告不确切等。若有A→Aα(左递归)，则死循环使分析无法进行下去。重写文法：①消除左递归，以避免陷入死循环；②提取左因子，以避免回溯。33.4.2消除左递归<1>消除文法的直接左递归考虑：A→Aα
5、β产生的语言：βα*替换为：A→βA'A'→αA'
6、ε消除一个直接左递归（等价）方法首先整理A产生式为
7、如下形式：A→Aα1
8、Aα2
9、...
10、Aαm
11、β1
12、β2
13、...
14、βn其中αi非空，βj均不以A开始。若αi为空，则形成一个有环的A产生式定义3.9若G对A和某个文法符号序列α存在推导AAα，则称G是左递归的。若G中有形如A→Aα的产生式，则称该产生式对A直接左递归。■+=>算法3.1消除直接左递归输入G中所有的A产生式(含直接左递归)输出等价的不含直接左递归的G'然后用下述产生式代替A产生式：A→β1A'
15、β2A'
16、...
17、βnA'A'→α1A'
18、α2A'
19、...
20、αmA'
21、ε■4<1>消除文法的直接左递归(续1)例3.17用算法3.1消除算术表达式文法的直接左递归：E→T
22、E'(1)E'→+TE'
23、ε(2)(G3.4')T→FT'(3)T'→*FT'
24、ε(4)F→(E)
25、-F
26、id(5)..(7)E→E+T
27、TT→T*F
28、F(G3.4)F→(E)
29、-F
30、id替换：A→Aα
31、β为：A→βA'A'→αA'
32、ε关键：将实际文法符号对应到A、α和β具体到E产生式：E+T
33、TAαβ5<1>消除文法的直接左递归(续2)输入序列：id+id*id改写的代价E→E+T
34、TT→T*F
35、FF→(E)
36、-F
37、id(G3.4)E→TE'(1)E'→+TE'
38、ε(2)T→FT'(3)T'→*FT'
39、ε(4)F→(E)
40、-F
41、id(5)..(7)(G3.4')结束E→E+
42、E
43、E*E
44、(E)
45、-E
46、id(G3.2)6<2>消除文法的左递归文法：S→Aa
47、bA→Ac
48、Sd
49、εS是左递归的(但不是直接左递归)因为：S=>Aa=>Sda注意：若G产生句子的过程中出现AA的推导，则无法消除左递归。+=>核心思想：将不是直接左递归的非终结符右部展开到其他产生式中。算法3.2消除左递归输入无回路文法G输出无左递归的等价文法G'方法将非终结符合理排序：A1，A2，...，An;foriin2..nloopforjin1..i-1loopendloop;endloop;■用Aj→δ1
50、δ2
51、...
52、δk的右部替换每个形如Ai→Ajγ产生式中的Aj,得到新产生式
53、：Ai→δ1γ
54、δ2γ
55、...
56、δkγ;消除Ai产生式中的直接左递归;7<2>消除文法的左递归（续1）例3.18用算法3.2消除文法(S→Aa
57、bA→Ac
58、Sd
59、ε)中的左递归。核心思想：将不是直接左递归的非终结符右部展开到其他产生式①将S的右部展开在A中，得到：A→Ac
60、Aad
61、bd
62、ε②消除新产生式中的直接左递归，得到：S→Aa
63、bA→bdA'
64、A'(G3.8')A'→cA'
65、adA'
66、ε83.4.3提取左因子当不确定用A产生式的哪个候选项替换A时，可以重写A产生式来推迟这种决定，直到看见足够的输入，能正确决定所需选择为止。这一过程被称为提取左因子，它类似于有限自动机的确
67、定化。公共前缀：A→αβ1
68、αβ2将：A→αβ1
69、αβ2替换为：A→αA'A'→β1
70、β2它等价于：A→α(β1
71、β2)S→cAdA→ab
72、a93.4.3提取左因子（续1）算法3.3提取文法的左因子输入文法G输出等价的无左因子文法G'方法重复下述过程，直到所有A产生式候选项中不再有公共前缀重排A产生式：A→αβ1
73、αβ2
74、...
75、αβn
76、γ；并用A→αA'
77、γ和A'→β1
78、β2
79、...
80、βn取代原A产生式。■例3.20考察悬空else文法：S→iCtS
81、iCtSeS
82、aC→b用算法3.3提取左因子，得到
