自上而下语法分析方法

第四章自上而下的语法分析方法1本章重点：1.LL(1)文法判别2.某些非LL(1)文法到LL(1)文法的等价转换3.预测分析法实现过程4.递归子程序法实现思想2四元式单词符号语法单位四元式目标代码词法分析器语法分析器语义分析与中间代码生成器优化段源程序表格管理出错处理目标代码生成器序：语法分析3语法分析的任务是分析一个文法的句子结构。语法分析器的功能：按照文法的产生式(语言的语法规则)，识别输入符号串是否为一个句子。源程序单词符号取下一单词...语法分析树词法分析器语法分析器符号表编译程序后续部分4自上而下分析法(Top-down)基本思想：它从文法的开始符号出发，反复使用各种产生式，寻找"匹配"的推导。递归下降分析法：对每一语法变量(非终结符)构造一个相应的子程序，每个子程序识别一定的语法单位，通过子程序间的信息反馈和联合作用实现对输入串的识别。预测分析程序

直观、简单和宜于手工实现。5自下而上分析法(Bottom-up)基本思想：从输入串开始，逐步进行“归约”，直到文法的开始符号。即从树末端开始，构造语法树。所谓归约，是指根据文法的产生式规则，把产生式的右部替换成左部符号。

算符优先分析法：按照算符的优先关系和结合性质进行语法分析。适合分析表达式。LR分析法：规范归约64.1确定自顶向下分析思想和LL(1)文法G1[S]:S→pA|qBA→cAd|aB→dB|b输入串：W=pccaddG1文法特点：(1)每个产生式的右部都由VT开始。(2)如果两个产生式有相同的左部，那么它们的右部由不同的VT开始。7G2[S]:S→Ap

S→BqA→aA→cA

B→bB→dBG2文法特点：(1)每个产生式的右部不全由VT开始。(2)如果两个产生式有相同的左部，那么它们的右部由不同的VT或VN开始。(3)文法中无空产生式输入串：W=ccap8FIRST集定义令G是一个上下无关文法，对G的所有非终结符的每个候选定义它的终结首符号集FIRST()为：

特别是，若，则规定FIRST()。9如果非终结符A的所有候选首符集两两不相交，即A的任何两个不同候选

i和

jFIRST(i)∩FIRST(j)＝当要求A匹配输入串时，A就能根据它所面临的第一个输入符号a，准确地指派某一个候选前去执行任务。这个候选就是那个终结首符集含a的。G2[S]:S→Ap

S→BqA→aA→cA

B→bB→dBFIRST(Ap)={a,c}FIRST(Bq)={b,d}10G3[S]:S→aA

S→dA→bASA→ε

输入串：W=abdG3文法特点：当某一VN的产生式中含有空产生式时，它的非空产生式右部的首符号集两两不相交，并与在推导过程中紧跟该VN右边可能出现的VT集合也不相交，仍可构造确定的自顶向下分析。111.若XV,则FIRST(X)={X}.2.若XVN,且有产生式Xa…，aV则把a加入到FIRST(X)中;若X是一条产生式,则把也加到FIRST(X)中。3.若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;根据定义计算FIRST集

124.若X

Y1Y2…Yk

是一个产生式,Y1,Y2,…,Y(i-1)(i≤k)都是非终结符,而且,对于任何j,(1≤j≤i-1)FIRST(Yj)都含有

(即Y1，Y2，…，Y(i-1)都

),则把FIRST(Yj)中的所有非元素和FIRST(Yi)都加到FIRST(X)中;特别是,若所有的FIRST(Yj

)

,

(

j=1,2,…,k)均含有,则把也加到FRIST(X)中。13例子文法：SABSbC

A

AbB

BaDCADCbDaSDcFIRST(D）FIRST(A)FIRST(B）FIRST(S）FIRST(C）

FIRST(AB)FIRST(AD)

14FOLLOW集定义令G是一个上下无关文法，对G的所有非终结符A定义它的后跟符号集FOLLOW(A)为：

特别是，若，则规定#FOLLOW(A)15G3[S]:S→aA

S→dA→bASA→ε

FOLLOW(S)={a,d,#}FIRST(A)={b,ε}输入串：W=abd16根据定义计算FOLLOW集1.对于文法的开始符号S,置#FOLLOW(S);2.若Ａ→αBβ是一个产生式,则把FIRST(β)-{}加至FOLLOW(B)中;3.若Ａ→αB

是一个产生式,或Ａ→αBβ是一个产生式，而β(即FIRST(β)），则把FOLLOW（A）加到FOLLOW（B）中。17例子文法：SABSbC

A

AbB

BaDCADCbDaSDcFOLLOW(S)={#}FOLLOW(A)={a,c,#}FOLLOW(B)={#}FOLLOW(C)={#}FOLLOW(D)={#}18SELECT集定义一个上下文无关文法的产生式A→α

若α

ε，则SELECT(A→α)=FIRST(α)若α

ε，则SELECT(A→α)=（FIRST(α)-{ε}）∩FOLLOW(A)19LL(1)文法的充要条件

一个上下文无关文法是LL(1)文法的充要条件是：对每个非终结符A的两个不同的产生式

A→α，A→β，满足

SELECT(A→α)∩SELECT(A→β)=其中α和β不能同时n次推出ε。20判别G3[S]文法是否为LL(1)文法？G3[S]:S→aA

S→dA→bASA→ε

判别G4[S]文法是否为LL(1)文法？G4[S]:S→aAS

S→bA→bAA→ε

21LL(1)文法判别的步骤(1)求出能推出ε的非终结符(2)计算每个VN的FIRST集(3)计算每个VN的FOLLOW集(4)计算每个产生式的SELECT集合根据充要条件判别文法是否为LL(1)224.2某些非LL(1)到LL(1)文法的等价变换

分析自顶向下分析过程中产生不确定性的原因：1.由于相同左部的产生式的右部FIRST集相交不为空而引起回溯2.由于相同左部非终结符的右部肯能推导出ε的产生式，且该非终结符的FOLLOW集合中含有其他产生式右部FIRST集合的元素3.由于文法含有左递归而引起回溯

23G1[S]:S→xAyA→ab|a输入串：

xayG2[S]:S→aAS|bA→bAS|ε

输入串：

abG3[S]:S→Sa|b输入串：baa公因子左递归244.2.1消除左递归1消除直接左递归消除直接左递归（改写为等价的右递归）形如：A

→

Aα|β

α非，

β不以A开始

改写为：A

→βB（B为新增加的非终结符）

B→αB|（因为改写前产生式可产生的短语形式为βαn改写后产生式可产生的短语形式也为βαn

）25例:E→E+T|T（含有E的左递归）

T→T*

F|F（含有T的左递归）

F→(E)|i

消除左递归后：

G[E]:(1)E→TE’(2)E’

→

+TE’(3)E’

→

(4)T→FT’(5)T’

→

*FT’(6)T’

→

(7)F→

(E)(8)F→i262消除一般左递归的方法若有多个左递归的产生式如：Ａ→Ａ1|Ａ2|…|Ａm|β1|β2|…|βn消除左递归后变为：Ａ→β1Ａ’|β2Ａ’|…|βnＡ’（因β1、β2、…、βn都可能替换Ａ）Ａ’→1Ａ’|2Ａ’|…|mＡ’|

（对每个左递归都改写为右递归）消除左递归要求文法:1.无回路（Ａ→Ａ）2.无空产生式27消除一般左递归例如：(1)S→Qc|c(2)Q→Rb|b(3)R→Sa|a把(1)的右部代入(3)得：(4)R→Qca|ca|a把(2)的右部代入(4)得：(5)R→Rbca|bca|ca|a消除R的直接左递归得：

R→(bca|ca|a)R’R’→bcaR’|

消除左递归后得：S→Qc|cQ→Rb|bR→(bca|ca|a)R’R’→bcaR’|

当然也可先把（3）的右部代入(2)，再把改变后的（2）的右部代入(1)，最后消除S的直接左递归。28消除一般左递归1

.以某种顺序将文法非终结符排列A1,A2,…,An2.fori:=1tondobeginforj:=1toi-1do用Ai

→

1r|2r|…|kr

替代形如Ai

→

Ajr

的规则，其中Aj

→

1|2|

…|k是关于Aj的全部产生式;消除Ai规则的直接左递归;

end;3.化简由2得到的文法当非终结符的排序不同时，变换后的文法形式可能不同，但是它们都和原文法是等价的。294.2.2提取左公因子将产生式Ａ→β|

变换为：

Ａ→B（B为新增加的非终结符）

B→β|例:提左公因子后变换为：

S→cAd

A→ab

A→aS→cAd

A→a

B

B→b|

304.3确定的自顶向下的分析方法31自上而下的语法分析面临的问题-实现考虑回朔文法的左递归性

S→Sa32自上而下分析对文法的要求例文法G0[S]:(1)S→Sa(2)S→b

分析baa是不是文法的句子按照自上而下的分析思想选用产生式(1)来推导SSa

语法树末端结点最左符号为非终结符，所以选用（1）继续推导SSaSaa

此时语法树末端结点最左符号仍为非终结符，所以选用（1）继续推导SSaSaaSaaa

问题——试图用S匹配输入串时，出现：在没有读入任何输入符号的情况下，又得重新要求S去进行新的匹配原因——文法含有左递归，33自上而下的语法分析－－左递归规则G[S]:S→SaS→bL={ban|n≥1}W=baaaSbSSa

Sa

34左递归－关于非终结符P的规则直接左递归若P→Pα|βα、β∈V*且α、β不以P开头一般左递归若P=>*Pα

S→Aa

A→Sb…35

自上而下分析的进一步讨论自上而下分析也称面向目标的分析方法，也就是从文法的开始符号出发企图推导出与输入的符号串完全匹配的句子，若能构造出推导则表明输入串是给定文法的句子，否则表明该输入不是给定文法的句子。自上而下分析对文法的要求－文法不能含有左递归规则。自上而下分析又可分为确定的和不确定的两种

不确定的分析方法称为带回溯的分析方法，这种方法实际上是一种穷举的试探方法

确定的分析方法需对文法有一定的限制36消除文法中左递归规则消除直接左递归形如：P→Pα|βα非，α，β不以P打头

改写为：P→

βQ

Q

→

αQ|

其中Q为新增加的非终结符37消除文法中左递归规则例:E→E+T|TT

→T*F|FF

→(E)|a

G[E]:(1)E→TE’(2)E’→+TE’(3)E’→

(4)T→FT’(5)T’→*FT’(6)T’→

(7)F→(E)(8)F→a38消除一般左递归要求文法:

1.无回路(A(=>+(A)2.无空产生式（1）

.以某种顺序将文法非终结符排列A1,A2…An（2）

fori:=1tondobegin

forj:=1toi-1do用Ai-->1|2r…|kr替代形如Ai-->Ajr的规则,其中Aj-->1|2…|k是关于Aj的全部产生式;消除Ai规则的直接左递归;

end;（3）化简由2得到的文法39回溯的原因例G[S]:

S→xAy

A→ab｜a

若当前输入串为xay，首先构造的推导SxAy

匹配进一步推导对A可选择A→ab替换，得SxAy

xaby

xay

xaby

匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，SxAy

xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。40在自上而下的分析方法中如何选择使用哪个产生式进行推导？ 假定要被代换的最左非终结符号是B，且有n条规则：B→A1|A2|…|An，那么如何确定用哪个右部去替代B？-------什么信息用于Parser做正确选择?(输入串,文法特点)41可预测的试探推导过程例文法G’[S]:S→

pA|qBA→cAd|a

B→dB|c

识别输入串w=pccadd是否是G1[S]的句子可预测的试探推导过程：SpApcAdpccAddpccadd

试探成功。42PL/0语言的EBNF〈程序〉∷=〈分程序〉.〈分程序〉∷=[〈常量说明部分〉][〈变量说明部分〉][〈过程说明部分〉]〈语句〉〈常量说明部分〉∷=CONST〈常量定义部分〉{，〈常量定义〉}；〈变量说明部分〉∷=VAR〈标识符〉{，〈标识符〉}；〈过程说明部分〉∷=PROCEDURE〈标识符〉〈分程序〉{；〈过程说明部分〉}；〈语句〉∷=〈标识符〉：=〈表达式〉|IF〈条件〉then〈语句〉|CALL…|READ…|BEGIN〈语句〉{；〈语句〉}END|WHILE…|…43PL/0分析《语句》的子程序片断begin(*statement*)ifsym=identthen(*parsingass.st.*)begin

getsym;ifsym=becomesthengetsymelseerror(13);

expression(fsys);endelseifsym=readsymthen(*parsingreadst.*)begin

getsym;ifsym<>lparenthenerror(34)elserepeat

getsym;ifsym<>identthenerror(35)elsegetsymuntilsym<>comma;ifsym<>rparenthenerror(33);end44例：递归子程序实现表达式的语法分析表达式的EBNF

〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}

〈项〉∷=〈因子〉{（*|/）〈因子〉}

〈因子〉∷=ident|number|‘（’〈表达式〉‘）’45〈表达式〉∷=[+|-]〈项〉{（+|-）〈项〉}int

expression(bool*fsys,int*ptx,int

lev){

if(sym==plus||sym==minus) /*开头的正负号*/ { …

getsym; …

term(nxtlev,ptx,lev); /*处理项*/ … } else /*此时表达式被看作项的加减*/ { …

term(nxtlev,ptx,lev); /*处理项*/ } while(sym==plus||sym==minus) { …

getsym; …

term(nxtlev,ptx,lev); /*处理项*/ …}}46〈项〉∷=〈因子〉{（*|/）〈因子〉}int

term(bool*fsys,int*ptx,int

lev){ … factor(nxtlev,ptx,lev);/*处理因子*/

while(sym==times||sym==slash){…

getsym; factor(nxtlev,ptx,lev); …}}47〈因子〉∷=〈标识符〉|〈无符号整数〉|‘（’〈表达式〉‘）’int

factor(bool*fsys,int*ptx,int

lev){ if(sym==ident) /*因子为常量或变量*/

getsymelse {if(sym==number) /*因子为数*/

getsym else {if(sym==lparen) /*因子为表达式*/ {expression(nxtlev,ptx,lev); if(sym==rparen)

getsym; elseerror(22); /*缺少右括号*/ }elseerror() }} 485.2预测分析程序（Predictiveparser）无回溯的自顶向下分析程序特征——根据下一个(几个）输入符号为当前要处理的非终结符选择产生式要求——文法是LL(1)的第一个L从左到右扫描输入串第二个L生成的是最左推导

1向前看一个输入符号（lookahead)预测分析程序的实现技术

1递归（下降）子程序

2表驱动分析程序49例：递归下降子程序ParseFunction()BNF描述program–>function_listfunction_list–>functionfunction_list|

function–>FUNCidentifier(parameter_list)statement…voidParseFunction(){MatchToken(T_FUNC);ParseIdentifier();MatchToken(T_LPAREN);ParseParameterList();MatchToken(T_RPAREN);ParseStatement();}50例：递归下降子程序ParseFunction()（续）voidMatchToken(intexpected){if(lookahead!=expected){printf("syntaxerror\n");exit(0);}else//ifmatch,consumetokenandmoveonlookahead=yylex();}51予测分析程序的实现

表驱动予测分析程序模型

Input#总控程序预测分析表stack52带a0a1a2a3a4a5a6a7a8…an-1an有限控制器磁头识别程序的数学模型下推自动机53

上下文无关语言句型分析（识别）程序的数学模型下推自动机Pda=(K,Σ,f,H,h0,S,Z)K:有穷状态集S：开始状态Z：接受状态的集合Σ：有穷输入字母集H:有穷堆栈字母表h0:H中的初始符号f:K（Σ{})

H–>KH*Pda的一个组态是KΣ*

H中的一个（k,w,)k:当前状态，w:余留输入串，：栈中符号，最左边的符号在栈顶。Pda的一次移动用组态表示终止和接受的条件:

1.到达输入串结尾时，处在Z中的一个状态或2.某个动作序列导致栈空时

54

例：PdaP=({A,B,C),{a,b,c),f,{h,i},i

A,{})

f(A,a,i)=(B,h)f(B,a,h)=(B,hh)f(C,b,h)=(C,)f(A,c,i)=(A,)f(B,c,h)=(C,h)接受输入串aacbb的过程(A,aacbb,i)读a,popi,pushh,gotoB(B,acbb,h)读a,poph,pushhh,gotoB(B,cbb,hh)读c,poph,pushh,gotoC(C,bb,hh)读b,poph,push,gotoC(C,b,h)读b,poph,push,gotoC(C,,)55

例：表驱动予测分析程序G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a56

a+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a

预测分析表57表驱动予测分析程序分析算法

首先把’#‘然后把文法开始符号推入栈；把第一个输入符号读进b;

FLAG：=TRUE；

WHILEFLAGDOBEGIN

把栈顶符号上托出去并放在Ｘ中；

IFX

VtTHENIFX=bTHEN

把下一个输入符号读进b

ELSEERRORELSEIFX=‘#’THENIFb=‘#’THENFLAG:=FALSEELSEERRORELSEIF[X,b]={X–>

X1X2..XK}THEN把XK，XK-1,..,X1一一推进栈

ELSE

ERRORENDOFWHILE;STOP/*分析成功，过程完毕*／58分析输入串#a+a#的步骤栈内容栈顶符号当前输入余留串

M[X,b]1#EEa+a#E–>

TE’2#E’TTa+a#T–>

FT’3#E’T’FFa+a#F–>

a4#E’T’aaa+a#5#E’T’T’+a#T’–>

6#E’E’+a#E’–>

+TE’7#E’T+++a#8#E’TTa#T–>

FT’9#E’T’FFa#F–>

a10#E’T’aaa#11#E’T’T’#T’–>

12#E’E’#E’–>

13###59回溯的原因例G[S]:

S→xAy

A→ab｜a

若当前输入串为xay，首先构造的推导SxAy

匹配进一步推导对A可选择A→ab替换，得SxAy

xaby

xay

xaby

匹配xa都已匹配，当前面临输入符为y与b不能匹配，所以将输入串指针退回到a，对A的替换重新选用下一个产生式A→a进行试探，SxAy

xay输入串中当前符a得到匹配，指针向前移动到y，与语法树中y匹配，匹配成功。由于相同左部的产生式的右部开始符号相同而引起回溯。60例G”[S]:

(1)S→aAS(2)S→b(3)A→bAS(4)A→ε对输入串ab的试探推导，SaAS

用产生式(1)推导，a得到匹配，输入串指针移到b，再将A向下推导，而对A的产生式可选(3)或(4)，先试选(3)：SaASabAS…由于相同左部非终结符A的右部存在能*ε的情况且跟在它后面的符号会含有b61

5.3LL（1）分析程序的生成LL（1）文法一个文法G是LL（1）的，当且仅当对于G的每一个非终结符Ａ的任何两个不同产生式Ａ

αβ，下面的条件成立：１．FIRST（α）∩FIRST(β)=,也就是α和β推导不出以同一个终结符a为首的符号串；它们不应该都能推出空字．２.假若β=>*

，那么，

FIRST（α)∩FOLLOW（A）＝.也就是，若β=>*

.则α所能推出的串的首符号不应在FOLLOW(A）中．．

62FIRST集和FOLLOW集的定义设G=(VT,VN,P，S)是上下文无关文法FIRST（）={a|=>*a,a∈VT,,∈V*}

若=>*

ε则规定ε∈FRIST（）FOLLOW（A）={aS=>*A且a∈

FRIST（），∈V*，∈V+}

若S=>*

uA,且=>*

ε，则#∈FOLLOW(A)LL(1)文法63计算FIRST集1.若XV,则FIRST(X)={X}2.若XVN,且有产生式Xa…，则把a加入到FIRST(X)中;若X也是一条产生式,则把也加到FIRST(X)中.3.若XY…是一个产生式且YVN,则把FIRST(Y)中的所有非元素都加到FIRST(X)中;若XY1Y2…YK

是一个产生式,Y1,Y2,…,Y(i-1)都是非终结符,而且,对于任何j,1≤j≤i-1,FIRST(Yj)都含有(即Y1..Y(i-1)=>*

),则把FIRST(Yj)中的所有非元素和FIRST(Yi)中的所有元素都加到FIRST(X)中;特别是,若所有的FIRST(Yj

,

j=1,2,…,K)均含有,则把加到FRIST(X)中.

64计算FOLLOW集1.对于文法的开始符号S,置#于FOLLOW(S)中;2.若Ａ

αBβ是一个产生式,则把FIRST(β)\{}加至FOLLOW(B)中;3.若Ａ

αB是一个产生式,或Ａ

αBβ是一个产生式而β=>*

(即FIRST(β)），则把FOLLOW（A）加至FOLLOW（B）中．65G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a·各非终结符的FIRST集合如下：FIRST(E)=｛(,a｝FIRST(E′)=｛+,ε｝FIRST(T)=｛(,a｝FIRST(T′)=｛*,ε｝FIRST(F)=｛(,a｝·各非终结符的FOLLOW集合为：FOLLOW(E)=｛),＃｝FOLLOW(E′)=｛)，＃｝FOLLOW(T)=｛＋，)，＃｝FOLLOW(T′)=｛＋,)，#}FOLLOW(F)=｛*,＋，),#}

66G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>aE’–>+TE’|FIRST(+TE’)=｛+｝

FOLLOW(E′)=｛)，＃｝T’–>*FT’|FIRST(*FT’)=｛*｝

FOLLOW(T′)=｛+,)，＃｝F–>(E)|aFIRST((E))=｛(｝

FIRST(a)=｛a｝所以G[E]是LL（1）的67予测分析表构造算法1.对文法G的每个产生式Ａ

执行第二步和第三步；2.对每个终结符aFIRST()，把Ａ

加至[A,a]中，3.若FIRST()，则对任何bFOLLOW(A)

把Ａ

加至[A,b]中，4.把所有无定义的[A,a]标上“出错标志”。可以证明，一个文法G的予测分析表不含多重入口，当且仅当该文法是LL(1)的68

LL(1)文法的性质：

LL(1)文法是无二义的

LL(1)文法不含左递归695.4非LL(1)文法的改造消除左递归提左公因子将产生式Ａ

β|变换为：

Ａ

BB

β|70E→E+T｜TT→T*F｜FF→i｜(E)FIRST(E)=｛(,i｝FIRST(T)=｛(,i｝FIRST(F)=｛(,i｝消左递归

E–>TE’E’–>+TE’E’–>

E→T+E｜TT→F*T｜FF→i｜(E)FIRST(E)=FIRST(T)=FIRST(F)=｛(,i｝提左公因子E→T(+E｜)T→F(*T｜)

71消除左递归和提左公因子并不一定都能将非LL(1)文法改造为LL(1)的S→ifCtS|

ifCtSeSC→b提左因子

S→ifCtSAA→eS|

First集Follow集Sif#,eAe,#,eCbtM[A,e]={A→eSA→}72LL(1)分析中的一种错误处理办法发现错误1栈顶的终结符与当前输入符不匹配2非终结符A于栈顶，面临的输入符为a，但分析表M的M[A,a]为空“应急”恢复策略跳过输入串中的一些符号直至遇到“同步符号”为止。同步符号的选择1把FOLLOW(A)中的所有符号作为A的同步符号。跳过输入串中的一些符号直至遇到这些“同步符号”，把A从栈中弹出，可使分析继续2把FIRST(A)中的符号加到A的同步符号集，当FIRST(A)中的符号在输入中出现时，可根据A恢复分析73

a+*()#E(1)(1)E’(2)(3)(3)T(4)(4)T’(6)(5)(6)(6)F(8)(7)G[E]:(1)E–>TE’(2)E’–>+TE’(3)E’–>

(4)T–>FT’(5)T’–>*FT’(6)T’–>

(7)F–>(E)(8)F–>a

syn

syn74练习

1.对文法G［S］S→a|∧|(T)T→T,S|S

（1）给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。（2）对文法G进行改写，改写后的文法G’是否LL(1)?

若是，给出它的递归下降分析程序和预测分析表，并描述对输入串(a,a)#的分析过程。2.已知文法G[S]：S→MH|aH→LSo|εK→dML|εL→eHfM→K|bLM

判断G是否是LL(1)文法，如果是，构造LL(1)分析表。753.对于一个文法若消除了左递归，提取了左公共因子后是否一定为LL(1)文法?试对下面文法进行改写，并对改写后的文法进行判断。(1)A→aABe|aB→Bb|d(3)S→Aa|bA→SB

B→ab76review---parsingThesyntaxanalysisphaseofacompilerverifiesthatthesequenceoftokensreturnedfromthescannerrepresentvalidsentencesinthegrammaroftheprogramminglanguage.Therearetwomajorparsingapproaches:top-downandbottom-up.Intop-downparsing,youstartwiththestartsymbolandapplytheproductionsuntilyouarriveatthedesiredstring.Inbottom-upparsing,youstartwiththestringandreduceittothestartsymbolbyapplyingtheproductionsbackwards.77Inthetop-downparsing,webeginwiththestartsymbolandateachstep,expandoneoftheremainingnonterminalsbyreplacingitwiththerightsideofoneitsproductions.Werepeatuntilonlyterminalsremain.Thetop-downparseprintsaleftmostderivationofthesentence.Abottom-upparseworksinreverse.Webeginwiththesentenceofterminalsandeachstepappliesaproductioninreverse,replacingasubstringthatmatchestherightsidewiththenonterminalontheleft.Wecontinueuntilwehavesubstitutedourwaybacktothestartsymbol.Ifyoureadfromthebottomtotop,thebottom-upparseprintsoutarightmostderivationofthesentence.78

lookaheadsymbol.Thelookaheadsymbolisthenextsymbolcomingupintheinput.backtracking.Basedontheinformationtheparsercurrentlyhasabouttheinput,adecisionismadetogowithoneparticularproduction.Ifthischoiceleadstoadeadend,theparserwouldhavetobacktracktothatdecisionpoint,movingbackwardsthroughtheinput,andstartagainmakingadifferentchoiceandsoonuntiliteitherfoundtheproductionthatwastheappropriateoneorranoutofchoices.79predictiveparserandLL(1)grammarPredictiveparserisanon-backtrackingtop-downparser.Apredictiveparserischaracterizedbyitsabilitytochoosetheproductiontoapplysolelyonthebasisofthenextinputsymbolandthecurrentnonterminalbeingprocessed.Toenablethis,thegrammarmusttakeaparticularform.WecallsuchagrammarLL(1).Thefirst“L”meanswescantheinputfromlefttoright;thesecond“L”meanswecreatealeftmostderivation;andthe1meansoneinputsymboloflookahead.80recursive-descentThefirsttechniqueforimplementingapredictiveparseriscalledrecursive-descent.Arecursivedescentparserconsistsofseveralsmallfunctions(procedures),oneforeachnonterminalinthegrammar.Asweparseasentence,wecallthefunctions(procedures)thatcorrespondtotheleftsidenonterminaloftheproductionsweareapplying.Iftheseproductionsarerecursive,weendupcallingthefunctionsrecursively.81Table-drivenLL(1)parsing

Inarecursive-descentparser,theproductioninformationisembeddedintheindividualparsefunctionsforeachnonterminalandtherun-timeexecutionstackiskeepingtrackofourprogressthroughtheparse.Thereisanothermethodforimplementingapredictiveparserthatusesatabletostorethatproductionalongwithanexplicitstacktokeeptrackofwhereweareintheparse.82Howatable-drivenpredictiveparserworks

Wepushthestartsymbolonthestackandreadthefirstinputtoken.Astheparserworksthroughtheinput,therearethefollowingpossibilitiesforthetopstacksymbolXandtheinputtokennonterminal

a:1.IfX=aanda=endofinput(#):parserhaltsandparsecompletedsuccessfully2.IfX=aanda!=#:successfulmatch,popXandadvancetonextinputtoken.Thisiscalledamatchaction.3.IfX!=aandXisanonterminal,popXandconsulttableat[X,a]toseewhichproductionapplies,pushrightsideofproductiononstack.Thisiscalledapredictaction.4.Ifnoneoftheprecedingcasesappliesorthetableentryfromstep3isblank,therehasbeenaparseerror83Thefirstsetofasequenceofsymbolsu,writtenasFirst(u)isthesetofterminalswhichstartallthesequencesofsymbolsderivablefromu.Abitmoreformally,considerallstringsderivablefromubyaleftmostderivation.Ifu=>*v,wherevbeginswithsometerminal,thatterminalisinFirst(u).Ifu=>*,then

isinFirst(u).84Thefollowsetofanonterminal

AisthesetofterminalsymbolsthatcanappearimmediatelytotherightofAinavalidsententialform.Abitmoreformally,foreveryvalidsententialformS=>*uAv,wherevbeginswithsometerminal,thatterminalisinFollow(A).85CalculatingfirstsetTocalculateFirst(u)whereuhastheformX1X2...Xn,dothefollowing:1.IfX1isaterminal,thenaddX1