05 第五章 语法分析-自下而上分析.pptx

第1页：第五章语法分析——自下而上分析

第五章语法分析——自下而上分析

• 编译原理

第2页：第五章语法分析——自下而上分析（续）

第五章语法分析——自下而上分析（续）

• 自上而下分析法(Top-down)
• 自下而上分析法(Bottom-up)

第3页：基本思想

基本思想

递归下降分析法

对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。

优点

直观、简单和宜于手工实现。

• 它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。
• 自下而上分析法(Bottom-up)
• 自上而下分析法(Top-down)
• 预测分析程序

第4页：基本思想（续）

基本思想（续）

算符优先分析法

按照算符的优先关系和结合性质进行语法分析。适合分析表达式。

LR分析法

规范归约

• 从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。
• 自下而上分析法(Bottom-up)

第5页：基本思想

基本思想

• E
• i| E+E | E-E | E*E | E/E | (E)i*i+iE*i+iE*E+iE+iE+EEi+*EiiEEEE

第6页：5.1.1归约

5.1.1归约

基本思想

用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

第7页：5.1.1归约（续）

5.1.1归约（续）

• aAcBe(2) A
• b(3) A
• Ab(4) B
• d试对abbcde进行“移进－归约”分析。abbcdebabcdeAabcdebAacdeAacdecAadedcAaeabbcdeeBcAaSBcAae

第8页：

第9页：bdbaceSABA分析树

bdbaceSABA分析树

自下而上分析过程

边输入单词符号，边归约。核心问题：识别可归约串

第10页：5.1.2规范归约

5.1.2规范归约

定义

令G是一个文法，S是文法的开始符号，假定

• 是文法G的一个句型，如果有且则
• 称是句型
• 相对于非终结符A的短语。特别是，如果有A
• ,则称
• 是句型
• 相对于规则A
• 的直接短语。一个句型的最左直接短语称为该句型的句柄。

第11页：5.1.2规范归约（续）

5.1.2规范归约（续）

短语

i1，i2，i3，i1*i2，i1*i2+i3

直接短语

i1，i2，i3

• E
• T | E+TT
• F | T*FF
• (E) | i和句型i1*i2+i3：E
• E+T
• E+F
• E+i3
• T+i3
• T*F+i3
• T*i2+i3
• F*i2+i3
• i1*i2+i3
• 句柄：i1

第12页：5.1.2规范归约

5.1.2规范归约

在一个句型对应的语法树中，以某非终结符为根的两代以上的子树的所有末端结点从左到右排列就是相对于该非终结符的一个短语，如果子树只有两代，则该短语就是直接短语。EFFTTTi1+*EFi3i2

第13页：5.1.2规范归约（续）

5.1.2规范归约（续）

• baAbcde(3) A
• AbaAcde(4) B
• daAcBe(1) S
• aAcBeS

第14页：5.1.2规范归约

5.1.2规范归约

• 是文法G的一个句子，我们称序列
• n，
• n-1，
• ，
• 0是的一个规范归约，如果此序列满足：1
• n=
• 2
• 0为文法的开始符号，即
• 0=S3对任何i，0
• i
• n，
• i-1是从
• i经把句柄替换成为相应产生式左部符号而得到的。

第15页：5.1.2规范归约（续）

5.1.2规范归约（续）

• 则得到：S
• aAcBe
• aAcde
• aAbcde
• abbcde显然这是一个最右推导。规范归约是关于是一个最右推导的逆过程最左归约规范推导由规范推导推出的句型称为规范句型。

第16页：5.1.2规范归约

5.1.2规范归约

• aceSABS

第17页：5.1.3符号栈的使用和分析树的表示

5.1.3符号栈的使用和分析树的表示

• 使用和分析树的表示
• 栈是语法分析的一种基本数据结构。’#’作为栈底符号
• 考虑文法G(E)：E
• T | E+TT
• F | T*FF
• (E) | i输入串为i1*i2+i3，分析步骤为：

第18页：5.1.3符号栈的使用和分析树的表（续）

5.1.3符号栈的使用和分析树的表（续）

• 1*i2+i3#进2#F*i2+i3#归用F→i3 #T*i2+i3#归，用T→F4#T*i2+i3#进
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第19页：5.1.3符号栈的使用和分析树的表示

5.1.3符号栈的使用和分析树的表示

• 2+i3#进6#T*F+i3#归用F→i7#T+i3#归，用T→T*F8#E+i3#归，用E→T9#E+i3#进
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第20页：5.1.3符号栈的使用和分析树的表（续）

5.1.3符号栈的使用和分析树的表（续）

• 进11#E+F#归用F→i12#E+T#归，用T→F13#E#归，用E→E+T14#E#接受
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第21页：5.1.3符号栈的使用和分析树的表示

5.1.3符号栈的使用和分析树的表示

• 自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。回顾

第22页：5.1.3符号栈的使用和分析树的表（续）

5.1.3符号栈的使用和分析树的表（续）

基本思想

用一个寄存符号的先进后出栈，把输入符号一个一个地移进到栈里，当栈顶形成某个产生式的候选式时，即把栈顶的这一部分替换成(归约为)该产生式的左部符号。

第23页：规范归约

规范归约

定义

令G是一个文法，S是文法的开始符号，假定

• 是文法G的一个句型，如果有且则
• 称是句型
• 相对于非终结符A的短语。特别是，如果有A
• ,则称
• 是句型
• 相对于规则A
• 的直接短语。一个句型的最左直接短语称为该句型的句柄。

第24页：规范归约（续）

规范归约（续）

• 是文法G的一个句子，我们称序列
• n，
• n-1，
• ，
• 0是的一个规范归约，如果此序列满足：1
• n=
• 2
• 0为文法的开始符号，即
• 0=S3对任何i，0
• i
• n，
• i-1是从
• i经把句柄替换成为相应产生式左部符号而得到的。

第25页：规范归约

规范归约

• 1*i2+i3#进2#F*i2+i3#归用F→i3 #T*i2+i3#归，用T→F4#T*i2+i3#进
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第26页：规范归约（续）

规范归约（续）

• 2+i3#进6#T*F+i3#归用F→i7#T+i3#归，用T→T*F8#E+i3#归，用E→T9#E+i3#进
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第27页：规范归约

规范归约

• 进11#E+F#归用F→i12#E+T#归，用T→F13#E#归，用E→E+T14#E#接受
• G(E)：E
• T | E+TT
• F | T*FF
• (E) | i

第28页：5.2算符优先分析

5.2算符优先分析

四则运算的优先规则

先乘除后加减，同级从左到右

考虑二义文法文法G(E)

G(E)：E

• i| E+E|E-E|E*E|E/E|(E)
• 它的句子有几种不同的规范规约。
• 归约即计算表达式的值。归约顺序不同，则计算的顺序也不同，结果也不一样。
• 如果规定算符的优先次序，并按这种规定进行归约，则归约过程是唯一的。

第29页：5.2算符优先分析（续）

5.2算符优先分析（续）

• 句子i+i-i*(i+i)Ei()i*EiEE+EEE-ii+EEE

第30页：5.2算符优先分析

5.2算符优先分析

Ei()i*EiEE+EEE-ii+EEE返回

第31页：5.2算符优先分析（续）

5.2算符优先分析（续）

• (1) i+i-i*(i+i)(2) E+i-i*(i+i)(3) E+E-i*(i+i)(4) E-i*(i+i)(5) E-E*(i+i)(6) E-E*(E+i)(7) E-E*(E+E)(8) E-E*(E)(9) E-E*E(10) E-E(11) E

第32页：5.2算符优先分析

5.2算符优先分析

• 借助于这种关系寻找“可归约串”和进行归约。

第33页：5.2算符优先分析（续）

5.2算符优先分析（续）

• 与数学上的<>=不同
• b a的优先级低于ba
• b a的优先级等于ba
• b a的优先级高于b
• +
• +
• a
• b并不意味着b
• a，如(
• +和+
• (

第34页：5.2.1算符优先文法及优先表构造

5.2.1算符优先文法及优先表构造

• 一个文法，如果它的任一产生式的右部都不含两个相继(并列)的非终结符，即不含如下形式的产生式右部：…QR…则我们称该文法为算符文法。
• 约定：
• a、b代表任意终结符；
• P、Q、R代表任意非终结符；
• ‘…’代表由终结符和非终结符组成的任意序列，包括空字。

第35页：5.2.1算符优先文法及优先表构造（续）

5.2.1算符优先文法及优先表构造（续）

• b)至多只满足下述三关系之一：a
• -产生式的算符文法。对于任何一对终结符a、b，我们说：1. a
• b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
• b，a
• b，a
• b则称G是一个算符优先文法。2. a
• b当且仅当G中含有形如P→…aR…的产生式，而R b…或R Qb…；3. a
• b当且仅当G中含有形如P→…Rb…的产生式，而R …a或R …aQ。

第36页：5.2.1算符优先文法及优先表构造

5.2.1算符优先文法及优先表构造

• 有‘(’
• F | P(4) P→(E) | i
• ‘)’；
• 由规则E→E＋T和T
• T*F，有＋
• *；
• 由(2)T→T*F和(3)F→P
• F，可得*
• ↑；
• 由(1)E→E＋T和E
• E+T，可得+
• +；
• 由(3)F→P
• F和F
• P
• F，可得↑
• ↑。
• 由(4)P→(E)和E
• E+T
• T+T
• T*F+T
• F*F+T
• P↑F*F+T
• i↑F*F+T有(
• +、(
• *、(
• ↑和(
• i。

第37页：优先关系表

优先关系表

优先关系表

第38页：优先关系表（续）

优先关系表（续）

的所有终结符对

1. a

• 可找出所有满足a
• b的终结符对。2. a
• b当且仅当G中含有形如P→…aR…的产生式，而R b…或R Qb…；3. a
• b当且仅当G中含有形如P→…Rb…的产生式，而R …a或R …aQ。
• 确定满足关系
• 和
• b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；

第39页：优先关系表

优先关系表

• 可找出所有满足a
• b的终结符对。
• 确定满足关系
• 和
• 的所有终结符对：
• 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：a
• b当且仅当G中含有形如P→…aR…的产生式，而Rb…或RQb…；

第40页：优先关系表（续）

优先关系表（续）

• 可找出所有满足a
• b的终结符对。
• 确定满足关系
• 和
• 的所有终结符对：
• 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：3. a
• b当且仅当G中含有形如P→…Rb…的产生式，而R …a或R …aQ。

第41页：优先关系表

优先关系表

• 可找出所有满足a
• b的终结符对。
• 确定满足关系
• 和
• 的所有终结符对：
• 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：比较比较

第42页：优先关系表（续）

优先关系表（续）

• 对任何b
• 和
• 的所有终结符对。
• FIRSTVT(P)，有a
• b。
• 假定有个产生式的一个候选形为…Pb…那么，对任何a
• LASTVT(P)，有a
• b。

第43页：按其定义

按其定义

• 可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式P→a…或P→Qa…，则a
• FIRSTVT(P)；2.若a
• FIRSTVT(Q)，且有产生式P→Q…，则a
• FIRSTVT(P)。

第44页：按其定义（续）

按其定义（续）

• 布尔数组F[P，a]，使得F[P，a]为真的条件是，当且仅当a
• FIRSTVT(P)。开始时，按上述的规则(1)对每个数组元素F[P，a]赋初值。
• 栈STACK，把所有初值为真的数组元素F[P，a]的符号对(P，a)全都放在STACK之中。

第45页：如果栈STACK不空

如果栈STACK不空

• 如果栈STACK不空，就将顶项逐出，记此项为(Q，a)。对于每个形如P→Q…的产生式，若F[P，a]为假，则变其值为真且将(P，a)推进STACK栈。
• 上述过程必须一直重复，直至栈STACK拆空为止。

第46页：如果栈STACK不空（续）

如果栈STACK不空（续）

如果把这个算法稍为形式化一点，我们可得如下所示的一个程序(包括一个过程和主程序)：PROCEDURE INSERT(P，a)；IF NOT F[P，a] THENBEGINF[P，a]:=TRUE；把(P，a)下推进STACK栈END；

第47页：如果栈STACK不空

如果栈STACK不空

BEGINFOR每个非终结符P和终结符a DOF[P，a]:=FALSE；FOR每个形如P→a…或P→Qa…的产生式DOINSERT(P，a)；WHILE STACK非空DOBEGIN把STACK的顶项，记为(Q，a)，上托出去；FOR每条形如P→Q…的产生式DOINSERT(P，a)；END OF WHILE；END

第48页：可构造计算LASTVT的算法

可构造计算LASTVT的算法

• 可构造计算LASTVT的算法。

第49页：按其定义

按其定义

• 可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P→… a或P→ … aQ，则a
• LASTVT(P)；2.若a
• LASTVT(Q)，且有产生式P→… Q，则a
• LASTVT(P)。

第50页：按其定义（续）

按其定义（续）

使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：

第51页：按其定义

按其定义

• =1 TO n-1 DOBEGINIF Xi和Xi+1均为终结符THEN置Xi
• Xi+1IF i
• n-2且Xi和Xi+2都为终结符但Xi+1为非终结符THEN置Xi
• Xi+2；IF Xi为终结符而Xi+1为非终结符THENFOR FIRSTVT(Xi+1)中的每个a DO置Xi
• a；IF Xi为非终结符而Xi+1为终结符THENFOR LASTVT(Xi)中的每个a DO置a
• Xi+1END

第52页：按其定义（续）

按其定义（续）

• F | P(4) P→(E) | i1.计算文法G的FIRSTVT和LASTVT;2.构造优先关系表;3. G是算符优先文法吗?

第53页：

第54页：G的算符优先关系表

G的算符优先关系表

结论: G是算符优先文法 G的算符优先关系表

第55页：G的算符优先关系表（续）

G的算符优先关系表（续）

注意

与数学上的<>=不同，a

• 定义任何两个可能相继出现的终结符a与b的优先关系三种关系a
• b a的优先级低于ba
• b a的优先级等于ba
• b a的优先级高于b
• b并不意味着b
• a

第56页：G的算符优先关系表

G的算符优先关系表

• b)至多只满足下述三关系之一：a
• -产生式的算符文法。对于任何一对终结符a、b，我们说：1. a
• b当且仅当文法G中含有形如P→…ab…或P→…aQb…的产生式；
• b，a
• b，a
• b则称G是一个算符优先文法。2. a
• b当且仅当G中含有形如P→…aR…的产生式，而R b…或R Qb…；3. a
• b当且仅当G中含有形如P→…Rb…的产生式，而R …a或R …aQ。

第57页：G的算符优先关系表（续）

G的算符优先关系表（续）

• 可找出所有满足a
• b的终结符对。
• 确定满足关系
• 和
• 的所有终结符对：
• 首先需要对G的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P)：比较比较

第58页：G的算符优先关系表

G的算符优先关系表

• 对任何b
• 和
• 的所有终结符对。
• FIRSTVT(P)，有a
• b。
• 假定有个产生式的一个候选形为…Pb…那么，对任何a
• LASTVT(P)，有a
• b。

第59页：按其定义

按其定义

• 可用下面两条规则来构造集合FIRSTVT(P)：1.若有产生式P→a…或P→Qa…，则a
• FIRSTVT(P)；2.若a
• FIRSTVT(Q)，且有产生式P→Q…，则a
• FIRSTVT(P)。

第60页：按其定义（续）

按其定义（续）

• 可用下面两条规则来构造集合LASTVT(P)：1.若有产生式P→… a或P→ … aQ，则a
• LASTVT(P)；2.若a
• LASTVT(Q)，且有产生式P→… Q，则a
• LASTVT(P)。

第61页：按其定义

按其定义

使用每个非终结符P的FIRSTVT(P)和LASTVT(P)，就能够构造文法G的优先表。构造优先表的算法是：

第62页：按其定义（续）

按其定义（续）

• =1 TO n-1 DOBEGINIF Xi和Xi+1均为终结符THEN置Xi
• Xi+1IF i
• n-2且Xi和Xi+2都为终结符但Xi+1为非终结符THEN置Xi
• Xi+2；IF Xi为终结符而Xi+1为非终结符THENFOR FIRSTVT(Xi+1)中的每个a DO置Xi
• a；IF Xi为非终结符而Xi+1为终结符THENFOR LASTVT(Xi)中的每个a DO置a
• Xi+1END

第63页：5.2.2算符优先分析算法

5.2.2算符优先分析算法

• 可归约串，句型，短语，直接短语，句柄，规范归约。
• 一个文法G的句型的素短语是指这样一个短语，它至少含有一个终结符，并且，除它自身之外不再含任何更小的素短语。
• 最左素短语是指处于句型最左边的那个素短语。

第64页：5.2.2算符优先分析算法（续）

5.2.2算符优先分析算法（续）

• F | P(4) P→(E) | iEEF+*TiFTFTP+ETP句型：T+F*P+i短语：直接短语：句柄：素短语：最左素短语：, T+F*P+iT, F, P, F*P,, iT+F*PT, F, P, iTF*P, iF*P

第65页：一个算符优先文法G

一个算符优先文法G

• 一个算符优先文法G的任何句型的最左素短语是满足如下条件的最左子串Njaj…NiaiNi+1，aj-1
• ajaj
• aj+1，…，ai-1
• aiai
• ai+1

第66页：使用一个符号栈S

使用一个符号栈S

• 用它寄存终结符和非终结符，k代表符号栈S的使用深度。

第67页：使用一个符号栈S（续）

使用一个符号栈S（续）

=1;S[k]

=‘#’;REPEAT把下一个输入符号读进a中；IF S[k]

VTTHEN j

=k ELSE j:=k-1;WHILE S[j]

VTTHEN j

=j-1 ELSE j:=j-2UNTIL S[j]

a THENBEGIN k

=k+1;S[k]:=a ENDELSE ERROR UNTIL a=‘#’自左至右，终结符对终结符，非终结符对非终结符，而且对应的终结符相同。N→X1X2… Xk-j↕↕↕S[j+1] S[j+2]…S[k]

• a DOBEGINREPEATQ:=S[j];IF S[j-1]
• Q;把S[j+1]…S[k]归约为某个N；k:=j+1;S[k]:=NEND OF WHILE;IF S[j]
• a OR S[j]

第68页：由于非终结符对归约没有影响

由于非终结符对归约没有影响

• 因此，非终结符根本可以不进符号栈S。

第69页：由于非终结符对归约没有影响（续）

由于非终结符对归约没有影响（续）

• (1) E→E+T | T(2) T→T*F | F(3) F→P
• F | P(4) P→(E) | i的句子i+i*i+i

第70页：算符优先分析法是一种广为应用

算符优先分析法是一种广为应用

优点

简单，快速

缺点

可能错误接受非法句子，能力有限.

• 行之有效的方法。
• 用于分析各类表达式
• ALGOL 60

第71页：5.2.3优先函数

5.2.3优先函数

优点

便于比较，节省空间；

缺点

原来不存在优先关系的两个终结符，由于自然数相对应，变成可以比较的。要进行一些特殊的判断。

• 把每个终结符
• 与两个自然数f(
• )与g(
• )相对应，使得若
• 1
• 2，则f(
• 1)< g(
• 2)若
• 1
• 2，则f(
• 1)= g(
• 2)若
• 1
• 2，则f(
• 1)> g(
• 2)f称为入栈优先函数，g称为比较优先函数。

第72页：5.2.3优先函数（续）

5.2.3优先函数（续）

• F | P(4) P→(E) | i的优先函数如下表

第73页：5.2.3优先函数

5.2.3优先函数

• 如果优先函数存在，则不唯一(无穷多)

第74页：5.2.3优先函数（续）

5.2.3优先函数（续）

• b，则从fa画一条弧至gb，如果a
• b，则画一条弧从gb至fa。2对每个结点都赋予一个数，此数等于从该结点出发所能到达的结点(包括出发点自身)。赋给fa的数作为f(a)，赋给ga的数作为g(a)。3检查所构造出来的函数f和g是否与原来的关系矛盾。若没有矛盾，则f和g就是要求的优先函数，若有矛盾，则不存在优先函数。

第75页：5.2.3优先函数

5.2.3优先函数

• 因为，若a
• b，则f(a)＝g(b)；若a
• b，则f(a)< g(b)；若a
• b，则f(a)>g(b)。
• b，则既有从fa到gb的弧，又有从gb到fa的弧。所以，fa和gb所能到达的结是全同的。
• 至于a
• b和a
• b的情形，只须证明其一。1对于每个终结符a，令其对应两个符号fa和ga，画一以所有符号和为结点的方向图。如果a
• b，则从fa画一条弧至gb，如果a
• b，则画一条弧从gb至fa。

第76页：5.2.3优先函数（续）

5.2.3优先函数（续）

• b，则有从fa到gb的弧。也就是，gb能到达的任何结fa也能到达。因此，f(a)
• g(b)。
• 我们所需证明的是，在这种情况下，f(a)＝g(b)不应成立。
• 我们将指出，如果f(a)＝g(b)，则根本不存在优先函数。假若f(a)＝g(b)，那么必有如下的回路：

第77页：因此有a

因此有a

• b, a1
• b, a1
• b1, …, am
• bm, a
• bm对任何优先函数f’和g’来说，必定有f’(a)> g’(b)
• f’(a1)
• g’(b1)
• …
• f’(am)
• g’(bm)
• f’(a)从而导致f’(a)> f’(a)，产生矛盾。因此，不存在优先函数f和g。fa1fafamgb1gbgbm……

第78页：因此有a（续）

因此有a（续）

• F | P(4) P→(E) | i的终结符+，*，↑，i

第79页：因此有a

因此有a

• fig+g*g
• gi

第80页：优先关系表的构造

优先关系表的构造

• FIRSTVT, LASTVT
• 自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。
• 优先函数
• 算符优先分析法回顾

第81页：规范归约

规范归约

定义

令G是一个文法，S是文法的开始符号，假定

• 是文法G的一个句型，如果有且则
• 称是句型
• 相对于非终结符A的短语。特别是，如果有A
• ,则称
• 是句型
• 相对于规则A
• 的直接短语。一个句型的最左直接短语称为该句型的句柄。

第82页：规范归约（续）

规范归约（续）

• 是文法G的一个句子，我们称序列
• n，
• n-1，
• ，
• 0是的一个规范归约，如果此序列满足：1
• n=
• 2
• 0为文法的开始符号，即
• 0=S3对任何i，0
• i
• n，
• i-1是从
• i经把句柄替换成为相应产生式左部符号而得到的。

第83页：5.3 LR分析法

5.3 LR分析法

LR分析法

1965年由Knuth提出分析表产生器文法分析表输入输出

• 产生分析表
• LR分析器工作LR分析总控程序分析表

第84页：5.3 LR分析法（续）

5.3 LR分析法（续）

• R分析表的构造方法及原理

第85页：5.3.1LR分析器

5.3.1LR分析器

“历史”

已移入符号栈的内容

“展望”

根据产生式推测未来可能遇到的输入符号

“现实”

当前的输入符号

第86页：an#输入串输出

an#输入串输出

• ai

第87页：an#输入串输出（续）

an#输入串输出（续）

• ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
• GOTO[s，X]：状态s面对文法符号X时，下一状态是什么

第88页：进行归约.假若

进行归约.假若

• 的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈.3.接受宣布分析成功，停止分析器工作.4.报错

第89页：进行归约.假若（续）

进行归约.假若（续）

• (s0s1
• an#)
• sm，# X1
• Xm，aiai+1
• an#)

第90页：进行归约.假若

进行归约.假若

• sm，# X1
• Xm，aiai+1
• an#)
• 分析器根据ACTION(sm, ai)确定下一步动作1.若ACTION(sm,ai)为移进，且s=GOTO(sm,ai),，则三元式格局变为:(s0s1
• sms，# X1
• Xmai，ai+1
• an#))2.若ACTION(sm, ai)为按A
• 归约，三元式变为:(s0s1
• sm-rs，# X1
• Xm-rA，aiai+1
• an#))此处,s=GOTO(sm-r,A), r为
• 的长度,
• =Xm-r+1
• Xm3.若ACTION(sm, ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功.4.若ACTION(sm, ai)为"报错"，则三元式变化过程终止，报告错误.(s0s1
• sm-rsm-r+1
• sm，# X1
• Xm-rXm-r+1
• Xm，aiai+1
• an#)(s0s1
• sm-r，# X1
• Xm-r，aiai+1
• an#))(s0s1
• sm-rs，# X1
• Xm-rA，aiai+1
• an#))

第91页：LR分析器示例

LR分析器示例

文法G(E)

(1) E→E＋T(2) E→T(3) T→T*F(4) T→F(5) F→(E)(6) F→i

第92页：LR分析器示例（续）

LR分析器示例（续）

其LR分析表为:

第93页：LR分析器示例

LR分析器示例

假定输入串为i*i+i，LR分析器的工作过程:步骤状态符号输入串(1)0#i*i+i#(2)05#i*i+i#(3)03#F*i+i#(4)02#T*i+i#(5)027#T*i+i#TiF*

第94页：LR分析器示例（续）

LR分析器示例（续）

假定输入串为i*i+i，LR分析器的工作过程:步骤状态符号输入串(5)027#T*i+i#(6)0275#T*i+i#(7)02710#T*F+i#(8)02#T+i#(9)01#E+i#(10)016#E+i#+iTF*TFiE

第95页：LR分析器示例

LR分析器示例

165#E+i#(12)0163#E+F#(13)0169#E+T#(14)01#E#(15)接受+iTF*TFiEiTFE

第96页：一个文法

一个文法

• 一个文法，如果能用一个每步顶多向前检查k个输入符号的LR分析器进行分析，则这个文法就称为LR(k)文法.
• 非LR结构
• LR文法不是二义的，二义文法肯定不会是LR的。S
• iCtS | iCtSeS栈输入…iCtS e…#

第97页：一个文法（续）

一个文法（续）

• 假定
• 是文法G的一个句子，我们称序列
• n，
• n-1，
• ，
• 0是的一个规范归约，如果此序列满足：1
• n=
• 2
• 0为文法的开始符号，即
• 0=S3对任何i，0
• i
• n，
• i-1是从
• i经把句柄替换成为相应产生式左部符号而得到的。

第98页：一个文法

一个文法

• 规范归约过程中
• 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
• 栈内的如果出现句柄，句柄一定在栈的顶部X•••a•句柄•句•••柄• • •柄句•••a• • ••柄句••a• • •栈内永远不会出现句柄之后的符号！

第99页：一个文法（续）

一个文法（续）

字的前缀

是指字的任意首部，如字abc的前缀有

活前缀

是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型

• ，a，ab，abc
• ，
• 为句柄，如果
• =u1u2…ur，则符号串u1u2…ui(1
• i
• r)是
• 的活前缀。(
• 必为终结符串)
• 对于一个文法G,可以构造一个DFA,它能识别G的所有活前缀.

第100页：指导思想——目标驱动

指导思想——目标驱动

• 踢足球“如果你不知道怎样踢球，就往球门方向踢”——施拉普纳
• LR分析“如果你不知道怎样分析，就保证栈中总是活前缀”1.一个语言都有哪些活前缀?2.那些字符串是活前缀?3.能不能构造一个DFA来识别活前缀?

第101页：XYZ有四个项目

XYZ有四个项目

• XYZ有四个项目：A
• .XYZA
• X.YZA
• XY.ZA
• XYZ.
• A
• .称为"归约项目"
• 归约项目S’
• .称为"接受项目"
• A
• .a
• (a
• VT)称为"移进项目"
• A
• .B
• (B
• VN)称为"待约项目".

第102页：XYZ有四个项目（续）

XYZ有四个项目（续）

该文法的项目有

1. S

• →EE→aA|bBA→cA|dB→cB|d
• →·E2. S
• →E·3. E→·aA4. E→a·A5. E→aA·6. A→·cA7. A→c·A8. A→cA·9. A→·d10. A→d·11. E→·bB12. E→b·B13. E→bB·14. B→·cB15. B→c·B16. B→cB·17. B→·d18. B→d·

第103页：XYZ有四个项目

XYZ有四个项目

• X1… Xi-1.Xi… Xn，状态j为X
• X1… Xi-1Xi.Xi+1… Xn，则从状态i画一条标志为Xi的有向边到状态j；2.若状态i为X
• .A
• ，A为非终结符，则从状态i画一条
• 边到所有状态A
• .
• 。

第104页：XYZ有四个项目（续）

XYZ有四个项目（续）

• 7
• a
• AEbBBcAcd识别活前缀的NFA

第105页：识别活前缀的DFA0

识别活前缀的DFA0

→·EE→·aAE→·bB4

A→c·AA→·cAA→·d2:E→a·AA→·cAA→·d1:S

→E·3

E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB

第106页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

构成识别一个文法活前缀的DFA的项目集(状态)的全体称为文法的LR(0)项目集规范族。

第107页：识别活前缀的DFA0

识别活前缀的DFA0

• 我们说项目A
• 1.
• 2对活前缀
• 1是有效的，其条件是存在规范推导
• 在任何时候，分析栈中的活前缀X1X2…Xm的有效项目集正是栈顶状态Sm所代表的那个集合。也正是从识别活前缀的DFA的初态出发，读出X1X2… Xm后到达的那个项目集(状态)。

第108页：对活前缀

对活前缀

• .B
• =
• 是有效的且B
• 是一个产生式，则项目B
• .
• 对
• =
• 也是有效的。所以，B
• .
• 对
• =
• 也是有效的。设，那么

第109页：对活前缀（续）

对活前缀（续）

考虑

项目：B

.d活前缀

bcS’

• →EE→aA|bBA→cA|dB→cB|d
• c.BB
• .cBB
• E
• bB
• bcBS’
• E
• bB
• bcB
• bccBS’
• E
• bB
• bcB
• bcd项目A
• 1.
• 2对活前缀
• 1是有效的，其条件是存在规范推导

第110页：对活前缀

对活前缀

• 假定文法G是一个以S为开始符号的文法，我们构造一个G
• ，它包含了整个G，但它引进了一个不出现在G中的非终结符S
• ，并加进一个新产生式S
• →S，而这个S
• 是G
• 的开始符号。那么，我们称G
• 是G的拓广文法。这样，便会有一个仅含项目S
• →S.的状态，这就是唯一的“接受”态。

第111页：对活前缀（续）

对活前缀（续）

-closure(I)为

i)若s

• 定义和构造I的闭包CLOSURE(I)如下：1. I的任何项目都属于CLOSURE(I)；2.若A→
• ·B
• 属于CLOSURE(I)，那么，对任何关于B的产生式B→
• ，项目B→·
• 也属于CLOSURE(I)；3.重复执行上述两步骤直至CLOSURE(I)不再增大为止。P50：NFA确定化设I是的状态集的一个子集，定义I的
• -闭包
• I，则s
• -closure(I)；ii)若s
• I，则从s出发经过任意条
• 弧而能到达的任何状态s’都属于
• -closure(I)
• -closure(I)=I
• {s’|从某个s
• I出发经过任意条
• 弧能到达s’}2.若状态i为X
• .A
• ，A为非终结符，则从状态i画一条
• 边到所有状态A
• .
• 。

第112页：对活前缀

对活前缀

• X·
• 的项目| A→
• ·X
• 属于I}。
• 直观上说，若I是对某个活前缀
• 有效的项目集，那么，GO(I，X)便是对
• X有效的项目集。
• 中的一个字符，定义Ia=
• -closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。

第113页：对活前缀（续）

对活前缀（续）

• →EE→aA|bBA→cA|dB→cB|d
• I0={S
• →·E, E→·aA, E→·bB}GO(I0, E)= closure(J)=closure({S’→E·})= {S’→E·} = I1GO(I0, a)= closure(J)=closure({E→a·A})={ E→a·A, A→·cA, A→·d} )=I2GO(I0, b)= closure(J)=closure ({E →b.B})={E →b.B, B→.cB, B→.d}= I3

第114页：对活前缀

对活前缀

• PROCEDURE ITEMSETS(G
• )；BEGINC:={CLOSURE({S
• ·S})}；REPEATFOR C中每个项目集I和G
• 的每个符号X DOIF GO(I，X)非空且不属于C THEN把GO(I，X)放入C族中;UNTIL C不再增大END
• 转换函数GO把项目集连接成一个DFA转换图.

第115页：对活前缀（续）

对活前缀（续）

→·EE→·aAE→·bB4

A→c·AA→·cAA→·dc5:B→c·BB→·cBB→·dc3:E→b·BB→·cBB→·db1:S

→E·E2

E→a·AA→·cAA→·da11:B→d·d8:A→cA·Accd10:A→d·dd9:B→cB·B6:E→aA·A7:E→bB·B

第116页：规范归约

规范归约

定义

令G是一个文法，S是文法的开始符号，假定

• 是文法G的一个句型，如果有且则
• 称是句型
• 相对于非终结符A的短语。特别是，如果有A
• ,则称
• 是句型
• 相对于规则A
• 的直接短语。一个句型的最左直接短语称为该句型的句柄。

第117页：规范归约（续）

规范归约（续）

• 是文法G的一个句子，我们称序列
• n，
• n-1，
• ，
• 0是的一个规范归约，如果此序列满足：1
• n=
• 2
• 0为文法的开始符号，即
• 0=S3对任何i，0
• i
• n，
• i-1是从
• i经把句柄替换成为相应产生式左部符号而得到的。

第118页：5.3 LR分析法

5.3 LR分析法

LR分析法

1965年由Knuth提出分析表产生器文法分析表输入输出

• 产生分析表
• LR分析器工作LR分析总控程序分析表

第119页：an#输入串输出

an#输入串输出

• ai

第120页：an#输入串输出（续）

an#输入串输出（续）

• ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作.
• GOTO[s，X]：状态s面对文法符号X时，下一状态是什么

第121页：进行归约.假若

进行归约.假若

• 的长度为r，归约动作是，去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈.3.接受宣布分析成功，停止分析器工作.4.报错

第122页：进行归约.假若（续）

进行归约.假若（续）

• (s0s1
• an#)
• sm，# X1
• Xm，aiai+1
• an#)

第123页：进行归约.假若

进行归约.假若

• sm，# X1
• Xm，aiai+1
• an#)
• 分析器根据ACTION(sm, ai)确定下一步动作1.若ACTION(sm,ai)为移进，且s=GOTO(sm,ai),，则三元式格局变为:(s0s1
• sms，# X1
• Xmai，ai+1
• an#))2.若ACTION(sm, ai)为按A
• 归约，三元式变为:(s0s1
• sm-rs，# X1
• Xm-rA，aiai+1
• an#))此处,s=GOTO(sm-r,A), r为
• 的长度,
• =Xm-r+1
• Xm3.若ACTION(sm, ai)为"接受"，则三元式不再变化，变化过程终止，宣布分析成功.4.若ACTION(sm, ai)为"报错"，则三元式变化过程终止，报告错误.(s0s1
• sm-rsm-r+1
• sm，# X1
• Xm-rXm-r+1
• Xm，aiai+1
• an#)(s0s1
• sm-r，# X1
• Xm-r，aiai+1
• an#))(s0s1
• sm-rs，# X1
• Xm-rA，aiai+1
• an#))

第124页：进行归约.假若（续）

进行归约.假若（续）

• 规范归约过程中
• 栈内的符号串和扫描剩下的输入符号串构成了一个规范句型
• 栈内的如果出现句柄，句柄一定在栈的顶部X•••a•句柄•句•••柄• • •柄句•••a• • ••柄句••a• • •栈内永远不会出现句柄之后的符号！

第125页：进行归约.假若

进行归约.假若

字的前缀

是指字的任意首部，如字abc的前缀有

活前缀

是指规范句型的一个前缀，这种前缀不含句柄之后的任何符号。即，对于规范句型

• ，a，ab，abc
• ，
• 为句柄，如果
• =u1u2…ur，则符号串u1u2…ui(1
• i
• r)是
• 的活前缀。(
• 必为终结符串)
• 对于一个文法G,可以构造一个DFA,它能识别G的所有活前缀.

第126页：进行归约.假若（续）

进行归约.假若（续）

• X1… Xi-1.Xi… Xn，状态j为X
• X1… Xi-1Xi.Xi+1… Xn，则从状态i画一条标志为Xi的有向边到状态j；2.若状态i为X
• .A
• ，A为非终结符，则从状态i画一条
• 边到所有状态A
• .
• 。

第127页：进行归约.假若

进行归约.假若

该文法的项目有

1. S

• →EE→aA|bBA→cA|dB→cB|d
• →·E2. S
• →E·3. E→·aA4. E→a·A5. E→aA·6. A→·cA7. A→c·A8. A→cA·9. A→·d10. A→d·11. E→·bB12. E→b·B13. E→bB·14. B→·cB15. B→c·B16. B→cB·17. B→·d18. B→d·

第128页：进行归约.假若（续）

进行归约.假若（续）

• 7
• a
• AEbBBcAcd识别活前缀的NFA

第129页：识别活前缀的DFA0

识别活前缀的DFA0

→·EE→·aAE→·bB4

A→c·AA→·cAA→·d2:E→a·AA→·cAA→·d1:S

→E·3

E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB

第130页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• 假定文法G是一个以S为开始符号的文法，我们构造一个G
• ，它包含了整个G，但它引进了一个不出现在G中的非终结符S
• ，并加进一个新产生式S
• →S，而这个S
• 是G
• 的开始符号。那么，我们称G
• 是G的拓广文法。这样，便会有一个仅含项目S
• →S.的状态，这就是唯一的“接受”态。

第131页：识别活前缀的DFA0

识别活前缀的DFA0

-closure(I)为

i)若s

• 定义和构造I的闭包CLOSURE(I)如下：1. I的任何项目都属于CLOSURE(I)；2.若A→
• ·B
• 属于CLOSURE(I)，那么，对任何关于B的产生式B→
• ，项目B→·
• 也属于CLOSURE(I)；3.重复执行上述两步骤直至CLOSURE(I)不再增大为止。P50：NFA确定化设I是的状态集的一个子集，定义I的
• -闭包
• I，则s
• -closure(I)；ii)若s
• I，则从s出发经过任意条
• 弧而能到达的任何状态s’都属于
• -closure(I)
• -closure(I)=I
• {s’|从某个s
• I出发经过任意条
• 弧能到达s’}2.若状态i为X
• .A
• ，A为非终结符，则从状态i画一条
• 边到所有状态A
• .
• 。

第132页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• X·
• 的项目| A→
• ·X
• 属于I}。
• 直观上说，若I是对某个活前缀
• 有效的项目集，那么，GO(I，X)便是对
• X有效的项目集。
• 中的一个字符，定义Ia=
• -closure(J)其中，J为I中的某个状态出发经过一条a弧而到达的状态集合。

第133页：识别活前缀的DFA0

识别活前缀的DFA0

• →EE→aA|bBA→cA|dB→cB|d
• I0={S
• →·E, E→·aA, E→·bB}GO(I0, E)= closure(J)=closure({S’→E·})= {S’→E·} = I1GO(I0, a)= closure(J)=closure({E→a·A})={ E→a·A, A→·cA, A→·d} )=I2GO(I0, b)= closure(J)=closure ({E →b.B})={E →b.B, B→.cB, B→.d}= I3

第134页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• PROCEDURE ITEMSETS(G
• )；BEGINC:={CLOSURE({S
• ·S})}；REPEATFOR C中每个项目集I和G
• 的每个符号X DOIF GO(I，X)非空且不属于C THEN把GO(I，X)放入C族中;UNTIL C不再增大END
• 转换函数GO把项目集连接成一个DFA转换图.

第135页：识别活前缀的DFA0

识别活前缀的DFA0

→·EE→·aAE→·bB4

A→c·AA→·cAA→·dc5:B→c·BB→·cBB→·dc3:E→b·BB→·cBB→·db1:S

→E·E2

E→a·AA→·cAA→·da11:B→d·d8:A→cA·Accd10:A→d·dd9:B→cB·B6:E→aA·A7:E→bB·B

第136页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• 假若一个文法G的拓广文法G
• 的活前缀识别自动机中的每个状态(项目集)不存在下述情况：1)既含移进项目又含归约项目，2)含有多个归约项目则称G是一个LR(0)文法。

第137页：识别活前缀的DFA0

识别活前缀的DFA0

• 令每个项目集Ik的下标k作为分析器的状态，包含项目S
• →·S的集合Ik的下标k为分析器的初态。

第138页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• 3.若项目S
• ·a
• 属于Ik且GO(Ik, a)＝Ij，a为终结符，则置ACTION[k,a]为“sj”。2.若项目A→
• ·属于Ik，那么，对任何终结符a(或结束符#)，置ACTION[k,a]为“rj”(假定产生式A→
• 是文法G
• →S·属于Ik，则置ACTION[k,#]为“acc”。4.若GO(Ik,A)＝Ij，A为非终结符，则置GOTO[k,A]=j。5.分析表中凡不能用规则1至4填入信息的空白格均置上“报错标志”。

第139页：识别活前缀的DFA0

识别活前缀的DFA0

• →EE→aA|bBA→cA|dB→cB|d

第140页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

→·EE→·aAE→·bB4

A→c·AA→·cAA→·d2:E→a·AA→·cAA→·d1:S

→E·3

E→b·BB→·cBB→·d5:B→c·BB→·cBB→·d11:B→d·9:B→cB·7:E→bB·10:A→d·6:E→aA·8:A→cA·ccbEadAccdddBAB

第141页：识别活前缀的DFA0

识别活前缀的DFA0

LR(0)分析表为

第142页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

d#3024#acccd#40244#acccd#502444#acccd#60244410#acccd#7024448#acccA#802448#accA#90248#acA#10026#aA#1101#E#

第143页：识别活前缀的DFA0

识别活前缀的DFA0

• LR(0)文法太简单，没有实用价值.
• 假定一个LR(0)规范族中含有如下的一个项目集(状态)I＝{X→
• ·b
• ，A→
• ·，B→
• ·}。FOLLOW(A)和FOLLOW(B)的交集为
• ，且不包含b，那么，当状态I面临任何输入符号a时，可以:1.若a=b，则移进；2.若a
• FOLLOW(A)，用产生式A→
• 进行归约；3.若a
• FOLLOW(B)，用产生式B→
• 进行归约；4.此外，报错。

第144页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• ·a1
• 1，A2→
• ·a2
• 2，…，Am→
• ·am
• m，B1→
• ·，B2→
• ·，…，Bn→
• ·}如果集合{a1，…，am}，FOLLOW(B1)，…，FOLLOW(Bn)两两不相交(包括不得有两个FOLLOW集合有#)，则：1.若a是某个ai，i=1,2,…,m，则移进；2.若a
• FOLLOW(Bi)，i=1,2,…,n，则用产生式Bi→
• 进行归约；3.此外，报错。

第145页：识别活前缀的DFA0

识别活前缀的DFA0

• 首先把G拓广为G
• ，对G
• 构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO.
• 然后使用C和GO，按下面的算法构造SLR分析表：
• 令每个项目集Ik的下标k作为分析器的状态，包含项目S
• →·S的集合Ik的下标k为分析器的初态。

第146页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• 3.若项目S
• ·a
• 属于Ik且GO(Ik,a)=Ij，a为终结符，则置ACTION[k,a]为“sj”；2.若项目A→
• ·属于Ik，那么，对任何终结符a，a
• FOLLOW(A)，置ACTION[k,a]为“rj”；其中，假定A
• 为文法G
• →S·属于Ik，则置ACTION[k,#]为“acc”;4.若GO(Ik,A)＝Ij，A为非终结符，则置GOTO[k,A]=j；5.分析表中凡不能用规则1至4填入信息的空白格均置上“出错标志”。

第147页：识别活前缀的DFA0

识别活前缀的DFA0

• 每个SLR(1)文法都是无二义的。但也存在许多无二义文法不是SLR(1)的.

第148页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• F(4) T→F(5) F→(E)(6) F→i

第149页：识别活前缀的DFA0

识别活前缀的DFA0

→E·E→E·+TI2

E→T·T→T·*FI3: T→F·I4: F→(·E)E→·E+TE→·TT→·T*FT→·FF→· (E)F→·iI5:F→i·I6: E→E+·TT→·T*FT→·FF→·(E)F→·iI7: T→T*·FF→·(E)F→·iI8: F→(E·)E→E·+TI9: E→E+T·T→T·*FI10: T→T*F·I11: F→(E)·

第150页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• E+T*TTiF(i(FE(Fi+F*()

第151页：识别活前缀的DFA0

识别活前缀的DFA0

I2

E→T·T→T·*FI1: S

→E·E→E·+TI9

E→E+T·T→T·*F

第152页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

其分析表如下:

第153页：识别活前缀的DFA0

识别活前缀的DFA0

• (4) L→i(5) R→L计算FOLLOW集合所得到的超前符号集合可能大于实际能出现的超前符号集

第154页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

→S·I2

S→L·=RR→L·I3：S→R·I4：L→*·RR→·LL→·*RL→·iI5：L→i·I6：S→L=·RR→·LL→·*RL→·iI7：L→*R·I9：S→L=R·I8：R→L·

• I0：S
• →·SS→·L=RS→·RS→·*RL→·iR→·LI1：S

第155页：

第156页：识别活前缀的DFA0

识别活前缀的DFA0

I2

S→L·=RR→L·

第157页：识别活前缀的DFA0（续）

识别活前缀的DFA0（续）

• (4) L→i(5) R→L
• 当状态2显现于栈顶而且面临输入符号为‘=’时，实际上不能用对栈顶L进行归约。不含“R=”为前缀的规范句型有含“*R=”为前缀的规范句型I2：S→L·=RR→L·

第158页：识别活前缀的DFA0

识别活前缀的DFA0

• .而且下一输入符号a
• FOLLOW(A),则状态i面临a时,可选用“用A
• 归约”动作。但在有些情况下,当状态i显现于栈顶时,栈里的活前缀未必允许把
• 归约为A，因为可能根本就不存在一个形如“
• Aa”的规范句型。因此，在这种情况下，用“A
• ”归约不一定合适。

第159页：5.3.4规范LR分析表的构造

5.3.4规范LR分析表的构造

• 我们需要重新定义项目，使得每个项目都附带有k个终结符。每个项目的一般形式是[A→
• ·
• , a1a2…ak]，这样的一个项目称为一个LR(k)项目。项目中的a1a2…ak称为它的向前搜索符串(或展望串)。
• 向前搜索符串仅对归约项目[A→
• ·，a1a2…ak]有意义。对于任何移进或待约项目[A→
• ·
• , a1a2…ak],
• ，搜索符串a1a2…ak没有作用。

第160页：我们只对k

我们只对k

·, a1a2…ak]意味着

当它所属的状态呈现在栈顶且后续的k个输入符号为a1a2…ak时，才可以把栈顶上的

• 归约为A。
• 1的情形感兴趣，向前搜索(展望)一个符号就多半可以确定“移进”或“归约”。
• 形式上我们说一个LR(1)项目[A→
• ·
• , a]对于活前缀
• 是有效的，如果存在规范推导其中，1)
• ＝
• ；2) a是
• 的第一个符号，或者a为#而
• 为
• 。

第161页：我们只对k（续）

我们只对k（续）

为构造有效的LR(1)项目集族我们需要两个函数CLOSURE和GO。

第162页：我们只对k

我们只对k

证明

若项目[A→

• ·B
• ,a]对活前缀
• ＝
• 是有效的，则对于每个形如B
• 的产生式，对任何b
• FIRST(
• a)，[B→·
• , b]对
• 也是有效的。
• ·B
• ,a]对
• ＝
• 有效，则有规范推导

第163页：我们只对k（续）

我们只对k（续）

• ·B
• ,a]属于CLOSURE(I)，B→
• 是一个产生式，那么，对于FIRST(
• a)中的每个终结符b，如果[B→·
• ,b]原来不在CLOSURE(I)中，则把它加进去。3.重复执行步骤2，直至CLOSURE(I)不再增大为止。

第164页：我们只对k

我们只对k

• X·
• ,a]的项目| [A→
• ·X
• ,a]
• I}

第165页：我们只对k（续）

我们只对k（续）

BEGINC

={CLOSURE({[S

• →·S，#]})};REPEATFORC中每个项目集I和G
• 的每个符号XDOIF GO(I，X)非空且不属于C，THEN把GO(I，X)加入C中UNTILC不再增大END

第166页：我们只对k

我们只对k

• 令每个Ik的下标k为分析表的状态，令含有[S

第167页：我们只对k（续）

我们只对k（续）

• 3.若项目[S
• ·a
• , b]属于Ik且GO(Ik, a)＝Ij，a为终结符，则置ACTION[k, a]为“sj”。2.若项目[A→
• ·，a]属于Ik，则置ACTION[k, a]为“rj”；其中假定A→
• 为文法G
• →S·, #]属于Ik，则置ACTION[k, #]为“acc”。4.若GO(Ik，A)＝Ij，则置GOTO[k, A]=j。5.分析表中凡不能用规则1至4填入信息的空白栏均填上“出错标志”。

第168页：我们只对k

我们只对k

• 具有规范的LR(1)分析表的文法称为一个LR(1)文法。
• LR(1)状态比SLR多，LR(0)
• SLR
• LR(1)
• 无二义文法

第169页：我们只对k（续）

我们只对k（续）

• →S(1) S→BB(2) B→aB(3) B→b

第170页：我们只对k

我们只对k

• S’
• •S, #S
• •BB, #B
• •aB, a/bB
• •b, a/bSI1: S’
• S •, #BI2: S
• B • B, #B
• •aB, #B
• •b, #aI3: B
• a•B, a/bB
• •aB, a/bB
• •b, a/bbI4:B
• b •, a/bBI5: S
• BB•, #aI6: B
• a•B, #B
• •aB, #B
• •b, #bI7:B
• b •, #BI8:B
• aB•, a/babaI9:B
• aB•, #BbI0: S’
• •S, #S
• •BB, #B
• •aB, aB
• •aB, bB
• •b, aB
• •b, b

第171页：LR(1)分析表为

LR(1)分析表为

LR(1)分析表为:

第172页：LR(1)分析表为（续）

LR(1)分析表为（续）

例:按上表对aabab进行分析步骤状态符号输入串00#aabab#103#aabab#2033#aabab#30334#aabab#40338#aaBab#5038#aBab#602#Bab#7026#Bab#80267#Baa#90269#BaB#10025#BB#1101#S#acc

第173页：LR(1)分析表为

LR(1)分析表为

例:按上表对abab进行分析步骤状态符号输入串00#abab#103#abab#2034#abab#3038#aBab#402#Bab#5026#Bab#60267#Bab#70269#BaB#8025#BB#901#S#acc

第174页：LR(1)分析表为（续）

LR(1)分析表为（续）

• P133—1，2，3
• P134—5 (1)，(2)，(3),(4)
• P134—8(选作)