编译讲义课件2自下而上3

一.句型的语法树和文法的二义性1.

语法树语法树是一棵树，这棵树表示一个句型的推导过程。句型E+F*i对应的语法树，如右图所示:ETE+*TFFi例，文法G的产生式:E→E+T│TT→T*F│FF→(E)│i3.5

自下而上分析由图不难看出:F是句型

E+F*i相对于T的直接短语；i是句型E+F*i相对于F的直接短语；F*i是句型E+F*i相对于T的短语；E+F*i是句型E+F*i相对于E的短语。F是句柄。ETE+*TFFi2.

文法的二义性若一个文法存在某个句型对应两棵不同的语法树，则称此文法是二义性文法。例，文法G:

E→E+E│E*E│(E)│i句型E*E+i

对应的两棵语法树EE*EE+EE+E

EiE*EiG虽是二义性文法，但L(G)不是二义性语言。定理:若文法是非二义的，则此文法的规范推导句型的句柄是唯一的。1.

给定一非二义性文法G=(VN,VT,P,S)，且任意给一符号串α∈V

*，若α∈L(G)，则α按规范归约(句柄是唯一的)T一定能归约成开始符S；否则，一定失败。2.

给定文法G，可用规范归约识别文法G的句子。例，文法G:

E→E+T│T，T→T*F│F，F→(E)│i句子i+i*i

的规范推导为:E

E+T

E+T*F

E+T*i

E+F*i

E+i*i

T+i*i

F+i*i

i+i*i规范归约是上述规范推导的逆过程。3.

规范规约算法(“移进-规约”分析法)工具:符号栈S[K]，存放句型的前缀,初始S[1]=#；输入缓冲区R，存放要识别的符号串，初始为i+i*i#。从输入串中读出的符号存在单元a中，每读一次符号，指针下推一个符号位置。算法:1.

[置初值] a=“”；

k=1；

S[k]=“#”；从R中读下一个符号存放入a；若S[k]的内容=“#E”∧a=“#”，则归约成功，结束；否则，执行4；S[k]栈顶部分是否为当前句型的句柄？是则执行5；否则，执行6；S[k]栈顶部分一定可用某个产生式左部替换。例如，

S[k]栈顶的符号X1…Xn是句柄，且有产生式A→X1…Xn则X1…Xn出栈，K=K-n+1，A进S[k]栈。转3；K=K+1；a中符号移进S[k]栈，转2；例，i+i*i

的规约过程如下:S[K]栈输入串动作#i+i*i#移进#i+i*i#规约，F→i#F+i*i#规约，T→F#T+i*i#规约，E→T#E+i*i#移进#E+i*i#移进#E+i*i#规约，F→i#E+F*i#规约，T→F#E+T*i#移进#E+T*i#移进#E+T*i#规约，F→i#E+T*F#规约，T→T*F#E+T#规约，E→E+T#E#空成功！3.6算符优先分析算法算符优先分析法是自下向上分析方法中的一种，特别适合表达式的分析，也宜于手工实现。在算术表达式的运算过程中，为了确保计算过程和结果的唯一性，规定了四则运算法则，实际上就是规定了运算之间的优先顺序和结合性质。第一，运算分为两级，乘除为一级，加减为另一级，乘除优先于加减。第二，同级运算服从左结合。所谓算符优先分析法就是仿照上述算术四则运算的运算过程，而设计的一种语法分析方法。它首先要规定运算符之间的优先关系，然后利用这种关系确定句型的“句柄”，进行归约。1i+i-i*(i+i)2E+i-i*(i+i)3E+E-i*(i+i)4E-i*(i+i)5E-E*(i+i)6E-E*(E+i)7E-E*(E+E)8E-E*(E)9E-E*E10E-E11E例，有文法G[E]:

Efi

E+E|E-E|E*E|E/E|(E)|i并有输入串i+i-i*(i+i)这个文法是一个二义性文法，因此有几种不同的规范规约，但若定义了算符优先顺序和结合规则，归约过程就唯一了。算符优先分析的规约过程不是一种规范规约。4.1.1

直观的算符优先分析法从上面的例子可以看到，算符优先分析法的关键就是要定义任意两个相继出现的终结符号a和b之间的优先关系(a与b之间可有一个非终结符)，一旦确定了这种优先关系，就可以用它来确定“句柄”进行归约。1.

优先关系，终结符之间的优先关系有三种:a的优先级高于b

记为:a的优先级等于b

记为:a

.>

ba

.

ba

<.

ba的优先级低于b

记为:若有:

b

.>

a，不一定有:

a

<.

b但+

.>

-

-

.>

+与数学中的<、=、>含义不同，如:同样:a

.

b，不一定有:

b

.

a(

.

)但却没有)

.

(><.

<.<.

.>

.>.>.>

<..>.>.>

.>

.2.

直观算符优先关系表VT={+,*,i,(,)}右终结符左终结符+

*

i+*i()#行表示相邻两个终结符号中左边的一个例，有文法G[E]:

E列fi表E示+E相|E邻*E两|(个E)终|i

结其优先关系矩阵为:符号中右边的一个两(

个终结)

符号#若不可能在句型中相邻，则它们之间<.无优先.>关系.>.>本运算.>量要首先计<.算，<所.以它的<.优先<.级最高。“.>#”是作为输入串.><.

对于的<.分界符<.，所以<.它

.的i因优为先它级表最示低基。为了保.证消去括号规定“(”和“)”优先关系相等3.

直观算符优先分析算法建立两个栈，OPTR用于存放运算符OPND用来存放运算数‘#’作为输入串的左右分界符开始分析时，‘#’进入OPTR，OPND为空q代表当前OPTR顶符号(q

=‘#’)a存放当前输入符号栈总控程序优先表算法描述如下:当前输入符号送a；若a为基本运算数i,则送OPND并转(1);若q

.>a，则根据Efi

E1qE2进行归约，其中E2和E1分别代表OPND的次栈顶和栈顶，从OPND中弹出E2和E1，并将结果E压入OPND中，同时OPTR栈顶q弹出，重新执行(3)。若q

.

a,

这只有两种可能:

其一，

q

=‘(’

而

a=‘)’，逐出OPTR顶的‘(’，放弃a中的‘)’，转(1)；其二，

q

=

a=‘#’，分析过程成功。若q

<.a,

则a入算符栈，成为算符栈新栈顶，转(1)；若q与a不存在优先关系，报告出错。序号OPNDOPTR优先关系a单元输入串0#i+i*i#1#i+i*i#2i#<.+i*i#3i#+i*i#4i

i#+<.*i#5i

i#+*i#6i

i

i#+*.>#7i

t#+.>#8e#

.#例，试用上述算法分析表达式i+i*i，即分析#i+i*i#t=i*ie=i+tq=a=‘#’4.

直观算符优先分析的缺陷算法可能产生离奇的结果。i

i+i*+i(

)这种缺陷表明，算符优先分析方法不能准确的指出输入串出错的位置。算符优先分析方法简单明了，易于实现。3.6.1

直观的算符优先分析法在文法的基础上定义了算符的优先关系和结合规则，实现规约的唯一性。是对算术表达式计算过程的一种模拟。例，有文法G[E]:Efi

E+EEfi

E-EEfi

E*EEfi

(E)|i输入串i+i-i*i1#i+i-i*i#2#E+i-i*i#3#E+E-i*i#4#E-i*i#5#E-E*i#6#E-E*E#7#E-E#8#E#3.6.2

算符优先分析法1、算符优先文法的定义算符文法:

任给一上下文无关文法G，若G的任何产生式右部都不含两个相继的非终极符，则称文法G为算符文法。例，文法G:

SfiUV

Ufia

Vfi

b就不是算符文法。算符优先关系:

设G是一个算符文法，a，b˛VT，A、R、Q˛VN，则a，b优先关系定义如下:a

.

b，当且仅当G中含有产生式:Afi

…ab…，或Afi

…aQb…；a

<.b，当且仅当G中含有产生式:Afi…aR…且R

+

b…，或R

+

Qb…；a

.>b，当且仅当G中含有产生式:Afi

…Rb…且R

+

…a，或R

+

…aQ；算符优先文法:

如果一个算符文法G不含空产生式，且G中的任意终极符对(a，b)至多满足下列算符优先关系之一:a

<.ba

.>

b则称G为算符优先文法。a

.

b总控程序算符优先关系表栈中心问题:算符优先关系表的构造。T

NVb…,b˛

V

,U,V˛V

}…aV,a˛

VT,U,V˛

VN}(2)

求法(以FIRSTVT(U)为例说明):直观定义:

若有产生式Ufib…或UfiVb…，U,V

˛VN， 则

b˛FIRSTVT(U)传递定义:

若有产生式UfiV…，且b˛

FIRSTVT(V)， 则

b˛FIRSTVT(U)2、算符优先关系表的构造(1)

定义两个重要集合:FIRSTVT(U)={b|

U

+

b…或U+

LASTVT(U) ={a|

U

+

…a或U+若存在Afi

…aU…，就若可存以在确定Afia

…<.bU，b…，b˛就F可IR以ST确V定Ta(U.>)b，a˛LASTVT(U)现将算符文法的非终极符给出一种排序A1，…，Am；终极符给出一种排序a1，…，an；而aj(j=1，…，n)∈FIRSTVT(Ai)(i=1，…，m)可用布尔矩阵表示，布尔矩阵的格式如下表所示，若aj∈FIRSTVT(Ai)则布尔矩阵的元素M[Ai，aj]＝“Ｙ”；a1a2...anA1YY...YA2Y.........YAm(3)

FIRSTVT(Ai)的矩阵FIRSTVT(Ai)的矩阵构造算法:对所有的Ai

（i=1，…，m），若有产生式Ai

→aj…或Ai→Akaj…,1≤i,k≤m,1≤j≤n则置M[Ai

，aj]=“Y”，且将符号对（Ai

，aj）推进S栈。repeat将S栈顶符号对(Ai，aj)逐出，由符号对(Ai，aj)检查产生式集合，看是否有形如AK→Ai…的产生式，若有，且M[AK

，aj]≠“Y”，则置M[AK

，aj]=“Y”，将符号对

(Ak

，aj)推进S栈。until S栈=空例，对于文法E→E+T

|

TT→T*F

|

FF→(E)

|

i构造FIRSTVT(Ai)的布尔矩阵，(Ai取值为:

E、T、F)，如下表所示。+*i()EYYYYTYYYFYY解:

因为非终极符E、T、F有如下产生式:E→E+TT→T*FF→(E)|iE→E+…T→T*…F→(…

|i所以，需要在表中置初值：M[E，+]=M[T，*]=M[F，(]=M[F，i]=“Y”又因为有产生式T→FE→T所以，需在表中填写：M[E，i]=M[E，(]=M[E，*]=M[T，i]=M[T，(]=“Y”(4)

LASTVT(Ai)直观定义:

若有产生式Ufi

…b或Ufi

…bV，U,V

˛VN，则b˛LASTVT(U)传递定义:

若有产生式Ufi…V，且b˛

LASTVT(V)， 则

b˛LASTVT(U)现将算符文法的非终极符给出一种排序A1，…，Am；终极符给出一种排序a1，…，an；而aj(j=1，…，n)∈LASTVT(Ai)(i=1，…，m)可用布尔矩阵表示，布尔矩阵的格式如下表所示

，若aj∈LASTVT(Ai)则布尔矩阵的元素M[Ai，aj]＝“Ｙ”；LASTVT(Ai)的矩阵构造算法:对所有的Ai

（i=1，…，m），若有产生式Ai

→…aj

或Ai→…ajAk

,1≤i,k≤m,1≤j≤n则置M[Ai

，aj]=“Y”，且将符号对（Ai

，aj）推进S栈。repeat将S栈顶符号对(Ai，aj)逐出，由符号对(Ai，aj)检查产生式集合，看是否是形如AK→…Ai的产生式，若有，且M[AK

，aj]≠“Y”，则置M[AK

，aj]=“Y”，将符号对

(Ak

，aj)推进S栈。until S栈=空例，对于文法E→E+T

|

TT→T*F

|

FF→(E)

|

i构造LASTVT(Ai)的布尔矩阵，(Ai取值为:

E、T、F)，如下表所示。+*i()EYYYYTYYYFYY解:

因为非终极符E、T、F有如下产生式:E→E+TT→T*FF→(E)|iE→…+TT→…*FF→…)|i所以，需要在表中置初值：M[E，+]=M[T，*]=M[F，)]=M[F，i]=“Y”又因为有产生式E→TT→F所以，需在表中填写：M[E，i]=M[E，)]=M[E，*]=M[T，i]=M[T，)]=“Y”(5)构造算符优先关系表的算法:文法G，设每个非终极符P

的FIRSTVT(P)和LASTVT(P)已求出，则构造算符优先关系表的算法如下所示。for (

G的每个产生式P→X1X2…Xn

)for (

i=1；i<=n-1；i++){ififif(Xi

,Xi+1∈VT)

置Xi

.

Xi+1；(

i<=n-2

&&

Xi

,Xi+2∈VT

&&

Xi+1∈VN

)(

Xi∈VT&&

Xi+1∈VN

)for

(b∈FIRSTVT(Xi+1)的每个b)置Xi

.

Xi+2；置Xi

<.b；if(

Xi∈VN

&&

Xi+1∈VT

)for (a

∈LASTVT(Xi)的每个a)置a

.>Xi+1

；}例，有文法G[E]:

Efi

E+T|T，Tfi

T*F|F，Ffi

(E)|i则优先关系表为：+*i()EYYYYTYYYFYY+*i()EYYYYTYYYFYYFIRSTVT(Ai)

LASTVT(Ai)+*i()#+.><.<.<..>.>*.>.><.<..>.>i.>.>.>.>(<.<.<.<.=.).>.>.>.>#<.<.<.<.=.4、最左素短语素短语:若一个文法的句型的短语称为素短语，则此短语至少包含有一个终结符号，并且除它自身之外，不再包含其它更小的素短语。例，设有文法G[E]:Efi

E+T|TTfi

T*F|FFfi

(E)

|

i的句型为T+T*F+i,要求找出其素短语。句型对应的语法树为:最左素短语是当前

T归是约句的柄对，象但

不是素短语EE+TE+

T*FT

TFi句型的短语有:其中素短语有:T*F,

i最左素短语:

任意句型最左边的素短语。T*F是句型T+T*F+i最左素短语。T(E),

T*F(T),i(F),T+T*F(E),

T+T*F+i(E)EE+TE+

T*FT

TFi算符优先文法的句型的最左素由短n语个终的结判符定号定组理成:，而每个相邻的终结符号之间至多算符文法句型的一般形式:有一个非终结符。#N1a1N2a2……NnanNn+1#

其中，Ni˛VN,ai˛VT最左素短语是满足下列条件的最左子串:NjajNj+1aj+1……NiaiNi+1其中优先关系为:>

ai+1aj-1

<.aj

，aj

j+1.

a

.

……

ai，

ai给.出了根据.句型之间的终结符号的优先关系判断最左素短语的方法。例，有文法G[E]:Efi

E+T

|TTfi

T*F

|

FFfi

(E)

|

i已知优先关系矩阵为：+*i()#+.><.<.<..>.>*.>.><.<..>.>i.>.>.>.>(<.<.<.<.=.).>.>.>.>#<.<.<.<.=.步骤句型优先关系最左素短语归约符号1#T+T*F+i##

<.+

<.*

.>

+

<.i

.>

#T*FT2#T+T+i##

<.+

.>

+

<.i

.>

#T+TE3#E+i##

<.+

<.i

.>

#iF4#E+F##

<.+

.>

#E+FE5#E#确认！要求用归约当前最左素短语的方法分析句型T+T*F+i:可见，素短语可以通过终结符号的优先关系确认。5、算符优先分析算法{

K++; S[K]=a;

}K=1;

S[K]=”#”;do{

将输入串的下一个符号读进a中;if (

S[K]∈VT

)

j=K;

else

j=K--;while

(

S[j]

.>

a)

{do{

Q=S[j];if

(

S[j-1]

∈VT

)

j--;

else

j-=2;}

while (

!

(S[j]

<.Q)

);将S[j+1]…S[K]归约成某个P(P∈VN);K=j++;S[K]=P;

}if ((

S[j]<.a

)

||

(

S[j]

=.

a))else error()

；}

while

(!a

=.

’#’

)序号S[K]栈a单元输入串1#i+i*i#2#i+i*i#3#E+i*i#4#E+i*i#5#E+T*i#6#E+T*i##7#E+T*F#8#E+T#9#E#例，#i+i*i#的分析过程6、算符优先函数1.在实际的算符优先分析中，一般不用文法的优先关系矩阵，而是用两个优先函数f和g，即我们把每个终结符号q与两个自然数f(q)和g(q)相对应，并满足以下条件:f称为入栈优先函数(左)，g称为比较优先函数(右)。若q1<.q2若q1

.q2若q1.>q2则f(q1)<g(q2)则f(q1)=g(q2)则f(q1)>g(q2)2.优先函数的构造方法:任给一符号θ∈VT∪{#}，令f(θ)=g(θ)=1；若θ

.>θ，但f(θ)£g(θ)，则f(θ

)=g(θ

)+1；1

2

1

2

1

2若θ

<.θ，但f(θ)