编译 第三章 语法分析.ppt

第三章 语法分析,语法分析方法,自下而上是指:根据文法,对输入字串进行归约,若能正确地归约 为文法的初始符号,则表示输入字串是合法的.典型方法是算符优先分析法.自上而下是指:从文法的初始符号进行推导,若能推导出与输入 字串相同的句子,则表示输入字串是合法的.典型方法是递归下降分析法.,语法分析概述,3.1分析器的作用,一、语法分析的任务:把单词符号作为基本单位,根据文法,分析源程序(字符串)是否为合法的程序.同时报告语法错误并进行错误的恢复，使后面的分析能够进行下去。,二、语法错误的处理,程序的错误有各种不同的性质。例如，错误可能是：(1)詞法错误，如标识符、关键字或算符的拼写错误(2)语法错误，如算术表达式的括号不配对(3)语义错误，如算符作用于不相容的运算对象(4)逻辑错误，如无穷的递归调用。大多数错误的诊断和恢复集中在语法分析阶段，原因如下：(1)大多数错误是语法错误(2)诊断语法错误比诊断语义错误和逻辑错误容易得多。分析器出错处理的基本目标是：(1)清楚而准确地报告错误的出现；(2)迅速从每个错误中恢复过来，以便诊断后面的错误(3)不应使正确程序的处理速度降低太多。,三、错误恢复策略,(1)紧急方式恢复：发现错误时，分析器每次抛弃一个输入记号，直至输入记号属于某个指定的同步记号集合为止。同步记号一般是定界符，如分号或end。优点：方法简单，不会陷入死循环。适用于一个语句中很少出现多个错误的情况。(2)短语级恢复：发现错误时，分析器对剩余输入作局部纠正，用可以使分析器继续分析的输入串来代替剩余输入的前缀。如：用分号代替逗号、删除多余的分号、插入遗漏的分号。这种替换可用于纠正任何输入串，已经用于几个错误修复编译器，首先是用于自上而下的分析方法。它的主要缺点是很难应付实际错误出现在诊断点以前的情况。(3)出错产生式：如果对经常遇到的错误了解得很清楚，就可以扩充语言的文法，增加产生错误结构的产生式，用此扩充的方法来构造分析器。(4)全局纠正：在处理不正确的输入串时，作尽可能少的修改。,3.2上下文无关文法,文法：是描述语言的语法结构的形式规则(即语法规则)形式描述：用一组数学符号和规则来描述语言的方式。形式语言：形式描述所用的数学符号和规则。形式：指仅考虑数学符号间的推演,而不涉及符号的具体含义。上下文无关文法是这样一种文法:它定义的语法单位,独立于该语法单位可能出现的环境,不必考虑上下文关系.自然语言不是上下文无关文法;程序语言是上下文无关文法.程序设计语言的许多结构包含固有的递归性，可用上下文无关文法定义。例：如果S1和S2是语句，E是表达式，则“if E then S1 else S2”是语句。使用语法变量stmt表示语句类，用expr表示表达式类，上述语句可用文法产生式方便地表示为：stmtif expr then stmt else stmt,1.上下文无关文法定义 上下文无关文法 G 是一个四元组:G=(VT,VN,S,P)VT：是一个非空有限集,每个元素称为终结符.程序设计语言的文法中记号是终结符的同义词。例如：if,then,else,while,do,等都是终结符。VN：是一个非空有限集,每个元素为非终结符,代表了一种语法单位.且 VT VN=.例如:表达式,短语,语句等。S:是一个非终结符，称为开始符号,S VN.S 是文法G 的最高层次的语法单位.在程序语言中,S代表了程序这一语法概念.P:是产生式的有限集合。一条产生式定义了一个非终结符，产生式形式如下:A(A VN,(VT VN)*)称A定义为.(有时也会用:=代替)(VT|VN)*,例：文法(id,+,-,*,/,(,),expr,op,expr,P)定义了简单的算术表达式，P是由下列产生式组成的有限集合：exprexpr op exprexpr(expr)expr-exprexpridop+op-op*op/op,b)用英文大写字母表前面的字母、字母S、小写字母串代表非终结符;英文小写字母表前面的字母、数字、运算符号、标点符号、黑体字代表终结符;希腊字母、大写字母后面的字母、小写字目表后面的字母串等代表由VT,VN组成的符号串;即:,(VT VN)*.c)一个文法,可以仅用开始符号及产生式代替.例如:表达式的文法可以定义如下:E E+E|E-E|E*E|E/E|(E)E 为文法的开始符号,+-*/()为终结符.,例如：考虑一个文法G1:,S bAA|a aA 它定义了一个什么样的语言呢？S是开始符号，是非终结符A是非终结符是终结符与非终结符组成的字符串b是终结符a是终结符 结论：S baa*,例如：E=E+E=E*E+E=i*E+E=i*i+E=i*i+i,E是我们的开始符号，也是非终结符+、-、*、/是终结符i是终结符E+E、E*E+E、i*E+E、i*i+E是句型i*i+i是句子E=E+E、E+E=E*E+E、E*E+E=i*E+E、i*E+E=i*i+E是经一步推导出-直接推导E=i*i+i是经多步推导出-可推导出,一个句型到另一个句型的推导有两种方式:最左推导和最右推导:最左推导是指每次直接推导,对句型的最左非终结符实行替换;最右推导是指每次直接推导,对句型的最右非终结符实行替换.,例如：有文法G:E=E+E|E*E|E/E|E-E|i,最左推导：E=E+EE+E=E*E+EE*E+E=i*E+Ei*E+E=i*i+Ei*i+E=i*i+i最右推导：E=E+EE=E+iE=E*E+iE=E*i+iE=i*i+i,4 语法树与文法的二义性 语法树可以表示句型的推导及句型的层次结构.语法树是一棵倒立树,根结点表示了文法的初始符号,每进行一步推导,树的叶结点构成的有序序列构成一个句型.例如:E=E+E=E*E+E=i*E+E=i*i+E=i*i+i 可表示为:语法树可以表示同一句型的多种推导,是多种推导的共性抽象.但未必代表了同一句型的所有推导:E=E*E=E*E+E=i*E+E=i*i+E=i*i+i,语法树,定义:若文法 G 的某个句型存在两个不同的语法树表示,称该文法 是二义文法.因此,文法 E 是二义文法.二义性导致了i*i+i 的两种不同运算结果:(i*i)+i 以及 i*(i+i).编译中应避免二义文法.E 文法的二义性是因为没有规定*,+运算符的优先顺序,改进 E 后,得到:ET|E+T TF|T*F F(E)|i,E为表达式,T 为项,F 为因子,该文法对于句子i*i+i的各种推导,对应的语法树是唯一的.,E,E,T,+,T,F,T,*,i,F,i,F,i,3.3 语言和文法,1、文法的优点：文法给出了精确的、易于理解的语言语法说明。某些文法类可以自动产生高效的分析器，分析器的构造过程可以揭示出语法的二义性和其他难于分析的结构。设计的漂亮的文法把结构加于程序设计语言，这些结构对于把源程序翻译成为正确的目标代码和错误诊断都是很有用的语言也是逐渐完善的，需要补充新的结构和完成附加的任务。如果存在以文法为基础的语言的实现，这些新结构的加入就更方便。但是不是所有的语言都可以用上下文无关文法来描述，例如：我们变量的使用就要求先定义后使用，后面的使用就的根据前面的类型和属性来决定。即：程序语言也有一定的语言环境。因此我们强调语法分析器的输出结果。本章介绍语法分析，是分析语法结构，使用文法；而前一节词法分析，是分析我们的词法规则，使用正规式；他们有什么区别、联系、相似之处。,2、正规式和上下文无关文法的比较,正规式所描述的每一种结构都可以用上下文无关文法来描述。例如：正规式(a|b)*abb和上下文无关文法 A0 aA0|bA0|aA1 A1 bA2 A2 bA3 A3 描述同样的语言。既然上下文无关文法可以跟正规式等价，那么，我们为什么不在词法分析阶段不介绍正规式，而仅仅介绍上下文无关文法？（1）语言的词法规则非常简单，不必要功能更强大的上下文无关文法来描述它。（2）对于记号，正规式比上下文无关文法提供了更见解和易于理解的符号表式。（3）从正规式可以自动地构造出比从其他文法更有效的词法分析器。（4）把语言的语法结构分成词法和非词法两部分，为编译器前段的模块化分提供了方便的途径。,3.文法的表式及产生的语言,例如 文法：S(S)S|推导我们的文法产生式，每一次推导得到的终结符为（）或则，（）成对出现，而是空串，所以此文法描述的语言是所有的配对括号组合。例如 文法：S if expr then stml A A else B|B S|stml stml S|stml|推导文法产生式，可以得到我们的if语句的语法结构，包括if的嵌套结构，描述所有的if语句。例如 文法：S while expr do stml stml stml|推导文法产生式，得到该文法描述的是我们所有的while循环语句。,例如 设expr和term为非终结符，用以表式不同的优先级，终结符为id、括号、运算符等，facter为产生表达式的基本单位。则：文法一 facter id|(expr)term term*facter|term/facter|facter expr expr+term|expr-term|term 这个表达式文法是无二义性的，句子id+id+id和id+id*id的分析树如下：,文法二：facter id|(expr)term term+facter|term-facter|facter expr expr*term|expr/term|term 对于文法二，就具有二义性，优先级于我们的语法结构不能对应，我们再分析id+id*id，得到语法树：,4.消除二义性,从上面例题可以看出，消除文法的二义性，可以重写文法的产生式，来使我们的算符优先级、算符结合性与我们的语法树相对应。例如 文法：stml if expr then stml|if expr then stml else stml|other 这里other代表任何语句，按照这个文法，复合的条件语句：if e1 then s1 else if e2 then s2 else s3,每个else和最近的还没有配对的then配对,但是以上是二义文法，因为串if e1 then if e2 then s1 else s2有两棵语法树,可以使用下面的文法消除二义性，思想是每个then和else之间的语句必须是配对的，配对是不包括不配对语句的“if then-else”结构的，文法：stml matched_stml|unmatched_stml matched_stml if expr then matched_stml else unmatched_stml|other unmatched_stml if expr then stml|if expr then matched_stml else unmatched_stml 分析以上文法，对于复合的条件语句：if e1 then s1 else if e2 then s2 else s3 表示同样的意义，但对于if e1 then s1 else if e2 then s2 却限定了只有一种分析。,5.消除左递归,文法是左递归的，如果它有非终结符A，对于串a，存在着推导A Aa，至上而下的分析方法不能处理左递归文法，因此需要消除二义性，左递归的产生式A Aa|，可以用非左递归的产生式：A A A Aa|来代替，他们没有改变从A推导出的串集。例如：考虑下面的算术表达是文法：E E+T|T T T*F|F F(E)|id 消除E和T的直接左递归（形式为A Aa 的产生式），可以得到：,E TE E+TE|T FT T*FT|F(E)|id 不管有多少A的产生是，我们都可以用下面的技术消除直接左递归。首先把A的产生式组在一起：A Aa1|Aa2|Aam|1|2|n 其中i都不以A开头，ai都非空，由产生式：A 1A|2A|nA A a1A|a2A|amA|代替。以上变换可以删除左递归，但不能消除两步或多步推导形成的左递归。例如 考虑文法：S Aa|b A Ac|Sd|,非终结符S式左递归的，因为S Aa Sda，但它不是直接左递归。用S产生式替换A Sd中的S，得到下面的文法：S Aa|b A Ac|Aad|bd|删除其中的直接左递归，产生如下的文法：S Aa|b A bdA|A A cA|adA|例如：是消除下列文法的直接左递归：G1S:S Sa|Ab|b|c A Bc|a B Sb|b G2S:S a|(T)T T.S|S,解答：采用引进新的非终结符的方法，将G1S改为：S AbS|bS|cS S aS|A Bc|a B Sb|b 采用扩充的BNF范式描述的方法，可以得到G1S的无直接递归文法如下：S Aba|ba|ca A Bc|a B Sb|b,采用引进新的非终结符的方法，将G2S改为：S a|(T)T ST T.ST|采用扩充的BNF范式描述的方法，可以得到G2S的无直接递归文法如下：S a|(T)T S.S例如 已知文法GA:A AB|B B BC|C C D|D D(A)|i其中“”表式“非”运算，试构造该文法的等价的无左递归文法：,解答：这题实际上是要消除文法的左递归。既可用扩充的BNF范式，也可用引进新的非终结符号的方法。采用扩充的BNF范式描述的方法，可得无左递归文法如下：GA:A B B B C C C D|D D(A)|i例如 消除下列文法的左递归。S SaP|Sf|P P QbP|Q Q cSd|e 解答：该文法的左递归为直接左递归。,采用引进新的非终结符号的方法，将文法改为：S PS S aPS|fS|P QbP|Q Q cSd|e采用扩充的BNF范式描述的方法，可得无直接左递归文法如下：S Pf|PaP P QbP|Q Q cSd|e,6.提左因子,提左因子也是一种文法变换，它用于产生适合预测分析的文法。当我们不清楚应该用两个选择的哪一个来替换非终结符A时，可以重写A产生式来推迟这种决定，直到看见足够多的输入，能正确决定所需选择为止。例如，有两个产生式 stml if expr then stml else stml|if expr then expr 看见输入记号if的时候，不能马上决定用哪个产生式来扩展stml，一般地，如果A a1|a2是A的两个产生式，输入串是由从a推导出的非空串开始的，我们不知道是用a1扩展A还是用a2去扩展它。然而，可以通过先扩展A到aA来推迟这个决定然后，看完了从a推出的输入后，再扩展A到1或2，这就是提左因子，原来的产生式成为：A aA A 1|2,例如：下面的文法是从悬空else问题中抽象出来的：S iEtS|iEtSeS|a E b 这里的i，t和e分别代表if，then和else，E和S是表达式和语句提左因子后语法成为：S iEtSS|a S eS|E b 这样，如果输入是i，扩展S到iEtSS，等到iEtS都看见后，再决定扩展S到eS还是 当然，由于文法是二义的，对于输入e，为S取哪个选择是不清楚的以后讨论解决这个困难的办法,例如：抽象语言：L1=wcw|W属于（a|b）*.,L1的前后是相同的字符串w，即：a和b组成的字符串，中间由c隔开，例如：aabcaab，这个例子可以很好地说明程序中标识符的申明应先于它的引用。7.非上下文无关文法的语言结构 例如：语言L2=,分析得a和c的个数相同，b和d的个数相同，类似于前面的例子，他也可以代表我们程序中的过程申明时的形式参数的个数应该与过程调用时的实际参数的个数相等。,我们前面说过，程序设计语言都是上下文无关的，对吗？我们程序设计语言的文法也不全是上下文无关的，那么类是于L1、L2的文法都不是上下文无关的吗？先看下面的例子。,例如：L1=wcwr|w（a|b）*是上下文无关的，其中wr代表逆序的w，他可由下面的文法产生：SaSa|bSb|c例如：语言L2=，也是上下文无关的，文法是：,S aSd|aAdA bAc|bc,例如：语言L3=，也是上下文无关的，文法是：,S aSb|ab,思考：语言L3=，有限自动机能不能接受语言L3,8 乔姆斯基文法分类定义:若G=(VT,VN,S,P)的每一个产生式型如:,(VT VN)*,且 至少含有一个非终结符,称 G 为 0 型文法;,(VT VN)*,至少含有一个非终结符,且满足|,称 G 为 1 型文法;A A VN,(VT VN)*,称 G 为 2 型文法(上下文无关文法);A B 或A,A,B VN,VT*,称 G 为 3 型文法(正则文法).,3.4 算符优先分析法,算符优先分析法是一种简单实用的自下而上分析方法,本节将详细介绍该方法,包括 介绍 什么是算符优先文法,优先关系表构造,可归约串的刻画与寻找方法,算符优先分析算法等内容.1 算符优先文法定义1:若一个文法 G 的任何产生式右部,都不含两个相继出现的 非终结符,则称 G 为算符文法.,定义2:设 G 是一个算符文法,任何相继出现的终结符对之间存在如下三种归约优先顺序:1)a b 当且仅当 G 中含有型如 P.ab.或 P.aQb.的产生式;2)a b 当且仅当 G 中含有型如 P.aR.,且 R b.或 R Qb.;3)a b 当且仅当 G 中含有型如 P.Rb.,且 R.a 或 R.aQ.优先关系可以用矩阵表示,称为优先关系表.,定义3:若文法 G 的任何相继终结符对至多只满足以上关系之一,称该文法为算符优先文法.2 优先关系表的构造 给定一个算符优先文法,求各终结符对间的优先关系.,示例:设文法 G 为:EE+T|T TT*F|F F(E)|i,根据定义1,这是一个算符文法.,对每个非终结符,求出:FIRSTVT(F)=(,i LASTVT(F)=),i FIRSTVT(T)=*,(,i LASTVT(T)=*,),i FIRSTVT(E)=+,*,(,i LASTVT(E)=+,*,),i 优先关系表如下:,根据定义3,该文法是算符优先文法,3 可归约串 在算符优先分析法中,用最左素短语描述可归约串.定义:素短语是一个短语,它至少含有一个终结符,且除自身之外不 含更小的素短语.一个句型的最左素短语即为可归约串.例如:设文法 G 为:EE+T|T 句型 为:F*F+i TT*F|F F(E)|i根据短语的定义,F*F+i 有如下四个短语:,其中,素短语有:F*F,i 两个,最左素短语为:F*F,4 寻找最左素短语 根据定义,算符优先文法的句型必为如下形式:N1a1N2a2.NmamNm+1 其中 ai Vt Ni Vn Ni可有可无.定理:一个算符优先文法 G 的任何句型的最左素短语,为满足 如下条件的最左子串:最左素短语=Niai.NjajNj+1 且满足,因此,可以在归约栈中,通过比较优先关系,寻找最左素短语.,示例:设文法 G 为:EE+T|T TT*F|F F(E)|i,优先关系表如右,分析表达式 i+i*i 是否为合法的表达式,算符优先分析过程中,产生式以及非终结符名已不再起作用,只有优先关系表决定了分析过程.,3.5 递归下降分析法,递归下降分析法是一种自顶向下分析方法,从文法开始符号自左向右进行推导,若能推出一个与输入串相等的句子,说明输入串是合法的句子.1 递归下降分析法存在的问题 递归下降分析法本质上是一种最左推导,根据输入串选择相应产生式进行推导.,从上面分析可知:若允许 P a|a.的产生式,则输入字 a 面临多个产生式可选择用于推导,这种情况下,推导只能试探性的进行,一旦后续推导中不能匹配,再回过头(回溯)选择下一个产生式候选进行推导.这种方式效率低,因此,应消除回溯.另外,递归下降分析中,不允许有如下的左递归推导:P P 这种左递归推导,会导致不匹配任何输入字而无止境的推导(死循环).因此,递归下降分析法中存在两个主要问题:1)文法的左递归 2)文法的回溯,定义:设 A 1|2.|m,且有 1)FIRST(i)FIRST(j)=,i j;2)若 FIRST(i),则对任意 i(1im)满足 FIRST(i)FOLLOW(A)=;若文法 G 满足上面条件,则 G 就是无回溯文法,也称为 LL(1)文法.换句话说,只要根据输入的一个字,就能唯一地确定产生式候选,进行最左推导.一个文法是LL(1)文法,且不含左递归,就可以进行无回溯的递归下降分析.,3 消除文法的左递归 1)直接左递归的消除 若 文法 G 中含有型如 PP|的产生式,称 G 含有直接左递归.可将直接左递归改写为等价的不含左递归的产生式:P P P P|这两组产生式都可推导出:*;一般而言,若产生式为:PP 1|P 2|.|P m|1|2|.|n 则可改写为如下等价的产生式:P 1 P|2 P|.|n P P 1 P|2 P|.|m P|,5 递归下降分析程序的实现 为每一个非终结符编写一个子程序.设文法 G 为:EE+T|T TT*F|F 消除左递归后 F(E)|i 左递归的文法,ET EE+T E|TF TT*FT|F(E)|iLL(1)且无左递归,procedure E;T;E;,procedure E;if sym=+then advance;T;E;,procedure T;F;T;,procedure T;if sym=*then advance;F;T;,procedure F;if sym=i then advance else if sym=(then advance;E;if sym=)then advance else Error else Error;,ET EE+T E|TF TT*FT|F(E)|i,6.非递归的预测分析器,显式地维持一个状态栈；同时根据产生式推导出各种非终结符号的可能推导（分析表）；再从输入字符串入手，进行分析，查阅分析表，选择产生式。,例如：,分析器的工作过程：程序根据栈顶当前的符号X和输入串中的输入符号a决定分析器的动作，有4种可能：（1）如果X=a=，分析器宣告分析成功完成而停机。（2）如果X=a，分析器弹出栈顶符号X，推进输入指针，指向下一个符号。（3）如果X式终结符而不是a，则报告出错，调用错误恢复例程。（4）如果X是非终结符，程序访问分析表M，若MX,a是X产生式，例如：MX,a=XUVW，那么程序用UVW代替栈顶的X，让U在栈顶。例如：考虑文法 E TE E+TE|T FT T*FT|F(E)|id,输入字符串：id+id*id,分析器程序,让ip指向w的每一个符号；Repeat 让X等于栈顶符号，并且让a是ip指向的符号；if X是终结符或 then if X=a then 把X从栈顶弹出，并推进ip else error()else/*X是非终结符*/if MX,a=X Y1Y2YK then begin 从栈中弹出X；把YK,YK-1,Y1压入栈，Y1在栈顶；输出产生式X Y1Y2YKEndElse error()Until X=/*栈空*/,以上文法的分析表,输入字符串：id+id*id,EETETFETidETEET+ETETFETidETETF*ETFETidETE,id+id*idid+id*idid+id*idid+id*id+id*id+id*id+id*idid*idid*idid*id*id*ididid,ETETFTFidT E+TET FTF idT*FTF idT E,栈 输 入 输 出,5.构造分析表,算法：输入：文法G 输出：分析表M 方法：（1）对文法的每个产生式A a，执行(2)或(3)。（2）对FIRST(a)的每个终结符a，把A a加到MA,a中。（3）如果在FIRST(a)中，对FOLLOW(A)的每个终结符b(包括)，把A a加到MA,b中。（4）M的其他没有定义的条目是error.例如：上面介绍的文法 因为FIRST(TE)=FIRST(T)=(,id，那么产生式E TE使得ME,(和 ME,id包含条目E TE。产生式E+TE使ME,+得到E+TE。因为FOLLOW(E)=),产生式E 使得ME,)和 ME,得到E,以上文法的分析表,输入字符串：id+id*id,6.LL(1)文法,例如 文法：SiEtSS|a Ses|Eb 求它的分析表。,M(S,e)的条目包括S 和SeS，因为FOLLOW(S)=e,。这个文法是二义的，即：看见e不知道选用那一条产生式。也就是说，M含有多重定义的条目。,课堂练习,1、试构造生成语言L=的文法。2、构造一文法，产生任意长的a,b串，式的|a|b|2|a|，其中“|a|”表式a字符的个数。3、有如下文法 G1S:S AB A aAb|ab B Bc|G2S:S SAS|b|c A aaA|a 他们分别描述什么样的语言？,