编译原理 第三章

第三章文法和语言第3章文法和语言3.1文法的直观概念3.2符号和符号串3.3文法和语言的形式定义3.4文法的类型3.5上下文无关文法及其语法树3.6句型的分析3.7有关文法实用中的一些说明3.8典型例题及解答学习目标本章目的是为语言的语法描述寻求工具掌握对源程序给出精确无二义（严谨、简洁、易读）的语法描述手段之一---文法。熟练使用文法定义程序设计语言的单词和语法成分对形式语言的理论有一个初步基础本章知识点(内容)引言和预备知识文法和语言的形式定义文法的类型上下文无关文法及其语法树上下文无关文法的句型分析有关文法实用中的一些说明学习内容什么是文法,什么是它定义的语言？在乔姆斯基（Chomsky）的文法类型中，我们为什么关注上下文无关文法？什么是语法分析？语法分析方法的分类？一个程序设计语言一个记号系统，如同自然语言一样，它的完整定义包括语法和语意两个方面。语法：是指一组规则，用它可以形成和产生一个合法的程序。目前，文法是广泛使用的语法描述工具。语法只定义什么样的符号序列是合法的，与这些符号的含义毫无关系，如类型匹配、变量作用域等就无法使用使用文法来检查，这些工作属于语义分析的工作。语义有静态语义和动态语义。静态语义是一系列限定规则，确定那些合乎语法的程序是合适的；动态语义是指运行语义或执行语义， 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 明程序程序要做些什么，要计算什么。3.1文法的直观概念当我们表述一种语言时，无非是说明这种语言的句子如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了对于含有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明(或者定义)句子的组成结构-----汉语规则3.1文法的直观概念比如：“我是大学生”是汉语的一个句子。采用EBNF来表示汉语的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉3.1文法的直观概念有了句子的一组规则以后，我们可以按照如下方式用它们去推导或产生句子。从〈句子〉开始，逐渐用规则的右边代替左边，直到产生字符串。这个动作过程为：3.1文法的直观概念句子：“我是大学生”的全部动作过程是：〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生3.1文法的直观概念“我是大学生”的构成符合上述规则，而“我大学生是”不符合上述规则，我们说它不是句子。这些规则成为我们判别句子结构合法与否的依据，换句话说，这些规则看成是一种元语言，用它描述汉语。这里仅仅涉及汉语句子的结构描述。这样的语言描述称为文法。文法是描述语言的语法结构的形式规则。语言概述语言是由句子组成的集合，是由一组符号所构成的集合。汉语--所有符合汉语语法的句子的全体研究语言每个句子的含义每个句子和使用者的关系程序设计语言--所有该语言的程序的全体。研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法Syntax语义Semantics语用Pragmatics语法：表示构成语言句子的各个记号之间的组合规律语义：表示各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用：表示在各个记号所出现的行为中，它们的来源、使用和影响。如果不考虑语义和语用，即只从语法这一侧面来看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。3.2符号和符号串符号：可以相互区别的记号（元素）。字母表：是字母的非空有穷集合；用Σ、V表示。符号串：字母表中符号组成的任意有穷序列。空串：不含有任何符号的串称作空串，记作。1、空符号串ε(没有符号的符号串)是上的符号串2、若x是∑上的符号串，a是∑的元素，则xa和ax是∑上的符号串；y是∑上的符号串，当且仅当它可以由1和2导出。例：Σ={a,b}，则ε,a,b,aa,ab,aabba…都是上的符号串3.2符号和符号串符号串的运算符号串s的头（前缀）：移走符号串s尾部的零个或多于零个符号得到的符号串.如：b是符号串banana的一个前缀.符号串s的尾（后缀）：删去符号串s头部的零个或多于零个符号得到的符号串.如:nana是符号串banana的一个后缀.符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串.如:ana是符号串banana的一个子串.3.2符号和符号串固有头和固有尾：如果z=xy是一符号串，那么x是z的头，y是z的尾，如果x是非空的，那么y是固有尾；同样如果y非空，那么x是固有头。例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外，其它都是固有头；z的尾是ε,c,bc,abc，z的固有尾是ε,c,bc。几种写法当我们对符号z=xy的头感兴趣而对其余部分不感兴趣时，我们可以采用省略写法：z=x…；如果只是为了强调x在符号串z中的某处出现，则可表示为：z=…x…；符号t是符号串z的第一个符号，则表示为z=t…。符号串的运算符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。ε的长度为0连接（乘积）运算：定义：符号串x、y的连接,是把符号串y写在符号串x之后的新符号串xy；如x=ab,y=cd则xy=abcd；又如，εa=aε若串集A={1，2，…}，串集B={1，2，…}，则乘积AB={|AandB}3.2符号和符号串方幂：符号串自身连接n次得到的符号串an定义为aa…aa，即n个a；a1=a,a2=aa则a0=ε。使用A*表示A上的一切符号串（包括ε）组成的集合。字母表A的闭包（A*）：A*=A0A1A2…即：由A上符号组成的所有串的集合（包括空串）。字母表A的正闭包（A+）：A+=A1A2…=A*-{}即：由A上符号组成的所有串的集合（不包括空串）。3.2符号和符号串例如：A={a,b};B={c,e,d}则AB={ac,ae,ad,bc,be,bd}例如：串集A＝{a}的各次方幂定义为：A0={}A1=A={a}……An=AAn-1(n>0)={a…a}Σ={a,b}Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}如何描述一种语言？如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示如果语言是无穷的，找出语言的有穷表示。语言的有穷表示有两个途经：生成方式（文法）识别方式（自动机）3.3文法和语言的形式定义生成方式（文法）：语言中的每个句子可以用严格定义的规则来构造。识别方式（自动机）：用一个模型，当输入的一任意串属于语言时，该过程经有限次计算后就会停机并回答“是”，若不属于，要麽能停机并回答“不是”，要麽不停机永远继续下去。文法即是生成方式描述语言的：语言中的每个句子可以用严格定义的规则来构造.3.3文法和语言的形式定义3.3文法和语言的形式定义文法G定义为四元组(VN，VT，P，S)。其中：VN为非终结符号(或语法实体，或变量)集；VT为终结符号集；P为产生式(也称规则)的集合；VN，VT和P是非空有穷集。VN和VT不含公共的元素，即VN∩VT=φ通常用V表示VN∪VT，V称为文法G的字母表S称作识别符号或开始符号，它是一个非终结符，至少要在一条产生式中作为左部出现。　　3.3文法和语言的形式定义规则，也称重写规则、产生式或生成式，是形如或∷=的(,)有序对，其中：是字母表V的正闭包V+中的一个符号，是V*中的一个符号。称为规则的左部，称为规则的右部。3.3文法和语言的形式定义例3.1 　　文法G=(VN，VT，P，S)，其中VN={S}，VT={0，1}，P={S→0S1，S→01}。非终结符集中只含一个元素S；终结符集由两个元素0和1组成；两条产生式；开始符号是S。3.3文法和语言的形式定义例3.2 文法G=(VN，VT，P，S)，其中VN={标识符，字母，数字}VT={a,b,c,…，x,y,z,0,1,…，9}P={〈标识符〉→〈字母〉〈标识符〉→〈标识符〉〈字母〉〈标识符〉→〈标识符〉〈数字〉〈字母〉→a|b…|z〈数字〉→0|1…|9｝S=〈标识符〉3.3文法和语言的形式定义元符号:→，∷=，|，<>文法习惯上只将产生式写出，并可有如下的约定：第一条产生式的左部是开始符号用尖括号括起来的是非终结符，否则为终结符；或者大写字母表示非终结符，小写字母或其他字母表示终结符G写成G[S]，S是开始符号S3.3文法和语言的形式定义文法的写法：1、G：S→aAbA→abA→aAbA→ε,其中S是开始符2、G[S]：A→abA→aAbA→εS→aAb3、G[S]：A→ab|aAb|εS→aAb3.3文法和语言的形式定义推导的概念:　　如是文法G=(VN，VT，P，S)的规则(或说是P中的一产生式)，γ和δ是V*中的任意符号，若有符号串v，w满足：v=γδ，w=γβδ则说v(应用规则)直接产生w，或者说，w是v的直接推导，也可以说，w直接归约到v，记作vw3.3文法和语言的形式定义例：文法G=(VN，VT，P，S)，其中VN={S}，VT={0，1}，P={S→0S1，S→01},可以给出直接推导的一些例子如下：v=0S1,w=0011,直接推导：0S10011，使用的规则：S→01，这里γ=0，δ=1。v=S,w=0S1，直接推导：S0S1使用的规则：S→0S1，这里γ=ε，δ=εv=0S1,w=00S11,直接推导：0S100S11，使用的规则：S→0S1，这里γ=0，δ=13.3文法和语言的形式定义长度为n(n≥1)的推导:如果存在直接推导的序列：v=w0w1...wn=w,(n＞0)则称v推导出(产生)w(推导长度为n)，或称w归约到v。记作v=>+w，读作经过1步或多步推导。长度为n(n≥0)的推导:若有v+w，或v=w，则记为v*w，读作经过0步或多步推导。3.3文法和语言的形式定义例G：S→0S1，S→010S100S1100S11000S111000S11100001111S0S100S11000S11100001111S=>+000011113.3文法和语言的形式定义句型：有文法G，若符号串x是从识别符号S推导出来的，S=>*x，则称x是文法G的句型。句子：有文法G，若S=>*x，且x∈VT*，则称x是文法G的句子。是仅含终结符的句型。例：G：S→0S1，S→01S0S100S11000S11100001111G的句型S,0S1,00S11,000S111,00001111G的句子000011113.3文法和语言的形式定义例：G[E]：E→E+T|TT→T*F|FF→(E)|aEE+TT+TF+Ta+Ta+T*Fa+F*Fa+a*Fa+a*a句子：用符号a，+，*，(和)构成的算术表达式3.3文法和语言的形式定义语言的概念：由文法G生成的语言记为L(G),它是文法G的一切句子的集合:L(G)={x|S=>*x，其中S为文法的开始符号，且x∈VT*}例：G：S→0S1，S→01L(G)={0n1n|n≥1}3.3文法和语言的形式定义例文法G[S]：（1）S→aSBE（2）S→aBE（3）EB→BE（4）aB→ab（5）bB→bb（6）bE→be（7）eE→eeL（G）=？L（G）={anbnen|n≥1}G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成3.3文法和语言的形式定义文法的等价性若L(G1)=L(G2)，则称文法G1和G2是等价的。如文法G1[A]:A→0R与G2[S]：S→0S1等价A→01S→01R→A13.4文法的类型Chomsky（乔姆斯基）对文法的分类：根据对产生式施加的限制，可分为：0型文法1型文法2型文法3型文法3.4文法的类型0型文法(短语文法或无限制文法)P中产生式其中V+并至少含有一个非终结符,V*.a)识别0型语言的自动机称为图灵机(TM).b)0型文法是对产生式限制最少的文法。c)任何0型语言都是递归可枚举的。d)对0型文法产生式的形式作某些限制，可得到其他类型文法的定义。3.4文法的类型1型文法P中产生式,除可能有S外均有||≥||.或者，除可能有S外,均有A,其中,V*,AVN,V+.a)1型文法又称为长度增加文法、上下文有关文法b)识别1型语言的自动机称为线性界限自动机(LBA);c)1型文法意味着，对非终结符进行替换时务必考虑上下文，并且，一般不允许替换成，除非是开始符号产生3.4文法的类型1型文法的例子：设文法G＝(VN,VT,P,S)，VN＝{S,B,E},VT＝{a,b,e}其中P为:(0)SaSBE(1)SaBE(2)EBBE(3)aBab(4)bBbb(5)bEbe(6)eEee3.4文法的类型2型文法：P中产生式具有形式A其中AVN，V*.a)2型文法对产生式的要求是：产生式左部一定是非终结符，产生式右部可以是VN、VT或；非终结符的替换不必考虑上下文;b)识别2型语言的自动机称为下推自动机(PDA);c)2型文法也称为上下文无关文法。3.4文法的类型2型文法例子:设文法G＝(VN,VT,P,S)，VN＝{S,A,B},VT＝{a,b}其中P为:(0)SaB(1)SbA(2)Aa(3)AaS|bAA(4)Bb(5)BbS|aBB3.4文法的类型3型文法：P中产生式具有形式AB，A，或者AB，A，其中A，BVN，VT*。a)3型文法也称为正规文法RG、右线性文法或左线性文法；b)3型文法中的产生式要么均是右线性产生式，要么是左线性产生式，不能既有左线性产生式，又有右线性产生式；若所有产生式均是左线性，则称为左线性文法；若所有产生式均是右线性，则称为右线性文法；c)识别3型语言的自动机称为有限状态自动机3.4文法的类型3型文法例子：设文法G＝(VN,VT,P,S)，VN＝{S,A,B},VT＝{0,1}其中P为:(0)S0A|1B|0(1)A0A|1B|0S(2)B1B|1|03.4文法的类型四种文法之间的逐级“包含”关系2型文法1型文法0型文法3型文法3.4文法的类型0型文法产生的语言称为0型语言1型文法或上下文有关文法(CSG)产生的语言称为1型语言或上下文有关语言(CSL)2型文法或上下文无关文法(CFG)产生的语言称为2型语言或上下文无关语言(CFL)3型文法或正则(正规)文法(RG)产生的语言称为3型语言正则(正规)语言(RL)3.4文法的类型0型文法(短语结构文法)的能力相当于图灵机，可以表征任何递归可枚举集，而且任何0型语言都是递归可枚举的1型文法(上下文有关文法)：产生式的形式为1A2→12，即只有A出现在1和2的上下文中时，才允许取代A。其识别系统是线性界限自动机。2型文法(上下文无关文法CFG)：产生式的形式为A→β，β取代A时与A的上下文无关。其识别系统是不确定的下推自动机。3型文法(正规文法RG)：产生的语言是有穷自动机(FA)所接受的集合。例1设L1={a2nbn|n>=1且a,bVT}试构造生成L1的文法G1设n=1，L1=aabn=2，L1=aaaabbn=3，L1=aaaaaabbb……所以得：SaaSbSaab例2设L2={aibjck|i,j,k>=1且a,b,cVT}试构造生成L2的文法G2SaSSaBBbBBbCCcC|c3.5上下文无关文法及其语法树一、语法树1、定义：用来表示语言句子结构的树。2、作用：使用语法树可以使语法分析过程直观、形象，易于判断文法二义性。3.5上下文无关文法及其语法树语法树应满足以下四个条件：每个节点都有一个V中的符号作为标记根的标记是开始符号S若一个节点n至少有一个它自己除外的子孙，并且n有标记A则AVN若节点n的直接子孙，从左到右的次序是节点n1，n2…nk,其标记分别为A1，A2…Ak,那么AA1A2…Ak一定是P中的一个产生式。3.5上下文无关文法及其语法树最左（最右）推导如果在推导的任何一步，其中，是句型，都是对中的最左（最右）非终结符进行替换，则称这种推导为最左（最右）推导。3.5上下文无关文法及其语法树例如，有一个2型文法G=({S,A},{a,b},P,S),其中P:(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba利用推导产生句子aabbaa:SaASaAaaSbAaaSbbaaaabbaaSaASaSbASaabASaabbaSaabbaaSaASaSbASaSbAaaabAaaabbaa3.5上下文无关文法及其语法树S最左推导S(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树SaAS最左推导SaAS(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树SaAS最左推导SaASaSbASSbA(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树SaaAS最左推导SaASaSbASaabASSbA(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树SaaASba最左推导SaASaSbASaabASaabbaSSbA(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树SaaASbaa最左推导SaASaSbASaabASaabbaSaabbaaSbA(0)SaAS(1)ASbA(2)ASS(3)Sa(4)Aba3.5上下文无关文法及其语法树语法规则为：<句子><主语><谓语><主语><形容词><名词><谓语><动词><宾语><宾语><形容词><名词><形容词>Young|pop<名词>men|music<动词>like能否用最左推导得出“Youngmenlikepopmusic”是个语法正确的句子?在推导过程中有哪些句型?3.5上下文无关文法及其语法树<句子><主语><谓语><形容词><名词><谓语>Young<名词><谓语>Youngmen<谓语>Youngmen<动词><宾语>Youngmenlike<宾语>Youngmenlike<形容词><名词>Youngmenlikepop<名词>Youngmenlikepopmusic最右归约最左推导用语法树表示<句子><主语><谓语><形容词><名词><动词><宾语><形容词><名词>Youngmenlikepopmusic例题已给G[E]：E→E+T|TT→T*F|FF→(E)|a构造a+a*a的语法树，最左推导，最右推导。3.5上下文无关文法及其语法树二义性1、句子二义性：如果文法的一个句子存在对应的两棵或两棵以上的语法树，则该句子是二义的。2、文法二义性：包含二义性句子的文法是二义文法。3.5上下文无关文法及其语法树例如：文法G=({E}，{+,*,(,),i}，P，E),其中：Ei|E+E|E*E|(E),对于句子（i*i+i)有几种最左推导?1）E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)2）E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)3.5上下文无关文法及其语法树1）E(E)(E+E)(E*E+E)(i*E+E)(i*i+E)(i*i+i)E(E)E+EE*Eiii3.5上下文无关文法及其语法树2）E(E)(E*E)(i*E)(i*E+E)(i*i+E)(i*i+i)E(E)E*EE+Eiii3.5上下文无关文法及其语法树二义性的几点说明：1）二义性会给语法分析带来不确定性。2）文法的二义性是不可判定的，即不存在算法，能够在有限步数内确切判定一个文法是否为二义文法。3）若要证明是二义性，只要举出一例4）若能控制文法的二义性，即加入人为的附加条件，则二义文法的存在并非坏事。3.5上下文无关文法及其语法树例如：if语句结构采用下面的产生式：SifCthenSelseSSifCthenSS其他语句C具体条件表达式判断它是不是二义性文法？解法：只要找到一个例子，一个句子有两个语法树，就可以证明它是二义性文法。，如ifc1thenifc2thens1elses2SifCthenSelseSc1ifCthenSs2c2s1SifCthenSc1ifCthenSelseSc2s1s23.6句型的分析句型分析：一个识别输入符号串是否是语法上正确的程序的过程。在语言的编译实现过程中，把完成句型分析的程序称为分析程序或识别程序。分析算法又称为识别算法。3.6句型的分析分析算法分为两大类:1）自上而下语法分析从文法的开始符号出发，反复使用不同产生式进行推导以谋求与输入符号串相匹配。2）自下而上语法分析对输入符号串寻找不同产生式进行归约直到文法开始符号。注：这里所说的输入符号指词法分析所识别的单词。3.6句型的分析自上而下的分析方法例：考虑文法G[S]:(1)ScAd(2)Aab(3)Aa识别输入串w＝cabd是否是该文法的句子？ScAdabScAdcabd3.6句型的分析自下而上的分析方法例：考虑文法G[S]:(1)ScAd(2)Aab(3)Aa识别输入串w＝cabd是否是该文法的句子？cabdASScAdcabd3.6句型的分析句型分析的有关问题在自上而下的分析中，在扩展非终结符A时，存在两个A的产生式，若利用产生式2可以顺利完成识别过程，若利用产生式1就无法往下推，导致识别程序得出错误的结论。当存在非终结符V的多条规测时用哪一个右部去替换的问题。解决方法为回溯。在自下而上的分析中，每一步采用哪一个子串进行规约？因此需要精确定义规约串。3.6句型的分析令G是一个文法，S是文法的开始符号，δ是文法G的句型，若有S*Aδ，且A+，则称是句型δ相对于非终结符A的短语。若有A则是句型δ相对于规则A的直接短语。一个句型的最左直接短语称为该句型的句柄。短语：子树的末端符号自左到右连成串，相对于子树树根而言称为短语。简单短语（直接短语）：若短语是某子树根经过1步推导得到的，则称之为该子树根的简单短语。句柄：句型中的最左简单短语。注：句柄是最左归约时要寻找的简单短语。3.6句型的分析文法G[E]：ET|E+TTF|T*FF(E)|i句型i*i+iEE+TTFi3T*Fi2i1F短语：直接短语：句柄：i1*i2+i3，i1*i2，i1，i2，i3i1，i2，i3i1文法中不得含有有害规则和多余规则有害规则：形如U→U的产生式。会引起文法的二义性多余规则：指文法中任何句子的推导都不会用到的规则，多余规则也可表示为：文法中不含有不可到达和不可终止的非终结符，分以下两种情况：1）文法中某些非终结符不在任何规则的右部出现，该非终结符称为不可到达。2）文法中某些非终结符，由它不能推出终结符号串，该非终结符称为不可终止。3.7有关文法实用中的一些说明例：文法G[S]:SBeBCe|AfAAe|eCCfDf请判断其中是否有多余规则化简文法:3.7有关文法实用中的一些说明1)文法中某些非终结符不在任何规则的右部出现；2）文法中某些非终结符，由它不能推出终结符号串例：G[S]：1)S→Be2)B→CeD为不可到达3)B→AfC为不可终止4)A→Ae5)A→e6)C→Cf7)D→f产生式2），6），7）为多余规则应去掉。3.7有关文法实用中的一些说明对于文法G[S]，为了保证任一非终结符A在句子推导中出现，必须满足如下两个条件：1.A必须在某句型中出现即有S=>*αAβ，其中α，β属于V*2.必须能够从A推出终结符号串t来即A=>*t，其中t∈VT*3.7有关文法实用中的一些说明3.8典型例题及解答证明文法G＝({E,O},{(,),+,*,v,d},P,E)是二义的。EEOE|(E)|v|dO+|*解：对于句子v*v+d的语法树不只一棵。消除二义性EE+T|TTT*F|FF(E)|v|d语言和文法构造方法小结{a2n+1bn|n>=0}{(akcd)nbn|k,n>0}{anbn|n>0}{ambn|m≥0,n>0}{ambn|m>0,n>0}{(ab)n|n>0}{bna|n≥0}{abn|n>0}{bn|n≥0}{bn|n>0}文法G’文法G语言L(G)=L(G’)语言和文法构造方法小结Y→KYH|aK→aaH→bY→aaYb|a{a2n+1bn|n>=0}X→DXH|DHD→AcdA→aA|aH→b{(akcd)nbn|k,n>0}X→aXb|ab{anbn|n>0}W→aW|BB→bB|bW→ABA→aA|εB→bB|b{ambn|m≥0,n>0}V→aV|aBB→bB|bV→ABA→aA|aB→bB|b{ambn|m>0,n>0}U→Uab|abU→EU|EE→ab{(ab)n|n>0}T→PaP→Pb|εT→PDD→aP→bP|ε{bna|n≥0}S→aBB→Bb|bS→DBD→aB→bB|b{abn|n>0}P→Pb|εP→bP|ε{bn|n≥0}B→Bb|bB→bB|b{bn|n>0}文法G’文法G语言L(G)=L(G’)本章目的为语言的语法描述寻求工具,以便：对源程序给出精确无二义的语法描述。（严谨、简洁、易读）根据语言文法的特点来进行语法分析从描述语言的文法可以自动构造出可用的分析程序制导语义翻译[本章小结]1.本章的概念较多,应重点理解文法,推导,句型句子及语言的定义等概念.语法分析有关内容在后面章节会详细讨论.2.文法作为程序语言的语法的描述工具,它用规则只能陈述的是:语言的所有句子以什麽样的符号串能出现.请记住文法和语言的形式定义中的“形式”的含义—只涉及语言的语法不涉及语言的语义.3.本章内容是形式语言理论的一部分.形式语言理论是对符号串集合的表示法、结构及其特性的研究。是程序设计语言语法分析研究的基础。1.已知文法G[A]，写出它定义的语言描述如：G[A]:A→0B|1CB→1|1A|0BBC→0|0A|1CC答案:G[A]定义的语言由0、1符号串组成，串中0和1的个数相同.典型问题典型问题2.给出语言描述，构造文法.如：构造一文法,其定义的语言是由算符+,*,(,)和运算对象a构成的算术表达式的集合.答案1:G[E]E→E+T|TT→T*F|FF→(E)|a答案2:G[E]E→E+E|E*E|(E)|a典型问题3、推导过程描述已知文法G[E]：T→T*F∣FE→E+T∣TF→(E)∣i请写出句子i*(i+i)的最左推导，最右推导和语法树。典型例题4、证明文法的二义性文法G[S]为：S→Ac|aBA→abB→bc该文法是否为二义的？为什么？典型例题5、短语的判定令文法G[E]为：E→T|E+T|E-TT→F|T*F|T/FF→(E)|i证明E+T*F是它的一个句型，指出这个句型的所有短语、直接短语和句柄。此句型对应语法树如图，故为此文法一个句型。或者：因为存在推导序列:E=>E+T=>E+T*F，所以E+T*F句型此句型相对于E的短语有:E+T*F；相对于T的短语有T*F直接短语为：T*F句柄为：T*F典型例题6、文法的等价判断文法G1[A]:A→0R与G2[S]：S→0S1等价A→01S→01R→A1请证明？L(G1)={0n1n|n≥1}=L(G2）