byyl-ch5.自底向上优先分析

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}

构造LRSM的思想： 如果在状态项目集ISi 中有项目A→B， 且B→是B的产生式，则在ISi 中增加项目 B→；对于ISi 这个过程继续到不可再扩 充为止。
构造LR(0)活前缀状态机LRSM的算法要点
构造初始状态 IS0：IS0=CLOSURE({Z→S})，并给 IS0标
Stack
LR分析模型
LR分析表
Action矩阵：行代表状态，列代表输入 符，而矩阵元素则表示相应的分析动作： Shift / Reduce / Accept / Error 。 GoTo矩阵：行代表状态，而列则代表语 法符号（非终极符，终极符），而矩阵 元素则表示移入或归约后的转向状态。 定义 若IS是一个LR(0)项目集，X是一个 文法符号，函数GO（IS, X）定义为 GO（IS, X）=CLOSURE（IS(X)），其中 IS(X)为LR(0)项目集IS的投影。
id
E→E+ T T→ id T→ (E)
E
7
S→E $ E→E +T
+
T→(E ) E→E +T
$
2 4
T
8
)
T→(E)
S→E $
E→E+T
GE的LRSM
LRSM给出了所有的可归活前缀
LRSM中的每个状态将对应一个饱和项目集： （1）其中一部分是由先驱状态分出来 (称为基本项目)； （2）一部分则是由基本项目扩展出来的 (称为扩展项目或派生项目)。派生部 分项目的特点是其中的“”出现在 产 生式右部的最左侧。

识别规约活前缀的LRSM的构造
派生定理


开始符产生式的右部是归约活前缀。 如果A是归约活前缀，且A→是产生式， 则也是归约活前缀。 任何归约活前缀，都可按上述方式被派生。 设文法开始符的产生式是： S →1|2|…|n RPSG={1,…,n}{|ARPSG,A→P}

算符优先关系表
+ + * / ^ ( ) i # > > > > < > > > > < > > > > < > > > > < < > > > < < < < > =. > > < > > > > > >. >. * / ^ ( ) >. i < < < < < < >. >. =. # >. >. >. >. >.
6.3 算符优先分析法
算符优先分析法只考虑算符（广义为终 结符）之间的优先关系，例如： （1）E → E+E (2) E → E-E (3) E → I 对输入串i1+i2*i3的归约过程可表示如下：
表6.3 对输入串i1+i2*i3的归约过程
步骤 1 2 3 4 5 6 7 8 9 10 11 # #i1 #E #E+ #E+i2 #E+E #E+E* #E+E*i3 #E+E*E #E+E #E 栈S
算符优先文法的定义
定义3: 设G是一个不含ε产生式的算符文法，如 果对任意两个终结符对a，b之间，至多 只有=.、<.、.>三种关系的一种成立， 则称G是一个算符优先文法。（Operator
Precedence Grammar)即OPG文法。
6.3.3 算符优先关系表的构造
（1）由定义直接构造（通过算法实现） （2）由关系图法构造（手工构造）

X >Y X…A Y …
当且仅当存在一个产生式A→…XB…
XB
并有B+Y…
…… BC …
X ⊲Y ：
…
当且仅当存在一个产生式A→…BC… .
并有B+…X，C*Y…
.
. ..… Y.
X
Y
文法G为简单优先文法如果满足： • 对于任意两个语法符号X和Y，至多成立一种 优先关系； • 任意两个产生式都具有不同的右部.
EE1 E1E1+ T1 | T1 T1T TT * F | F F(E) | i
)
i 实例
#
E FIRST E1 ,T1
E1 E1,T1
T1 T ,F ,( ,i
T T ,F ,( ,i
ห้องสมุดไป่ตู้F ( ,i
LAST E1 ,T1 ,T ,F ,),i T1 ,T ,F ,),i T ,F ,),i F ,),i
7
文法优先关系的确定
FIRST(W) ={S | W + S…，S(VNVT)} LAST(W) ={S | W + …S，S(VN VT)}
若有U…SiSj…: 则有Si Sj ; 若Sj有U…SiW…:任SjFIRST(W),有Si ⊲ Sj 若有U…VW…:任SiLAST(V), Sj(FIRST(W) {W})
Shift 3. M (L
Shift Shift
4. L Ma) 分析字符串：b(aa)b
Reduce[2]
Shift
#b(Ma
#b(Ma) ⊳
#b(L
⊳
#bM
#bMb
⊳
#Z
) b # Shift b # Reduce[4]