发布时间 : 星期一 文章编译原理期末复习更新完毕开始阅读
PROCEDURE E； BEGIN V; E’ END;
PROCEDURE E’； IF SYM=‘+’ THEN BEGIN ADVANCE； E
END
PROCEDURE F； PROCEDURE N； IF SYM=‘[’ THEN IF SYM=‘i’ THEN
BEGIN ADVANCE ADVANCE; ELSE ERROR; E； IF SYM=‘]’ THEN ADVANCE ELSE ERROR END
ELSE ERROR;
PROCEDURE Ｖ； BEGIN N;V’ END;
考题2：为文法G[E]:E→E+T|T T→T*F|F F→(E)|i构造递归下降识别程序 解：（1）消除左递归：E→TE? E?→+TE? | ? T→FT? T?→*FT? | ? F→(E) | i
(2)构造递归下降识别程序
PROCEDURE E； BEGIN
T；E? END；
PROCEDURE T； BEGIN F；T? END
PROCEDURE F； IF SYM=‘i’ THEN ADVANCE ELSE IF SYM=‘(’ THEN BEGIN ADVANCE; E； IF SYM=‘)’
THEN ADVANCE
ELSE ERROR END ELSE ERROR;
PROCEDURE E?；
IF SYM=‘+’ THEN BEGIN ADVANCE； T；E? END
PROCEDURE T?； IF SYM=‘*’ THEN BEGIN
ADVANCE； F；T? END
7、自底向上分析法——LR（0）分析法
注：自底向上分析法本质是从输入串开始，逐步进行“归约”，直到文法的开始符号,其关键问题是寻找句柄。
自底向上分析法还有算符优先分析法，SLR(1),LR（1）等等，老师那天重点讲了一道LR(0)分析法的题目，他说算符优先分析法A卷不考，但是补考的B卷会考，按照他的意思，这次期末考试LR(0)是考定的了，SLR(1),LR（1）应该不考，因为LR(0)分析法个人感觉也是所有题目中最繁的了，下面已老师讲的题目为例这，也是一份试卷上的考题，首先介绍一些相关知识。
13 / 21
（1）
LR(0)项目：通俗点讲，文法G中的任何一个产生式的右部的任何位置添加一个圆点就成了LR(0)项目，比如A→Ab是产生式，则A→?Ab A→A?b A→Ab?都是该产生式对应的全部项目。项目动态的表示归约的一个阶段：对于项目A→A?b，可以这样理解它：“?”之前的A表示的是在识别Ab过程中已输入到栈终的部分；“?”之后的表示在识别Ab过程中期望出现的部分；“?”表示则是在识别Ab过程中当前的识别进度的定位。项目A→Ab?已经具备了识别Ab的一切条件，因此被称为归约项目。
项目可以分为以下四类：P→α?aβ称为移进项目其中, P→α?Xβ称为待约项目，其中X为非终结符，P→α? 称为归约项目，S’ →S称为接收项目 （2）LR(0)的分析栈可以看成两部分状态栈
LR分析器的核心是一张分析表：
ACTION[s，a]：当状态s面临输入符号a时，应采取什么动作. GOTO[s，X]：状态s面对文法符号X时，下一状态是什么.
下面几张PPT大家看看，对基本概念有个印象： LR分析方法：把\历史\及\展望\综合抽象成状态；由栈顶的状态和现行的输入符号唯一确定每一步工作Sm?每一项ACTION[s，a]所规定的四种动作:1. 移进 把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号.2. 归约 指用某产生式A进行归约. 假若的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈.3. 接受 宣布分析成功，停止分析器工作.4. 报错Xm?a1a2ai an#输入串S1S0X1# LR分析程 序 输出状态符号分析栈 action goto江西财经大学信息管理学院 LR分析表 江西财经大学信息管理学院
这一章的概念较多较抽象，我一时半会也讲不完讲不清楚，这里不再赘述，直接看题目，知道怎么做就行，下面以一道考题这也是老师讲的原题为例讲解如何做这类题目，首先一般这种题目分三步走：
14 / 21
(1)拓广文法：假定文法G是一个以S为开始符号的文法，我们构造一个G?，它包含了整个G，但它引进了一个不出现在G中的非终结符S?，并加进一个新产生式S?→S，而这个S?是G?的开始符号。那么，我们称G?是G的拓广文法。这样，便会有一个仅含项目S?→S.的状态，这就是唯一的“接受”态。
（2）构造识别文法活前缀的DFA:对于任意的项目即I,其闭包CLOSURE(I)计算方法如下，I中的所有项目都属于CLOSURE(I);如果P→α?Xβ,并且X为非终结符，则所有形如X→?γ的项目也属于ClOSURE(I)定义函数GO(I,X)，其中I是项目集，X是任意的文法符号（终结符，非终结符都可以），GO(I，X)=CLOSURE(J).J是从I中项目出发后读取X后到达的后继项目,即J={P→αX?β| P→α?Xβ∈I}
有了上述CLOSURE和GO的定以后，从CLOSURE({S?→?S})出发，利用GO函数，产生出它在每个可能的文法符号下，要转移的项目集，再对新产生的项目集采取同样的方法直到没有新产生的项目集未被处理为止。
(4) 根据计算出的项目集之间的关系画出DFA和LR(0)分析表，其中LR(0)构造方法如
下:
对具体的句子运用LR(0)分析的方法如下： 每一项ACTION[s，a]所规定的四种动作:
1. 移进 把(s，a)的下一状态s’和输入符号a推进栈，下一输入符号变成现行输入符号.
2. 归约 指用某产生式A→β进行归约. 假若β的长度为r， 归约动作是， 去除栈顶r个项，使状态sm-r变成栈顶状态，然后把(sm-r, A)的下一状态s’=GOTO[sm-r, A]和文法符号A推进栈.
3. 接受（即acc） 宣布分析成功，停止分析器工作. 4. 报错
考题：构造文法G[E]的LR(0)分析表，并给出accd的分析过程。
（0）S?→E（1）E→aA （2）E→bB （3）A→cA （4） A→d （5）B→cB （6）B→d 分析：题中已经进行了推广文法，所以第一步就不需要了，下面就是开始构造识别活前缀的DFA，然后构造出LR（0）分析表，最后在进行分析，实际上对于accd我们自己可以先推一下，E?aA?acA?accA?accd所以该句子符合文法，那么最终构造出的LR（0）分析表对该句子进行分析后必定得到“acc”（接受的意思），否则构造的LR(0)分析表出错。
15 / 21
(5)
答：（1）构造识别活前缀的DFA:
I0=Closure({S?→?E })={ S?→?E, E→?aA, E→?bB }
I1=GO(I0,E)=Closure({S?→E?})={ S?→E? }
I2=GO(I0,a)=Closure({ E→a?A })={ E→a?A，A→?cA ，A→?d } I3=GO(I0,b)=Closure({ E→b?B })={E→b?B, B→?cB ，B→?d }
（为了方便，下面计算中的Closure不再写了，直接给出答案,考试时可以不写，当然计算I0是必须要的）
I4=GO(I2,A)={ E→aA?} I5=GO(I2,c)={ A→c?A，A→?cA ，A→?d } I6= GO(I2,d)={ A→d?} I7=GO(I3,B)={ E→bB?}
I8= GO(I3,c)= { B→c?B，B→?cB ，B→?d } I9= GO(I3,d)={ B→d?} I10= GO(I5,A) ={ A→cA?} GO(I5,c)=I5 GO(I5.d)=I6 I11= GO(I8,B) { B→cB?} GO(I8,c)=I8 GO(I8.d)=I9 画出DFA:
注：实际上构造LR(0)分析表时这个图没有必要画，根据上述计算结果即可填写下表。 （2）画出LR(0)分析表
16 / 21