《编译原理课程教案》第4章：LR分析方法.ppt

初态是活前缀 ε 的有效项目集 活前缀γ的有效项目集是从初态出发经过γ道路 所到达的那个状态所代表的项目集 分析过程中分析栈中的活前缀的有效项目集是 栈顶状态 Sm 所代表的那个集合，栈顶状态体 现了栈里一切有用的信息
32

2013-9-10
4.5
LR分析
例：文法G’ S’ E E T + E E T T int * T T int T (E)


例： 求 closure ( { E’ ·E } )
E’ E EE+T | T TT*F | F F ( E ) | id
2013-9-10
28
4.5

LR分析
goto 函数

goto ( I, X ) goto ( I, X ) = closure (A→αX·β)，其中 A→α·Xβ在 I 中

0
a
c
B
6 9
8
aAcBe b Ab d

分析句子的过程可以看作在上面这个 DFA 上运 行的过程
13
2013-9-10

例子：
步骤 1 0 栈 输入串 abbcde$ ACTION S2 GOTO
S
1 * 2
b
A c B
4 3
b e

0
a
6
5
d
2013-9-10
7
9
14
8

例子：
步骤 1 2 0 0a2 栈 输入串 abbcde$ bbcde$ ACTION S2 S4 GOTO
例子：
分析句子：abbcde
2013-9-10
6

2022/3/20
中南大学软件学院 陈志刚
6
第四章 语法分析-自上而下分析
4.2 自上而下分析面临的问题
➢ 顾名思义，自上而下就是从文法的开始符号出 发，向下推导，推出句子。 • 带回溯的分析方法 • 不带回溯的递归子程序（递归下降）分析方 法
➢ 自上而下分析的主旨： 对任意输入串，试图用一切可能的办法，从文 法开始符号（根结）出发，自上而下地为输入 串建立一棵语法树。或者说，为输入串寻找一 个最左推导。
设 ，有P→Pα|β，若α≠>ε，β不以P开头 （否则不可能消除左递归）。
则改写为：
可消除左递归。
2022/3/20
中南大学软件学院 陈志刚
12
第四章 语法分析-自上而下分析
一般地，若 αi≠ε，βj不以P开头， 则可改写为：
从而消除直接左递归。 ■ 例：S→Sabc|Sab|ab ■ 消除直接左递归得：
2022/3/20
中南大学软件学院 陈志刚
13
2、完全消除左递归 分析
第四章 语法分析-自上而下分析
虽不含直接左递归，但
所以含有左递归。
■ 如果文法G不含回路（ ），也不含ε产生式，
则下列算法可消除左递归（完全）
①把G的非终结符按任意顺序排列成P1,…,Pn
②for i:=1 to n do
begin for j:=1 to i-1 do
➢ 关键：对一个文法，当给你一串（终结）符号 时，怎样知道它是不是该文法的一个句子呢？ 这就要判断，看是否能从文法的开始符号出发 推导出这个字符串。或者，从概念上讲，就是 要建立一棵与输入串相匹配的语法分析树。
2022/3/20
中南大学软件学院 陈志刚

a
– aAb[3]
a,aA
– aAcd[4]
a,aA,aAc
– aAcBe[1]
a,aA,aAc,aAcB
ＬＲ分析程序
LR 文法 对于一个cfg 文法, 假如可以构造一张 LR 分析表, 使得它的每一个入口均是唯一的 〔Sj,rj,acc,空白〕，那么称该 cfg 是LR 文法．
ＬＲ分析
特征: – ．标准的 – ．符号栈中的符号是标准句型的前缀，
动作
移进 移进 归约(A→b) 移进 归约(A→Ab) 移进 移进 归约(B→d) 移进 归约 承受
对输入串abbcde#的移进-规约分析过程
符号串abbcde是否是G[S]的子
S aAcBe aAcde aAbcde abbcde
步骤 符号栈 输入符号串 动作
状态栈 ACTION GOTO
1〕 #
LR〔0〕LC〔Ab〕=ab
LR〔0〕LC〔AAb〕=aAb
LR〔0〕LC〔Bd〕=aAcd 的正规式
〔 =VnVt〕上
x
0 S①
2
a 3
b④
5
a
A 6
7
b
⑧
9
a
A
c
10
11
12
d⒀
a
A
c
14 15
16
17
B 18 e ⒆
DFA
a
A
b
x
2
3
6
S
b
1
4
c
B
e
5
7
9
d
8
构造LR〔0〕工程集标准族
活前缀与句柄的关系：
G[S]:
R
=>αβω

EE+T | T TT*F | F F (E) | id
并用SLR(1)方法分析id*id+id∈L(G[E]) ?
G的拓广文法G[E]：
(0) E E
(4) TF
(1) EE+T
(5) F (E)
(2) ET
(6) F id
(3) TT*F
I0:E.E E.E+T E.T T.T*F T.F F.(E) F.id
Q = G的LR(0)项目集规范族, q0 = closure( {S.S} )， F = 所有含归约项目的有效项目集组成的集合， = go(I,X) )。
若将所有状态均视为终态，则识别活前缀的自动 机DFA M= ( = VTVN,
Q = G的LR(0)项目集规范族, q0 = closure({S.S})， F = Q， = go (I,X) )。
I8: (I4,A) AcA.
I9: (I5,B) BcB.
I10: (I4,d) Ad.
I11: (I3,d) Bd.
识别文法 活前缀的DFA
c
a
S.S
start S.aA
S
S.bB
I0
b
c
Ac.A A.cA A.d
I4 c
Sa.A A.cA A.d
I2
Sb.B B.cB B.d
J ={A X . | A . X I }
称函数go(I, X)为转移函数。
项目A X . 称为项目A . X后继。
二、识别句柄和活前缀的自动机
若文法G = ( VT, VN, S, P)，则识别G的句柄的自动 机为DFA M = ( = VTVN，
B 是产生式，则项目 B . 对活前缀 = 1 也是 有效的。