编译原理语法分析

编译原理语法分析第1页，课件共108页，创作于2023年2月自下而上分析法是一种移进-归约法。分析过程中采用了一个FIFO分析栈。分析开始后，把输入符号自左至右逐个移进分析栈，边移入边分析，一旦栈顶符号串形成句柄就进行一次归约，再继续查看栈顶是否形成新的句柄，若仍为句柄，则再归约，如此重复直至栈顶不是句柄。此时再继续向栈中移进后续输入符号。重复该过程，直到将整个输入串处理完毕。若此时分析栈只有文法开始符，则输入串是一个句子，否则输入串有错。第2页，课件共108页，创作于2023年2月下面通过例子说明这种分析过程。文法G[S]：S→aAbBA→c∣AcB→d

试对输入串accbd进行分析，检查该符号串是否是G[S]的一个句子。假设“#”为输入串界符，将输入串前的“#”放入分析栈，接着将输入串的符号依次进栈，具体分析过程如下:第3页，课件共108页，创作于2023年2月步骤分析栈句柄输入串动作1#

accbd#移进2#a

ccbd#移进3#ac

cbd#移进4#aAccbd#归约(用A→c)5#aAc

bd#移进6#aAAcbd#归约(用A→Ac)7#aAb

d#移进8#aAbd

#移进9#aAbBd#归约(B→d)10#SaAbB#归约(S→aAbB)第4页，课件共108页，创作于2023年2月SaccbdABA(d)accbdABA(c)accAA(b)acA(a)在自下而上分析过程中，每一步归约都可画出一棵子树，随着归约的完成，这些子树连成一棵完整的分析树。上述分析过程可用分析树表示如下:第5页，课件共108页，创作于2023年2月由上述建树过程知，自下而上分析过程的每一步归约都是对当前句型的句柄进行归约，即句柄一旦形成总是出现在分析栈栈顶。由于每一步归约都把栈顶符号串用某产生式左部符号替换，故把栈顶的这样一串符号称为可归约串。上述第6步若不选A→Ac而选A→c进行归约，则无法归约到S。如何确知栈顶的Ac是可归约串而c不是呢？这需精确定义“可归约串”的概念。第6页，课件共108页，创作于2023年2月若文法G[S]是无二义文法，则规范推导的逆过程必是规范归约(最左归约)。对于移进-归约过程，句柄的最左性和分析栈栈顶相关。对于规范推导所得句型(规范句型)，句柄后面不会出现非终结符，故可用句柄刻画“可归约串”，规范归约的实质是在移进过程中当栈顶呈现句柄时进行归约。第7页，课件共108页，创作于2023年2月为加深对句柄和归约等概念的理解，用修剪语法树方法进一步阐明自下而上分析过程。语法树的一个子树由该树的某结点及其所有子孙组成，子树的所有叶结点的自左至右排列形成一个相对于子树根的短语。一个句型的句柄是该句型对应的语法树中最左简单子树的所有树叶的自左至右排列。第8页，课件共108页，创作于2023年2月可采用修剪语法树方法实现归约，即寻找当前语法树的句柄，将句柄中的树叶剪去(归约)，不断修剪直到只剩根结点，完成整个归约过程：SaAbBAcdcSaAbBAcdSaAbBdSaAbBS第9页，课件共108页，创作于2023年2月至此讨论了句柄和规范归约这两个基本概念，但并没有解决规范归约的问题，因为没有给出寻找句柄的算法。事实上，规范归约的中心问题就是如何寻找句柄。寻找句柄的不同算法对应不同的规范归约方法，这一点将在LR分析器中讨论。第10页，课件共108页，创作于2023年2月算符优先分析法是一种简单直观、广为使用的自下而上分析法，特别适合于表达式分析且宜于手工实现。它实际上是依照表达式四则运算过程来进行语法分析。所谓算符优先分析，就是预先规定运算符(确切地说是终结符)之间的优先关系和结合性质，借助于这种优先关系来比较相邻运算符的优先级，以确定句型的可归约串并进行归约。注意：算符优先分析不是规范归约。3.4.2算符优先分析法第11页，课件共108页，创作于2023年2月

1.算符优先文法

算符文法:若一个文法的任一产生式的右部都不含两个相继的非终结符，即不含…QR…这样的右部，则称该文法为算符文法。

算符优先文法:

算符优先文法首先应是算符文法,

其次还要定义任意两个可能相继出现的终结符的优先关系。具体定义如下:第12页，课件共108页，创作于2023年2月假定G是一个不含ε产生式的算符文法,对任一对终结符a,b,定义(1)a=b当且仅当文法G中含有形如

P→…ab…

或P→…aQb…的产生式;(2)a<b当且仅当G中含有形如

P→…aR…的产生式，而R

b…或RQb…;(3)a>b当且仅当G中含有形如

P→…Rb…的产生式，而R…a

或R

aQ。+

+

+

+

第13页，课件共108页，创作于2023年2月若一个算符文法G中任一终结符对(a,b)

至多满足下述三种关系之一:a=b，a<b，a>b则称文法G是一个算符优先文法。例3.10

试说明下述文法G是算符文法，但不是算符优先文法。

E→E+E∣E*E∣(E)∣i解:由于文法G的任一产生式右部都不含两个相邻的非终结符，故文法G是算符文法。第14页，课件共108页，创作于2023年2月

(1)由于存在E→E+E，而E+E中第二个E可推出E*E，故有+<*(2)由于存在E→E*E，而E*E中第一个E可推出E+E，即有+>*

可见,运算符+和*之间同时存在两种不同的优先关系，故文法G不是算符优先文法。第15页，课件共108页，创作于2023年2月2.算符优先关系表的构造通过检查文法的每个产生式的各个侯选式,可找出所有满足a=b的终结符对。为找出所有满足关系“<”和“>”的终结符对,需先对文法的每个非终结符P构造两个集合FIRSTVT(P)和LASTVT(P):FIRSTVT(P)={a|P a…或PQa…,a∈VT而Q∈VN｝

LASTVT(P)={a|P …a或P…aQ,a∈VT而Q∈VN｝+

+

+

+

第16页，课件共108页，创作于2023年2月FIRSTVT集的构造方法：(1)若有产生式P→a…或P→Qa…，则a∈FIRSTVT(P)；(2)若有产生式P→Q…,且a∈FIRSTVT(Q),

则a∈FIRSTVT(P)。第17页，课件共108页，创作于2023年2月例如试构造文法G[E]的FIRSTVT集。

G[E]:E→E+T∣T T→T*F∣F F→(E)∣i解:①根据规则(1)知：由E→E+…得,FIRSTVT(E)={+}；由T→T*…得,FIRSTVT(T)={*}；由F→(…和F→i得,FIRSTVT(F)={(,i}②根据规则(2)知：由T→F和FIRSTVT(F)={(,i}得,FIRSTVT(T)={*,(,i}；由E→T和FIRSTVT(T)得,FIRSTVT(E)={+,*,(,i}第18页，课件共108页，创作于2023年2月LASTVT集构造方法：(1)若有产生式P→…a或P→…aQ，则a∈LASTVT(P)；(2)若有产生式P→…Q,且a∈LASTVT(Q),

则a∈LASTVT(P)。第19页，课件共108页，创作于2023年2月例如试构造文法G[E]的LASTVT集。

G[E]:E→E+T∣T T→T*F∣F F→(E)∣i解:①根据规则(1)知：由E→…+T得,LASTVT(E)={+}

由T→…*F得,LASTVT(T)={*}

由F→…)和F→i得,LASTVT(F)={),i}②根据规则(2)知：由T→F和LASTVT(F)得,LASTVT(T)={*,),i};

由E→T和LASTVT(T)得,LASTVT(E)={+,*,),i}。第20页，课件共108页，创作于2023年2月构造优先关系表的方法：(1)对形如P→…ab…或P→…aQb…的产生式,有a=b；(2)对形如P→…aR…的产生式,

若b∈FIRSTVT(R),则a<b；(3)对形如P→…Rb…的产生式,

若a∈LASTVT(R)，则a>b。(4)对于语句括号#,有

#=#

#

<FIRSTVT(S)中的元素

LASTVT(S)中的元素>#第21页，课件共108页，创作于2023年2月例3.11

构造文法G[E]的算符优先关系表。

G[E]:E→E+T∣T T→T*F∣F F→(E)∣i解:构造FIRSTVT集①根据规则(1)知：由E→E+…得,FIRSTVT(E)={+}；由T→T*…得,FIRSTVT(T)={*}；由F→(…和F→i得,FIRSTVT(F)={(,i}②根据规则(2)知：由T→F和FIRSTVT(F)={(,i}得,FIRSTVT(T)={*,(,i}；由E→T和FIRSTVT(T)得,FIRSTVT(E)={+,*,(,i}第22页，课件共108页，创作于2023年2月构造LASTVT集①根据规则(1)知：由E→…+T得,LASTVT(E)={+}；由T→…*F得,LASTVT(T)={*}；由F→…)和F→i得,LASTVT(F)={),i}。②根据规则(2)知：由T→F和LASTVT(F)得,LASTVT(T)={*,),i};

由E→T和LASTVT(T)得,LASTVT(E)={+,*,),i}。第23页，课件共108页，创作于2023年2月构造优先关系表①根据规则(1),由“(E)”知,(=)。②根据规则(2),

由E→…+T知,+<FIRSTVT(T),

即+<*,+<(,+<i

由T→…*F知,*<FIRSTVT(F),

即*<(,*<i

由F→(E…知,(<FIRSTVT(E),

即(<+,(<*,(<(,(<i第24页，课件共108页，创作于2023年2月③根据规则(3)知：由E→E+…知,LASTVT(E)>+，即+>+，*>+，)>+，i>+

由T→T*…知,LASTVT(T)>*，即*>*，)>*，i>*

由F→…E)知,LASTVT(E)>)，即+>)，*>)，)>)，i>)④由#E#知,#

=#；

#<FIRSTVT(E),即#<+,#<*,#<(,#<iLASTVT(E)>#,即+>#,*>#,)>#,i>#第25页，课件共108页，创作于2023年2月故算术表达式文法的优先关系表如下:

+*i()#+><<<>>*>><<>>i>>

>>(<<<<)>>

>>#<<<<

==第26页，课件共108页，创作于2023年2月3.算符优先分析算法的设计由于算符优先分析法仅在终结符之间定义了优先关系而未对非终结符定义优先关系，这就无法使用优先关系表去识别由单个非终结符组成的可归约串，因此算符优先分析法不是用句柄而是用最左素短语来刻画“可归约串”。所谓句型的素短语是指这样一种短语,它至少包含一个终结符且除自身外不再包含其它更小的素短语。最左素短语是处于句型最左边的那个素短语。第27页，课件共108页，创作于2023年2月如何让计算机寻找最左素短语？算符优先文法的句型的一般形式为

#N1a1N2a2…NnanNn+1#

其中,ai是终结符,Ni是可有可无的非终结符。算符优先文法任一句型的最左素短语是满足下述条件的最左子串:NjajNj+1aj+1

…Niai

Ni+1aj-1<aj=aj+1=…=ai

>ai+1第28页，课件共108页，创作于2023年2月查找最左素短语的方法：(1)最左子串法先找出句型中终结符由左至右满足aj-1<aj=aj+1=…=ai>ai+1的最左子串。再检查文法的每个候选式,看其是否满足:所有终结符由左至右的排列恰为ajaj+1…ai,即终结符对应相等而非终结符仅对应位置相同。若存在这样的候选式,则用该候选式进行归约。第29页，课件共108页，创作于2023年2月

(2)语法树法

先画出句型ω的语法树,再找语法树中所有相邻终结符间的优先关系。确定相邻终结符间优先关系的原则:①语法树中同层的优先关系为“=”;②不同层时,层次在下的优先级高,

层次在上的优先级低;③在句型ω两侧加上语句括号“#”,

则有#<ω和ω>#。

最后按最左素短语必须具备的条件确定最左素短语。第30页，课件共108页，创作于2023年2月例3.12

文法G[E]:E→E+T|TT→T*F|FF→(E)|i

试确定F+T*i的最左素短语。解:画句型F+T*i的语法树,

根据语法树确定相邻终结符间优先关系如图,

故最左素短语为i。注意:最左直接短语为FE＋EE*TFTiF#＜＋＜*＜i＞#第31页，课件共108页，创作于2023年2月算符优先分析算法:

k=1;S[k]=‘#’;//k代表栈S的使用深度

do{a=下一个输入符;

if(S[k]

VT)j=k;elsej=k−1;//j指栈顶终结符

while(S[j]>a){//找最左S[j]<…=…=S[k]>a

do{Q=S[j];//j从最左素短语末逐步移向首

if(S[j−1]∈VT)j=j−1;elsej=j−2;}while(S[j]=Q);

把S[j+1]…S[k]归约为某个N;

k=j+1;S[k]=N;//把N置于原S[j+1]位置

}if((S[j]<a)||(S[j]=a)){k=k+1;S[k]=a;}elseerror();//若栈顶S[j]<a或=a则将a压栈

}while(a!=‘#’);第32页，课件共108页，创作于2023年2月上述算法工作过程中,若出现j减1后其值小于等于0,则意味着输入串有错。正确情况下,算法工作完毕时符号栈将呈现#S#。例3.13

文法G[E]及其优先关系如例3.12

所示,试给出输入串i+i*i的算符优先分析过程。解:输入串i+i*i的算符优先分析过程如下:第33页，课件共108页，创作于2023年2月符号栈输入串动作#i+i*i##<i#i+i*i##<i>+,用F→i归约#F+i*i##<+#F+i*i##<+<i#F+i*i#…+<i>*,用F→i归约#F+F*i##<+<*#F+F*i##<+<*<i#F+F*i#…*<i>#,用F→i归约#F+F*F#…+<*>#,用T→T*F归约#F+T##<+>#,用E→E+T归约#E##E#结束第34页，课件共108页，创作于2023年2月算符优先分析的归约只关心句型中由左至右终结符序列的优先关系,不涉及非终结符。再以i+i为例,给出其算符优先分析过程和规范归约过程。算符优先分析比规范归约要快得多。这既是算符优先分析的优点,也是它的缺点,因为这可能把本来不成句子的输入串误认为是句子,这种缺点易于弥补。第35页，课件共108页，创作于2023年2月例3.14

试设计下述文法的算符优先分析表:G[S]:S→iBtS∣iBtAeS∣aA→iBtAeS∣aB→b解:首先构造FIRSTVT集和LASTVT集

FIRSTVT(S)={i,a};FIRSTVT(A)={i,a};FIRSTVT(B)={b};LASTVT(S)={t,e,a};LASTVT(A)={e,a};LASTVT(B)={b};

由A→…S知,LASTVT(S)

LASTVT(A)

即LASTVT(A)={t,e,a}第36页，课件共108页，创作于2023年2月然后构造优先关系表:(1)由产生式S→iBtAeS和S→iBtS可知:①由S→iB…得,i<FIRSTVT(B)；②由S→…Bt…得,LASTVT(B)>t；③由S→…tA…得,t<FIRSTVT(A)；④由S→…Ae…得,LASTVT(A)>e；⑤由S→…eS得,e<FIRSTVT(S)；⑥由S→…iBt…得,i=t；⑦由S→…tAe…得,t=e；⑧由S→…tS…得,t<FIRSTVT(S)。(2)由于存在t>e和t=e,由iBtAeS知,此时应将iBtAeS同时归约为S或A,即取t=e。第37页，课件共108页，创作于2023年2月最后得到优先关系表如下:

iteabi

<t<<e<><a

>b

>==第38页，课件共108页，创作于2023年2月4.优先函数用优先关系表表示终结符间的优先关系时,存储量大,查找费时。若给终结符赋一个值,值的大小反映其优先关系,则终结符间的优先关系比较就转为值的比较。一个终结符在栈中与在输入串中的优先值不同,例如,既存在+>),又存在)>+。因此,对一个终结符a而言,它应该有一个左优先数f(a)和一个右优先数g(a)。第39页，课件共108页，创作于2023年2月若根据一个文法的算符优先关系表,使得文法中每个终结符a和b满足下述条件:(1)若存在a=b，则有f(a)=g(b)；

(2)若存在a>b，则有f(a)＞g(b)；

(3)若存在a<b，则有f(a)＜g(b)。则称f和g为优先函数,其中,f称为入栈优先函数,g称为比较优先函数。第40页，课件共108页，创作于2023年2月表中若存在f和g,则有f(a)=g(a);f(a)＞g(b)f(b)=g(a);f(b)=g(b)这将导致如下矛盾:f(a)＞g(b)=f(b)=g(a)=f(a)注意:对应一个优先关系表的优先函数f和

g不唯一;若存在一对,则存在无穷多对;有些优先关系表不存在优先函数。例如,下述优先关系表不存在优先函数。

aba>b===第41页，课件共108页，创作于2023年2月根据优先关系表构造优先函数f和g的方法有两种:关系图法、直接构造法

(1)用关系图法构造优先函数的步骤①对每个终结符a(包括“#”),令其对应两个符号fa和ga,画一张以所有fa和ga为结点的方向图：若a>b或a=b,画一条从fa到gb的有向边;

若a<b或a=b,画一条从gb到fa的有向边;第42页，课件共108页，创作于2023年2月②对每个结点都赋予一个数,此数等于从该结点出发所能到达的结点(包括出发结点自身)的个数,赋给fa的数作为f(a),赋给gb的数作为g(b);③检查所构造的函数f和g,看它们同原来的关系表是否有矛盾。若没有矛盾,则f和g就是所要的优先函数;若有矛盾,则不存在优先函数。第43页，课件共108页，创作于2023年2月(2)直接构造法由定义直接构造优先函数的步骤:

对每个终结符a(包括“#”),令f(a)=g(a)=1①若a>b而f(a)≤g(b),则令f(a)=g(b)+1；②若a<b而f(a)≥g(b),则令g(b)=f(a)+1；③若a=b而f(a)≠g(b),则令

f(a)=g(b)=max{f(a),g(b)}④重复①～③步直到过程收敛。若重复过程中有一个值大于2n,

则表明该文法不存在优先函数。第44页，课件共108页，创作于2023年2月使用优先函数的好处：一是节省空间；二是便于进行比较运算。例3.15

试用关系图法和直接定义法求下述优先关系表的优先函数(不含“#”)。

+*i()#+><<<>>*>><<>>i>>

>>(<<<<)>>

>>#<<<<

==第45页，课件共108页，创作于2023年2月解:(1)用关系图法构造的优先关系图如下:f＋f*fif)g＋g*gig(g)f(第46页，课件共108页，创作于2023年2月

+*i()f46626g35772由上图求得优先函数如下:第47页，课件共108页，创作于2023年2月迭代函数函数+*i()0(初值)f11111g111111f24414g235512f35515g246613f35515g24661(2)由定义直接计算优先函数的过程如下:第48页，课件共108页，创作于2023年2月3.5LR分析法

LR分析法是一种自下而上进行规范归约的语法分析方法,L指自左向右扫描输入串,R指最右推导(规范归约)。

LR分析法比递归下降分析法、LL(1)分析法对文法的限制要少得多,大多数无二义性CFG语言都可用LR分析器识别,且速度快,并能准确、指出输入串的语法错误及出错位置。

LR分析法的主要缺点:手工构造工作量相当大,必须求助自动产生工具。第49页，课件共108页，创作于2023年2月3.5.1LR分析器的工作原理规范归约(最右推导逆过程)的关键是寻找句柄。LR分析法的基本思想:在规范归约过程中,一方面记住已移进和归约出的符号串,即记住“历史”;另一方面根据所用产生式推测未来可能遇到的输入符,即对未来进行“展望”。当一串貌似句柄的符号串呈现于分析栈栈顶时,希望能根据所记载的“历史”、“展望”及“现实”材料来确定栈顶符号是否构成句柄。第50页，课件共108页，创作于2023年2月

LR分析器的结构示意如下所示,它由分析栈、分析表和总控程序三部分组成:a1a2…ai…an#LR分析表总控程序输入串：栈顶#x1…xm输出s0s1…sm分析栈第51页，课件共108页，创作于2023年2月

LR分析器实质上是一个带先进后出栈的DFA。“历史”和“展望”材料被抽象成某些“状态”,而分析栈用来存放这些状态,栈里的每个状态概括了从分析开始直到某一归约阶段的全部“历史”和“展望”资料。任何时候,栈顶的状态都代表了整个“历史”和已推测出的“展望”。第52页，课件共108页，创作于2023年2月

LR分析器的每一步工作都由栈顶状态和现行输入符唯一决定。为了易于归约,把已归约出的文法符号也放在栈中。栈的每一项内容包括状态s和文法符号X两部分。(s0,#)为分析开始前预先放入栈里的初始状态和句子括号。栈顶状态为sm,符号串X1X2…Xm是已移进归约出的文法符号串。第53页，课件共108页，创作于2023年2月

LR分析表是LR分析器的核心,它包括两部分:动作表(ACTION表)(二维数组)

状态转换表(GOTO表)(二维数组)

ACTION[s,a]规定了状态s面临输入符a时应采取的动作。GOTO[s,X]规定了状态s面对文法符号X(终结符或非终结符)时的下一状态。显然,GOTO[s,X]定义了一个以文法符号为字母表的DFA。第54页，课件共108页，创作于2023年2月ACTION[s,a]的动作:(1)移进:使(s,a)的下一状态s'=GOTO[s,a]和输入符a进栈,下一输入符变现行输入符。注:对终结符a,下一状态s'的值GOTO[s,a]

实际上放在ACTION[s,a]中(2)归约:用某一产生式A→β进行归约。若β的长度为γ,则归约动作是去掉栈顶的γ个项,使状态sm-γ变成栈顶状态,然后使(sm-γ,A)的下一状态s'=GOTO[sm-γ,A]

和文法符号A进栈。归约不改变现行输入符。执行归约意味着栈顶符号串Xm-γ+1…Xm是句柄。第55页，课件共108页，创作于2023年2月(3)接受:宣布分析成功,分析器停止工作。(4)报错:报告发现源程序有错,调用出错处理程序。LR分析器总控程序的工作十分简单,它的任一步只需按分析栈栈顶状态s和现行输入符a执行ACTION[s,a]所规定的动作。LR分析器的工作过程可看成是栈中状态序列、已归约串和输入串构成的三元式的变化过程。第56页，课件共108页，创作于2023年2月例如,算术表达式文法G[E]如下:G[E]:(1)E→E+T(2)E→T(3)T→T*F(4)T→F(5)F→(E)(6)F→i文法G[E]的LR分析表见表3.13,试给出语句i+i*i的LR分析过程。第57页，课件共108页，创作于2023年2月表3.13算术表达式文法的LR分析表状态ACTIONGOTOi+*()#ETF0s5

s4

1231

s6

acc

2

r2s7

r2r2

3

r4r4

r4r4

4s5

s4

8235

r6r6

r6r6

6s5

s4

937s5

s4

108

s6

s11

9

r1s7

r1r1

10

r3r3

r3r3

11

r5r5

r5r5

第58页，课件共108页，创作于2023年2月步骤状态栈符号栈输入串动作说明10#i+i*i#ACTION[0,i]=s5,状态5入栈205#i+i*i#r6:F→i归约,GOTO(0,F)=3入栈303#F+i*i#r4:T→F归约,GOTO(0,T)=2入栈402#T+i*i#r2:E→T归约,GOTO(0,E)=1入栈501#E+i*i#ACTION[1,+]=s6,状态6入栈6016#E+i*i#ACTION[6,i]=s5,状态5入栈表3.14i+i*i的LR分析过程第59页，课件共108页，创作于2023年2月70165#E+i*i#r6:F→i归约,GOTO(6,F)=3入栈80163#E+F*i#r4:T→F归约,GOTO(6,T)=9入栈90169#E+T*i#ACTION[9,*]=s7,状态7入栈1001697#E+T*i#ACTION[7,i]=s5,状态5入栈11016975#E+T*i#r6:F→i归约,GOTO(7,F)=10入栈120169710#E+T*F#r3:T→T*F归,GOTO(6,T)=9入栈130169#E+T#r1:E→E+T,GOTO(0,E)=1入栈1401#E#Acc:分析成功第60页，课件共108页，创作于2023年2月如何由文法构造LR分析表?

LR文法:对于一个文法,如果能够构造一张LR分析表使得它的每个入口均是唯一确定的,则称该文法为LR文法。对于LR文法,当分析器对输入串进行自左至右扫描时,一旦句柄呈现于栈顶,能及时对它实行归约。有些情况下LR分析器需“展望”和实际检查未来的k个输入符才能决定应采取什么样的“移进-归约”决策。第61页，课件共108页，创作于2023年2月

LR(k)文法:一个文法如果能用一个每步最多向前检查k个输入符的LR分析器进行分析,则称该文法为LR(k)文法。若一个文法的任何“移进-归约”分析器都存在下述情况:尽管栈的内容和下一输入符都已了解,但仍无法确定是“移进”还是“归约”,或无法从几种可能的归约中确定其一,则该文法为非LR(1)文法。注意:(1)LR文法肯定是无二义的,一个二义文法不会是LR文法。(2)LR分析技术可适当修改以适于一定的二义文法。第62页，课件共108页，创作于2023年2月四种LR分析表的构造方法:(1)LR(0)表的构造方法:该法局限性很大,

但它是建立一般LR分析表的基础。

(2)SLR(1)表(简单LR表)的构造方法:

该法较易实现又极有使用价值。

(3)LR(1)表(规范LR表)的构造方法:

该法适用于大多数CFG文法,但分析表体积庞大。

(4)LALR表(向前LR表)的构造方法:

该法介于SLR(1)和LR(1)之间。第63页，课件共108页，创作于2023年2月3.5.2LR(0)分析表的构造希望仅由一种只概括“历史”资料而不包含推测性“展望”材料的简单状态就能识别呈现在栈顶的某些句柄，LR(0)项目集就是这样一种简单状态。讨论LR分析法时,需要定义一个重要概念,这就是文法规范句型的活前缀。字的前缀是指该字的任意首部,例如,字abc的前缀有ε、a、ab或abc。所谓活前缀是指规范句型的一个前缀,这种前缀不含句柄之后的任何符号。第64页，课件共108页，创作于2023年2月在LR分析过程中的任何时候，栈里的文法符号X1X2…Xm应构成活前缀。把输入串的剩余部分匹配于其后应成为规范句型(如果整个输入串确为一个句子的话)。因此，只要输入串的已扫描部分保持可归约成一个活前缀，就意味着所扫描的部分没有错误。第65页，课件共108页，创作于2023年2月对于文法G[S],首先要构造一个NFA,它能识别G[S]的所有活前缀,这个NFA的每个状态称为一个项目。

项目:文法G[S]中每一产生式的右部添加一个圆点,称为文法G[S]的一个LR(0)项目,简称项目。例如,产生式A→XYZ对应四个项目：

A→·XYZA→X·YZA→XY·ZA→XYZ·注意,产生式A→ε只对应一个项目A→·第66页，课件共108页，创作于2023年2月一个项目指明了在分析过程的某个时刻看到产生式的多大一部分。通过使用文法的项目可构造一个NFA来识别文法的所有活前缀，再用子集法把识别活前缀的NFA确定化，使之成为一个以项目集合为状态的DFA，这个DFA就是建立LR分析算法的基础。第67页，课件共108页，创作于2023年2月识别一个文法活前缀的DFA的项目集的全体称为这个文法的LR(0)项目集规范族。这个规范族提供了建立一类LR(0)和SLR(1)分析器的基础。圆点在最右端的项目,如A→α·,称为一个归约项目;对文法的开始符号S‘的归约项目,如S’→α·,称为接受项目;形如A→α·aβ的项目(a为终结符),称为移进项目;形如A→α·Bβ的项目(B为非终结符)，称为待约项目。第68页，课件共108页，创作于2023年2月1.LR(0)项目集规范族的构造可用ε_CLOSURE构造一个文法的LR(0)项目集规范族。首先构造文法G[S]的拓广文法G'[S']，它包含整个G[S]并引进一个不出现在G[S]中的非终结符S'，同时加进了一个新产生式S'→S。这样，仅含项目S'→S·的状态是唯一的接受状态。第69页，课件共108页，创作于2023年2月假定I是文法G‘[S’]的任一项目集,

定义和构造CLOSURE(I)的方法:(1)I的任何项目都属于CLOSURE(I)；

(2)若A→α·Bβ属于CLOSURE(I)，则对任何关于B的产生式B→γ,

其项目B→·γ属于CLOSURE(I)。

(3)重复(1)～(2)直至CLOSURE(I)不再增大为止。第70页，课件共108页，创作于2023年2月假定I是文法G‘[S’]的任一项目集,X是一个文法符号(终结符或非终结符),则状态转换函数GO(I,X)的定义为

GO(I,X)=CLOSURE(J)

其中J={任何形如A→αX·β的项目|A→α·Xβ属于I}。若I是对某个活前缀γ有效的项目集(状态),则GO(I,X)是对γX有效的项目集(状态)。第71页，课件共108页，创作于2023年2月通过CLOSURE(I)和GO(I,X)构造拓广文法G'[S']的LR(0)项目集规范族的方法:(1)求出I的闭包CLOSURE(I)(2)先用GO(I,X)求出J,再对J求其闭包CLOSURE(J)。以此类推,最终可构造出拓广文法G'[S']的LR(0)项目集规范族。第72页，课件共108页，创作于2023年2月2.LR(0)分析表的构造若文法G[S]的拓广文法G‘[S’]的活前缀识别自动机中的每个状态(项目集)不存在下述情况：既含移进项目又含归约项目或含有多个归约项目,则G[S]是一个LR(0)文法。换言之,LR(0)文法的项目集规范族中任一项目集均不包含冲突项。对于LR(0)文法,可直接从它的项目集规范族C和状态转换函数GO(I,X)构造出其LR(0)分析表。第73页，课件共108页，创作于2023年2月假定C={I0,I1,…,In},令每个项目集Ik的下标k作为分析器的状态,并令包含项目S‘→·S的集合Ik的下标k为分析器的初态,则LR(0)分析表的构造算法如下:(1)若项目A→α·aβ属于Ik且

GO(Ik,a)=Ij,a为终结符,

则置ACTION[k,a]为“将(j,a)移进栈”,简记为sj。第74页，课件共108页，创作于2023年2月

(2)若项目A→α·属于Ik,

则对任何终结符a或#,置

ACTION[k,a]为“用A→α归约”,

简记为rj(其中j是第j个产生式。

(3)若项目S‘→S·属于Ik,

则置ACTION[k,#]为接受,简记acc。

(4)若GO(Ik,A)=Ij,A为非终结符,则置

GOTO[k,A]=j。

(5)分析表中凡不能用规则(1)～(4)填入的空白格均置为“出错标志”。第75页，课件共108页，创作于2023年2月例3.16

试构造文法G[S]的LR(0)分析表:G[S]:S→BBB→aB∣b

解:将文法G[S]拓广为文法G'[S']：

G'[S']:(0)S'→S(1)S→BB(2)B→aB(3)B→b第76页，课件共108页，创作于2023年2月该文法的LR(0)项目集规范族为:I0:S‘→·S S→·BBB→·aBB→·bI1:S’→S·I2:S→B·BB→·aBB→·bI3:B→a·BB→·aBB→·b I4:B→b·I5:S→BB· I6:B→aB·第77页，课件共108页，创作于2023年2月S

I0:S→·SS→·BB

B→·aB

B→·b

I1:S→S·S

I2:S→B·BB→·aBB→·b

I5:S→BB·B

I4:B→b·bb

I3:B→a·BB→·aBB→·bab

I6:B→aB·Baa识别该文法活前缀的DFA为:第78页，课件共108页，创作于2023年2月该文法的LR(0)分析表为:状态ACTIONGOTOab#SB0s3s4

121

acc

2s3s4

53s3s4

64r3r3r3

5r1r1r1

6r2r2r2

第79页，课件共108页，创作于2023年2月3.5.3SLR(1)分析表的构造

LR(0)文法是一类非常简单的文法,其特点是该文法的活前缀识别自动机的每一状态都不含冲突项。但即使是算术表达式文法也不是LR(0)的,因此需要研究一种简单“展望”材料的LR分析法,即SLR(1)法。实际上,许多冲突性的动作都可以通过考察有关非终结符的FOLLOW集而获得解决。第80页，课件共108页，创作于2023年2月SLR(1)冲突解决办法如下：假定LR(0)规范族的任一项目集I中含有m个移进项目:A1→α·a1β1,A2→α·a2β2,…,Am→α·amβm

同时含有n个归约项目:B1→α·,B2→α·,…,Bn→α·

若集合{a1,…,am},FOLLOW(B1),…,FOLLOW(Bn)两两不相交,

则隐含在I中的动作冲突可通过检查现行输入符a属于上述n+1个集合中的哪个集合而获得解决,即:第81页，课件共108页，创作于2023年2月

(1)若a是某个ai,i=1,2,…,m,则移进;(2)若a∈FOLLOW(Bi),i=1,2,…,n,

则用产生式Bi→α进行归约;(3)对(1)(2)以外的情况,报错。冲突性动作的这种解决办法叫做

SLR(1)冲突解决办法。第82页，课件共108页，创作于2023年2月文法G[S]的SLR(1)分析表的构造方法:

先把G[S]拓广为G‘[S’]，对G‘[S’]构造LR(0)项目集规范族C和活前缀识别自动机的状态转换函数GO，然后再使用C和GO按下面的算法构造G‘[S’]的SLR(1)分析表:

假定C={I0,I1,…,In},令每个项目集Ik的下标k为分析器的一个状态,并令含项目S‘→·S的Ik的下标k为初态,则SLR(1)分析表可按如下方法构造:第83页，课件共108页，创作于2023年2月(1)若项目A→α·aβ属于Ik且GO(Ik,a)=Ij,a为终结符,则置ACTION[k,a]为“将状态j和符号a移进栈”,即sj。(2)若项目A→α·属于Ik,

则对任何输入符a,a∈FOLLOW(A),

置ACTION[k,a]为“用产生式A→α进行归约”,即rj。(3)若项目S‘→S·属于Ik,

则置ACTION[k,#]为接受,即acc。(4)若GO(Ik,A)=Ij,A为非终结符,

则置GOTO[k,A]=j。第84页，课件共108页，创作于2023年2月

(5)凡不能用规则(1)～(4)填入信息的空白格均置“出错标志”。若按上法构造的ACTION表和GOTO表不含多重入口,则称它为文法G[S]的SLR(1)表。具有SLR(1)表的文法称为一个SLR(1)文法。使用SLR(1)表的分析器叫做SLR(1)分析器。若按上述算法构造的分析表存在多重入口,则不能用上述算法构造分析器。第85页，课件共108页，创作于2023年2月例3.18

构造例3.16文法SLR(1)分析表。解:先拓广文法,再求文法的LR(0)项目集规范族及DFA,求所有形如A→α·的项目的FOLLOW(A),即对S→BB·,B→aB·,B→b·求FOLLOW集:

由FOLLOW集的构造方法得：①FOLLOW(S')={#}；②FIRST(B)

FOLLOW(B),即

FOLLOW(B)={a,b}；③由S‘→S,FOLLOW(S')

FOLLOW(S),

即FOLLOW(S)={#}；由S→BB,FOLLOW(S)

FOLLOW(B),

即FOLLOW(B)={a,b,#}。第86页，课件共108页，创作于2023年2月最后求G‘[S’]的SLR(1)分析表如下:状态ACTIONGOTOab#SB0s3s4

121

acc

2s3s4

53s3s4

64r3r3r3

5

r1

6r2r2r2

第87页，课件共108页，创作于2023年2月*3.5.4LR(1)分析表的构造在SLR(1)方法中，若项目集Ik含有A→α·，那么在状态k时，只要当前输入符a∈FOLLOW(A)，就采取“用A→α归约”的动作。但在某种情况下，当状态k呈现于栈顶时，栈里的符号串所构成的活前缀βα未必允许把α归约为A，因为可能没有一个规范句型含有前缀βAa。因此，在这种情况下，用A→α进行归约未必有效。第88页，课件共108页，创作于2023年2月可设想让每个状态含有更多的展望信息,这些信息将有助于克服动作冲突和排除无效归约,必要时对状态进行分裂,使得LR分析器的每个状态能确切指出当α后跟哪些终结符时才允许把α归约为A。为此,需重新定义项目,使得每个项目都附带有k个终结符。现在每个项目的一般形式为[A→α·β,a1a2…ak]

此处,A→α·β是一个LR(0)项目,ai是终结符,这种项目称为LR(k)项目,其中,a1a2…ak称为向前搜索串(或展望串)。第89页，课件共108页，创作于2023年2月向前搜索串仅对归约项目[A→α·,a1a2…ak]有意义,对移进或待约项目不起作用。归约项目[A→α·,a1a2…ak]意味着当它所属状态呈现在栈顶且后续的k个输入符为a1a2…ak时,才把栈顶的α归约为A。这里只对k≤1的情形感兴趣。构造有效的LR(1)项目集族的方法和构造LR(0)项目集规范族的方法本质上一样,也需两个函数:CLOSURE(I)和GO(I,X)。第90页，课件共108页，创作于2023年2月项目集I的闭包可按如下方式构造：

(1)I的任何项目都属于CLOSURE(I)。

(2)若项目[A→α·Bβ,a]属于CLOSURE(I),B→γ是一产生式,则对于FIRST(βa)中的每个终结符b,若[B→·γ,b]原来不在CLOSURE(I)中,把它加进去。

(3)重复(2)直到CLOSURE(I)不再增大。函数GO(I,X)定义为:GO(I,X)=CLOSURE(J)

其中J={形如[A→αX·β,a]的项目|[A→α·Xβ,a]属于I}第91页，课件共108页，创作于2023年2月构造LR(1)分析表的算法:

假定C={I0,I1,…,In},令每个Ik的下标k为分析表的状态,令含有[S‘→·S,#]的Ik的k为分析器的初态。LR(1)分析表可按如下方法构造：

(1)若项目[A→α·aβ,b]属于Ik且GO(Ik,a)=Ij,a为终结符,则置ACTION[k,a]为“将状态j和符号a移进栈”,简记为sj；第92页，课件共108页，创作于2023年2月

(2)若项目[A→α·,a]属于Ik,则置ACTION[k,a]为“用产生式A→α归约”,简记为rj,其中j是产生式的编号;(3)若项目[S‘→S·,#]属于Ik,则置ACTION[k,#]为接受,简记为acc;(4)若GO(Ik,A)=Ij,A为非终结符,则置GOTO(Ik,A)=j;(5)分析表中凡不能用规则(1)～(4)填入信息的空白栏均填“出错标志”。第93页，课件共108页，创作于2023年2月对于LR(1),有些状态(项目集)除向前搜索符不同外,其核心部分都相同,即LR(1)比SLR(1)和LR(0)存在更多的状态。因此,LR(1)的构造比LR(0)和SLR(1)更复杂,占用的存储空间也更多。第94页，课件共108页，创作于2023年2月3.5.5LALR分析表的构造{自学}

对LR(1)来说,存在着某些状态(项目集),这些状态除向前搜索符不同外,其核心部分都相同,能否将核心部分相同的诸状态合并为一个状态,这种合并是否会产生冲突?下面将对此进行讨论。

两个LR(1)项目集具有相同的心是指除去搜索符之后这两个集合是相同的。如果把所有同心的LR(1)项目集合并为一,将看到这个心就是一个LR(0)项目集,这种LR分析法称为LALR方法。第95页，课件共108页，创作于2023年2月对于同一个文法,LALR分析表和LR(0)以及SLR分析表永远具有相同数目的状态。LALR方法本质上是一种折中方法，LALR分析表比LR(1)分析表要小得多，能力也差一点，但它却能对付一些SLR(1)所不能对付的情况。第96页，课件共108页，创作于2023年2月由于GO(I,X)的心仅仅依赖于I的心，因此LR(1)项目集合并之后的转换函数GO可通过GO(I,X)自身的合并而得到，因而在合并项目集时无需考虑修改转换函数问题(假定I1与I2的心相同，即项目集相同，则GO(I1,X)=GO(I2,X)，但这里的项目集是不包括搜索符的)。但是，动作ACTION必须进行修改，使之能够反映被合并的集合的既定动作。第97页，课件共108页，创作于2023年2月假定有一个LR(1)文法,它的LR(1)项目集不存在动作冲突,但如果把同心集合并为一,就可能导致产生冲突。这种冲突不会是移进/归约的冲突,因为若存在这种冲突,则意味着面对当前的输入符号a,有一个项目[A→α·,a]要求采取归约动作,而同时有另一项目[B→β·aγ,b]要求把a移进;这两个项目同处于(合并前的)某一个集合中,则意味着合并前必有某个c使得[A→α·,a]和[B→β·aγ,c]同处于(合并前的)某一集合,这意味着原来的LR(1)项目集已存在移进/归约冲突。第98页，课件共108页，创