第四章-语法分析和语法分析程序

编译原理语法分析和语法分析程序,计算机与软件学院陆克中手机公电话:26732030QQ:8256546Email:kzlu办公地点:科技楼七楼北侧701,编译程序的逻辑结构,词法分析程序,语法分析程序,语义分析程序,中间代码生成,代码优化程序,目标代码生成,信息表管理程序,错误检查和处理程序,源程序,目标代码,编译程序的组织,语法分析程序,语义分析及代码生成程序,词法分析程序,整理目标程序,源程序,目标程序,停机,开始,语法树,语法树（分析树、推导树）每个结点均有标记VNVT根的标记为开始符号S内部结点标记VN若以A为标记的结点有k个孩子分别标记为X1,X2,Xk,则AX1X2Xk必然是G的一个产生式文法的二义性：一个句子对应多个语法树对无二义文法，一个句子只对应一个语法树,两类语法分析方法,按产生语法树的方向分自顶向下递归下降法LL自底向上算符优先法LR,自顶向下的语法分析例子,文法GE:ET|EATTF|TMFF(E)|iA+|-M*|/建立从E到i+i*i的最左推导左递归与死循环：EEAT,必须消除左递归,直接左递归的消除,前提：掌握算法2.1-2.6消除无用符号和产生式、产生式和单产生式直接左递归的形式：AA，V+直接左递归的消除方法一：将AA|改写为A方法二：引入A，改写为AA和AA|一般化：将AA1|A2|An|1|2|m改写为：A1A|2A|mA和A1A|2A|nA|,左递归的消除,从线性方程组到矩阵方程从3类文法到2类文法只关心产生式右部各符号串的首字符对n个非终结符X1Xn，得到矩阵方程或表示为：X=XA+B方程的解为：X=BA*,回避闭包A*的计算,由于A*=I+A+A2+=I+AA*(r*=|rr*)若令A*=Z，则对X=BA*可得X=BZ和Z=I+AZX会不会产生左递归Z会不会产生左递归,例子与练习,消除下列文法的左递归1）SSa|Ab|a，ASc2）SAS|b,ASA|a,FIRST集的定义,对符号串,FIRST()=a|*a,且aVT,V*,(当*,约定FIRST(),即FIRST()由推导出的每个符号串的首个终结符组成。若以终结符a打头，则FIRST()=FIRST(a)=a若以非终结符X打头，则FIRST()=FIRST(X)=,构造FIRST(X)集1/2,令X，YiVN，aVT，X的产生式具有下述3种形式：,构造FIRST(X)集2/2,SetFIRST(X)ft=;if(XVT)returnX;if(XP)ft+=;forEach(XY1Y2YkP)forEach(Yi)if(FIRST(Yi)ft+=(FIRST(Yi)-);if(i=k)ft+=;elseft+=FIRST(Yi);break;returnft;,例题与练习,对文法GE:ETEEATE|TFTTMFT|F(E)|iA+|-M*|/求每个非终结符的FIRST集合。练习：P173,4-4之求FIRST集,FOLLOW集的定义,对非终结符X，FOLLOW(X)=a|S#*Xa,且aVT#,V*,即FOLLOW(X)由语言中可能出现在X后面的终结符组成。,构造FOLLOW集1/2,令XVN，,V*，X的产生式具有下述4种形式：,构造FOLLOW集2/2,SetFOLLOW(X)if(X=SGS)return#fw=;forEach(AXP)if(FIRST()fw+=(FIRST();fw+=FOLLOW(A);elsefw+=FIRST();forEach(AXP)fw+=FOLLOW(A);returnfw(X);,例题与练习,对文法GE:ETEEATE|TFTTMFT|F(E)|iA+|-M*|/求每个非终结符的FOLLOW集合。练习：P173,4-4之求FOLLOW集,4.1FIRST和FOLLOW的区别,令XVN，有如下断言：,FIRST(X)，,FOLLOW(X)，,#FIRST(X)，,#FOLLOW(X)，,可能为真,一定不为真,一定不为真,可能为真,#FOLLOW(X)为真的条件是什么？,LL(1)文法,自顶向下的语法分析过程：为了实现无回溯的自顶向下语法分析，需满足对于G中的每个产生式A1|2|m,满足FIRST(i)FIRST(j)=，(1i,jm,ij)若有j*,则FIRST(i)FOLLOW(A)=,(i=1.m,ij)把满足上述条件的文法称为LL(1)文法自左向右扫描L最左推导L向前查看一个字符(1),某些非LL(1)文法的改造,1）消除左递归2）提取公因子若有形如A1|2|n则提取公因子后，上述产生式被替换为以下两个产生式：AAA1|2|n,若1n之间还有公因子，则继续提取,LL(1)文法的递归下降分析法,递归下降分析法的原理：对于文法的每个非终结符,根据其各候选式的结构,为其建立一个递归的子程序(函数),用于识别该非终结符所表示的语法范畴。,递归下降分析法1/2,例如,产生式E+TE,相应的子程序(函数)expr_prime()if(match(PLUS)/Lookahead=PLUSadvance();/Lookahead=nexttokenterm();expr_prime();,i+i*j-k,递归下降分析法2/2,验证4.2文法Gstatements:statementsexression;statements|expressiontermexpressionexpression+termexpression|termfactortermterm*factorterm|factornum_or_id|(expression)为LL(1)文法条件。阅读P114-119程序4-1,4-2,4-3。,LL(1)文法回顾,LL(1)文法,无（最）左递归（最）左公因子要合并,First集不相交，或First集与Follow集（当产生式的某可选右则可推出）不相交,递归下降分析法,非终结符=一个递归的子函数,自顶向下分析程序的手工构造,是否存在向顶向下分析程序的自动构造方法？,自动构造自顶向下分析程序的思想,预测语法分析机,预测分析表,预制软件,1.预测分析机的逻辑结构,t1t2titn#,tiYZ#,输入单词流,分析栈,分析表为二维数组，M:VN(VT#)(PERR),MA,ti的值按下述规则确定:对于每个产生式A1|2|m,(1)若tiFIRST(i),则置MA,ti=“Ai”;,(2)FIRST(i),tiFOLLOW(A),置MA,ti=“Ai”,(3)除上述两种情况外,其它元素均填“ERR”.,分析表元素的含义:指明当前应用何产生式进行推导,或指明输入串出现错误,2.分析机的工作原理-1初始化分析栈,#,S,2.分析机的工作原理-2.1分析栈顶为VN,#,分析栈,输入单词流,X1X2Xm,V,XmX2X1,VN出栈查分析表，if单元格非ErrorthenVN产生式右则逆向压栈,VVN,VX1X2Xm,2.分析机的工作原理-2.2分析栈顶为VT,#,分析栈,输入单词流,Xm.X2Yn.a2,t1,t1,2.分析机的工作原理-2.3分析成功格局,分析成功意味着什么？,输入串是分析表所对应文法的句子,2.分析机的工作原理-2.4语法错误的识别-1,#,分析栈,输入单词流,Xm.X2Yn.Y2,Y1,分析栈顶Y1为VN,2.分析机的工作原理-2.4语法错误的识别-2,#,分析栈,输入单词流,Xm.X2Yn.Y2,a1,分析栈顶a1为VT,3.预测分析法实例-1文法,GE:ETEEATE|TFTTMFT|F(E)|iA+|-M*|/,GE是LL(1)文法吗？,3.预测分析法实例-2预测分析表,GE:ETEEATE|TFTTMFT|F(E)|iA+|-M*|/,i+-*/()#,ETETE,EATEATE,TFTFT,TMFTMFT,Fi(E),A+-,M*/,在分析表单元格中我们有意省略了左侧的非终结符(why?).,实际存储表时,还可用产生式编号作为单元格内容，以进一步减少表的存储空间,1.i+i*i#,E,初始化分析栈,#,3.预测分析法实例,步骤分析栈余留输入串所用产生式,ETE,2.#i+i*i#,ET,逆向压入分析栈,VN，出栈,E,3.预测分析法实例,步骤分析栈余留输入串所用产生式,1.#Ei+i*i#ETE,TFT,2.#ETi+i*i#,3.#ETFi+i*i#,Fi,4.#ETii+i*i#,3.预测分析法实例,步骤分析栈余留输入串所用产生式,1.#Ei+i*i#ETE,2.#ETi+i*i#,3.#ETFi+i*i#,4.#ETii+i*i#,TFT,Fi,5.#ET+i*i#,3.预测分析法实例,步骤分析栈余留输入串所用产生式,1.#Ei+i*i#ETE,2.#ETi+i*i#,3.#ETFi+i*i#,4.#ETii+i*i#,TFT,Fi,5.#ET+i*i#,T,6.#E+i*i#,下一步是什么？,3.预测分析法实例,步骤分析栈余留输入串所用产生式,6.#E+i*i#,i+-*/()#,ETETE,EATEATE,TFTFT,TMFTMFT,Fi(E),A+-,M*/,请大家写完余下的分析,3.预测分析法实例,6.#E+i*i#EATE,步骤分析栈余留输入串所用产生式,7.#ETA+i*i#A+,8.#ET+i*i#,9.#ETi*i#TFT,10.#ETFi*i#Fi,11.#ETii*i#,12.#ET*i#TMFT,13.#ETFM*i#M*,14.#ETF*i#,15.#ETFi#Fi,3.预测分析法实例,步骤分析栈余留输入串所用产生式,15.#ETFi#Fi,16.#ETii#,17.#ET#T,18.#E#E,19.#成功,回顾与扩展,为什么要限制为LL(1)文法？LL(1)文法的设计思想？LL(k)文法,自底向上的语法分析,例子：SAB|cAbA|aBaSb|c用最左归约分析符号串bbaacb是否句子的过程两个重要动作：移近与归约简单优先分析法算符有限分析法LR分析法,简单优先分析法1/3,对规范句型中任意两个相邻符号Si和Sj，它们和的句柄间的关系必然是如下4种情况之一Si在句柄中，Sj不在句柄中Si先于Sj被归约（Sj必为终结符？）Si和Sj均在句柄中Si和Sj同时被归约Si不在句柄中，Sj在句柄中Sj先于Si被归约（Si是否必为终结符？）Si和Sj均不在句柄中在其它规范句型中可能存在先后被归约的次序也可能不具有先后关系,简单优先分析法2/3,例4.4（P128）如何求优先关系？简单优先分析算法，程序4-4（P130）理解表4-5（P131）,简单优先分析法3/3,局限性与文法改造进一步扩展：算符优先分析法+T+T*,算符优先分析法1/2,广义运算符（终结符）文法限制：产生式右部不允许出现两个非终结符相连的情况确定终结符（算符）间的优先级Uab或UaAb：a=b有UaA和（A+b或A+Bb）：ab若满足任何一对终结符间至多只有一种关系成立，则称为算符优先分析,算符优先分析法2/2,素短语与最左素短语树架子特点与优缺点,回顾,特点和局限性LL(1)分析法往前看一个字符，根据它来选定产生式各候选式的First集互不相交（出现还包括Follow集）简单优先分析法各个符号间至多只能有一种优先关系算符优先分析法各个终结符间至多只能有一种优先关系至多有一产生式对应终结符的组成形式(N1aN2bN3c),LR分析器简介,总控程序,分析表,分析栈,a1a2aian#,根据“现在”状态+输入V+分析表决定(移进、归约、接受、报错),一个LR分析例子,1.LE，L3.Ea2.LE4.EbP148表4-9，4-10，4-11，4-12Action：移近，归约，接受，出错Goto：状态转移程序4-6：pop（第i个产生式右部文法符号的个数）,如何产生分析表,LR(0)SLR(1)LR(1)LALR(1),一个例子,对AX1X2Xn，用有历史的状态表示归约到哪！SA|BAaAb|cBaBb|d若w是文法的句子，则w应可归约为S。又因为SA|B，则w应可归约为A或B。又因为AaAb|cBaBb|d，则w应可归约为aAb或c或aBb或d综合起来，若w是文法的句子，则其应可归约为S、A、B、aAb、c、aBb或d。因为尚无已归约出的符号，记为S、A、B、aAb、c、aBb和d。（记为起始状态S0）,若w=w1w2,进一步分析，若w=w1w2且w1VNVT若w1已归约为S，记为S，状态S1；若w2为#则w是句子，否则不是。若w1已归约为A，记为A；状态S2，则应将A归约为S，若w1已归约为B，记为B；状态S3，则应将B归约为S，若w1为a，记为aAb或aBb；状态S4，则应先分析w2能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）若w1为c，记为c；状态S5，则应将c归约为A若w1为d，记为d；状态S6，则应将d归约为B,若w2=w21w22,若w1为a，记为aAb或aBb；状态S4，则应先分析w2能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）若w21已归约为A，记为aAb；状态S7，则需先分析w22是否为b（分析到aAb时再归约为A）若w221为b，记为aAb；状态S8，则应将aAb归约为A若w21已归约为B，记为aBb；状态S9，则需先分析w22是否为b，（分析到aBb时再归约为B）若w221为b，记为aBb；状态S10，则应将aBb归约为B因为AaAb|cBaBb|d，所以w21可能为aAb或c或aBb或d若w211为a，记为aAb或aBb；则应先分析w212能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）；状态S4！若w211为c，记为c；则应将c归约为A；状态S5！若w211为d，记为d；则应将d归约为B；状态S6！,回顾LR分析中的“历史”、“现在”与“未来”,总控程序,分析表,分析栈,a1a2aian#,根据“现在”状态+输入V+分析表决定(移进、归约、接受、报错),LR(0)分析表1/3,为了预防开始符号S出现在产生式右部导致分析复杂化，引入新的开始符号S和SS，G称为G的拓广文法。显然L(G)=L(G)，加入圆点，分隔已识别部分，得到LR(0)项目SS产生SS和SS两个项目对LR(0)项目，对应刚才的分析过程，建立DFAI0=SS，SA，SB，AaAb，Ac，BaBb，Bd也称为基本项目集SS的闭包。闭包如何计算？,LR(0)分析表2/3,DFA与活前缀规范句型不含句柄右部符号的前缀称为活前缀LR(0)项目的分类归约项目：在产生式最右端移近项目：紧跟在后的符号为终结符待约项目：紧跟在后的符号为非终结符LR(0)的限制不允许移近和归约项目并存不允许多个归约项目并存,LR(0)分析表3/3,(1)AX项目属于Ii,且GO(Ii,X)=Ij若XVT,则置ACTIONi,X=sj,否则(XVN),置GOTOi,X=j;(2)A项目属于Ii,且A是P中第j产生式,则对于aVT#,置ACTIONi,a=rj(3)若接受项目SS属于Ii,则置ACTIONi,#=“acc”(4)在表中其它未填入信息的栏目中均填“ERR”.在存储ACTION表时,可用正负值分别表示归约和移进.,LR(0)分析表构造例子,文法GS的扩展文法0.S-S1.S-A2.S-B3.A-aAb4.A-c5.B-aBb6.B-d,LR(0)SLR(1),LR(0)的限制不允许移近和归约项目并存不允许多个归约项目并存项目集Bb,A,C哪里冲突？如果希望能够通过向后看多一个字符，来判断应移近或归约成什么，那么应该如何做？Follow(A)、Follow(C)与b需要满足什么情况？,试求下述例子的LR(0)或SLR(1)分析表,SSSCbBAAAab|abBC|DbCaDa,SLR(1)的局限性,利用Follow集确定归约可能产生的问题Follow集不考虑上下文归约需要考虑上下文（有状态的历史）所以，可能归约出“死前缀”（非活前缀）所以，需要明确的考察下一个字符可能或应该是什么加了“”，再加“，a”表示后续可能是什么字符A,a,LR(1)的分析表,先求出First集，在LR(0)的基础上从SS,#产生SCbBA,#，再产生Ca,b，为什么从变成b?SCbBA,#，BC,?1BDb,?2Ca,?3Da,?4?1-?4分别是什么？,由LR(1)的DFA到分析表,根据“，a”逗号后面的a确定action该移近，还是归约Goto内容与LR(0)类似对前部相同的项目，合并“，a”逗号后面的内容，得到LALR(1),一个例子,对AX1X2Xn，用有历史的状态表示归约到哪！SA|BAaAb|cBaBb|d若w是文法的句子，则w应可归约为S。又因为SA|B，则w应可归约为A或B。又因为AaAb|cBaBb|d，则w应可归约为aAb或c或aBb或d综合起来，若w是文法的句子，则其应可归约为S、A、B、aAb、c、aBb或d。因为尚无已归约出的符号，记为S、A、B、aAb、c、aBb和d。（记为起始状态S0）,若w=w1w2,进一步分析，若w=w1w2且w1VNVT若w1已归约为S，记为S，状态S1；若w2为#则w是句子，否则不是。若w1已归约为A，记为A；状态S2，则应将A归约为S，若w1已归约为B，记为B；状态S3，则应将B归约为S，若w1为a，记为aAb或aBb；状态S4，则应先分析w2能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）若w1为c，记为c；状态S5，则应将c归约为A若w1为d，记为d；状态S6，则应将d归约为B,若w2=w21w22,若w1为a，记为aAb或aBb；状态S4，则应先分析w2能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）若w21已归约为A，记为aAb；状态S7，则需先分析w22是否为b（分析到aAb时再归约为A）若w221为b，记为aAb；状态S8，则应将aAb归约为A若w21已归约为B，记为aBb；状态S9，则需先分析w22是否为b，（分析到aBb时再归约为B）若w221为b，记为aBb；状态S10，则应将aBb归约为B因为AaAb|cBaBb|d，所以w21可能为aAb或c或aBb或d若w211为a，记为aAb或aBb；则应先分析w212能否归约为Ab或Bb（分析到aAb或aBb时再归约为A或B）；状态S4！若w211为c，记为c；则应将c归约为A；状态S5！若w211为d，记为d；则应将d归约为B；状态S6！,LR(0)分析表1/2,为了预防开始符号S出现在产生式右部导致分析复杂化，引入新的开始符号S和SS，G称为G的拓广文法。显然L(G)=L(G)，加入圆点，分隔已识别部分，得到LR(0)项目SS产生SS和SS两个项目对LR(0)项目，对应刚才的分析过程，建立DFAI0=SS，SA，SB，AaAb，Ac，BaBb，Bd也称为基本项目集SS的闭包。闭包如何计算？,LR(0)分析表2/2,DFA与活前缀规范句型不含句柄右部符号的前缀称为活前缀LR(0)项目的分类归约项目：在产生式最右端移近项目：紧跟在后的符号为终结符待约项目：紧跟在后的符号为非终结符LR(0)的限制不允许移近和归约项目并存不允许多个归约项目并存,回顾LR分析中的“历史”、“现在”与“未来”,总控程序,分析表,分析栈,a1a2aian#,根据“现在”状态+输入V+分析表决定(移进、归约、接受、报错),LR(0)分析表1/3,为了预防开始符号S出现在产生式右部导致分析复杂化，引入新的开始符号S和SS，G称为G的拓广文法。显然L(G)=L(G)，加入圆点，分隔已识别部分，得到LR(0)项目SS产生SS和SS两个项目对LR(0)项目，对应刚才的分析过程，建立DFAI0=SS，SA，SB，AaAb，Ac，BaBb，Bd也称为基本项目集SS的闭包。闭包如何计算？,LR(0)分析表2/3,DFA与活前缀规范句型不含句柄右部符号的前缀称为活前缀LR(0)项目的分类归约项目：在产生式最右端移近项目：紧跟在后的符号为终结符待约项目：紧跟在后的符号为非终结符LR(0)的限制不允许移近和归约项目并存不允许多个归约项目并存,LR(0)分析表3/3,(1)AX项目属于Ii,且GO(Ii,X)=Ij若XVT,则置ACTIONi,X=sj,否则(XVN),置GOTOi,X=j;(2)A项目属于Ii,且A是P中第j产生式,则对于aVT#,置ACTIONi,a=rj(3)若接受项目SS属于Ii,则置ACT