第5章 自顶向下语法分析方法

26
4. 计算SELECT集
27
28
5.3 非LL(1)文法到LL(1)文法的等价变换
在确定的自顶向下分析中,要求对给定语言的文法必须 是LL(1)文法,然而不一定每个语言都有LL(1)文法。 如何对一个语言的非LL(1)文法变换为等价的LL(1)形式? 由LL(1)文法的定义知道,当文法中含有直接或间接左递归, 或含有左公共因子时,这样的文法肯定不是LL(1)文法。 因此，首先设法消除文法中的左递归与提取左公共因子 对文法进行等价变换。在某些情况下,使其变换为LL(1)文法。
语法分析就是识别由词法分析给出的单词符号序列是 否是给定文法的正确句子(程序). 语法分析常用的方法:
自顶向下分析
自底向上分析 自底向上分析分为: 算符优先分析 LR分析
2
第五章 自顶向下语法分析
自顶向下分析（面向目标的分析方法） 从文法的开始符号出发企图推导出与输入的单词串完全相 匹配的句子. 自顶向下分析方法分为: 确定的分析方法－对文法有一定的限制。 不确定的分析方法－回溯的分析方法，一种穷举的试 探方法。
18
例题分析： 求文法中符号与符号串的FIRST集。
G[S]: S->AB | bC A->b |ε B->aD |ε C->AD | b
D->aS | c
FIRST(S)=FIRST(A)∪FIRST(B)∪{ε} ∪{b}={b,a, ε} FIRST(A)={b} ∪{ε}={b, ε} FIRST(B)={ε} ∪{a}={a, ε} FIRST(C)={FIRST(A)- {ε}}∪FIRST(D) ∪FIRST(b)={b,a, c} FIRST(D)={a} ∪{c}={a, c}

第5章 自顶向下语法分析方法
语法分析的主要工作： 是识别由词法分析给出的单词序列是否是给定的
正确句子（程序）。
பைடு நூலகம்语法分析常用的方法： 自顶向下的语法分析和自底向上的语法分析两大
类。
自顶向下分析思想
自顶向下的方法： 从文法的开始符号（设为〈程序〉）开始进行分析，
逐步推导的往下构造语法树，使其树叶正好构造出所给 定的源程序串(输入串)。
例5.1若有文法G[S]：
S → pA S → qB
A → cAd A→a
若有输入串w = pccadd.
考察自顶向下的推导过程。
解：推导过程为：
S pA pcAd pccAdd pccadd 其相应的语法树见右图：
S pA
cAd c Ad
a
这个文法的特点：
[1]每个产生式的右部都由终结符号开始。 [2]如果两个产生有相同的左部，那么它们的右部由不同的终 结符开始。
FOLLOW(A)的元素。
因此当文法中含有形如： A→α和 A→β的产生式时，其中 A∈VN ,α,β∈V*,当α和β不同时推导出空串时，设α * ε，β\ * ε， 则当FIRST(α) ∩(FIRST(β)∪FOLLOW(A))=φ时，对于非终结符 A的替代仍可唯一地确定候选。
定义5.3：
定义选择符集合SELECT如下： 对于给出上下文无关文法的产生式
自顶向下方法的关键： 是在推导过程中确定的选择候选式的问题。
自顶向下的主要思想： 从开始符出发导出句型并一个符号一个符号地与
给定输入串 (终结符串)进行匹配。如果全部匹配成功， 则表示开始符号可推导出给定的终结符串。因此判定 给定终结符号串是正确句子。
自顶向下的缺点:

P→1P | 2P |… | mP |
（2）消除间接左递归
对于间接左递归的消除需先将间接左递归变为直接左 递归，然后再按a)消除直接左递归。
例：文法G为例： (1) A→aB (2) A→Bb (3) B→Ac (4) B→d 用产生式(1)、(2)的右部 代替产生式(3)中的非终 结符A得到左部为B的产 生式为： (1) B→aBc (2) BG的产生式为： (1) S→aSb (2) S→aS (3) S→ε 请提取文法中的左公因子
对产生式(1)、(2)提取左公因子后得： S→ aS(b|ε) S→ε 进一步变换为文法G′： S→aSA A→b A→ε S→ε
例2：若文法G的产生式为： (1) A→ad (2) A→Bc (3) B→aA (4) B→bB 请提取文法中的隐式左公因子。 对文法G2分别用(3)、(4)的右 部替换(2)中的B，可得： 提取产生式(1)、(2)的左 (1) A→ad 公共因子得： (2) A→aAc A→a(d|Ac) (3) A→bBc A→bBc (4) B→aA B→aA (5) B→bB B→bB
由上面所举例子可以说明以下问题：
① 不一定每个文法的左公共因子都能在有限的步骤内 替换成无左公共因子的文法，上面文法G4就是如此。 ② 一个文法提取了左公共因子后，只解决了相同左部 产生式右部的FIRST集不相交问题，当改写后的文法 不含空产生式，且无左递归时，则改写后的文法是 LL(1)文法，否则还需用LL(1)文法的判别方式进行判 断才能确定是否为LL(1)文法。
例:文法G(E):
E→TE E→+TE | T→FT T→*FT | F→(E) | i
每个非终结符有对应的子程序的定义， 首先在分析过程中，当需要从某个非终 结符出发进行展开(推导)时，就调用这 个非终结符对应的子程序。

《编译原理》课后习题答案第5章《编译原理》课后习题答案第5章.pdf《编译原理》课后习题答案第5章.pdf第5章自顶向下语法分析方法第1题对文法G[S] S→a|∧|(T) T→T,S|S(1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。

(2) 对文法G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。

(3) 经改写后的文法是否是LL(1)的?给出它的预测分析表。

(4) 给出输入串(a,a)#的分析过程，并说明该串是否为G的句子。

答案：(1) 对(a,(a,a)的最左推导为：S(T) (T,S) (S,S) (a,S) (a,(T)) (a,(T,S)) (a,(S,S)) (a,(a,S)) (a,(a,a))对(((a,a),∧,(a)),a) 的最左推导为：S(T) (T,S) (S,S) ((T),S) ((T,S),S) ((T,S,S),S) ((S,S,S),S) (((T),S,S),S) (((T,S),S,S),S) (((S,S),S,S),S) (((a,S),S,S),S) (((a,a),S,S),S) (((a,a),∧,S),S) (((a,a),∧,(T)),S)(((a,a),∧,(S)),S)《编译原理》课后习题答案第5章.pdf《编译原理》课后习题答案第5章.pdf(((a,a),∧,(a)),S) (((a,a),∧,(a)),a)(2) 改写文法为：0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε非终结符FIRST集FOLLOW集S {a,∧,(} {#,,,)} T {a,∧,(} {)} N {,,ε} {)}对左部为N的产生式可知：FIRST （→, S N）={，} FIRST （→ε）={ε} FOLLOW （N）={)}由于SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是LL(1)的。