编译原理第四讲

1、Compiler Construction Principles1.文法的类型通过对产生式施加不同的限制，通过对产生式施加不同的限制，Chomsky将文法分将文法分为四种类型：为四种类型：0型文法：对任一产生式型文法：对任一产生式，都有，都有(V(VN NVVT T) )+ +， (V(VN NVVT T) )* *1 1型文法：型文法：对任一产生式对任一产生式，都有，都有|， 仅仅仅仅 SS除外除外2 2型文法：型文法：对任一产生式对任一产生式，都有，都有VVN N ， (V(VN NVVT T) )* *3 3型文法：型文法：任一产生式任一产生式的形式都为的形式都为AaBAaB或或AaAa

2、，其，其中中AVAVN N ，BVBVN N ，aVaVT TCompiler Construction Principles文法的类型例：例：1 1型（上下文有关）文法型（上下文有关）文法 文法文法GSGS： SCDSCDAbbAAbbA CaCA CaCABaaBBaaB CbCB CbCBBbbBBbbBADaDADaD C CBDbDBDbD D DAabDAabDCompiler Construction Principles文法的类型例：例：2 2型（上下文无关）文法型（上下文无关）文法 文法文法GS：SABABABS|0BS|0BSA|1SA|1Compiler Construc

3、tion Principles3型文法GS： S0A|1B|00A|1B|0A0A|1B|0S0A|1B|0SB1B|1|01B|1|0GI： I lT lTI l lT lT lTT dT dTT l lT d dCompiler Construction Principles2.文法之间的包含关系2型文法型文法1型文法型文法0型文法型文法四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系3型文法型文法Compiler Construction Principles3.文法和语言0型文法产生的语言称为型文法产生的语言称为0型语言型语言1 1型文法或上下文有关文法（型文法或上下文有关文法

4、（ CSG ）产生的语言称为产生的语言称为1 1型型语言语言或上下文有关或上下文有关语言（语言（CSL）2 2型文法或上下文无关文法（型文法或上下文无关文法（ CFG ）产生的语言称为产生的语言称为2型型语言语言或上下文无关或上下文无关语言（语言（ CF L ） 3 3型文法或正则（正规）文法（型文法或正则（正规）文法（ RG ）产生的语言称为产生的语言称为3型型语言语言正则（正规）正则（正规）语言（语言（ RL ） Compiler Construction Principles上下文无关文法及其语法树上下文无关文法有足够的能力描述程序设计语言的语法结上下文无关文法有足够的能力描述程序设计语

5、言的语法结构构语法树语法树-句型推导句型推导的的直观表示直观表示Compiler Construction Principles描述简单算术表达式的文法G=(E,+,*,i,(,),P,E)其中P为：Ei , EE+E , EE*E , E(E) 描述一种简单赋值语句的产生式：赋值语句i =E描述条件语句的产生式：条件语句if条件then语句 if条件then语句else语句Compiler Construction Principles1.规范推导和规范归约规范推导和规范归约Gs: SaAS ASbA ASS Sa Aba推导过程一：推导过程一：S aAS aAa aSbAa aSbbaa

6、aabbaa推导过程二：推导过程二：S aAS aSbAS aabAS aabbaS aabbaa推导过程三：推导过程三：S aAS aSbAS aSbAa aabAa aabbaaCompiler Construction Principles1.规范推导 规范句型最左（最右）推导：在推导的任何一步最左（最右）推导：在推导的任何一步，其中，其中、是句型，都是对是句型，都是对中的最左（右）非终结符进行替换中的最左（右）非终结符进行替换最右推导被称为规范推导。最右推导被称为规范推导。由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型规范推导的逆过程，称为最左归约，也称为规范归约。规

7、范推导的逆过程，称为最左归约，也称为规范归约。例：设有文法例：设有文法GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|a给出句子给出句子a+aa+a* *a a的最左和最右推导的最左和最右推导Compiler Construction Principles2.语法树设G=( VN,VT,P,S)为一cfg，若一棵树满足下列4个条件，则此树称作G的语法树(推导树)(派生树）：1. 每个结点都有一个标记，此标记是V的一个符号2. 根的标记是S3. 若一结点n至少有一个它自己除外的子孙，并且有标记A，则肯定AVN4. 如果结点n有标记A,其直接子孙结点从左

8、到右的次序是n1，n2，nk，其标记分别为A1，A2，Ak，那么AA1A2，Ak一定是P中的一个产生式语法树的结果：语法树的结果：从左到右读出叶子的标记而构成的行谓之 Compiler Construction Principles构造语法树GE E： EE+T|TEE+T|T TT TT* *F|FF|F F(E)|a F(E)|aE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aCompiler Construction PrinciplesE EE+T T+T F+T a+T a+T*F a+F*F a+a*F a+a*aE EE+T E+T*F E+T

9、*a E+F*a E+a*a T+a*a F+a*a a+a*aE EE+T T+T T+T*F F+T*F F+F*F a+F*F a+F*a a+a*a E E E + T E + T T T T T * * F F F F a F F a a a a a 看不出句型中的符号被替代的顺看不出句型中的符号被替代的顺序序Compiler Construction Principles一棵语法树表示了一个句型的种种可能的一棵语法树表示了一个句型的种种可能的( (但未必但未必是所有的是所有的) )不同推导过程，包括最左不同推导过程，包括最左( (最右最右) )推导。推导。但是，一个句型是否只对应唯

10、一的一棵语法树但是，一个句型是否只对应唯一的一棵语法树呢呢? ?一个句型是否只有唯一的一个最左一个句型是否只有唯一的一个最左( (最右最右) )推推导呢导呢? ?Compiler Construction Principles例：例：GE:GE:E iE iE E+EE E+EE EE E* *E EE (E)E (E) E E E + E E + E E E * * E i E i i i i i E E E E * * E E i E + E i E + E i i i i句型句型 i*i+i 的两个不同的最左推导：的两个不同的最左推导：推导推导1：E E+E E*E+E i*E+E i*

11、i+E i*i+i推导推导2：E E*E i*E i*E+E i*i+E i*i+iCompiler Construction Principles3.文法的二义性 若一个文法存在某个句子对应两棵不同的语法树，若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是则称这个文法是二义二义的的或者，若一个文法存在某个句子有两个不同的或者，若一个文法存在某个句子有两个不同的最左（右）推导，则称这个文法是最左（右）推导，则称这个文法是二义二义的的 Compiler Construction Principles文法的二义性和语言的二义性是两个不同的概念。因为可文法的二义性和语言的二义性是两个不同的

12、概念。因为可能有两个不同的文法能有两个不同的文法G G和和GG，其中，其中G G是二义的，但是却是二义的，但是却有有L(G)=L(G)L(G)=L(G)，也就是说，这两个文法所产生的语言，也就是说，这两个文法所产生的语言是相同的。是相同的。如果产生上下文无关语言的每一个文法都是二义的，则说如果产生上下文无关语言的每一个文法都是二义的，则说此语言是先天二义的。对于一个程序设计语言来说，常此语言是先天二义的。对于一个程序设计语言来说，常常希望它的文法是无二义的，因为希望对它的每个语句常希望它的文法是无二义的，因为希望对它的每个语句的分析是唯一的。的分析是唯一的。Compiler Construct

13、ion Principles判定任给的一个上下文无关文法是否二义，或它是判定任给的一个上下文无关文法是否二义，或它是否产生一个先天二义的上下文无关语言，这两个否产生一个先天二义的上下文无关语言，这两个问题是递归不可解的，但可以为无二义性寻找一问题是递归不可解的，但可以为无二义性寻找一组充分条件组充分条件二义文法改造为无二义文法二义文法改造为无二义文法GE: E i GEGE: E i GE：E T|E+TE T|E+T E E+E T F|T E E+E T F|T* *F F E E E E* *E F E F （E E）|i|i E (E) E (E) 规定优先顺序和结合律规定优先顺序和结

14、合律 Compiler Construction Principles句型的分析句型分析句型分析就是就是识别识别一个符号串是否为某文法的一个符号串是否为某文法的句型句型，是某个是某个推导推导的构造过程。的构造过程。在语言的编译实现中，把在语言的编译实现中，把完成句型分析完成句型分析的的程序程序称为称为分析程序分析程序或或识别程序识别程序。分析算法又称。分析算法又称识别算法识别算法。从左到右的分析算法从左到右的分析算法，即，即总是从总是从左左到到右右地地识别输入识别输入符号串符号串，首先识别符号串中的，首先识别符号串中的最左最左符号，进而符号，进而依依次识别右边次识别右边的一个符号，的一个符号，

15、直到分析结束直到分析结束。Compiler Construction Principles句型的分析算法分类分析算法可分为：分析算法可分为：自上而下分析法自上而下分析法：从文法的开始符号出发从文法的开始符号出发，反复使用文法的产生式，反复使用文法的产生式，寻找寻找与与输入符号串输入符号串匹配匹配的的推导推导。自下而上分析法自下而上分析法：从从输入符号串输入符号串开始开始，逐步进行逐步进行归约归约，直至，直至归约归约到到文法的文法的开始符号开始符号。 Compiler Construction Principles两种方法反映了两种语法树的构造过程。自上而下方法自上而下方法是从文法符号开始，将它

16、做为语法树的根，向下逐步建立语法树，使语法树的结果正好是输入符号串自下而上方法自下而上方法则是从输入符号串开始，以它做为语法树的结果，自底向上地构造语法树Compiler Construction Principles1.自上而下的语法分析例：文法例：文法G：S cAd A ab A a识别输入串识别输入串w=cabd是否为该文法的是否为该文法的句子句子SSScAdcAd a b推导过程：推导过程：S cAd cAd cabdCompiler Construction Principles2.自下而上的语法分析例：文法例：文法G： S cAd A ab A a识别输入串识别输入串w=cabd是

17、否该文法的是否该文法的句子句子SAA c a b d c a b d c a b d 规约规约过程构造的推导：过程构造的推导： cAd cabd S cAdCompiler Construction Principles句型分析中的关键问题1）在自上而下的分析方法中）在自上而下的分析方法中如何如何选择选择使用使用哪个哪个产生式产生式进行推导进行推导？假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B，且有，且有n条规则：条规则：BA1|A2|An，那么如何确定用哪个右部去替代，那么如何确定用哪个右部去替代B？2）在自下而上的分析方法中）在自下而上的分析方法中如何如何识别可归约的串识

18、别可归约的串？在分析程序工作的每一步，都是从当前串中在分析程序工作的每一步，都是从当前串中选择一个选择一个子串子串，将它，将它归约归约到到某个非终结符号某个非终结符号，该子串称为，该子串称为“可可归约串归约串”Compiler Construction Principles刻画“可归约串”文法文法GS句型的短语句型的短语S =* A且且 A =+ ，则称则称是是句型句型相对于相对于非终结符非终结符A的的短语短语句型的直接短语句型的直接短语若有若有A ，则称则称是句型是句型相对于非终结符相对于非终结符A 的的直接短语直接短语句型的句柄句型的句柄一个句型的一个句型的最左直接短语最左直接短语称为称为

19、该句型该句型的的句柄句柄Compiler Construction Principles例 ：i*i+i 的短语、直接短语和句柄 E E + T T FT * F i3 短语短语：i1* * i2+ + i3， i1* * i2 ，F i2 i1 ， i2 ， i3 。 i1 直接短语直接短语： i1 ， i2 ， i3 。句柄句柄： i1 GEGE：EE+T|TEE+T|T TT TT* *F|FF|F F(E)|i F(E)|i句型：句型：i i* *i+ii+iCompiler Construction Principles化简文法化简文法文法实用中的一些说明 文法中文法中不含有不含有有

20、害规则有害规则和和多余规则多余规则有害规则有害规则：形如：形如UU的产生式。会的产生式。会引起引起文法的文法的二义性二义性多余规则多余规则：指文法中：指文法中任何句子的推导任何句子的推导都都不会用到的规则不会用到的规则文法中文法中不含有不含有不可到达和不可终止的不可到达和不可终止的非终结符非终结符1）文法中某些）文法中某些非终结符不在任何规则的右部出现非终结符不在任何规则的右部出现，该非终，该非终结符称为结符称为不可到达不可到达。2）文法中某些）文法中某些非终结符非终结符，由它，由它不能推出终结符号串不能推出终结符号串，该非，该非终结符称终结符称为为不可终止不可终止。Compiler Cons

21、truction Principles 对于文法对于文法GS，为了保证任一非终结符，为了保证任一非终结符A在在句子句子推导中出现，必须满足如下两个条件：推导中出现，必须满足如下两个条件：1. A必须在某句型中出现必须在某句型中出现 即有即有S =* A，其中，其中，属于属于V V* * 2. 必须能够从必须能够从A推出终结符号串推出终结符号串t来来 即即A =* t，其中，其中tVT*Compiler Construction Principles化简文法化简文法l例：例：GS ： 1) SBe 2) BCe D为不可到达为不可到达 3) BAf C为不可终止为不可终止 4) AAe 5) A

22、e 6) CCf 7) Df 产生式产生式 2），），6），），7）为）为多余规则多余规则应去应去掉。掉。Compiler Construction Principles上下文无关文法中的规则上下文无关文法中某些规则可具有形式上下文无关文法中某些规则可具有形式A，称这，称这种规则为种规则为规则规则因为因为规则会使得有关文法的一些讨论和证明变得复规则会使得有关文法的一些讨论和证明变得复杂杂,有时会限制这种规则的出现有时会限制这种规则的出现两种定义的唯一差别是两种定义的唯一差别是句子在不在语言中句子在不在语言中文法构思的启示是要找出语言的有穷描述，而如果文法构思的启示是要找出语言的有穷描述，而如果

23、语言语言L有一个有穷的描述，则有一个有穷的描述，则L1=L也同样也同样有一个有穷的描述，并且可以证明，若有一个有穷的描述，并且可以证明，若L是上下是上下文有关语言、上下文无关语言或正规语言，则文有关语言、上下文无关语言或正规语言，则L和和L-分别是上下文有关语言、上分别是上下文有关语言、上下文无关语言和正规语言。下文无关语言和正规语言。Compiler Construction Principles思考思考本章目的为语言的语法描述寻求工具本章目的为语言的语法描述寻求工具,以便：以便：对源程序给出精确无二义的语法描述。（严谨、简洁、易读）对源程序给出精确无二义的语法描述。（严谨、简洁、易读）根据

24、语言文法的特点来进行语法分析根据语言文法的特点来进行语法分析从描述语言的文法可以自动构造出可用的分析程序从描述语言的文法可以自动构造出可用的分析程序制导语义翻译制导语义翻译1.什麽是文法,什麽是它的语言?2.我们为什麽关注上下文无关文法?3.语法分析方法的分类语法分析方法的分类?Compiler Construction Principles本章小结1.本章出现的概念较多本章出现的概念较多,应重点理解文法应重点理解文法,推导推导,句型句子及句型句子及语言的定义等概念语言的定义等概念.语法分析有关内容在后面章节会详细语法分析有关内容在后面章节会详细讨论讨论.2.文法作为程序语言的语法的描述工具文

25、法作为程序语言的语法的描述工具,它用它用规则只能陈述规则只能陈述的是的是:语言的所有句子以什麽样的符号串能出现语言的所有句子以什麽样的符号串能出现.请记住请记住文法和语言的形式定义中的文法和语言的形式定义中的 “形式形式”的含义的含义只涉及只涉及语语言的语法不涉及语言的语义言的语法不涉及语言的语义.3.本章内容是形式语言理论的一部分本章内容是形式语言理论的一部分.形式语言理形式语言理论是对符号串集合的表示法、结构及其特性的论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。研究。是程序设计语言语法分析研究的基础。 本章小结本章小结 考察本章知识点最典型的题目是考察本

26、章知识点最典型的题目是 1.1.已知文法已知文法GAGA，写出它定义的语言描述，写出它定义的语言描述 如：如：GA: A 0B|1CGA: A 0B|1C B 1|1A|0BB B 1|1A|0BB C 0|0A|1CC C 0|0A|1CC答案答案:GA:GA定义的语言由定义的语言由0 0、1 1符号串组成，串中符号串组成，串中0 0和和1 1的个数的个数相同相同. .2.2.给出语言描述，构造文法给出语言描述，构造文法. .如：构造一文法如：构造一文法, ,其定义的语言是由算符其定义的语言是由算符+, +, * *, (,), (,)和运算和运算对象对象a a构成的算术表达式的集合构成的算

27、术表达式的集合. .答案答案1: GE EE+T|T1: GE EE+T|T TT TT* *F|FF|F F(E)|a F(E)|a答案答案2: GE EE+E|E2: GE EE+E|E* *E|(E)|aE|(E)|aCompiler Construction Principles相关术语的回顾（英文版）相关术语的回顾（英文版）上下文无关文法A context free grammar(grammar for short) consists of terminals ,nonterminals,a start symbol,and productions.Terminals are th

28、e basic symbols from which strings are formed.Nonterminals are syntactic variables that denote sets of strings that help define the language generated by the grammar.In a grammar,one nonterminal is distinguished as the start symbol,and the set of strings it denotes is the language defined by the gra

29、mmar.The productions of a grammar specify the manner in which the terminals and nonterminals can be combined to form string.Compiler Construction Principles句型句子和语言句型句子和语言Given a grammar G with start symbol S,we can use the =* relation to define L(G),the language generated by G. Strings in L(G) may c

30、ontain only terminal symbols of G.We say a string of terminals w is in L(G) if and only if S =* w .The string w is called a sentence of G. If S =* ,wher may contain nonterminals then we say that is a sentential form of G Compiler Construction Principles验证文法生成的语言验证文法生成的语言A proof that a grammar G gene

31、rates a language L has two parts:we must show that every string generated by G is in L,and coversely that every string in L can indeed be generated by G.Compiler Construction Principles语法树和推导语法树和推导A parse tree may be viewed as a graphical representation for a derivation that filt out the choice rega

32、rding replacement order. The leaves of the parse tree are labeled by nonterminals or terminals and ,read from left to right,they constitute a sentential form,called the yield or frontier of the tree.Compiler Construction Principles句型分析，语法分析句型分析，语法分析Parsing is the process of determing if a string of

33、token can be generated by a grammar. Most parsing methods fall into one of two classes,called the top-down and bottom-up methods.These terms refer to the order in which nodes in the parse tree are constructed.In the former,construction starts at the root and proceeds towards the leaves,while,in the

34、later,construction starts at the leaves and proceeds towards the root.Compiler Construction Principles二义性二义性A grammar that produces more than one parse tree for some setence is said to be ambiguous. Put another way, an ambiguous grammar is one that produces more than one leftmost or more than rightmost derivation for the same sentence.Sometimes an ambiguous grammar can be rewritten to eliminate the ambiguity. For exmple suitable grammars for expression can often be constructed using associativity and precedence information ,as in the slide74 Compiler Constructi