编译原理-课件第6讲

3.2

语言和文法

3.2.7

提左因子有左因子的文法

A

1|2提左因子

A

A A

1|2

3.2

语言和文法

例

悬空else的文法

stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

3.2

语言和文法

例

悬空else的文法

stmt

ifexprthenstmtelsestmt

|ifexprthenstmt |other

提左因子

stmt

ifexprthenstmt

optional_else_part |other optional_else_partelsestmt |3.2

语言和文法

3.2.8

非上下文无关的语言结构L1={wcw|w属于(a|b)*}

标识符的声明应先于其引用的抽象

L2={anbmcndm|n0,m0}形参个数和实参个数应该相同的抽象

L3={anbncn|n0}早先排版描述的一个现象的抽象L1={wcwR|w(a|b)*}

SaSa|bSb|cL2={anbmcmdn|n1,m1}

SaSd|aAd AbAc|bcL

2={anbncmdm|n1，m1} SAB AaAb|ab

BcBd|cdL3

={anbn|n

1}

SaSb|ab3.2

语言和文法L3

={anbn|n

1}

SaSb|abL3是不能用正规式描述的语言的一个范例

若存在接受L3的DFAD，状态数为k个。

设D读完,

a,aa,

…,ak

分别到达状态s0,s1,

…,sk至少有两个状态相同，例如是si和sj，则ajbi属于L3

si…。。。fs0标记为ai的路径标记为bi的路径标记为aj

i的路径…。。。…。。。3.2

语言和文法

3.2.9

形式语言鸟瞰文法G=(VT

,VN,S,P)0型文法：，,(VNVT)*,||11型文法：||||，但S可以例外，此时S不出现在任何产生式的右侧。2型文法：A，AVN,(VN∪VT)*3型文法：AaB或Aa，A,BVN,aVT

短语文法上下文有关文法上下文无关文法正规式3.2

语言和文法

例：L3＝{anbncn|n1}的上下文有关文法S

aSBC

S

aBC

CB

BCaB

ab

bB

bb bC

bccC

ccanbncn的推导过程如下：S*an-1S(BC)n1S+an(BC)n

S+anBnCnS+anbBn1CnS+anbnCn

S+anbncCn-1S+anbncn温故知新正规式上下文无关文法功能有限四元组定义推导分析树图形化表示最左推导最右推导二义性消除二义性左递归消除左递归左因子消除左因子A

1|2A+Aa

0型文法1型文法2型文法3型文法3.3

自上而下分析

3.3.1自上而下分析的一般方法例：

文法 S

aCb C

cd|c

为输入串w=acb建立分析树SSSaCbaaCCbbcdc

不能处理左递归、复杂的回溯技术、回溯导致语义工作推倒重来、难以报告出错的确切位置、效率低3.3

自上而下分析

3.3.2LL(1)文法

对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FIRST(

)={a|

*a…,a

VT}

1、特别是，

*时，规定

FIRST(

) 2、如果AB,则FIRST(B)应该加入FIRST(A) 对A的任何两个不同的选择i

和j，希望有 FIRST(i)FIRST(j)=但有一个前提，FIRST(i)和FIRST(j)都不含3.3

自上而下分析

3.3.2LL(1)文法

对文法加什么样的限制可以保证没有回溯？先定义两个和文法有关的函数FOLLOW(A)={a|S

*…Aa…，aVT}

1、如果A是某个句型的最右符号，那么$属于FOLLOW(A) 2、如果存在AB或AB且*，则FOLLOW(A)的全体元素要加入FOLLOW(B)3.3

自上而下分析引起回溯的原因：由于相同左部的产生式的右部First集交集不为空而引起回溯例：

文法 S

aCb C

cd|c

为输入串w=acb建立分析树2.由于相同左部VN的右部存在能*的产生式，且该VN的Follow集中含有其他产生式右部First集的元素

例：S->aAS|bA->bAS|

输入串ab#

（因为A*

所以First(bAs)Follow(A)≠

）3.由于文法左递归引起回溯

例：S->Sa|b

输入串baa#3.3

自上而下分析LL(1)文法 任何两个产生式A|都满足下列条件：

FIRST(

)FIRST()=若

*

，那么FIRST()FOLLOW(A)=LL(1)文法有一些明显的性质没有公共左因子不是二义的不含左递归FIRST集合计算方法若Xa..，则将终结符ａ加入FIRST(X)中若X，则将加入FIRST(X)中若XY…，且Y属于非终结符，则将FIRST(Y)\{}加入到FIRST(X)中若XY1Y2..YK,且Y1,Y2,..Yi-1都是非终结符，且Y1,Y2,..Yi-1的FIRST集合中均包含，则将FIRST(Yj)的所有非元素加入到FIRST(X)中，（j=1,2,..i）.特别地，若Y1~YK均有产生式，则将加到FIRST(X)中。FIRST集合及FOLLOW集合的计算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW集合计算方法对文法开始符号S,置$于FOLLOW(S)中。若有AB，则将FIRST()\{}加入FOLLOW(B)中。（此处可以为空）若AB或AB,且*（即属于FIRST()）,则将

FOLLOW(A)加入FOLLOW(B)中（此处可以为空）。FIRST集合及FOLLOW集合的计算方法SBAABS|dBaA|bS|cFIRST(B)={a,b,c}FIRST(A)={a,b,c,d}FIRST(S)={a,b,c}FOLLOW(S)=?FOLLOW(A)=?FOLLOW(B)=?3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|id3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}3.3

自上而下分析

例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}3.3

自上而下分析

例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}3.3

自上而下分析例 E

TE E

+TE

| T

FT T

*

FT

| F

(E)|idFIRST(E)=FIRST(T)=FIRST(F)={(,id}FIRST(E)={+,}FRIST(T)={*,}FOLLOW(E)=FOLLOW(E)={),$}FOLLOW(T)=FOLLOW(T)={+,),$}FOLLOW(F)={+,*,),$}3.3

自上而下分析

3.3.3递归下降的预测分析为每一个非终结符写一个分析过程这些过程可能是递归的例： type

simple |id |array[simple]oftype simpleinteger |char |numdotdotnum3.3

自上而下分析

一个辅助过程procedurematch(t:token);begin iflookahead==tthen lookahead:=nexttoken() elseerror()end;3.3

自上而下分析

proccduretype;begin iflookaheadin{integer,char,num}then simple() elseiflookahead=thenbegin match();match(id) end elseiflookahead=arraythenbegin match(array);match([);simple(); match(]);match(of);type() end elseerror()end;type

simple |id |array[simple]oftype3.3

自上而下分析

proceduresimple;begin iflookahead=integerthen match(integer) elseiflookahead=charthen match(char) elseiflookahead=numthenbegin match(num);match(dotdot);match(num) end elseerror()end;simpleinteger |char |numdotdotnumprocedurematch(t){if当前输入符号＝tthen取下一个符号作为当前输入符号else报错。}procedureA{ if当前符号=‘a’then {match(a);调用A;} elsereturn;}procedureB{ if当前符号=‘b’then {match(b);调用B;} elseif当前符号=‘c’thenreturn;else报错。

}procedureS{ switch当前符号

case‘a’:调用A; case‘b’:调用B;}SA|BAaA|

BbB|c

aaaaa,bbbbcaaaaa,aa,bbbc,bbc当非终结符的产生式有多种选择，即意味着分析过程有不同的展开方式。而我们只能根据当前输入符号来决定采用哪种展开方式（选择），这样就有了FIRST（）函数。1、LL(1)文法的自上而下分析及FIRST函数理解3.3

自上而下分析3.3.4非递归的预测分析a+b$输入预测分析程序分析表M输出

XYZ$栈3.3

自上而下分析非终结符输

入

符

号

id+*

...EE

TE

E

E

+TE

T

T

FT

T

T

T

*FTF

F

id3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$

$ET

id*id+id$

E

TE

$ETF

id*id+id$

T

FT

$ETid

id*id+id$

F

id

$ET

*

id+id$

$ETF*

*

id+id$

T

*FT

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$$ETF*

*

id+id$T

*FT

$ETF

id+id$

预测分析器接受输入id*id+id的动作

3.3

自上而下分析栈

输

入

输

出

$E

id*id+id$$ET

id*id+id$E

TE

$ETF

id*id+id$T

FT

$ETidid*id+id$F

id$ET

*

id+id$$ETF*

*

id+id$T

*FT

$ETF

id+id$$ETidid+id$F

id预测分析器接受输入id*id+id的动作

栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EEE$2、LL(1)文法的自上而下的非递归分析方法理解深度优先构造分析树E

TEE

+TE|T

FTT

*FT

|F

(E)|id输入：id*id栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

TE’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

FT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

ididT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

idT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

F*FT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FFT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FididT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ETF

id*id$

T

FT

$ETid

id*id$

F

id

$ET

*

id$

$ETF*

*

id$

T

*FT

$ETF

id$

$ETid

id$

F

id

$ET$$E$T$$EETE

FT

id*T

FidT’E’$栈

输

入

输

出

$E

id*id$

$ET

id*id$

E

TE

$ET