编译程序的组织 (8).ppt
12.5 2.5 上下文无关文法的句型分析上下文无关文法的句型分析 句型的分析句型的分析就是识别一个符号串是否为某文法的句型，就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。是某个推导的构造过程。句型分析句型分析是识别一个输入符号串是否为语法上正确的是识别一个输入符号串是否为语法上正确的程序的过程。程序的过程。在语言的编译实现中，把完成句型分析的程序称为分在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称析程序或识别程序，分析算法又称识别算法识别算法。2常见分析方法有常见分析方法有自顶向下分析自顶向下分析和和自底向上分析自底向上分析两类；两类；自上而下分析法，自上而下分析法，是从文法的开始符号出发，反复使用各是从文法的开始符号出发，反复使用各种产生式，寻找种产生式，寻找“匹配匹配”于输入符号串的推导。于输入符号串的推导。自下而上的方法，自下而上的方法，则是从输入符号串开始，逐步进行则是从输入符号串开始，逐步进行 归约归约，直至归约到文法的开始符号，直至归约到文法的开始符号。3自上而下的语法分析自上而下的语法分析例：文法例：文法G G：S cAdS cAd A ab A ab A a A a识别输入串识别输入串w=cabdw=cabd是否该文法的句子是否该文法的句子 推导过程：推导过程：S cAd cabdScAda b4自下而上的语法分析自下而上的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否该文法的句子是否该文法的句子规约过程：规约过程：S cAd cabd S A c a b d规范推导规范推导(1)E E+T E+T*F T+T*F T+T*i F+T*i i+T*i i+F*ii+i*i(2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*F i+i*i(3)E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*i(4)推导过程可能不唯一。推导过程可能不唯一。例如，文法例如，文法GEGE中从中从 E E 到到 i+i*i i+i*i 的推导有：的推导有：最左推导最左推导最右推导最右推导例：例：GE：EE+T|TTT*F|FF（E）|i形式上，形式上，从符号串从符号串 到符号串到符号串 的推导序列的推导序列 *xUy xuy*总有总有 x VT*(y VT*)时，称为时，称为最左（右）推导最左（右）推导定义：最左（右）推导所得句型称为定义：最左（右）推导所得句型称为左（右）句型；左（右）句型；最最右推导右推导称为称为规范推导规范推导；右句型右句型称为称为规范句型规范句型。每个每个句子句子都有相应的最左和最右推导，因此，都有相应的最左和最右推导，因此，句子即是句子即是左句型左句型也是也是右句型右句型（规范句型）（规范句型）并不是每个句型都有最左和最右推导并不是每个句型都有最左和最右推导规范推导规范推导 E E+E+i*T E+i*T 即不是左句型，也不是右句型即不是左句型，也不是右句型因为因为最左（右）推导不出这个句型最左（右）推导不出这个句型例：例：GE：EE+T|TTT*F|FF（E）|i对于给定的符号串对于给定的符号串w，采用，采用自顶向下自顶向下的分析来判断的分析来判断w是否为是否为L(GS)的句子的常见方法是：的句子的常见方法是：试图建立从开始符试图建立从开始符 S到到w最左推导最左推导:S*w 显然，每步推导时，对应于最左非终结符相应的产生式可能显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。因此，会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是推导过程可能是带回溯带回溯的的。规范推导规范推导例：例：GE：EE+T|TTT*F|FF（E）|I 句型：句型：i+i*i 为提高效率，就应尽量避免回溯为提高效率，就应尽量避免回溯(1)E T F i(2)E E+T T+T F+T i+T i+T*F i+F*F i+i*F i+i*F i+i*i自底向上的语法分析自底向上的语法分析自底向上的语法分析自底向上的语法分析就是从已给的符号串就是从已给的符号串w出发，试图以相反的出发，试图以相反的方向为方向为w建立一个规范推导，最终得到文法的开始符建立一个规范推导，最终得到文法的开始符。例：例：GE：EE+T|TTT*F|FF（E）|I句型句型 i i+i*i+i*i最右推导：最右推导：=E E+T E+T*F E+T*i E+F*i E+i*i T+i*i F+i*i i+i*I =归约归约自底向上的语法分析自底向上的语法分析归约归约:符号串符号串:产生式产生式A A 例：例：GE：EE+T|TTT*F|FF（E）|I句型句型 F F+i*i+i*iF+i*i F+i*i 归约归约 T+i*iT+i*iTF若从给定的符号串若从给定的符号串w出发，一步步地将其归约，最终得到文法的开始出发，一步步地将其归约，最终得到文法的开始符号，则说明符号，则说明w是该文法定义的一个句子。归约成功，否则，归约失是该文法定义的一个句子。归约成功，否则，归约失败。败。若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是则称该归约是规范归约规范归约（即（即最左归约最左归约）。）。规范归约是规范推导的逆过程规范归约是规范推导的逆过程。10短语、直接短语、句柄的定义短语、直接短语、句柄的定义 短语：短语：文法文法GS,S=*AGS,S=*A且且 A-*A-*，则称则称是句型是句型相对于非终结符相对于非终结符A A的短语。的短语。直接短语：直接短语：若有若有A A ，则称，则称是句型是句型 相对于非终结符相对于非终结符A A 的直接短语。（表明含的直接短语。（表明含A A 的产生式）的产生式）句柄：句柄：一个句型的最左直接短语称为该句型的句柄。一个句型的最左直接短语称为该句型的句柄。从语法树上可以清晰的看到：从语法树上可以清晰的看到：(2)E(2)E*E+T*F+F F E+T*F+F Fi,i,i i是是句型 E+T*F+i 相对于产生式相对于产生式F-iF-i的的直接短语直接短语;(3)(3)E E*E+i E+i与与 E E+E+T*F,E+T*F,E+T*FE+T*F是是相对于非终结符相对于非终结符E E的的短语短语;(4)E(4)E*E+T*F+i,E+T*F+i E+T*F+i,E+T*F+i是是相对于相对于E E的的短语短语注注:由定义可知由定义可知,直接短语也是短语直接短语也是短语,但短语不一定是直接短语但短语不一定是直接短语.注意：注意：句型句型E+T*F+iE+T*F+i中中E+TE+T绝不是它的一个直接短语绝不是它的一个直接短语 不存在从不存在从E E到到E*F+iE*F+i的推导的推导.例：例：GE：EE+T|TTT*F|FF（E）|I句型句型 E+T*F+iE+T*F+i(1)E(1)E*E+T+i E+T+i E+T*F+i E+T*F+i T-T*FT-T*FT*FT*F是是句型句型 E+T*F+iE+T*F+i相对于产生式相对于产生式T-T*FT-T*F的的直接短语直接短语;自底向上分析过程中，主要问题就是寻找句柄自底向上分析过程中，主要问题就是寻找句柄,每步每步归约归约就是将句柄归约。就是将句柄归约。
