第3章 语法分析

第3章语法分析本章要点上下文无关文法自上而下语法分析自下而上语法分析语法分析器的自动生成

语法分析器的功能语法分析器的功能：分析、判断记号序列是否符合语法规则。词法分析器记号取下一个记号源程序分析树前端的其余部分语法分析器中间表示符号表3.1上下文无关文法3.1.1上下文无关文法的定义正规式能定义一些简单的语言，能表示给定结构的固定次数的重复或者没有指定次数的重复 例：a(ba)5,a(ba)*正规式不能用于描述配对或嵌套的结构 例1：配对括号串的集合 例2：{wcw|w是a和b的串}

可以用形式语言中的文法来描述产生式产生式(规则)是定义语法单位的一种书写规则。它的形式为：α→β（或α::=β）

其中：“→”读作“定义为”

α，β为符号串箭头左边称为产生式左部箭头右边称为产生式右部

例：S→0S1，0S→01上下文无关文法上下文无关文法G是一个四元组（VT,VN,S,P）

VT：终结符集合-通常表示语言集中不能再分割的单词记号

VN：非终结符-表示程序语言中的语法单位，且

VN∩VT=φ

S：开始符号，至少在某个产生式左部出现一次

P：产生式集合（有限），每个产生式的形式为：

P→α，P∈VN，α∈（VN∪VT）*例：算术表达式文法({id,+,,,(,)},{expr,op},expr,P)

VT：{id,+,,,(,)}VN：{expr,op}S：exprP：{expr

expr

op

exprop+expr(expr)op

expr

exprexpr

id}

说明：为书写方便，常把若干左部相同的产生式合并为一个，并用元语言符号“|”隔开。上例简化表示expr

expr

op

expr |

(expr)|

expr|idop+|习惯上，常用大写字母表示非终结符，小写字母表示终结符。上例简化表示E

EAE|(E)|E|idA+|例：文法G(S)

G(S)=（VT，VN，S，P）其中:

VT={a,b}VN={S,A}

P={S→bA,A→aA|a}

是上下文无关文法文法G(E):

E

EAE|0E0|a

A

b|c

也是上下文无关文法

G(S)=（VT,

VN,

S,

P)

VT:{id,

+,*,

(

,

),

}VN:{S,E,A}P:{S→id=E

EEAE|(E)|E|idA+|}

例：赋值语句的上下文无关文法描述3.1.2推导把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替,这个过程在语法分析中有重要意义。例:E

E+E|E

E|(E)|

E|idE

E

(E)

(E+E)

(id+E)(id+id)显然，(id+id)是合法的表达式概念直接推出

如果A→γ是一个产生式，而α，β∈（VT∪VN）*，则将产生式A→γ用于符号串αAβ得到符号串αγβ，记为αAβ=>αγβ，称αAβ直接推出αγβ。

如：E=>(E),(E+E)=>(i+E)推导设α1,α2,…,αn(n>0)∈(VT∪VN)*，且有α1=>α2=>…=>αn

则称这个序列是从α1到αn的一个推导。若存在一个α1到αn的一个推导，则称α1可推导出αn，记为：α1=>+αn

(经一步或若干步推导）或α1=>*αn

（经0步或若干步推导）句型假定G是一个文法，S是它的开始符号，如果S=>α，则称α是文法G的一个句型。如：(E+E),(i+E),(i+i),E都是G（E）的句型。句子仅由终结符组成的句型称为句子。

如：(i×i+i),(i+i)都是G（E）的句子。语言文法G所产生句子的全体,即:L(G)={α|S=>+α，α∈VT*}概念最左(右)推导若某推导中任何一步直接推出α=>β都是对α中的最左（最右）非终结符进行替换，则称其为最左（最右）推导。例:E

E+E|E

E|(E)|

E|id最左推导 E lm

Elm

(E)lm

(E

+E)

lm

(id+E)lm(id+id)最右推导（规范推导） E rm

Erm

(E)rm

(E+E)

rm

(E+id)rm(id+id)E=>(E)=>(E+E)=>(E×E+E)=>(E×E+i)。既非最右也非最左推导。3.1.3分析树文法句型（句子）推导的树形表示即语法分析树，简称分析树。分析树的构造

语法分析树是一棵根在上，叶子在下的倒立的树，（1）根结点由开始符号标记，随着推导的展开，向下画一分支；（2）某个非终结符被它的某个候选式所替换时，产生下一代新结点，候选式中自左到右的每个符号作为新结点的标记；（3）每个新结点和其父结点间有一条连线。3.1.3分析树例：E

E+E|E

E|(E)|

E|id

(id+id)的分析树EE()EEE+idid在一棵语法树生长过程中的任何时刻，所有那些没有后代的端末结点自左到右排列起来就是一个句型。3.1.4二义性

例：E

E+E|E

E|(E)|

E|id

句子idid+id的最左推导如下

E

E

E

E

E+E idE

E

E+E

id

E+E id

E+E

idid+E idid+E idid+id idid+idEEE*+EEidididEEidE*+EEidid如果一个文法存在某个句子对应两棵不同的语法树,则称这个文法是二义的。文法二义不代表语言一定是二义的。当产生一个语言的所有文法都是二义时,这个语言才称为二义的。有些语法分析器希望处理的文法是无二义的，则要构造无二义文法；出于某些需要，也可以构造允许二义文法的分析器，不过文法要附带消除二义性的规则。如对文法G(E)，规定“*”的优先级高于“+”，并服从左结合，文法改写为 E→T|E+T

T→F|T*F

F→(E)|id是无二义性的。文法的二义性3.2语言和文法文法的优点

文法给出了精确的，易于理解的语法说明自动产生高效的分析器可以给语言定义出层次结构以文法为基础的语言的实现便于语言的修改文法的问题文法能描述编程语言的大部分语法，但不是所有。3.2.1

正规式和上下文无关文法的比较正规式可以描述的语言都能用上下文无关文法描述，通过NFA可以变换出相应文法。正规式(a|b)*ab文法A0

a

A0|bA0|a

A1A1

b

A2A2

12开始a0abb3.2.2分离词法分析器理由为什么要用正规式定义词法

词法规则非常简单，不必用上下文无关文法对于词法记号，正规式描述简洁且易于理解从正规式构造出的词法分析器效率高从软件工程角度看，词法分析和语法分析的分离有如下好处简化词法分析器设计，改进编译器的效率编译器的可移植性加强便于编译器前端的模块划分3.2.3验证文法产生的语言例：G:S

(S)S|L(G)：配对的括号串的集合按推导步数进行归纳：推出的是配对括号串归纳基础：S

归纳假设：少于n步的推导都产生配对的括号串归纳步骤：n步的最左推导如下：

S(S)S*(x)S*(x)y3.2.3验证文法产生的语言例：G:S

(S)S|L(G)：配对的括号串的集合按串长进行归纳：配对括号串可由S推出归纳基础：S

归纳假设：长度小于2n的都可以从S推导出来归纳步骤：考虑长度为2n(n

1)的w=(x)y

S(S)S*(x)S*(x)y3.2.4适当的表达式文法

用一种层次观点看待表达式

idid(id+id)+idid+id

id

id

(id+id)

文法 expr

expr+term|term term

term

factor|factor

factor

id|(expr)expr

expr+term|termterm

term

factor|factor

factor

id|(expr)expridtermfactorididterm*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+idid分析树

ididid分析树

3.2.4适当的表达式文法

3.2.5消除二义性stmt

ifexprthenstmt |ifexprthenstmtelsestmt |other句型：ifexprthenifexprthenstmt

elsestmt两个最左推导：

stmtifexprthenstmt

ifexprthenifexprthenstmtelsestmt

stmtifexprthenstmtelsestmt

ifexprthenifexprthenstmt

elsestmt

无二义的文法stmt

matched_stmt

|unmatched_stmtmatched_stmt

ifexprthenmatched_stmt

elsematched_stmt

|otherunmatched_stmt

ifexprthenstmt |ifexprthenmatched_stmt

elseunmatched_stmt3.2.5消除二义性3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||13.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||1短语文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短语文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外短语文法、上下文有关文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短语文法、上下文有关文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*短语文法、上下文有关文法、上下文无关文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短语文法、上下文有关文法、上下文无关文法3.2.6形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短语文法、上下文有关文法、上下文无关文法、正规文法上下文有关文法举例例 L3＝{anbncn|n1}的上下文有关文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推导过程如下：S*an-1S(BC)n1 用S

aSBCn-1次S+an(BC)n 用S

aBC1次S+anBnCn 用CB

BC交换相邻的CBS+anbBn1Cn 用aB

ab1次S+anbnCn 用bB

bbn-1次S+anbncCn-1 用bC

bc1次S+anbncn 用cC

cc

n-1次3.3自上而下分析3.3.1自上而下分析的一般方法对任何的输入串(单词记号流),试图用一切可能的办法,从文法的开始符号出发,为输入串寻找一个最左推导,也就是自上而下地为输入串建立一棵语法树。这是一种带回溯的试探过程。

判定输入串x*y是否为它的句子?

SxAySxAyS**用S→xAy

推导过程：S=>xAy用A→*用A→**=>x**yxAy*(成功)(回溯)(回溯)=>x*y(成功)例:文法G：S→

xAy

A→**│*

一个文法,如果存在非终结符：P=>+

Pα，称它是含有左递归的。文法的左递归使分析过程陷入无限循环。回溯使分析走大段错路。存在虚假匹配现象。报告分析不成功时，难于知道输入串中出错的确切位置。效率低，代价高，有理论意义，实践价值不大。自上而下分析面临的问题3.3.2LL(1)文法对于LL(1)文法，可以进行不带回溯的自上而下的LL(1)分析。LL(1)是指从左(Left)到右扫描输入串；构造句子的最左(Leftmost)推导；分析时每步向前看一个字符。消除左递归消除回溯FIRST集合,FOLLOW集合LL(1)文法LL(1)分析方法1.消除左递归例：

E→E+T│TT→T*F│F F→(E)│i

P→Pα│β(α≠ε，β不以P开头)P→βP'

P'→αP’│εE→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i(1)消除直接左递归一般地:若P→Pα1│Pα2│…│Pαm│β1│β2│…│βn其中：αi≠ε，βi不以P开头改写为:P→β1P’│β2P’│...│βnP’P’→α1P’│α2P’│…│αmP’│ε(2)消除间接左递归例:设文法G(S)为：

S→Qc│c Q→Rb│b R→Sa│a

该文法不含直接左递归，但含间接左递归。如：S=>Qc=>Rbc=>Sabc等等解:

1）排序:R、Q、S

2）代入:Q→Sab│ab│b

S→Sabc│abc│bc│c

消除直接左递归:

S→abcS’│bcS’│cS’

S’→abcS’│ε

Q→Sab│ab│b

R→Sa│a

3）化简:S→abcS’│bcS’│cS’

S’→abcS’│εG(S):

S→Qc│c

Q→Rb│b

R→Sa│a例:为文法消除间接左递归算法

1）排序:P1、P2、…、Pn2）FORi:=1TOnDOBEGINFORj:=1TOi-1DO

把形如Pi→Pjγ的规则改写为：

Pi→δ1γ│δ2γ│…│δkγ

其中：Pj→δ1│δ2│…│δk

消除关于Pi规则的直接左递归

END3）化简:删除永不使用的产生式

解2:

1）排序：S、Q、R

2）代入得：S→Qc│c Q→Rb│b R→Rbca│bca|ca|a

消除直接左递归：

S→Qc│c Q→Rb│b R→bcaR‘│caR’|aR‘

R’→bcaR‘│εG(S):

S→Qc│c

Q→Rb│b

R→Sa│a例:为文法消除间接左递归在分析过程中，对任非终结符A,用它匹配输入串时要求能够根据当前输入，准确地指派一个候选式,若匹配成功,则不虚假,若匹配不成功,则其它的候选式也不会成功。即当A执行匹配时,A→α1│α2│…│αn

若A面临的第一个输入符号为a,则应该准确地指派某一个αi,其成败完全代表A,无需进行试探和回溯。2.消除回溯定义：符号串α的终结首符集FIRST(α)

FIRST(α)={a│α=>*a…,a∈VT}特别地，若α=>*ε，则规定ε∈FIRST(α）对文法的任一非终结符号A，A→α1│α2│…│αn，

若要准确地指派候选式，则应满足FIRST(αi)∩FIRST(αj)=Φ，i≠j通过提取公共左因子，将文法改造成任何非终结符的所有候选首符集两两不相交。

设A→δβ1│δβ2│…│δβn│

γ1│γ2│…│γm

（其中γ1、

γ2、

…、

γm不以δ开头） 改写:

A→δB│γ1│γ2│…│γm

B→β1│β2│…│βn例1：文法G：S→aSb|aS|ε解：提取：S→aS(b|ε）

S→ε引入新符：S→aSA|ε A→b|ε 提取左因子例2：对文法G2：A→ad提左公因子

A→Bc B→aA B→bB

解：先替换为：

A→ad A→aAc A→bBc B→aA B→bB再提取A→a（Ac|d)A→bBcB→aAB→bB引入新符A→aA‘A→bBcA’→Ac|dB→aAB→bB一般地，经过反复提取左因子可把每一个非终结符的所有候选首符集变成两两不相交。结论当文法满足：（1）消除了左递归（2）FIRST(αi)∩FIRST(αj)=Φ，i≠j）对某个输入符号a，及待匹配的非终结符A，若a∈FIRST（αi），则对A选用αi候选式工作。这种选择是唯一、确定和无虚假匹配的。3.

LL(1)文法当文法满足以上两个条件，但对任意αi，a都不属于FIRST（αi）时，该如何选择A的候选式，或者就认为a的出现是一种语法错误？例：G(S): S→aA|d 输入符号串abd是否为句子？

A→bAS|εS=>aA=>abAS=>abS=>abd这是因为A有产生式A→ε,而从开始符号S可以得出S=>*…Ad…

定义A的后继终结符号集FOLLOW(A)设S是文法G的开始符号，对G的任何非终结符A，定义A的后继终结符号集为：

FOLLOW(A)＝{a│S=>*…Aa…,a∈VT}当特别地,若S=>*…A，则规定$∈FOLLOW(A)非终结符A面临输入符号a，如果a∈/FIRST(αi)(对任意i)，ε∈FIRST(A)，那么，当a∈FOLLOW(A)时，就选用产生式A→ε工作。此时满足：FIRST(A)∩FOLLOW(A)

=Φ要正确进行不带回溯的语法分析，文法应满足以下条件：（1）文法不含左递归；（2）对文法中每个非终结符A的各个产生式的候选首符集两两不相交，即A→α1│α2│…│αn

，FIRST(αi)∩FIRST(αj)=Φ，（i≠j）；（3）对文法中的每个非终结符A，若它存在某个候选首符集中包含ε，则FIRST(A)∩FOLLOW（A）=Φ称满足以上条件的文法为LL（1）文法。LL(1)文法对一个LL(1)文法，可以对某个输入串进行有效的无回溯的自上而下分析。设面临的输入符号为a，要用非终结符A进行匹配，且A→α1│α2│…│αn

，则可如下分析(1)若a∈FIRST（αi)，则指派αi执行匹配任务；(2)否则

1)若ε∈FIRST(A)，且a∈FOLLOW(A),则让A与ε自动匹配；

2)否则，a的出现是一种语法错误。LL(1)分析方法4.FIRST集合和FOLLOW集合的构造

FIRST(α)={a│α=>*a…,a∈VT}FOLLOW（A）＝{a│S=>*…Aa…,a∈VT}以下讨论：对于每个文法符号X∈VT∪VN，构造FIRST(X)对于符号串α=X1X2…Xn，构造FIRST(α)对于文法的每个非终结符，构造FOLLOW(A)FIRST(X)构造对于文法G的每个文法符号X∈VT∪VN，构造FIRST(X)的方法

1）若X∈VT，则FIRST（X）={X}；

2）若X∈VN，且有产生式X→a…,a∈VT，则把a加入到FIRST（X）中，若有X→ε，则把ε加入FIRST（X）；

3）若X∈VN,且X→Y…,Y∈VN,则FIRST(Y)-{ε}加到 FIRST(X)中，若X→Y1Y2…Yk

,Y1,Y2,…,Yi

-1∈VN,ε∈FIRST(Yj) (1<=j<=i-1)则FIRST(Yi)-{ε}加到FIRST(X)中。特别地，若ε∈FIRST(Yj)(1<=j<=k)，则ε加入FIRST(X)例

G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i求每个非终结符号的FIRST集合解：

FIRST(E)=FIRST(T)=FIRST(F) ={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}对于符号串α=X1X2…Xn，构造FIRST(α)1）置FIRST(α)=FIRST(X1)-{ε};2）若对1<=j<=i-1,ε∈FIRST(Xj),

则把FIRST(Xi)-{ε}加到FIRST(α)中；

3）若对1<=j<=n,ε∈FIRST(Xj),则把ε加到 FIRST(α)中。FIRST(α)构造例G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i求每个产生式右部符号串的FIRST集合

解

FIRST(TE’)={(,i}FIRST(+TE’)={+}FIRST(FT’)={(,i}FIRST(*FT’)={*}FIRST((E))={(} FIRST（i)={i}

对于文法G的每个非终结符，构造FOLLOW(A)的方法是:1）若A为文法开始符号，置$于FOLLOW(A）中;2）若有产生式B→αAβ,

则将FIRST(β)-{ε}加到FOLLOW(A)中;3）若有B→αA或B→αAβ,且β=>*ε

则将FOLLOW(B)加到FOLLOW(A)中；

4）反复使用以上规则,直至FOLLOW(A)不再增大为止FOLLOW(A)构造例

G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│i

求每个非终结符号的FOLLOW集合解

FOLLOW(E)={$,)}FOLLOW(E’)=FOLLOW(E)

={$,)}

FOLLOW(T)={+,$,)}FOLLOW(T’)=FOLLOW(T) ={+,$,)}FOLLOW(F)={*,+,$,)}

3.3.3递归下降的预测分析预测分析是指能根据当前的输入符号为非终结符确定一个候选式，LL(1)文法满足这个要求。递归下降的预测分析是为每一个非终结符写一个分析过程，由于文法定义是递归的，因此这些过程也是递归的。在处理输入串时，首先执行的是开始符号的过程，然后根据产生式右部出现的非终结符，依次调用相应的过程，这种逐步下降的过程调用序列隐含地定义了输入的分析树。程序构造对每一个非终结符A，编写一个相应的子程序P(A),如果A→α1│α2│…│αn相应的子程序为：

IFchINFIRST(α1)THENP(α1)

ELSEIFch

INFIRST(α2)THENP(α2)ELSE……ELSEIFchINFIRST(αn)THENP(αn)ELSEIF(ε

∈

FIRST(A))AND(chINFOLLOW(A))THENRETURN

ELSEERROR对于符号串α=γ1γ2γ3…γm相应的子程序P(

α)为：

BEGINP(γ1)P(γ2)…P(γm)END如果γi∈VT,则P(γi)为:

IFch=γiTHENread(ch)ELSEERROR；如果γi∈VN,则P(

γi)为非终结符相应的子程序程序构造例

E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|iFIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}E→TE’

P(E)BeginP(T)；P(E’)；End;E’→+TE’|P(E’)BeginIfch=‘+’Thenbeginread(ch);P(T);P(E’)；

End;

elseifch=“)”Thenreturn;elseifch=‘#’Thenreturn;elseError;End;T→FT’P(T)BeginP(F)；P(T’)；End;T’→*FT’|P(E’)BeginIfch=‘*’Thenbeginread(ch);P(F)；P(T’)；

End;

//chFollow(E’)?End;例

E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|i

FIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}F→(E)|i

P(F)

Beginifch=‘i’thenread(ch)elseifch=‘(’then

beginread(ch);P(E);ifch=‘)’then read(ch)elseErrorEndelseError;End;例E→TE’;E’→+TE’|;T→FT’;T’→*FT’|;F→(E)|i

FIRST(＋TE’)={+}FIRST(*FT’)={*}

FOLLOW(E’)={),$}FOLLOW(T’)={+,),$}FIRST((E))={(}FIRST(i)={i}例:产生Pascal类型子集的文法

type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum一个辅助过程voidmatch(terminalt){ if(lookahead==t)lookahead=nextToken(); elseerror();}Type过程voidtype(){ if((lookahead==integer)||(lookahead==char)|| (lookahead==num)) simple(); elseif(lookahead==){match();match(id);} elseif(lookahead==array){ match(array);match([);simple(); match(]);match(of);type(); } elseerror();}typesimple |id |array[simple]oftypeSimple过程voidsimple(){ if(lookahead==integer)match(integer); elseif(lookahead==char)match(char); elseif(lookahead==num){ match(num);match(dotdot);match(num); } elseerror();}simpleinteger |char |numdotdotnum

3.3.4非递归的预测分析递归下降分析器需要具有能够实现递归过程的语言和编译系统，使程序实现受到一定限制。如果显示地维持一个栈，就可以构造非递归的预测分析程序,这是实现LL(1)分析的另一种有效方法。非递归预测分析程序的关键是如何选择候选式，分析程序通常由三部分组成：

预测分析表（LL(1)分析表）、符号栈、总控程序

1、LL（1）分析表

若文法有m个非终结符n个终结符，则LL(1)分析表是一个(m+1)*(n+2)的矩阵M，行标题为文法非终结符，列标题为终结符号和输入结束符$。M[A,a]为一条关于A的产生式，指出当A面临a时，应使用的产生式或空格(出错标志)例G:E→TE’E’→＋TE’│ε T→FT’T’→*FT’│ε F→(E)│ii+*()$EE→TE’E→TE’E’E’→＋TE’E’→εE’→εTT→ET’T→FT’T’T’→εT’→*FT’‘T’→εT’→ε

FF→i

F→(E)2、分析栈STACK:

放文法符号,初始放一个$号,

再放入开始符号S。3、总控程序:设栈顶为X，当前输入符号为a，则对于任何（X，a）执行以下三种动作之一：若X=a=“#”则分析成功若X=a≠“#”

则把X从STACK栈中弹出,a指向下一输入符号若X是非终结符,则按M[X,a]中的产生式进行推导(弹出X,将右部符号串反序入栈),或进行出错处理。例:G:E→TE’E’→＋TE’│εT→FT’T’→*FT’│εF→(E)│ii+*()$EE→TE’E→TE’E’E‘→+TE’E’→εE’→εTT→FT’T→FT’T’T’→εT’→*FT’T’→εT’→εFF→iF→(E)输入串:i+i*i的分析过程

步骤分析栈 输入串 产生式或动作

1$E i+i*i$ E→TE’ 2 $E’T i+i*i$ T→FT’3 $E'T’Fi+i*i$ F→i4 $E'T’i i+i*i$ i退栈,输入前进

5 $E'T’ +i*i$ T’退栈

6 $E' +i*i$ E’→+TE’7 $E'T+ +i*i$ +退栈,输入前进

8 $E'Ti*i$ T→FT’9 .........17$ $ 成功3.3.5构造预测分析表（1）对文法的每个产生式A

，执行(2)和(3)（2）对FIRST()的每个终结符a， 把A

加入M[A,a]（3）如果在FIRST()中，对FOLLOW(A)的每个终结符b（包括$）,把A

加入M[A,b]（4）M中其它没有定义的条目都是errorEE’TT’Fi+*()$E→TE’E→TE’T→FT’T→FT’T’→εT’→*FT’T’→εT’→εF→iF→(E)例

:对G构造分析表

E→TE’

E’→＋TE’│ε

T→FT’T’→*FT’│ε

F→(E)│iE’→+TE’E’→εE’→εFIRST(TE’)={(,i}FIRST（＋TE’）={+}FIRST(FT’)={（，i}FIRST(*FT’)={*}FIRST(（E）)={（}FOLLOW(E’)={$,)}FOLLOW(T’〕={+,$,)}

说明：

若文法G的分析表每一项M[A,a]，均不含有多重定义入口,当且仅当G为LL(1)文法。条件对任意A→α│βFIRST(α)∩FIRST(β)=Φ若β=>*ε,则FIRST(α)∩FOLLOW(A)=Φ

总控程序的形式化描述

BEGIN

＃及S进栈(push(‘#’);push(‘S’);)；

read(a)；

FLAG：＝TRUE；

WHILEFLAGDOBEGIN

把STACK栈顶弹出放在X中(X=pop())；

IFX∈VT

THEN IFX＝aTHENread(a)ELSEERROR

ELSEIFX=“＃”

THEN IFX=aTHENFLAG:=FALSEELSEERROR

ELSEIFM[X,a]={X→X1…Xk} THEN把Xk,Xk-1,…,X1逐一进栈

ELSEERRORENDOFWHILE；

END3.3.6LL（1）分析中的出错处理出错场合栈顶的终结符与当前的输入符号不匹配栈顶的非终结符A与当前输入符号a，分析表中M[A,a]为空。错误恢复的思路分析器检测到一个错误时，暂时放弃分析并给出错误信息；如果分析器能到达一个状态，从该状态可以对剩余输入继续分析，则从该状态恢复。3.3.6LL（1）分析中的出错处理处理方法发现错误时，分析器跳过输入串中的一些符号，直到输入符号属于某个“同步符号”为止。通过选择适当的“同步符号”，可以使分析器迅速从错误中恢复过来。

A的同步符号集（synch）的选择FOLLOW(A)

的所有终结符放入A的同步符号集合。即如果跳过一些符号直到看见FOLLOW(A)的元素，再把A弹出，分析一般可以继续下去。3.3.6LL（1）分析中的出错处理把高层构造的开始符号加到低层构造的同步记号集合中。如： a=expr;if… (语句的开始符号作为表达式的同步记号，以免表达式出错又遗漏分号时忽略if语句等一大段程序)3.3.6LL（1）分析中的出错处理把FIRST(A)的终结符加入A的同步记号集合。 如：a=expr;,if…（语句的开始符号作为语句的同步符号，以免多出一个逗号时会把if语句忽略了）如果非终结符可以产生空串，若出错时栈顶是这样的非终结符，则可以使用推出空串的产生式。如果终结符在栈顶而不能匹配，弹出此终结符例：加入同步符号集（FOLLOW集合元素）的LL(1)分析表i+*()$EE→TE’E→TE’synchsynchE’E’→＋TE’E’→εE’→εTT→FT’synchT→FT’synchsynchT’T’→εT’→*FT’T’→εT’→εFF→isynchsynchF→（E）synchsynch对输入串+id*+id的语法分析与错误处理过程见P62表3.53.4自下而上分析3.4.1

归约例:

S

aABe输入串abbcde

的分析过程 A

Abc|b B

d

3.4.1归约例:

S

aABe输入串abbcde

的分析过程 A

Abc|b B

dab

bcde

（读入ab）

ab3.4.1归约例:

S

aABe输入串abbcde

的分析过程 A

Abc|b B

dab

bcdeaAbcde（归约）

abA3.4.1归约例:

S

aABe输入串abbcde

的分析过程 A

Abc|b B

dabbcdeaAbcde（再读入bc）

abAbc3.4.1归约例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAde（归约）

abAbAc3.4.1归约例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAde（再读入d）

abAbdAc3.4.1归约例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABe（归约）

abAbdAcB3.4.1归约例:

S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABe(再读入e)

eabAbdAcB

3.4.1归约例： S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeS（归约）SeabAbdAcB3.4.1归约例： S

aABe

A

Abc|b B

dabbcdeaAbcdeaAdeaABeSSrmaABermaAdermaAbcdermabbcdeSeabAbdAcB3.4.2句柄句型的句柄是和某产生式右部匹配的子串，并且，把它归约成该产生式左部的非终结符时，恰是最右推导的逆过程的一步。

S

aABe

A

Abc|b B

dSrmaABe

rmaAdermaAbcdermabbcde句柄的右边仅含终结符如果文法二义，那么句柄可能不唯一例：句柄不唯一

文法：EE+E|EE|(E)|id在句型EE+id3中，句柄不唯一ErmEE

E

rmE+ErmE

E+E

rmE+id3rmEE+id3

rmEE+id3rmE

id2

+id3

rmE

id2

+id3

rm

id1

id2+id3

rm

id1

id2+id3

3.4.2句柄3.4.3用栈实现移进归约分析先通过移进归约分析器在分析输入串id1

id2+id3时的动作序列，来了解移进归约分析的工作方式。栈输入

动作

$

id1

id2

+id3$移进

$id1

id2

+id3$按E

id归约

$E

id2

+id3$移进

$E

id2

+id3$ 移进

$Eid2

+id3$按E

id归约

$EE

+id3$

移进

$EE+

id3$ 移进

$EE+id3

$ 按E

id归约

$EE+E

$ 按E

E+E归约

$EE

$ 按E

EE归约

3.4.3用栈实现移进归约分析要想很好地使用移进归约方式，尚需解决一些问题如何决策移进还是归约进行归约时，如何确定右句型中将要归约的子串进行归约时，如何确定选择哪一个产生式3.4.4移进归约分析的冲突1、移进归约冲突例 stmt

ifexprthenstmt |ifexprthenstmtelsestmt|other 如果移进归约分析器处于格局 栈

输入 …ifexprthenstmt else…$是移进还是归约？-冲突！2、归约归约冲突stmtid(parameter_list)|expr=exprparameter_list

parameter_list,parameter|parameterparameter

idexpr

id(expr_list)|idexpr_list

expr_list,expr|expr分析由A(I,J)开始的语句 栈 输入 …id(id ,id)…归约成expr还是parameter?3.5

LR分析器本节介绍LR(k)分析技术特点适用于一大类上下文无关文法效率高主要介绍构造LR分析表的三种技术简单的LR方法（简称SLR）规范的LR方法向前看的LR方法（简称LALR）

3.5.1LR分析算法输入LR分析程序输出栈LR分析器的模型actiongotosmXmsm-1Xm-1…s0…a1ai…an$L表示从左到右扫描输入串；R表示构造一个最右推导的逆过程例

(1)E

E+T(2)E

T

(3)T

TF(4)

T

E

(5)F(E)(6)Fid(P70)状态动

作(action

)转

移(goto)

id

+()$

E

TF

0s5s41231s6acc

2

r2s7r2r23r4r4r4r44…

s5s4

…

…

823……

移进(Sj)把当前a和状态j进栈归约(rj)按第j个产生式归约

接受(acc)成功结束出错(空白或出错处理）GOTO(S,X)状态S面对文法符号X时,下一状态是什么栈输入

动作

0

id

id

+id$移进

0id5

id

+id$按F

id归约

0F3

id

+id$按TF归约

0T2

id

+id$ 移进

0T2*7

id+id$移进

0T2*7id5

+id$按F

id归约

0T2*7F10

+id$ 按T

T*F归约

0T2

+id$ 按E

T归约

…