计算机编译精选文档.ppt

计算机编译本讲稿第一页，共一百二十六页2.词法分析器和语法分析器的关系（1）词法分析作为单独的一遍输入串词法分析器语法分析器单词流本讲稿第二页，共一百二十六页（2）词法分析作为子程序输入串词法分析器语法分析器符号表取下一单词返回下一单词本讲稿第三页，共一百二十六页二.单词的种类 (1)标识符:用来命名程序中出现的变量、数组、函数、过程、标号等 (2)基本字:也可称关键字或保留字,如if、while、for、do、goto等 (3)常数:各种类型的常数,如216、3.14159、TRUE等 (4)运算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等本讲稿第四页，共一百二十六页三.单词的编码1.单词的输出形式二元式 (单词类别,单词的属性)区分单词所属的类(整数编码)单词的值本讲稿第五页，共一百二十六页2.单词类别的划分u基本字、运算符、界符:一字一码u标识符:单列一种u常数:按类型分类本讲稿第六页，共一百二十六页四.词法错误检查u非法字符u不合规则的常数u标识符前缀为保留字本讲稿第七页，共一百二十六页五.词法分析器的生成1.词法分析技术超前搜索 为了判定一个单词符号的类别,必须扫描到某一地方,而该单词符号并没有这么长,这种扫描方式叫做“超前搜索”。如：DO100I=1,10 DO100I=1.10 IF(5.EQ.M)GOTO 100 IF(5)=100本讲稿第八页，共一百二十六页2.状态转换图u有限的有向图u有限边上标记字符u一个初态u若干终态本讲稿第九页，共一百二十六页例:某语言允许 标识符、基本字、数字串、+、-、*、*、=、=、=、:=、：、；本讲稿第十页，共一百二十六页0412356789开始空白字母/数字字母非字母数字数字非数字+-*非*数字本讲稿第十一页，共一百二十六页101112=1314151617其它=181920：其它=其它2122=；其它*本讲稿第十二页，共一百二十六页 3.实现方法 每个状态结对应一小段程序u分支状态if或case语句u循环状态while语句u终态return语句 4.一个示意算法本讲稿第十三页，共一百二十六页start:token:=;getchar;getnb;case character of az:begin while letter or digit do begin concatenate;getchar end;retract;c:=reserve;if c=0 then begin buildlist;return(id,id在符号表中的位置)end else return(保留字码,)end;本讲稿第十四页，共一百二十六页09:begin while digit do begin concatenate;getchar end;retract;return(num,num在常数表中的位置)end;+:return(plus-op,);-:return(minus-op,);*:begin getchar;if character=*then return(power-op,);retract;return(mul-op,);end;本讲稿第十五页，共一百二十六页 then return(rel-op,NE);retract;return(rel-op,LT)end;=:return(rel-op,EQ);:begin getchar;if character=then return(rel-op,GE);retract;return(rel-op,GT)end;:begin getchar;if character=then return(assign-op,);retract;return(colon,)end;:return(semicolon,)end of case;error本讲稿第十六页，共一百二十六页全局量及过程:(1)token(2)character(3)getchar(4)getnb(5)concatenate(6)letter和digit(7)reserve(8)retract:退一字符;character置空(9)buildlist:为标识符登记符号表本讲稿第十七页，共一百二十六页第二节 自顶向下语法分析u语法分析:自上而下(自顶而下)自下而上(自底而上)u自顶向下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。本讲稿第十八页，共一百二十六页一.回溯分析法 1.一个实例 SxAy Aaba输入串为xay,说明分析过程本讲稿第十九页，共一百二十六页Sx A ySx A ya bSx A ya本讲稿第二十页，共一百二十六页 2.存在的问题(1)回溯公共左因子的存在 A1|2(2)左递归 AA 或 AA+本讲稿第二十一页，共一百二十六页二.无回溯的递归下降分析法 1.提取公共左因子 A1|2|.|n|改写为:AB|B 1|2|.|n 本讲稿第二十二页，共一百二十六页 2.左递归的消除(1)直接左递归的消除 PP改写为:PP PP一般地 AA1|A2|Am|1|2|n （i，j不以A开头）改写为:P1P 2P.nP P 1P2P.mP本讲稿第二十三页，共一百二十六页(2)间接左递归的消除 PP(a)将文法G的所有非终结符按任一给定的顺序排列,设 为A1,A2,An;+本讲稿第二十四页，共一百二十六页(b)消除可能的左递归;for i:=1 to n do begin for j:=1 to i-1 do 把一个形如AiAj的产生式改写为 Ai1|2|k 其中Aj1|2|k是Aj的所有产生式;消除Ai产生式的直接左递归 end(c)化简本讲稿第二十五页，共一百二十六页以 SQcc QRbb RSaa为例,按S,Q,R排列,或R,Q,S排列本讲稿第二十六页，共一百二十六页u按S、Q、R排列,代入后 SQcc QRbb R Rbcabcacaau消除R中的直接左递归 R bcaRcaRaR R bcaRu文法产生的语言:(bca|ca|a)(bca)*bc|bc|c本讲稿第二十七页，共一百二十六页u按R、Q、S排列,代入后 RSaa QSababb SSabcabc bcc u消除S中的直接左递归 SabcSbcScS SabcSu文法产生的语言:(abc|bc|c)(abc)*本讲稿第二十八页，共一百二十六页 3.递归下降分析器的构造 当改造文法为无公共左因子,无左递归时,让每个非终结符对应一个过程;该过程对相应的非终结符产生式的右部短语进行语法分析本讲稿第二十九页，共一百二十六页例:G(E)EE+TT TT*FF F(E)iu消除左递归:ETE E+TE TFT T*FT F(E)i本讲稿第三十页，共一百二十六页u过程match:匹配单词符号,并读入下一符号u变量lookahead:即将处理但尚未处理的符号procedure match(t:token);begin if lookahead=t then lookahead=nexttoken else errorend;本讲稿第三十一页，共一百二十六页procedure E;begin T;Eend;procedure T;begin F;Tend;本讲稿第三十二页，共一百二十六页procedure E;if lookahead=+then begin match(+);T;E end;procedure T;if lookahead=*then begin match(*);F;T end;本讲稿第三十三页，共一百二十六页procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if lookahead=)then match()else error end;本讲稿第三十四页，共一百二十六页4.文法的另一种表示及应用.(1)表示形式:u用花括号表示闭包运算*;u用 表示可任意重复0次至n次 =0=;u用方括号表示 ,即表示的出现可有可无(等价于)n00010本讲稿第三十五页，共一百二十六页例:实数可定义为 decimal signinteger.digitexponent exponentEsigninteger integerdigitdigit sign+-本讲稿第三十六页，共一百二十六页(2)左递归的消除 pxy.zpv改写成:p(xy.z)v本讲稿第三十七页，共一百二十六页(3)文法的转换图表示 因产生式右端是一个正则式,故可用转换图表示。如:ET+T 表示成012T+本讲稿第三十八页，共一百二十六页(4)递归下降分析器的改进procedure E;begin T;while lookahead=+do begin match(+);T end end;本讲稿第三十九页，共一百二十六页procedure T;begin F;while lookahead=*do begin match(*);F end end;本讲稿第四十页，共一百二十六页procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if lookahead=)then match()else error end;本讲稿第四十一页，共一百二十六页三.预测分析程序u 构成:下推栈,预测分析表,控制程序,输入串1.预测分析表 形式:MA,a矩阵,AVN,a VT$内容:A或出错标志(空白)本讲稿第四十二页，共一百二十六页预测分析表EETTFi+*()$ETEETEE+TETFTTFTT*FTFiF(E)EETTT本讲稿第四十三页，共一百二十六页2.分析方法 初始时,$和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:x=a=$,成功x=a$,匹配 xVN,查表本讲稿第四十四页，共一百二十六页例:i+i*i的分析过程下推栈输入串查分析表i+i*i$E$ET$ETF$ET$ETi$E$ET$ET+i+i*i$+i*i$i+i*i$i+i*i$+i*i$+i*i$i*i$ETETFTTFTFiTE+TE本讲稿第四十五页，共一百二十六页$ETF i*i$ETi$ET$ETF*$ETi$ETF$ET$E *i$i$*i$i$T*FT结束FiT i*i$FiE本讲稿第四十六页，共一百二十六页四.LL(1)文法1FIRST集(1)定义:对(VTVN)*,有 FIRST（）a|a.,aVT 若,则FIRST()(2)对文法符号XVTVN(3)当=X1X2Xn时*本讲稿第四十七页，共一百二十六页uXVT,则FIRST(X)=X;uXVN,分三种情形:Xa XY XY1Y2Yk本讲稿第四十八页，共一百二十六页 2.FOLLOW集(1)定义:对AVN,有 FOLLOW(A)=aS.Aa.,aVT 若S .A,则$FOLLOW(A),其中S为开始符号*本讲稿第四十九页，共一百二十六页(2)求法u$FOLLOW(S)uAB:将FIRST()-加入FOLLOW(B)uAB或者AB且:将FOLLOW(A)加入FOLLOW(B)注意:求FOLLOW(B)实际上是考察B在产生式右端的每一次出现*本讲稿第五十页，共一百二十六页例:G(E)ETE E+TE TFT T*FT F(E)i本讲稿第五十一页，共一百二十六页EETTFFIRSTFOLLOW(i(i(i+*)$)$+)$+)$*+)$本讲稿第五十二页，共一百二十六页 3.LL(1)文法定义 设 上 下 文 无 关 文 法G的 产 生 式 形 如A1|2|m,当G满足下述条件时则称为LL(1)文法:FIRST(i)FIRST(j)=,ij,i,j=1,2,.,n若i,则FIRST(j)FOLLOW(A)=,j=1,2,.,n且ji。于是,在自顶向下分析时,可根据当前输入符号a选择aFIRST(i)的Ai。*本讲稿第五十三页，共一百二十六页五.预测分析表的构造1.构造算法 对每个产生式A对aFIRST(),将A记入MA,a中;若FIRST(),对bFOLLOW(A),将A记入MA,b中;凡未被定义的MA,a项中标以出错标志。本讲稿第五十四页，共一百二十六页如:G(E)ETE E+TE TFT T*FT F(E)iEETTFFIRSTFOLLOW(i(i(i+*)$)$+)$+)$*+)$本讲稿第五十五页，共一百二十六页预测分析表EETTFi+*()$ETEETEE+TETFTTFTT*FTFiF(E)EETTT本讲稿第五十六页，共一百二十六页2.预测分析表的改进MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xn xn-1.x1;当xn xn-1.x1的x1VT时,x1必为a,x1无须入栈,只移动输入指针。本讲稿第五十七页，共一百二十六页第三节 自底向上语法分析u方法:从输入串开始,归约,直至文法开始符。本讲稿第五十八页，共一百二十六页O.规范归约简介1.什么叫规范归约?假定是文法G的一个句子,序列n,n-1,0满足下述条件时称为规范归约。(1)n=;(2)0为文法的开始符,即0=S;(3)对i,0in,i-1是从i经把句柄替换为相应产生式的左部符号而得到的。本讲稿第五十九页，共一百二十六页 2.分析过程例1:G(E)EE+TT TT*FF F(E)i i+i*i的分析过程本讲稿第六十页，共一百二十六页EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE本讲稿第六十一页，共一百二十六页例2:G(S)SaAcBe AAb|b Bd abbcde的分析过程本讲稿第六十二页，共一百二十六页Sa A c B e A b d babbcdeaAbcdeaAcdeaAcBeS本讲稿第六十三页，共一百二十六页一.算符优先分析法1.算符文法 上下文无关文法G,没有形如P或P.QR.的产生式,则称G为算符文法算符文法本讲稿第六十四页，共一百二十六页2.终结符之间的优先关系 对算符文法G,a,bVT 定义(1)a=b:G中有P.ab.或P.aQb.(2)ab:G中有P.Qb.且Q.a 或QaR+本讲稿第六十五页，共一百二十六页3.算符优先文法 若算符文法G的任何终结符a,b之间的优先关系至多有=、=算符优先关系表本讲稿第六十七页，共一百二十六页从上表可知:(1)相同终结符之间的优先关系未必是=(2)有aa(3)a、b之间未必一定有优先关系 故=、不同于关系运算符“等于”、“小于”、“大于”本讲稿第六十八页，共一百二十六页4.算符优先分析方法 设a为栈顶终结符初始化:$栈读一符号ba=b=$ab归约最左素短语,最左素短语出栈,左部符号入栈结束b入栈出错YNYYNN本讲稿第六十九页，共一百二十六页u归约最左素短语的方法:这是一种结构归约,处于栈顶待归约的最左素短语与对应的产生式在结构上应一致,即长度一致,对应的终结符一致,而非终结符可以不一致。例 G(E)EE+TT TT*FF F(E)i i+i*i的分析过程本讲稿第七十页，共一百二十六页步骤1234567891011下推栈输入串动作$i+i*i$+,用Fi归约$F+i*i$+,移进+$F+i*i$+*,用Fi归约$F+F *i$+*,移进*$F+F*i$*$,用Fi归约*$,用TT*F归约+$,用EE+T归约结束$F+F*F$F+T$E本讲稿第七十一页，共一百二十六页EET+FTii*FTiFEET+FTii*FTF本讲稿第七十二页，共一百二十六页EET+FT*FTFEET+FTi*FTF本讲稿第七十三页，共一百二十六页EET+TF本讲稿第七十四页，共一百二十六页EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE本讲稿第七十五页，共一百二十六页 5.优先关系表的构造 (1)FIRSTVT集FIRSTVT(P)=a|Pa,或PQa,aVT,Q VNu若Pa或PQa,则aFIRSTVT(P);u若PQ,则FIRSTVT(Q)FIRSTVT(P);直至FIRSTVT(P)不再增大。+本讲稿第七十六页，共一百二十六页 (2)LASTVT集LASTVT(P)=a|P.a,或PaQ,aVT,Q VNu若P.a或PaQ,则aLASTVT(P);u若P.Q,则LASTVT(Q)LASTVT(P);直至LASTVT(P)不再增大。+本讲稿第七十七页，共一百二十六页例 G(E)EE+TT TT*FF F(E)iETFFIRSTVTLASTVT(i +*(i)i +*)i *)i(i *本讲稿第七十八页，共一百二十六页 (3)构造优先关系表的算法FOR 每条产生式PX1X2Xn DO FOR i:=1 TO n-1 DO BEGIN IF Xi和Xi+1均为终结符 THEN Xi=Xi+1;IF i=n-2 且 Xi和Xi+2均为终结符 但 Xi+1VN THEN Xi=Xi+2;IF XiVT,Xi+1VN THEN aFIRSTVT(Xi+1)XiXi+1 END;本讲稿第七十九页，共一百二十六页例 G(E)EE+TT TT*FF F(E)iETFFIRSTVTLASTVT(i +*(i)i +*)i *)i(i *考察EE+T中的E和+、+和T考察TT*F中的T和*、*和F考察F(E)中的(和E、(和)、E和)本讲稿第八十页，共一百二十六页+*ii()$=算符优先关系表本讲稿第八十一页，共一百二十六页 二.LR分析法1.LR(K)分析法 自底向上的LR分析法是指从左向右扫描输入串,每次分析由分析栈中符号及向前搜索K个输入符号,以确定作为产生式右部的短语(句柄)是否已在分析栈的栈顶形成,从而决定应采取的动作。这种分析方法称为LR(K)分析法。一般只考虑K1的情况。本讲稿第八十二页，共一百二十六页其组成为:分析栈,控制程序,分析表,输入串输入串分析栈驱动程序输出actiongoto分析表s0.sm-1sma1ai$.本讲稿第八十三页，共一百二十六页 2.分析栈 存放状态;初始时,置初始状态s0;栈里的每一状态概括了从分析开始到某一时刻已进行的分析工作。本讲稿第八十四页，共一百二十六页 3.分析表 由actions,a和gotos,x两个子表组成。(1)actions,a定义了在状态s下,当前输入符号为a时应采取的分析动作:移进,归约,接受,出错。(2)goto表是一个状态及非终结符的二维矩阵,gotos,x定义了在状态s下,面对文法符号x时的状态转换。本讲稿第八十五页，共一百二十六页例 G0(E)(1)EE+T (2)ET (3)TT*F (4)TF (5)F(E)(6)Fi的LR分析表如后本讲稿第八十六页，共一百二十六页LR分析表状态01234567891011actiongotoi+*()$ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5本讲稿第八十七页，共一百二十六页 4.控制程序的工作 据actions,a进行:(1)若actions,a=sj,则将状态j推入栈顶,输入指针指向下一输入符号;(2)若actions,a=rj,则按第j个产生式A归约,设|=t,应在分析栈栈顶上托t个状态出栈,呈现栈顶的状态设为si,则根据si及归约后的非终结符A,查goto表,gotosi,A=j,则将状态j下推入分析栈栈顶。(3)若actions,a=acc,则结束分析,输入串被接受。(4)若actions,a或gotos,A不是上述情况,转出错处理程序。本讲稿第八十八页，共一百二十六页123456789分析栈符号栈输入串动作$(i+i*i)$移进$,(,i +i*i)$移进00,40,4,5$,(i+i*i)$归约0,4,3$,(,F +i*i)$归约0,4,2$,(,T +i*i)$归约0,4,8$,(,E +i*i)$移进0,4,8,6$,(,E,+i*i)$移进0,4,8,6,5$,(,E,+,i *i)$归约0,4,8,6,3$,(,E,+,F *i)$归约例:(i+i*i)的分析过程本讲稿第八十九页，共一百二十六页101112131415161718190,4,8,6,9$,(,E,+,T*i)$移进0,4,8,6,9,7$,(,E,+,T,*i)$移进0,4,8,6,9,7,5$,(,E,+,T,*,i )$归约0,4,8,6,9,7,10$,(,E,+,T,*,F )$归约0,4,8,6,9$,(,E,+,T )$归约0,4,8$,(,E )$移进0,4,8,11$,(,E,)$归约0,3$,F$归约0,2$,T$归约0,1$,E$接受(续表)本讲稿第九十页，共一百二十六页123456789分析栈符号栈输入串动作(i+i*i)$移进 +i*i)$移进00,40,4,5 i+i*i)$归约0,4,3 +i*i)$归约0,4,2 +i*i)$归约0,4,8 +i*i)$移进0,4,8,6 i*i)$移进0,4,8,6,5 *i)$归约0,4,8,6,3 *i)$归约例:(i+i*i)的分析过程本讲稿第九十一页，共一百二十六页101112131415161718190,4,8,6,9*i)$移进0,4,8,6,9,7 i)$移进0,4,8,6,9,7,5 )$归约0,4,8,6,9,7,10 )$归约0,4,8,6,9 )$归约0,4,8 )$移进0,4,8,11$归约0,3$归约0,2$归约0,1$接受(续表)本讲稿第九十二页，共一百二十六页EET+FTii*FTiF(i+i*i)(F+i*i)(T+i*i)(E+i*i)(E+F*i)(E+T*i)(E+T*F)(E+T)(E)TFESE()S本讲稿第九十三页，共一百二十六页 5.几种LR分析法及其比较 LR(0)、SLR(1)、LR(1)、LALR(1)本讲稿第九十四页，共一百二十六页三.识别活前缀的DFA1.活前缀:规范句型的不含句柄之后任何符号的一个前缀。亦即:若A是文法的一个产生式,且有 SA 则的任何前缀都是规范句型的活前缀。*RR本讲稿第九十五页，共一百二十六页(1)作为规范句型的活前缀,它不含句柄后的任何符号。(2)活前缀与句柄之间的三种关系:u活前缀不含句柄的任何符号,此时期待从剩余输入串中识别由A的能推导出的符号串;u活前缀只含句柄的真前缀,也即产生式A中已识别于分析栈栈顶之上,期待从剩余输入串中识别由所能推导出的符号串;u活前缀已含句柄的全部符号,这表明产生式A的右部符号已在分析栈栈顶之上,应将归约为A。(3)句柄是一类活前缀的后缀,如果能识别一个文法的所有活前缀,自然也就能识别这个文法的所有句柄了。本讲稿第九十六页，共一百二十六页2.项目及分类uu项目项目:在产生式右部添加一个圆点 如A、A、Au归约项目:形如Au移进项目:形如Aa，aVTu待约项目:形如AB，BVNu接受项目:形如S，S为开始符本讲稿第九十七页，共一百二十六页3.拓广文法 增加产生式SS，从而SS成为唯一的接受项目。4.NFA的构造 一个项目对应一个状态,SS为唯一初态，其余均为终态(活前缀识别态)。本讲稿第九十八页，共一百二十六页例如,文法 SE EE+T|T TT*F|F F(E)|i这个文法的项目有:1.SE 8.ET 15.F(E)2.SE 9.TT*F 16.F(E)3.EE+T 10.TT*F 17.F(E)4.EE+T 11.TT*F 18.F(E)5.EE+T 12.TT*F 19.Fi6.EE+T 13.TF 20.Fi 7.ET 14.TF本讲稿第九十九页，共一百二十六页2413567891011201318121415161719EE+TTT*FiF(E)识别活前缀的NFA本讲稿第一百页，共一百二十六页 5.项目的有效性 (1)对于项目A,如果有 SA则称A对活前缀有效。意思是:到达项目A时,已识别出,希望继续识别从推出的串。*RR本讲稿第一百零一页，共一百二十六页 (2)若AB对活前缀有效,则B 对活前缀也有效。因为 SAB则,设,有 SAB B即 SB所以,B 对也有效。*RRR*RRRRRR*本讲稿第一百零二页，共一百二十六页 (3)有效项目集:对活前缀有效的项目的集合称为对的有效项目集。(4)LR(0)项目集规范族:文法G的所有有效项目集组成的集合。本讲稿第一百零三页，共一百二十六页 6.closure(I)设I是文法G的一个LR(0)项目集,(1)对iI,都有iclosure(I);(2)若ABclosure(I),且B为文法G的一个产生式,则B closure(I)；(3)重复(2)直至closure不再增大。本讲稿第一百零四页，共一百二十六页 7.go(I,X)设XVTVN go(I,X)=closure(AX|AXI)因为 AX对有效所以 SAX 故 AX对X有效*RR本讲稿第一百零五页，共一百二十六页 8.LR(0)项目集规范族的构造begin C:=closure(SS);repeat for C中每一项目集I和文法符号X do if go(I,X)不空 且 go(I,X)C then 把go(I,X)加入C中 until C不再增大end;本讲稿第一百零六页，共一百二十六页例:文法(0)SE(1)EE+TT(2)TT*FF(3)F(E)i本讲稿第一百零七页，共一百二十六页I0=closure(SS)SE,EE+T,ET,TT*F,TF,F(E),F iI1=go(I0,E)SE,EE+T 移进-归约冲突I2=go(I0,T)ET,TT*F 移进-归约冲突I3=go(I0,F)TFI4=go(I0,()F(E),EE+T,ET,TT*F,TF,F(E),F iI5=go(I0,i)F i本讲稿第一百零八页，共一百二十六页I6=go(I1,+)EE+T,TT*F,TF,F(E),F iI7=go(I2,*)TT*F,F(E),F iI8=go(I4,E)F(E),EE+TI9=go(I6,T)EE+T,TT*F 移进-归约冲突I10=go(I7,F)TT*FI11=go(I8,)F(E)本讲稿第一百零九页，共一百二十六页四.SLR分析表的构造 1.SLR方法 当某个项目集形如 I=Xb,A,B时,出现了移进-归约冲突和归约-归约冲突,可用如下方法解决,该方法称为SLR方法。本讲稿第一百一十页，共一百二十六页 a是当前输入符号,当bFOLLOW(A)FOLLOW(B)=时(1)a=b,则移进输入符a;(2)aFOLLOW(A),则用A归约;(3)aFOLLOW(B),则用B归约;(4)此外出错。本讲稿第一百一十一页，共一百二十六页 2.SLR分析表的构造 (1)C=I0,I1,In,Ii对应状态i,I0=closure(SS)为唯一初态;(2)对每个Ii,u若AaIi,且go(Ii,a)=Ij,则actioni,a=sj;u若AIi,A为第j个产生式,则bFOLLOW(A),actioni,b=rj;u若SSIi,则actioni,$=acc;(3)若go(Ii,A)=Ij,则gotoi,A=j;(4)凡不能用规则(2)、(3)登记的表项均为“错误”。本讲稿第一百一十二页，共一百二十六页 若由该方法构造的分析表,不含多重入口,则该分析表称为SLR分析表,相应文法G称为SLR(1)文法。本讲稿第一百一十三页，共一百二十六页LR分析表状态01234567891011actiongotoi+*()$ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5本讲稿第一百一十四页，共一百二十六页五.关于二义文法例1:G(E)EE+E|E*E|(E)|i拓广文法:(0)SE(1)EE+E(2)EE*E(3)E(E)(4)Ei本讲稿第一百一十五页，共一百二十六页I0=closure(SE)SE,EE+E,EE*E,E(E),E iI1=go(I0,E)SE,EE+E,EE*E 移进-归约冲突I2=go(I0,()E(E),EE+E,EE*E,E(E),E iI3=go(I0,i)EiI4=go(I1,+)EE+E,EE+E,EE*E,E(E),E iI5=go(I1,*)EE*E,EE+E,EE*E,E(E),E i本讲稿第一百一十六页，共一百二十六页I6=go(I2,E)E(E),EE+E,EE*EI7=go(I4,E)EE+E,EE+E,EE*E 移进-归约冲突I8=go(I5,E)EE*E,EE+E,EE*E 移进-归约冲突I9=go(I6,)E(E)本讲稿第一百一十七页，共一百二十六页例2:G(S)SiSeS|iS|a拓广文法:(0)SS(1)SiSeS(2)SiS(3)Si本讲稿第一百一十八页，共一百二十六页I0=closure(SS)SS,SiSeS,SiS,SaI1=go(I0,S)SSI2=go(I0,i)SiSeS,SiS,SiSeS,SiS,SaI3=go(I0,a)SaI4=go(I2,S)SiSeS,SiS 移进-归约冲突I5=go(I4,e)SiSeS,SiSeS,SiS,SaI6=go(I5,S)SiSeS本讲稿第一百一十九页，共一百二十六页第四节 LEX和YACC简介一.LEX LEX是一个描述词法分析器的语言,一个词法分析器的LEX程序由一组正规式以及与每个正规式相应的一个动作组成。本讲稿第一百二十页，共一百二十六页 1.LEX编译系统的组成LEX编译程序LEX源程序词法分析器L词法分析器L输入串单词符号串本讲稿第一百二十一页，共一百二十六页 2.语言LEX的一般描述 一个LEX源程序主要包括两部分:辅助定义式、识别规则。本讲稿第一百二十二页，共一百二十六页u辅助定义式 D1R1 D2R2 DnRn其中,每个Ri是一个正规式,Di是代表这个正规式的简名,而且在Ri中只允许出现字母表中的字符和前面已定义的简名D1,D2,Di-1。本讲稿第一百二十三页，共一百二十六页u识别规则 P1 A1 P2 A2 Pm Am其中,每个Pi是一个正规式,称为词形。Pi是D1,D2,Dn上的一个正规式;每个Ai是一小段程序代码,在识别出词形为Pi的单词之后,词法分析器所应采取的动作。本讲稿第一百二十四页，共一百二十六页二.YACC输入YACCLALR(1)分析表其中,输入为:文法、优先级、结合性等输入串控制程序分析表输出本讲稿第一百二十五页，共一百二十六页第五章习题(必做题):5-5、5-8(a)、5-12(a)(b)、5-13本讲稿第一百二十六页，共一百二十六页