编译器语法分析程序功能

11T设给定文法G和字符串（句子）(∈V*T2即检查、判定2 .44 设有文法G和输入串G：S→aA|A→BaA|B→+|–|*| S=>aA=>aBaA=>a*aA=>5=> => =$5 上

下 77.10进行匹配，直到归约到文法G10$S→aA|A→BaA| B→+|-|*| S=>aA=>=>aBaBaA=>=>aBa+a=>a*a+a=

$ *a+aA→BaA|B→+|–|*| S=>aA=>=>aBaBaA=>aBaBε=>aBa+a=>a*a+a=

*a+a$G1313定义4.1是G的一个句型，若有S*>A且A+>,则相对于A的短语。定义4.2是G的一个句型，若有S*>A且A=>,则相对于A1515 对$S=>aAcBaPcBaabcB=>也是相对于A对$存在推导S=>aAcB=>aPcB=> cB=>ababS=>aAcB=>aAcd=>aPcd=>S 1919 设有如下文法G和字符串$=S→cAdA→ab|a

$=$= 规则A→ab失败SS

$= $= 分析的本质是一种带回溯的自上而下分析，是Ch4语法分析 不确定的自上而下分析法 I→I0|Ia|$： … …

一.文法的直接左递归表现在其含有A→A(∈(VT∪VN)*)形式的产生式规则，则在语法分析的最左推导中会呈现A=>A……的间接左递归文法会呈现A>A…… P的规则改写成如下等价的非直接左递归P′→α P→Pα| P=> E→E+E|E*E|（E）|E→E+T| |E→E+T| |E→TE′E→TE′T→FT′T′→*FT′|εP→P1|P2|…|Pn|β1|β2|…|P的规则改写成如下等价的非直接左PP→β1P′|β2P′|…P′→1P′|2P′|…| I→I0|Ia|Ib|a|II→aI'|bII'→0I'|aI'|bI'有些文法表面上不具有左递归性，却隐含A→Ba|B→Cb|C→Ac|A=>Ba=>Cba=>B=>Cb=>Acb=>C=>Ac=>Bac=>把间接左递归文法改写为直接左递归算法4.1②for(i=1;i=n;i++for(j=1;j=i-1;j++{Ai}A|aB|bC|cB→BA，A的规A→Acba│cba│ba│aA→A′→C→Ac|cA→cbaA′|baA′|C→Ac|cA→cbaA′|baA′|aA′A′→cbaA′|ε二.P1|2|…| 在自上而下分析中，对于一个VN进行推导继而试图去匹配句子剩余符号时，若VN含先选1，与当前输入i匹配，若成功，2FIRST()={a|>a……，a∈VTε,如果对文法G的一个产生式A，设AA→1|2|…|i如果它的每个候选式i均不存在>εi S→Ap|A→a|B→b| FIRST(Ap)FIRST(Bq)

{a,c{b,dFIRST(Ap∩FIRST(Bq FIRST(a)={aFIRST(cA)={cFIRST(a∩FIRST(cA FIRST(b)={bFIRST(dB)={dFIRST(b∩FIRST(dBFIRST(Ap)={a,cFIRST(Bq)={b,dFIRST(a)={aFIRST(cA)={cFIRST(b)={bFIRST(dB)={dS $:cap $: $:FIRST(Ap)={a,cFIRST(Bq)={b,dFIRST(a)={aFIRST(cA)={cFIRST(b)={bFIRST(dB)={dS $:acaAFIRST(i)的相互两个彼此交集≠Φ，是因为i中有公共左因子，可以A→δβ1|δβ2|…|δ(β1|β2|…|A′→β1|β2|…|A→11|12|…|1n|21|22|…|21(1|2|…|n)

2(1|2|…|m)A′→β1|β2|…|βnA"→1|2|…|Recursive-DescentParser) 设有文法G(E)E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|iEE({T;T′({if(c==‘*’){n++;F;}T({F;T({F;F({if(c==‘i’)n++;if(c==‘(’ n++;if(c==‘)’)else}else}E′({if{n++;T;}}E→E→T→E′→T′→$1=i+i*i

i+i*ii+i*ii+i*i#i+i*i#i+i*i#i+i*i

i+i*i$1=（+i

（+i（+i（+i（+i（+iF→（E）| （+i为每个产生式Ax1x2xn建立从初态到终态的路径，弧标记为x1x2„**其中：xiE→50E′→50 入t状态; 分析器进入A的开始状态，输入指针不变，到达A的终态时返回到t状态;若5151E→TE′ E→TE′E′→+TE′|εT→FT′T′→*FT′|εF→（E）|iT

55 55

存放分析过程中的文法符号（待匹配和已SS# 文

M(A1,a1)

…法

#a1a2…an若当前分析栈顶符号Ｘ和ai都是文法的终结X＝ai＝“＃”，表示分析成功，停止分析②X＝ai≠“＃”，则将Ｘ从分析栈顶退掉，p③X≠aiM(X,aiXM(X,ai # ###

# # # #E’T’ # # ***ii## $ FIRSTG，若G中产生式形如A→且没有=>ε的情况，则产生LL(1)分析表的预测函数：M(A,aA→ S→Ap|A→a|B→b| FIRST(Ap)∩ FIRST(a对B FIRST(bFIRST(dB)6464文法：S→Ap| A→a| B→b|对B BS→ApS→Bq 若是ε∈FIRST()aFIRST(S>…Aa…，a∈VT｝*句型中，能够紧跟在非终结符A之后的一1FOLLOW文法G中的每一个A∈ＶN，为构造FOLLOW(A)，可②若文法G中有形如A→αBβ的规则，且β≠ε，则将FIRST(β)中的一切非ε符号加入FOLLOW(B)；68GA→αB，A→αBβ的规则且ε∈FIRST(β68 S→AB| A→ε| B→ε|C→AD| D→aS|FOLLOW(S)=FOLLOW(A)={a,c,#FOLLOW(B)=FOLLOW(C)=FOLLOW(D)==>=>=> S→AB| A→ε| B→ε|C→AD| D→aS|FOLLOW(A)=FOLLOW(B)=FOLLOW(C)=

{a,c,#=>=>=>则对情况的文法确定惟一候选：A1|12不同时推出为ε时，设2M(Ab)Aεa∈FIRST(1M(A,a)A1；M(Ab)Aε FOLLOW(A)＝｛a│SS>„Abb设S>„αγAbβ„由于对文法规则存在A→αε∈FIRST(α)，当α=>εA=>ε*>„αγAbβ„Ｍ(A,bA→ε(算法4.4LL(1输入：文法G；GFIRSTFOLLOW集合输出：文法G的LL(1)分析表for文法G的每个产生式A→γ1|γ2| /*G a∈FIRST(γi置Ｍ(AaA→γiif Ab}} E→E’→+TE’│εT→FT’F→(E)│i对E：FIRST(TE)=对T：FIRST(FT’)=对F：FIRST((E))=FIRST(i)

{(，i{(，i{( {i

∩=E→ E’→+ T→T’→ F→(E)│对EFIRST(+TEFIRST(ε)={ε}FOLLOW(E’)={#,)}满足：ε∪对T：FIRST(*FT’)*#)FIRST(ε)={ε}#)77满足：*}ε∪77T’T’FE→E’→+TE’│εT→FT’F→(E)│iEE’ E T FF→F→ S→iCtSS’│aＣ→b

iifC：e,t：elsethen FIRST(FIRST(eS)={eFIRST(ε)={ε}F