计算机编译优秀PPT.ppt

《计算机编译优秀PPT.ppt》由会员分享，可在线阅读，更多相关《计算机编译优秀PPT.ppt（126页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。

1、计算机编译现在学习的是第1页，共126页2.词法分析器和语法分析器的关系（1）词法分析作为单独的一遍输入串词法分析器语法分析器单词流现在学习的是第2页，共126页（2）词法分析作为子程序输入串词法分析器语法分析器符号表取下一单词返回下一单词现在学习的是第3页，共126页二.单词的种类 (1)标识符:用来命名程序中出现的变量、数组、函数、过程、标号等 (2)基本字:也可称关键字或保留字,如if、while、for、do、goto等 (3)常数:各种类型的常数,如216、3.14159、TRUE等 (4)运算符:如+、-、*、/等 (5)界符:如;、:、/*、*/等现在学习的是第4页，共126页三

2、.单词的编码1.单词的输出形式二元式 (单词类别,单词的属性)区分单词所属的类(整数编码)单词的值现在学习的是第5页，共126页2.单词类别的划分u基本字、运算符、界符:一字一码u标识符:单列一种u常数:按类型分类现在学习的是第6页，共126页四.词法错误检查u非法字符u不合规则的常数u标识符前缀为保留字现在学习的是第7页，共126页五.词法分析器的生成1.词法分析技术超前搜索 为了判定一个单词符号的类别,必须扫描到某一地方,而该单词符号并没有这么长,这种扫描方式叫做“超前搜索”。如：DO100I=1,10 DO100I=1.10 IF(5.EQ.M)GOTO 100 IF(5)=100现在学

3、习的是第8页，共126页2.状态转换图u有限的有向图u有限边上标记字符u一个初态u若干终态现在学习的是第9页，共126页例:某语言允许 标识符、基本字、数字串、+、-、*、*、=、=、=、:=、：、；现在学习的是第10页，共126页0412356789开始空白字母/数字字母非字母数字数字非数字+-*非*数字现在学习的是第11页，共126页101112=1314151617其它=181920：其它=其它2122=；其它*现在学习的是第12页，共126页 3.实现方法 每个状态结对应一小段程序u分支状态if或case语句u循环状态while语句u终态return语句 4.一个示意算法现在学习的是第

4、13页，共126页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;现在学习的是第14页，共126页09:begin while digit do begin concatenate;getchar end;retract;return(nu

5、m,num在常数表中的位置)end;+:return(plus-op,);-:return(minus-op,);*:begin getchar;if character=*then return(power-op,);retract;return(mul-op,);end;现在学习的是第15页，共126页 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,

6、GT)end;:begin getchar;if character=then return(assign-op,);retract;return(colon,)end;:return(semicolon,)end of case;error现在学习的是第16页，共126页全局量及过程:(1)token(2)character(3)getchar(4)getnb(5)concatenate(6)letter和digit(7)reserve(8)retract:退一字符;character置空(9)buildlist:为标识符登记符号表现在学习的是第17页，共126页第二节 自顶向下语法分析u语

7、法分析:自上而下(自顶而下)自下而上(自底而上)u自顶向下语法分析法:或从开始符号出发,找最左推导;或从根开始,构造推导树。现在学习的是第18页，共126页一.回溯分析法 1.一个实例 SxAy Aaba输入串为xay,说明分析过程现在学习的是第19页，共126页Sx A ySx A ya bSx A ya现在学习的是第20页，共126页 2.存在的问题(1)回溯公共左因子的存在 A1|2(2)左递归 AA 或 AA+现在学习的是第21页，共126页二.无回溯的递归下降分析法 1.提取公共左因子 A1|2|.|n|改写为:AB|B 1|2|.|n 现在学习的是第22页，共126页 2.左递归的

8、消除(1)直接左递归的消除 PP改写为:PP PP一般地 AA1|A2|Am|1|2|n （i，j不以A开头）改写为:P1P 2P.nP P 1P2P.mP现在学习的是第23页，共126页(2)间接左递归的消除 PP(a)将 文 法G的 所 有 非 终 结 符 按 任 一 给 定 的 顺 序 排 列,设 为A1,A2,An;+现在学习的是第24页，共126页(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)化简

9、现在学习的是第25页，共126页以 SQcc QRbb RSaa为例,按S,Q,R排列,或R,Q,S排列现在学习的是第26页，共126页u按S、Q、R排列,代入后 SQcc QRbb R Rbcabcacaau消除R中的直接左递归 R bcaRcaRaR R bcaRu文法产生的语言:(bca|ca|a)(bca)*bc|bc|c现在学习的是第27页，共126页u按R、Q、S排列,代入后 RSaa QSababb SSabcabc bcc u消除S中的直接左递归 SabcSbcScS SabcSu文法产生的语言:(abc|bc|c)(abc)*现在学习的是第28页，共126页 3.递归下降分析

10、器的构造 当改造文法为无公共左因子,无左递归时,让每个非终结符对应一个过程;该过程对相应的非终结符产生式的右部短语进行语法分析现在学习的是第29页，共126页例:G(E)EE+TT TT*FF F(E)iu消除左递归:ETE E+TE TFT T*FT F(E)i现在学习的是第30页，共126页u过程match:匹配单词符号,并读入下一符号u变量lookahead:即将处理但尚未处理的符号procedure match(t:token);begin if lookahead=t then lookahead=nexttoken else errorend;现在学习的是第31页，共126页pro

11、cedure E;begin T;Eend;procedure T;begin F;Tend;现在学习的是第32页，共126页procedure E;if lookahead=+then begin match(+);T;E end;procedure T;if lookahead=*then begin match(*);F;T end;现在学习的是第33页，共126页procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if lookahead=)then match()else er

12、ror end;现在学习的是第34页，共126页4.文法的另一种表示及应用.(1)表示形式:u用花括号表示闭包运算*;u用 表示可任意重复0次至n次 =0=;u用方括号表示 ,即表示的出现可有可无(等价于)n00010现在学习的是第35页，共126页例:实数可定义为 decimal signinteger.digitexponent exponentEsigninteger integerdigitdigit sign+-现在学习的是第36页，共126页(2)左递归的消除 pxy.zpv改写成:p(xy.z)v现在学习的是第37页，共126页(3)文法的转换图表示 因产生式右端是一个正则式,故

13、可用转换图表示。如:ET+T 表示成012T+现在学习的是第38页，共126页(4)递归下降分析器的改进procedure E;begin T;while lookahead=+do begin match(+);T end end;现在学习的是第39页，共126页procedure T;begin F;while lookahead=*do begin match(*);F end end;现在学习的是第40页，共126页procedure F;if lookahead=i then match(i)else if lookahead=(then begin match();E;if loo

14、kahead=)then match()else error end;现在学习的是第41页，共126页三.预测分析程序u 构成:下推栈,预测分析表,控制程序,输入串1.预测分析表 形式:MA,a矩阵,AVN,a VT$内容:A或出错标志(空白)现在学习的是第42页，共126页预测分析表EETTFi+*()$ETEETEE+TETFTTFTT*FTFiF(E)EETTT现在学习的是第43页，共126页2.分析方法 初始时,$和开始符入栈,输入指针指向第一个符号,然后根据下推栈栈顶符x和当前输入符a进行工作:x=a=$,成功x=a$,匹配 xVN,查表现在学习的是第44页，共126页例:i+i*i

15、的分析过程下推栈输入串查分析表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现在学习的是第45页，共126页$ETF i*i$ETi$ET$ETF*$ETi$ETF$ET$E *i$i$*i$i$T*FT结束FiT i*i$FiE现在学习的是第46页，共126页四.LL(1)文法1FIRST集(1)定义:对(VTVN)*,有 FIRST（）a|a.,aVT 若,则FIRST()(2)对文法符号XVTVN(3)当=X1X2Xn时*现在学习的是第47页，共126页uXVT,则FI

16、RST(X)=X;uXVN,分三种情形:Xa XY XY1Y2Yk现在学习的是第48页，共126页 2.FOLLOW集(1)定义:对AVN,有 FOLLOW(A)=aS.Aa.,aVT 若S .A,则$FOLLOW(A),其中S为开始符号*现在学习的是第49页，共126页(2)求法u$FOLLOW(S)uAB:将FIRST()-加入FOLLOW(B)uAB或者AB且:将FOLLOW(A)加入FOLLOW(B)注意:求FOLLOW(B)实际上是考察B在产生式右端的每一次出现*现在学习的是第50页，共126页例:G(E)ETE E+TE TFT T*FT F(E)i现在学习的是第51页，共126页

17、EETTFFIRSTFOLLOW(i(i(i+*)$)$+)$+)$*+)$现在学习的是第52页，共126页 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。*现在学习的是第53页，共126页五.预测分析表的构造1.构造算法 对每个产生式A对aFIRST(),将A记入MA,a中;若FIRST(),对bFO

18、LLOW(A),将A记入MA,b中;凡未被定义的MA,a项中标以出错标志。现在学习的是第54页，共126页如:G(E)ETE E+TE TFT T*FT F(E)iEETTFFIRSTFOLLOW(i(i(i+*)$)$+)$+)$*+)$现在学习的是第55页，共126页预测分析表EETTFi+*()$ETEETEE+TETFTTFTT*FTFiF(E)EETTT现在学习的是第56页，共126页2.预测分析表的改进MA,a中只记产生式右部;对=x1x2.xn,在M,a中记xn xn-1.x1;当xn xn-1.x1的x1VT时,x1必为a,x1无须入栈,只移动输入指针。现在学习的是第57页，共

19、126页第三节 自底向上语法分析u方法:从输入串开始,归约,直至文法开始符。现在学习的是第58页，共126页O.规范归约简介1.什么叫规范归约?假定是文法G的一个句子,序列n,n-1,0满足下述条件时称为规范归约。(1)n=;(2)0为文法的开始符,即0=S;(3)对i,0in,i-1是从i经把句柄替换为相应产生式的左部符号而得到的。现在学习的是第59页，共126页 2.分析过程例1:G(E)EE+TT TT*FF F(E)i i+i*i的分析过程现在学习的是第60页，共126页EET+FTii*FTiFi+i*iF+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE现在学习的是

20、第61页，共126页例2:G(S)SaAcBe AAb|b Bd abbcde的分析过程现在学习的是第62页，共126页Sa A c B e A b d babbcdeaAbcdeaAcdeaAcBeS现在学习的是第63页，共126页一.算符优先分析法1.算符文法 上下文无关文法G,没有形如P或P.QR.的产生式,则称G为算符文法算符文法现在学习的是第64页，共126页2.终结符之间的优先关系 对算符文法G,a,bVT 定义(1)a=b:G中有P.ab.或P.aQb.(2)ab:G中有P.Qb.且Q.a 或QaR+现在学习的是第65页，共126页3.算符优先文法 若算符文法G的任何终结符a,b

21、之间的优先关系至多有=、=算符优先关系表现在学习的是第67页，共126页从上表可知:(1)相同终结符之间的优先关系未必是=(2)有aa(3)a、b之间未必一定有优先关系 故=、不同于关系运算符“等于”、“小于”、“大于”现在学习的是第68页，共126页4.算符优先分析方法 设a为栈顶终结符初始化:$栈读一符号ba=b=$ab归约最左素短语,最左素短语出栈,左部符号入栈结束b入栈出错YNYYNN现在学习的是第69页，共126页u归约最左素短语的方法:这是一种结构归约,处于栈顶待归约的最左素短语与对应的产生式在结构上应一致,即长度一致,对应的终结符一致,而非终结符可以不一致。例 G(E)EE+TT

22、 TT*FF F(E)i i+i*i的分析过程现在学习的是第70页，共126页步骤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现在学习的是第71页，共126页EET+FTii*FTiFEET+FTii*FTF现在学习的是第72页，共126页EET+FT*FTFEET+FTi*FTF现在学习的是第73页，共126页EET+TF现在学习的是第74页，共126页EET+FTii*FTiFi+i*i

23、F+i*iT+i*iE+i*iE+F*iE+T*iE+T*FE+TE现在学习的是第75页，共126页 5.优先关系表的构造 (1)FIRSTVT集FIRSTVT(P)=a|Pa,或PQa,aVT,Q VNu若Pa或PQa,则aFIRSTVT(P);u若PQ,则FIRSTVT(Q)FIRSTVT(P);直至FIRSTVT(P)不再增大。+现在学习的是第76页，共126页 (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)不再增大。+现在学习的是第77页

24、，共126页例 G(E)EE+TT TT*FF F(E)iETFFIRSTVTLASTVT(i +*(i)i +*)i *)i(i *现在学习的是第78页，共126页 (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;现在学习的是第79页，共126页例 G(E)EE+TT TT*FF F(E)

25、iETFFIRSTVTLASTVT(i +*(i)i +*)i *)i(i *考察EE+T中的E和+、+和T考察TT*F中的T和*、*和F考察F(E)中的(和E、(和)、E和)现在学习的是第80页，共126页+*ii()$=算符优先关系表现在学习的是第81页，共126页 二.LR分析法1.LR(K)分析法 自底向上的LR分析法是指从左向右扫描输入串,每次分析由分析栈中符号及向前搜索K个输入符号,以确定作为产生式右部的短语(句柄)是否已在分析栈的栈顶形成,从而决定应采取的动作。这种分析方法称为LR(K)分析法。一般只考虑K1的情况。现在学习的是第82页，共126页其组成为:分析栈,控制程序,分析

26、表,输入串输入串分析栈驱动程序输出actiongoto分析表s0.sm-1sma1ai$.现在学习的是第83页，共126页 2.分析栈 存放状态;初始时,置初始状态s0;栈里的每一状态概括了从分析开始到某一时刻已进行的分析工作。现在学习的是第84页，共126页 3.分析表 由actions,a和gotos,x两个子表组成。(1)actions,a定义了在状态s下,当前输入符号为a时应采取的分析动作:移进,归约,接受,出错。(2)goto表是一个状态及非终结符的二维矩阵,gotos,x定义了在状态s下,面对文法符号x时的状态转换。现在学习的是第85页，共126页例 G0(E)(1)EE+T (2

27、)ET (3)TT*F (4)TF (5)F(E)(6)Fi的LR分析表如后现在学习的是第86页，共126页LR分析表状态01234567891011actiongotoi+*()$ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5现在学习的是第87页，共126页 4.控制程序的工作 据actions,a进行:(1)若actions,a=sj,则将状态j推入栈顶,输入指针指向下一输入符号;(2)若actions,a=rj,则按第j个产生式A归约,设|=t,应在分析栈栈

28、顶上托t个状态出栈,呈现栈顶的状态设为si,则根据si及归约后的非终结符A,查goto表,gotosi,A=j,则将状态j下推入分析栈栈顶。(3)若actions,a=acc,则结束分析,输入串被接受。(4)若actions,a或gotos,A不是上述情况,转出错处理程序。现在学习的是第88页，共126页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

29、,8,6,5$,(,E,+,i *i)$归约0,4,8,6,3$,(,E,+,F *i)$归约例:(i+i*i)的分析过程现在学习的是第89页，共126页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$接受(续表)现在

30、学习的是第90页，共126页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)的分析过程现在学习的是第91页，共126页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

31、)$移进0,4,8,11$归约0,3$归约0,2$归约0,1$接受(续表)现在学习的是第92页，共126页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现在学习的是第93页，共126页 5.几种LR分析法及其比较 LR(0)、SLR(1)、LR(1)、LALR(1)现在学习的是第94页，共126页三.识别活前缀的DFA1.活前缀:规范句型的不含句柄之后任何符号的一个前缀。亦即:若A是文法的一个产生式,且有 SA 则的任何前缀都是规范句型的活前缀。*RR现在学习的是第95页，共126页(

32、1)作为规范句型的活前缀,它不含句柄后的任何符号。(2)活前缀与句柄之间的三种关系:u活前缀不含句柄的任何符号,此时期待从剩余输入串中识别由A的能推导出的符号串;u活前缀只含句柄的真前缀,也即产生式A中已识别于分析栈栈顶之上,期待从剩余输入串中识别由所能推导出的符号串;u活前缀已含句柄的全部符号,这表明产生式A的右部符号已在分析栈栈顶之上,应将归约为A。(3)句柄是一类活前缀的后缀,如果能识别一个文法的所有活前缀,自然也就能识别这个文法的所有句柄了。现在学习的是第96页，共126页2.项目及分类uu项目项目:在产生式右部添加一个圆点 如A、A、Au归约项目:形如Au移进项目:形如Aa，aVTu

33、待约项目:形如AB，BVNu接受项目:形如S，S为开始符现在学习的是第97页，共126页3.拓广文法 增加产生式SS，从而SS成为唯一的接受项目。4.NFA的构造 一个项目对应一个状态,SS为唯一初态，其余均为终态(活前缀识别态)。现在学习的是第98页，共126页例如,文法 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现

34、在学习的是第99页，共126页2413567891011201318121415161719EE+TTT*FiF(E)识别活前缀的NFA现在学习的是第100页，共126页 5.项目的有效性 (1)对于项目A,如果有 SA则称A对活前缀有效。意思是:到达项目A时,已识别出,希望继续识别从推出的串。*RR现在学习的是第101页，共126页 (2)若AB对活前缀有效,则B 对活前缀也有效。因为 SAB则,设,有 SAB B即 SB所以,B 对也有效。*RRR*RRRRRR*现在学习的是第102页，共126页 (3)有效项目集:对活前缀有效的项目的集合称为对的有效项目集。(4)LR(0)项目集规范族:

35、文法G的所有有效项目集组成的集合。现在学习的是第103页，共126页 6.closure(I)设I是文法G的一个LR(0)项目集,(1)对iI,都有iclosure(I);(2)若ABclosure(I),且B为文法G的一个产生式,则B closure(I)；(3)重复(2)直至closure不再增大。现在学习的是第104页，共126页 7.go(I,X)设XVTVN go(I,X)=closure(AX|AXI)因为 AX对有效所以 SAX 故 AX对X有效*RR现在学习的是第105页，共126页 8.LR(0)项目集规范族的构造begin C:=closure(SS);repeat for

36、 C中每一项目集I和文法符号X do if go(I,X)不空 且 go(I,X)C then 把go(I,X)加入C中 until C不再增大end;现在学习的是第106页，共126页例:文法(0)SE(1)EE+TT(2)TT*FF(3)F(E)i现在学习的是第107页，共126页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)

37、F i现在学习的是第108页，共126页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)现在学习的是第109页，共126页四.SLR分析表的构造 1.SLR方法 当某个项目集形如 I=Xb,A,B时,出现了移进-归约冲突和归约-归约冲突,可用如下方法解决,该方法称为SLR方法。现在学习的是第110页，共126页 a是当前输入符号,当bFOLLOW(A)FOLLOW(B)=时(

38、1)a=b,则移进输入符a;(2)aFOLLOW(A),则用A归约;(3)aFOLLOW(B),则用B归约;(4)此外出错。现在学习的是第111页，共126页 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)登记的表项均为“错误”。现在学习的是

39、第112页，共126页 若由该方法构造的分析表,不含多重入口,则该分析表称为SLR分析表,相应文法G称为SLR(1)文法。现在学习的是第113页，共126页LR分析表状态01234567891011actiongotoi+*()$ETFs5s4123s6accr2s7r2r2r4r4r4r4r4s5s4823r6r6r6r6s5s493s5s410s6s11r1s7r1r1r3r3r3r3r5r5r5r5现在学习的是第114页，共126页五.关于二义文法例1:G(E)EE+E|E*E|(E)|i拓广文法:(0)SE(1)EE+E(2)EE*E(3)E(E)(4)Ei现在学习的是第115页，共1

40、26页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现在学习的是第116页，共126页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

41、,)E(E)现在学习的是第117页，共126页例2:G(S)SiSeS|iS|a拓广文法:(0)SS(1)SiSeS(2)SiS(3)Si现在学习的是第118页，共126页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现在学习的是第119页，共126页第四节 LEX和YACC简介一.LEX LEX是一个描述词法分析器的语言

42、,一个词法分析器的LEX程序由一组正规式以及与每个正规式相应的一个动作组成。现在学习的是第120页，共126页 1.LEX编译系统的组成LEX编译程序LEX源程序词法分析器L词法分析器L输入串单词符号串现在学习的是第121页，共126页 2.语言LEX的一般描述 一个LEX源程序主要包括两部分:辅助定义式、识别规则。现在学习的是第122页，共126页u辅助定义式 D1R1 D2R2 DnRn其中,每个Ri是一个正规式,Di是代表这个正规式的简名,而且在Ri中只允许出现字母表中的字符和前面已定义的简名D1,D2,Di-1。现在学习的是第123页，共126页u识别规则 P1 A1 P2 A2 Pm Am其中,每个Pi是一个正规式,称为词形。Pi是D1,D2,Dn上的一个正规式;每个Ai是一小段程序代码,在识别出词形为Pi的单词之后,词法分析器所应采取的动作。现在学习的是第124页，共126页二.YACC输入YACCLALR(1)分析表其中,输入为:文法、优先级、结合性等输入串控制程序分析表输出现在学习的是第125页，共126页第五章习题(必做题):5-5、5-8(a)、5-12(a)(b)、5-13现在学习的是第126页，共126页