编译原理第4章 语法分析 自上而下_第1页
编译原理第4章 语法分析 自上而下_第2页
编译原理第4章 语法分析 自上而下_第3页
编译原理第4章 语法分析 自上而下_第4页
编译原理第4章 语法分析 自上而下_第5页
已阅读5页,还剩79页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

4.1语法分析——自上而下分析内容语法分析的任务与分类自上而下分析面临的问题递归下降分析程序构造LL(1)分析法句型、句子、语言的定义句型有文法G,若Sx,且x∈V*,则称x是文法G的句型。句子有文法G,若Sx,且x∈VT*,则称x是文法G的句子。例:G:S→0S1,S→01S0S100S11000S11100001111上下文无关文法的句型的推导最左(最右)推导:在推导的任何一步αβ,其中α、β是句型,都是对α中的最左(右)非终结符进行替换最右推导被称为规范推导。由规范推导所得的句型称为规范句型句型的分析句型分析就是识别一个符号串是否为某文法的句型,是某个推导的构造过程。在语言的编译实现中,把完成句型分析的程序称为分析程序或识别程序。分析算法又称识别算法。从左到右的分析算法,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号。

语法分析的任务:

对任一给定w∈VT*,判断w∈L(G)?

语法分析器:按照产生式规则,做识别w的工作词法分析器语法分析器编译程序后续部分符号表源程序单词符号取下一个单词符号语法分析语法分析器在编译程序中的地位分析算法分类:自上而下分析法(自顶向下):

从文法的开始符号出发,反复使用各种产生式,寻找与输入符号匹配的最左推导。自下而上分析法(自底向上):

从输入符号串开始,逐步进行归约(最右推导的逆过程),直至归约到文法的开始符号。语法分析算法分类语法分析方法 递归子程序 自顶向下 预测分析(LL(1)分析器) 算符优先 自底向上 LR(0)、SLR(1),LR(1)、LALR(1)

自上而下语法分析的一般过程从文法的开始符号出发,反复使用各种产生式,寻找与输入符号匹配的最左推导。

如果能够推导出,则该输入串是给定文法的句子;

如果不能推导出,则该输入串不是给定文法的句子。主旨:从文法开始符号出发,自上而下的为输入串建立一棵语法树自顶向下语法分析要解决的关键问题假定要被代换的最左非终结符号是B,且有n条规则:B→A1|A2|…|An,那么如何确定用哪个右部去替代B?例1:文法G(S):S→pAS→qBA→cAdA→a输入串W=pccadd相应的语法树:SpApcAdpccAddpccaddSPASPAcdAcdASPAcdAcdASPAcdAaS→pAS→qBA→cAdA→aW=pccadd文法G(S):S→pAS→qBA→cAdA→a该文法的特点:(1)每个产生式的右部都由终结符号开始;(2)如果两个产生式有相同的左部,则它们的右部由不同的终结符开始。对于这样的文法,其推导过程可以根据当前的输入符号决定选择哪个产生式往下推导,因此,分析过程是唯一确定的。ScAdabaS—>cAdA—>abA—>a输入串w:文法G:IP分析过程:1)w——输入串;IP—>‘c’S——扩充;cad2)α=cAd;与IP—>‘c’匹配;3)IP—>‘a’A扩展,第一式ab,IP—>‘a’与ab匹配;IP—>‘d’,但d与b不匹配;4)报告失败,撤销A的子树,回到A;指针回退到IP—>‘a’;A还有替换式未试过,而又可能匹配;语法树的形成过程匹配结束,语法树形成例:文法G为:S→xAy|z,A→**|*输入串=#x*y#自上而下的分析过程:(1)S有两个侯选式“xAy”和“z”,侯选式“xAy”与输入串“x*y”相匹配,故推导:SxAy。 (2)非终极符A也有两个侯选式“**”和“*”,若选第一个侯选式“**”对句型进行推导,则得:SxAyx**y,不相匹;推导回溯到句型“xAy”;再用非终极符A的第二个侯选式“*”进行推导,即:SxAyx*y。且都是终极符,输入串“x*y”是所给文法的句子。过程调用示意图描述句型的推导过程例4.1

文法G41=({P,U},{a},{P→aU,U→P|},P),L(G41)={an|n≥1}例4.2

文法G42=({P,B},{a},{P→B|a,B→Pa},P),L(G42)=L(G41)例4.3

文法G43=({P},{a},{P→aP|a},P),L(G43)=L(G41)G41过程调用图

输入串为#aa#文法G42=({P,B},{a},{P→B|a,B→Pa},P)

过程调用图--输入串为#aa#

首先,是文法的左递归问题。一个文法是含有左递归的,如果存在非终结符P的产生式P⇒Pα含有左递归的文法将使上述的自上而下的分析过程陷入无限循环。即,当试图用P去匹配输入串时,我们会发现,在没有识别任何输入符号的情况下,又得重新要求P去进行新的匹配。因此,使用自上而下分析法必须消除文法的左递归性。自上而下分析面临的问题其次,由于回溯,如果走了一大段错路,最后必须回头,那么,就应把已经做的一大堆语义工作(指中间代码产生工作和各种表格的簿记工作)推倒重来。回溯会引起时间和空间的大量消耗应设法消除回溯。最后,如果被识别的语句是错的,算法无法指出错误的确切位置。问题解决--消除左递归1.一个文法含有下列形式的产生式时,a)AAAVN,V*b)ABBAA,BVN,

,V*

称为左递归文法。其中a)是直接递归,b)是间接递归。如果一个文法是左递归时,则不能采用自顶向下分析法。例:文法SSaSb是直接左递归所产生的语言是:L={ban|n≥0}例:文法为:AaBABbBAcBd是间接左递归※消除左递归的方法:(1)消除直接左递归:方法:改为右递归。保持其语言不变。直接左递归的消除候选式:A->Aα|βββαβααβααα……A->βA’A’->αA’|ε消去直接左递归后:E—>TE′ E′—>+TE′|ε T—>FT′ T′—>*FT′|ε F—>(E)|i例4.2文法: E—>E+T|TT—>T*F|FF—>(E)|i消除方法:若:A—>Aα|β

,修改为

A—>βA′A′—>αA′|ε一般地,若文法的产生式为:P→P1|P2|……|Pn|1|2|……|m其中:j不以P打头,i非空(1≤j≤m,1≤i≤n);消除左递归后,为:P→1P'|2P'|……|mP'P'→1P'|2P'|……|nP'|

(2)消除隐含的左递归要求文法中不含回路,即无AA的推导①给文法VN中的符号一个排序:A1,A2,…,An;for(i=1;i<=n;i++){for(j=1;j<=i-1;j++){把形如Ai→Aj的规则改成 Ai→1|2|…|k 其中:Aj→1|2|…|k是关于Aj的所有规则;}/*替换为直接左递归*/ 消除关于Ai规则的直接左递归; }; 化简所得到的文法(去掉无用产生式),结束。+例子G46:S→Qc|cQ→Rb|bR→Sa|a有推导:S⇒Qc⇒Rbc⇒Sabc,存在左递归。按R、Q、S排序,执行算法①得:i=1,j从1至0,R的产生式R→Sa|a无直接左递归,无需消除直接左递归。i=2,j从1至1,R的产生式代入Q的产生式得:Q→Sab|ab|b,无直接左递归。i=3,j从1至2,j=1,S的候选式不含R,所以无需替换;j=2,S的候选式含Q,将Q→Sab|ab|b代入S的候选式得: S→Sabc|abc|bc|c再消除直接左递归得: S→abcS'|bcS'|cS' S'→abcS'|ε消除无用产生式:Q→Sab|ab|b,R→Sa|a,得文法G47: S→abcS'|bcS'|cS' S'→abcS'|ε 文法G47对应的正规式:V1=(abc|bc|c)(abc)*。S→Qc|cQ→Rb|bR→Sa|a消除隐含的左递归算法与非终极符排序方法无关;例如,文法G46按S、Q、R排序所得文法对应正规式相同。…………..=bc(abc)*(abc)|c(abc)*(abc)|(abc)*(abc)|bc|c=bc(abc)+|c(abc)+|(abc)(abc)*|bc(abc)0|c(abc)0=bc((abc)+|(abc)0)|c((abc)+|(abc)0)

|(abc)(abc)*=bc(abc)*|c(abc)*|(abc)(abc)*=(abc|bc|c)(abc)*=V1例如,有产生式: 语句->if条件then语句else语句 |while条件do语句 |begin语句表end

若要寻找一个语句,那么关键字if,while,begin就提示某个替换式是唯一的替换式。2、消除回溯、提左公因子回溯原因

若当前符号=a,下一步要展开A,而A->α1|α2|…|αm,那么,要知道哪一个αi是获得以a开头的串的式。怎样选择αi? ①以a为头的αi如果只有一个,则替换唯一;

②若以a为头有多个αi的,则替换不唯一,需要回溯,这是文法的问题,应该变换文法。解决办法--提取左公因子

要求文法的任一非终极符的侯选式之间无左公因子,使相匹的侯选式是唯一的,提取左公因子的方法是增加非终结符,改写文法。提取左公因子--例如:S→ifBthenSelseS|ifBthenS其中,S表示语句,if、then、else为终极符。提取左公因子,增加非终结符S3,产生式改成:S→ifBthenSS3S3→elseS|经过反复提取左因子,就能够把每个非终结符(包括新引进者)的所有候选首符号变成为两两不相交。为此付出的代价是,大量引进新的非终结符和ε-产生式。4.1.2递归下降分析程序构造 在不含左递归和每个非终结符的所有候选式的终结首符集都两两不相交条件下,构造一个不带回溯的自上而下分析程序,该分析程序由一组递归过程组成,每个过程对应文法的一个非终结符。这样的一个分析程序称为递归下降分析器。递归下降分析器

文法G消除左递归得:E→TE'E'→+TE'|T→FT'T'→*FT'|F→(E)|i给出#i+i*i#的最左推导:过程调用程序示意图

E=>TE'=>FT'E'=>iT'E'=>iE'=>i+TE'=>i+FT'E'=>i+iT'E'=>i+i*FT'E'=>i+i*iT'E'=>i+i*iE'=>i+i*i当前句型应选候选式当前输入符号余下的符号ETE’ii+i*i上述分析方法的实现:

①每一非终结符对应一个递归子程序;在只生成有限个串的文法,过程是无须递归的,而对生成无数个串的文法,递归是不可避免的;

②递归子程序:是一个过程,一旦发现它的某个候选式与输入串匹配,它就按此式扩充(语法树),指针移过已匹配子串。否则,返回error,保持原来的(语法树)和指针不变。使用记号:sym存放读单词子程序读来的单词,称为当前输入符号,进入程序前,输入串的第一个符号应读入sym中;使用过程:advance()将读单词子程序的单词指针下移一个单词位置,且读出指针所指的单词,存入sym。

将过程调用示意图写成程序,程序称为递归下降分析器。E'→+TE'|

voidE'(void){if(sym=='+'){advance();T();E'();}}F→(E)|i

voidF(void){if(sym=='i')advance();

else

if(sym=='('){advance();E();if(sym=')')advance();

elseerror();}

elseerror();}sym存放读单词子程序读来的单词,称为当前输入符号;advance将指针下移一个单词位置,且读出单词,存入sym。过程调用程序示意图

问题:用递归子程序描写递归下降分析 器,要求实现该编译系统的语言允 许递归。改进:使用一张分析表和一个栈同样可实现递归下降分析,用这种方法实现的语法分析程序叫预测分析程序。4.3.1LL(1)分析器LL(1)分析法LL(1)分析法又称预测分析法,是一种不带回溯的非递归自上而下分析法。

LL(1)的含义:第一个L表明自左至右扫描输入串;第二个L表明最左推导;1表明向右查看一个符号。类似地,可有LL(k)文法,即向前查看k个符号才能确定选用哪个产生式,不过LL(k)(k>1)在实际中极少使用。LL(1)分析器LL(1)分析法的基本思想:

根据输入串的当前输入符确定选用某一个产生式进行推导,当该输入符与推导的第一个符号相同时,再取输入串的下一个符号,继续确定下一个推导应选的产生式,如此下去,直到推出被分析的输入串为止。

LL(1)分析器组成:一张LL(1)分析表(预测分析表)

一个分析栈(后进先出)

一个控制程序(表驱动程序)组成。a1a2…ai…an#分析表M控制程序输入串:栈顶#x1…xj输出分析栈LL(1)分析器表项:M[A,a]A的产生式待分析的符号串,它以“#”作为结束标志。存放分析过程中的文法符号。分析开始时栈底先放一个“#”对LL(1)分析器说明如下:

(1)输入串是待分析的符号串,它以“#”作为结束标志。

(注:#∈VT但不是文法符号,是由分析程序自动添加的)(2)分析栈STACK存放分析过程中的文法符号。分析开始时栈底先放一个“#”,再压入文法开始符;当分析栈中仅剩“#”且输入串指针指向串尾的“#”时,分析成功。

(3)分析表用一个矩阵M(二维数组)表示,它概括了文法的全部信息。矩阵的每一行与文法的一个非终结符相关联,而每一列与文法的一个终结符或“#”关联(见表4-2)。分析表元素M[A,a]中的内容为

一条A的产生式(比如:A→aB)表明当A面临输入符a时应采用的候选式;当元素内容为空时,表明A不应面临输入符a,即输入串含语法错误。(4)总控程序根据分析栈栈顶符号x和当前输入符a查表决定分析器的动作:①若x=a=“#”,即STACK栈顶符号为“#”,当前输入符号为“#”,则分析成功。②若x=a≠“#”,即栈顶符号x与当前输入符a匹配,则将x从栈顶弹出,输入串指针后移,读入下一个符号存入a,继续对下一个字符进行分析。

③若x为非终结符A,则查分析表M[A,a]:i.若M[A,a]为一产生式,则A自栈顶弹出,M[A,a]中产生式的右部符号逆序压栈;若M[A,a]为A→ε,则只将A自栈顶弹出。ii.若M[A,a]为空,则发现语法错误,调用出错处理程序进行处理。控制程序描述如下:1.将“#”和文法开始符依次入栈Stack;2.把第一个输入符读入a;do{pop(Stack,x)//弹出栈顶放入x中;

if(x∈VT){

if(x==a)//x=a≠“#”,将下一输入符读入a;

elseerror();}

elseif(M[x,a]==“x→y1y2…yk”){把y1y2…yk按逆序入栈;若M[x,a]为X->ε,ε不入栈;输出“x→y1y2…yk”;}

elseerror();

}while(x!=“#”)3.分析成功,完毕!//x=a=“#”分析表格式i+*()#EE—>TE′E—>TE′E’E′—>+TE′E′—>εE′—>εTT—>FT′T—>FT′T’T′—>εT′—>*FT′T′—>εT′—>εFF—>iF—>(E)E—>TE′ E′—>+TE′|εT—>FT′ T′—>*FT′|εF—>(E)|i返回

i+i*i的最左推导:E=>TE’=>FT’E’=>iT’E’=>iE’=>i+TE’=>i+TE’=>i+FT’E’=>i+iT’E’=>i+i*FT’E’=>…i+i*iE—>TE′ E′—>+TE′|εT—>FT′ T′—>*FT′|εF—>(E)|i例按LL(1)分析法,分析句子#i+i*i#栈输入输出1#Ei+i*i#2#E′Ti+i*i#E—>TE′3#E′T′Fi+i*i#T—>FT′4#E′T′ii+i*i#F—>i5#E′T′+i*i#6#E′+i*i#T′—>ε7#E′T′++i*i#E′—>+TE′#E′T′i*i##E′T′Fi*i#T—>FT′M[E,i]=E—>TE′M[T,i]=T—>FT′左部出栈,右部反序压栈!M[F,i]=F—>i匹配,i出栈输入串指针后移XaEiTiFiii栈输入输出10#E′T′ii*i#F—>i11#E′T′*i#12#E′T′F**i#T′—>*FT′13#E′T′Fi#14#E′T′ii#F—>i15#E′T′#16#E′#T′—>ε##E′—>ε

有:X=a=#,分析成功。

iiXaT

′i**FiiiT’#E’###结论:①输出的产生式就是最左推导的产生式。栈中存放产生式右部,等待与α匹配;②当栈顶X=a时,表指出如何扩充语法树,出错能马上发现。实质:栈:部分句型,句型右部,还未得到推导的 表:指出VN按哪一条扩充,依赖于VTF—>(E)F—>iFT′—>εT′—>εT′—>*FT′T′—>εT′T—>FT′T—>FT′TE′—>εE′—>εE′—>+TE′E′E—>TE′E—>TE′E#)(*+ii+i*i#:+E΄TFT΄*FT΄iiεεETE΄FT΄iε上述分析过程生成的语法树:分析表的构造分析表格式:i+*()#EE—>TE′E—>TE′E′E′—>+TE′E′—>

εE′—>

εTT—>FT′T—>FT′T′T′—>

εT′—>*FT′T′—>

εT′—>

εFF—>iF—>(E)思路:

1)把产生式填到何处?

2)按A?

将产生式分为两种: 一种是:Aa…

另种是:Aε2.LL(1)分析表的构造

LL(1)分析器中除分析表因文法的不同而不同外,分析栈、控制程序都相同。因此构造一个LL(1)分析器实际上就是构造文法的LL(1)分析表。构造分析表M,需预先定义FIRST集和FOLLOW集。假定是文法任一符号串,(VT∪VN)*

先要构造两个与G有关的集合:FIRST(α)和FOLLOW(A);

1)若有文法G,α∈V*,S,A∈VN定义4.1FIRST(α)={a|αa…,a∈VT}

特别的,若α

ε,规定ε∈FIRST(α)定义4.2FOLLOW(A)={a|S

αAaβ,a∈VT,α,β∈V

*}若S…A成立,则规定句子的右界符#∈FOLLOW(A)2)构造FIRST(α)先构造FIRST(X),X∈V。

连续使用以下规则,直至再无终结符,或ε加入任一FIRST集为止①若X∈VT,则FIRST(X)={X}②若X∈VN,且X->aα,则FIRST(X)={a}∪FIRST(X)

X->ε,则FIRST(X)={ε}∪FIRST(X)③若X∈VN,X->Y…,Y∈VN,则FIRST(Y)\{ε}FIRST(X)进而:若X->Y1Y2…Yi-1Yi…Yk,Yj∈VN,1≤j≤i-1

ε∈FIRST(Yj),即Y1Y2…Yi-1

ε,则特别,若Y1Y2…Ykε,则ε∈FIRST(x)。

2)先构造FIRST(X),X∈V。若x∈(VN∪VT)*,不妨设x=x1x2x3…xn

①FIRST(X1)的非ε终结符加入FIRST(α)FIRST(x)=FIRST(x1)-{ε};

②若ε∈FIRST(X1), 则FIRST(X2)的所有非ε终结符加入FIRST(α)③若ε∈FIRST(X1),ε∈FIRST(X2), 则FIRST(X3)的所有非ε终结符加入FIRST(α)最后,若ε∈FIRST(Xi),i=1..n,则{ε}加入FIRST(α)即:例如,已知文法的产生式为: X→Y1Y2Y3Y4Y5 Y1→a|ε Y2→b|ε Y3→c|ε Y4→d|ε Y5→e|ε求FIRST(X)的过程如下:(1)FIRST(X)={};(2)for(i=1;I<=5;I++) FIRST(X)=FIRST(X)∪FIRST(Yi)\{ε};(3)if(Y1Y2Y3Y4Y5ε)FIRST(X)=FIRST(X)∪{ε};计算结果:FIRST(X)={a,b,c,d,e,ε}3)构造FOLLOW(A)①置初值:对任一A∈VN,置FOLLOW(A):={};若A是文法的开始符号,则置FOLLOW(A):={#},“#”是句子右界符;②若有A→αBβ,B∈VN,则置FOLLOW(B)=FOLLOW(B)∪FIRST(β)-{ε};③若有产生式A→αB或A→αBβ,且有βε,则置FOLLOW(B)=FOLLOW(B)∪FOLLOW(A);④重复②、③,直至每个FOLLOW(A)不扩大为止。4)例4.6已知文法G:E—>TE′ T′—>*FT′|εE′—>+TE′|εF—>(E)|iT—>FT′求它的FIRST(α),FOLLOW(A)FIRST集的构造:FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}①#属于FOLLOW(S)②若存在A->αBβ,则FIRST(β)FOLLOW(B),除ε外由①得:FOLLOW(E)={#}由②得:E—>TE′则FIRST(E’)\{ε}FOLLOW(T), 即FOLLOW(T)={+}T—>FT′则FIRST(T’)\{ε}FOLLOW(F), 即FOLLOW(F)={*}F—>(E)则FIRST())∈FOLLOW(E), 即FOLLOW(E)={#,)}

FOLLOW集的构造:FIRST(T’)={*,ε}FIRST(E’)={+,ε}即FOLLOW(F)={*,,,}③若有A->αB,或A->αBβ且ε∈FIRST(β),则FOLLOW(B)FOLLOW(A)FOLLOW(E)={),#}FOLLOW(T)={+}FOLLOW(F)={*}由③得:E—>TE′得FOLLOW(E)FOLLOW(E’),即FOLLOW(E’)={,})

#

E—>TE′且E’—>ε得FOLLOW(E)FOLLOW(T),即FOLLOW(T)={+,,})

#

T—>FT′得FOLLOW(T)FOLLOW(T’),即FOLLOW(T’)={,,}T—>FT′且T’—>ε得FOLLOW(T)

FOLLOW(F),)

#

+

)

#

+

FIRST(E)=FIRST(T)=FIRST(F)={(,i}FIRST(E’)={+,ε}FIRST(T’)={*,ε}FOLLOW(E)=FOLLOW(E’)={),#}FOLLOW(T)=FOLLOW(T’)={+,),#}FOLLOW(F)={*,+,),#}最终构造结果:注意:FIRST集针对终结符,非终结符,候选式而构造;FOLLOW集只对非终结符构造。Follow(S)=Follow(A)=Follow(B)=Follow(C)=Follow(D)=文法为:SAB|bCAε|bBε|aDCAD|bDaS|c思考:求FOLLOW集SAB

BbBAAaDFollow(S)={#}Follow(A)={a,#,c}Follow(B)={#}Follow(C)={#}Follow(D)={#}文法为:SAB|bCAε|bBε|aDCAD|bDaS|cS为开始符号,加入#SABA

AABAaDbCbADbAc69693构造分析表基本思想是:当文法中某一非终结符呈现在栈顶时,根据当前的输入符号,分析表应指示要用该非终结符里的哪一条规则去匹配输入串(即进行下一步最左推导)根据这个思想,不难把构造分析表算法构造出来.终结符号非终结符号i+i*i的最左推导:E=>TE’=>FT’E’=>iT’E’=>iE’=>i+TE’=>i+TE’=>i+FT’E’=>i+iT’E’=>i+i*FT’E’=>…i+i*i构造分析表算法:输入——G文法,输出——分析表M①对文法的每一个A->α,做②和③;②对于任a∈FIRST(α),把A->α加进M[A,a]③若ε∈FIRST(α),则把A->α加进M[A,b],b∈FOLLOW(A);

④若M[A,a]为空时,则填ERROR。上述方法构造的分析表称为LL(1)分析表。若LL(1)分析表无重复定义(即任一M[A,a]值唯一),则相应的文法为LL(1)文法。例:

E—>TE′填法:∵ FIRST(TE′)=FIRST(T)={(,i}∴ M[E,(]={E—>TE′} M[E,i]={E—>TE′}

E—>+TE′填法:

M[E,+]={E—>+TE′}E′—>ε填法:∵ FOLLOW(E′)={),#}∴ M[E′,)]={E′—>ε} M[E,#]={E′—>ε}定理4.1、LL(1)文法的条件LL(1)文法一个文法G,若它的分析表M不含多重定义入口,则称它是一个LL(1)文法。(1)FIRST(α)∩FIRST(β)=φ(2)若βε,则FIRST(α)∩FOLLOW(A)=Φ

文法G是LL(1)的,则对于G的每一个非终结符A的任何两个不同产生式A->α|β,有:说明: 使用LL(1)文法,一定可以实现不带回溯的自上而下分析;①对A->α|β,若条件(1)不成立, 则 FIRST(α)∩FIRST(β)≠φ,假设,FIRST(α)∩FIRST(β)={a}

那么,当A面临输入符号a,而a同时属于FIRST(α)和FIRST(β),则分析无法继续进行下去,因为不能确定用哪一个候选式可以保证一定能够得到匹配而不进行回溯。

实质就是分析表的M[A,a]中包含两条候选式 A->α A->β反之,分析表的M[A,a]中只包含一条候选式则意味着可以进行确定性的无回溯的分析。②对A->α|β,若βε,且条件(2)不成立, 则 FIRST(α)∩FOLLOW(A)≠Φ假设,FIRST(α)∩FOLLOW(A)={a} 那么,当A面临输入符号a时, 若选候选式A->α,则由于a∈FIRST(α)可以使a一定得到匹配;同时,若选候选式A->β也可以满足要求,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论