第4章语法分析自上而下

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

第四章语法分析---自上而下4.1语法分析综述4.2自上而下分析4.3递归下降分析程序的构造4.4预测分析程序4.5LL(1)分析法2语法分析是编译过程的核心部分。语法分析的任务是分析一个文法的句子结构。语法分析根据文法的产生式,识别任何给定的输入符号串ω是否为该文法所产生的语言的句子,即ω∈L(G)?3源程序词法分析器语法分析器语义分析中间代码生成单词符号分析树符号表取下一个单词4通常分为两大类:自上而下分析方法(推导)从文法的开始符号出发,利用产生式逐步进行推导,看是否能推出给定的输入串。自底向上分析(归约)每次在句型中选择一个可归约的串,用产生式左部来代替它,逐步归约到文法的开始符号。5推导推导是从开始符号开始,通过使用产生式的右部代替左部,最终产生语言的一个句子的过程。最左(右)推导:每次替换符号串最左(右)非终结符。最右推导称为规范推导。归约归约是推导的逆过程,从给定的源语言的句子开始,通过使用产生式的左部代替右部,最终达到开始符号的过程。最左(右)归约是最右(左)推导的逆过程。最左归约称为规范归约。6句子主语谓语形容词名词谓语年轻名词谓语年轻女士谓语年轻女士动词宾语年轻女士喜欢宾语年轻女士喜欢形容词名词年轻女士喜欢红名词年轻女士喜欢红帽子句子→主语谓语主语→形容词名词谓语→动词宾语宾语→形容词名词形容词→年轻│红名词→女士│帽子动词→喜欢最左推导最右规约7自上而下分析法的主旨:从文法开始符号出发,自上而下的为输入串建立一棵语法树。自上而下分析法存在一些问题例:文法G1:S→cAdA→ab|a输入串:w=cad,为它建立语法树8ScAdabaS→cAdA→abA→a输入串w:文法G:IP1)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还有替换式未试过,还有可能匹配;语法树的形成9上述分析方法的实现:①每一非终结符对应一个递归子程序,在只生成两个串的文法,过程无须递归,而对生成无数个串的文法,递归是不可避免的;②递归子程序:是一个布尔过程,一旦发现它的某个候选式与输入串匹配,它就按此式扩充语法树,并返回true,指针移过已匹配子串。否则,返回false,保持原来的语法树和指针不变。10程序实现:使用记号:input_symbol:当前符号内容input_pointer:输入字符指针使用过程:ADVANCE():把input_pointer移到下一输入符号位置,置input_symbol是当前符号内容;使用两个过程:S()和A(),它们送回trueorfalse,决定于它们是否在输入串中找到相应的非终结符所构成的串。11procedureS();beginifinput_symbol=‘c’thenbeginADVANCE();ifA()thenifinputSymbol=‘d’thenbeginADVANCE();returntrueendend;returnfalse;end;procedureA();beginisave:=input_pointer;ifinput_symbol=‘a’thenbeginADVANCE();ifinputSymbol=‘b’thenbeginADVANCE();returntrue;endend/*failuretofindab*/input_pointer:=isave;ifinputSymbol=‘a’thenbeginADVANCE();returntrue;endelsereturnfalse;end;12例:表达式文法:如果完全按这个文法写递归分析程序,则会出现死循环。因为,对E过程,E又调用了E,…。没有终止条件。将这种产生式称为左递归。E→E+T|TT→T*F|FF→(E)|i13文法的左递归回溯用替换符的顺序会影响所接受的语言如:A→ab|a改为A→a|ab难以报告出错的确切位置穷举试探法——低效的分析方法14消除文法的左递归克服回溯问题15左递归一般有三种情况直接左递归:P→P(VNUVT)即在最左推导中有PP形式间接左递归:A→Bb,B→C,C→A即在最左推导中有PP形式潜在左递归:形如:N→αN,αε++16对于P→P1P2…|Pm12…ni≠,不以P开头改写为:P→1P2P………nPP→1P2P………mP17例:EE+TT,改写为:ETEE+TETT*FF,改写为:TFTT*FT18A→B…B→C…C→A…间接左递归:AB…C…A…例:文法GS→Qc|cQ→Rb|bR→Sa|a最左推导:SQcRbcSabc193.消除间接和潜在左递归(续)代入法将一个产生式规则右部的中的非终结符N替换为N的候选式。如果N有n个候选式,右边的重复n次,而且每一次重复都用N的不同候选式来代替N。例:N→Sa|Bc|ε在S→Nq中的代入结果为S→Saq|Bcq|q间接和潜在左递归通常通过代入能转换为直接左递归20对文法G的所有非终结符进行排序按上述顺序对每一个非终结符Pi依次执行:for(j=1;j=i-1;j++)将Pj代入Pi的产生式(若可代入的话);消除关于Pi的直接左递归;化简上述所得文法。21对文法的非终结符排序为R,Q,S。R不存在直接左递归,把R代入Q的产生式:Q→Sab|ab|b再把Q代入S:S→Sabc|abc|bc|c消除S的左递归:S→abcS|bcS|cSS→abcS|化简:Q和R的产生式不再被引用,删除Q和RS→Qc|cQ→Rb|bR→Sa|a22对非终结符排序的不同,最后得到的文法在形式上可能不一样,但它们等价的。例:若将非终结符排序为S,Q,R。S不存在直接左递归,Q的产生式不包含S,把S带入R得到:R→Qca|ca|a,R不存在直接左递归将Q带入R,得到:R→Rbca|bca|ca|a消除R的直接左递归:R→bcaR|caR|aRR→bcaR|文法改写为:(没有多余产生式,不需要化简)S→Qc|cQ→Rb|bR→bcaR|caR|aRR→bcaR|S→Qc|cQ→Rb|bR→Sa|a23回溯原因若当前符号=a,对A展开,而A→α1|α2|…|αm,那么,要知道哪一个αi是获得以a开头的串的唯一替换式。即:选择哪一个αi,亦即通过查看第一个(当前)符号来发现合适的替换式αi。怎样选择αi?以a为头的αi如有多个αi以a为头的,这是文法的问题24例如,有产生式:语句-if条件then语句else语句|while条件do语句|begin语句表end若要寻找一个语句,那么关键字if,while,begin就提示我们哪一个替换式是仅有可能成功的替换式。思考:若要求不得回溯,文法G(当然G不含左递归)的必要条件是什么,也即对文法有什么要求?25设α(VNUVT)*是所有非终结符的每个候选式,定义:FIRST(α)={a|αa…,aVT}若有α,则FIRST(α)直观理解:FIRST(α)是α的所有可能推导出的起始终结符或者。**26若一个A∈VN,就有若干FIRST(αi),如果A的任何两个候选式αi和αj,均有FIRST(αi)∩FIRST(αj)=φ意味着,A的每一候选式α推导后所得的字符串的第一个终结符均不同。于是,对输入符号a,如果a∈FIRST(αi),则anot∈FIRST(αj),(j≠i),因此,对A的展开无疑应选候选式αi,才有可能命中。27消除回溯的目的非终结符A的所有侯选式的首符集两两不相交消除回溯的方法提取公共左因子若:A→δβ1|δβ2|…|δβn|γ1|γ2|…|γm(其中,每个γ不以δ开头)那么,可以把这些规则改写成A→δA′|γ1|γ2…|γmA′→β1|β2|…|βn28在不含左递归且每个非终结符的所有候选式的终结首符集两两不相交时就有可能构造一个不带回溯的自上而下分析程序,这个程序由一组递归过程组成,每个过程对应文法的一个非终结符。这样的分析程序就称为递归下降分析器29例.有文法GE→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i每个非终结符对应的递归子程序如下:30E→TE’PROCEDUREEBEGINT;E’END;T→FT’PROCEDURET;BEGINF;T’END;E’→+TE’|εPROCEDUREE’BEGINIFSYM=‘+’THENBEGINADVANCE;读入下一个字符T;E’ENDEND;31T’→*FT’|εPROCEDURET′;IFSYM=‘*’THENBEGINADVANCE;F;T′END;F→(E)|iPROCEDUREF;IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCE;E;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;32i1+i2*i3分析过程:ETE΄FT΄i1εPROCEDUREE;BEGINT;E′END;PROCEDURET;BEGINF;T′END;PROCEDUREF;IFSYM=‘i’THENADVANCEELSEIFSYM=‘(’THENBEGINADVANCE;E;IFSYM=‘)’THENADVANCEELSEERRORENDELSEERROR;PROCEDURET′;IFSYM=‘*’THENBEGINADVANCE;F;T′END;33E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|ii1+i2*i3分析过程:ETE΄FT΄+E΄TFT΄*FT΄i1εi2i3εεPROCEDUREE′;IFSYM=‘+’THENBEGINADVANCE;T;E′END;PROCEDURET′;IFSYM=‘*’THENBEGINADVANCE;F;T′END;34E→TE’E’→+TE’|εT→FT’T’→*FT’|εF→(E)|i递归下降程序直观、易设计,但效率可能比较低。递归下降分析法存在的问题:用递归子程序描写递归下降分析器,要求实现该编译系统的语言允许递归。改进:使用一张分析表和一个栈同样可实现递归下降分析,用这种方法实现的语法分析程序叫预测分析程序。35……a……﹟总控程序预测分析表Mx…#输出输入串36一个输入:含有要分析的串,右端有#一个栈:栈底是#,栈内是一系列文法符号开始时,#和S(开始符号)先进栈分析表:二维数组M[A,a],其中:a∈VT;A∈VN输出:根据分析表内元素做规定的语义动作37栈顶元素为X,当前输入符为a,由(X,a)决定程序动作,三种可能:1)若X=a=#,分析停止,宣告成功地完成分析;2)若X=a≠#,则X弹出栈,下移输入指针;3)若X∈VN,则去查分析表M的元素M[X,a],该元素或为X的产生式,或为一个出错元素。若M[X,a]为空,则出错;若M[X,a]有一个产生式X→X1…Xn,则将产生式右部符号串以反序进栈。38有文法GS→AaS|BbS|dA→aB→ε|cabcd#SS→AaSS→BbSS→BbSS→dAA→aBB→εB→c预测分析表步骤栈余留符号串下一步动作(1)#Saabd#(2)(3)(4)(5)(6)(7)(8)(9)(10)分析:aabd用S→AaS,AaS逆序进栈#SaAaabd#用A→a,a进栈#Saaaabd##Saabd##Sbd##SbB#Sb#S#d

1 / 68
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功