编译原理张晶版 第二章 文法和语言

1、第二章第二章 编译基础编译基础 l 预备知识预备知识 - - 形式语言基础形式语言基础 l 文法和语言的定义文法和语言的定义 l 几个重要概念几个重要概念 l文法的表示：扩充的文法的表示：扩充的BNFBNF范式范式 和语法图和语法图 l文法的构造和语言的分类文法的构造和语言的分类 第二章第二章 编译基础（编译基础（1 1） 1.1.字母表：字母表：非空有穷非空有穷字符集字符集 -用用，V V表示表示 例如：例如：=a-Z,A-Z,0-9,+,-,=a-Z,A-Z,0-9,+,-,* *,/,(,),=,/,(,),=. 2.2.符号：是语言中最基本的不可再分的单位符号：是语言中最基本的不可再分

2、的单位 3.3.符号串：字母表中符号组成的任何符号串：字母表中符号组成的任何有穷有穷数列数列单词单词 例如：例如：scanf,int,3.1415,x1,100,ascanf,int,3.1415,x1,100,a. 空串：不含有任何符号的串称作空串，记作空串：不含有任何符号的串称作空串，记作e e 4 4、句子：字母表上符合某种规则构成的串、句子：字母表上符合某种规则构成的串 5 5、语言：字母表上句子的集合、语言：字母表上句子的集合 注：约定用注：约定用a,b,ca,b,c表示符号；用表示符号；用a,b,ga,b,g. .表示符号串；用表示符号串；用A,B,CA,B,C. 表示其集合表示其

3、集合 2.1 2.1 预备知识预备知识一、字母表和符号串一、字母表和符号串 第二章第二章 编译基础（编译基础（7 7） 二、符号串和符号串集合的运算二、符号串和符号串集合的运算 1.1.符号串相等符号串相等：若：若x x、y y是集合上的两个符号串，则是集合上的两个符号串，则x xy y iff iff（当且仅当）组成（当且仅当）组成x x的的每一个每一个符号和符号和 组成组成y y的的每一个每一个符号依次相等。符号依次相等。 2.2.符号串的长度符号串的长度：x x为符号串，其长度为符号串，其长度|x|x|等于组成该符等于组成该符 号串的符号个数。号串的符号个数。 例：例： x xSTV S

4、TV ， |x|=3 |x|=3 第二章第二章 编译基础（编译基础（9 9） 3.3.符号串的联结：符号串的联结：若若x x、y y是定义在是定义在上的符号串，上的符号串， 且且 x xXYXY，y yYXYX，则，则x x和和y y的联结的联结 xyxyXYYXXYYX也是也是上的符号串。上的符号串。 注意：一般注意：一般xyyxxyyx，而，而xxxx 4.4.符号串集合的乘积运算：符号串集合的乘积运算：令令A A、B B为符号串集合，定义为符号串集合，定义 ABAB abab | |a aA,A,b bB B 例：例：A Aa,b,B=c,d, AB= a,b,B=c,d, AB= ？

5、因为因为xxxxx x，所以，所以A=A=AA=A=A acac，adad，bcbc，bdbd 第二章第二章 编译基础（编译基础（1010） 5. 5. 符号串集合的幂运算：符号串集合的幂运算：有符号串集合有符号串集合A A，定义，定义 A0 =,A1=A, A2=AA,A3=AAA, AnAn-1A=AAn-1 ，n0 6.6.符号串集合的闭包运算符号串集合的闭包运算：设设A A是符号串集合，定义是符号串集合，定义 A A1 A2 A3 An 称为集合称为集合A A的的正闭包正闭包。 A* A0 A 称为集合称为集合A A的的闭包闭包 例：例：A=x,y A=x,y A ？ ？ A* ？ x

6、,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, , A1 A2 A3 , x,y, xx,xy,yx,yy , xxx,xxy,xyx,xyy, , A0 A1 A2 A3 第二章第二章 编译基础（编译基础（1111） 2.22.2文法的非形式讨论文法的非形式讨论 1.1.什么是什么是文法文法：文法是对语言结构的定义与描述。即从形式上：文法是对语言结构的定义与描述。即从形式上 用于描述和规定语言结构的称为用于描述和规定语言结构的称为“文法文法”（或称为（或称为“语法语法”）。）。 例：有一句子：例：有一句子：“我是大学生我是大学生” 。这是一个在语法、。这是一个在语法、

7、语义上都正确的句子，该句子的结构（称为语法结构）是由语义上都正确的句子，该句子的结构（称为语法结构）是由 它的语法决定的它的语法决定的 。在本例中它为。在本例中它为“主谓结构主谓结构”。 第二章第二章 编译基础（编译基础（1414） 2.2.语法规则语法规则：我们通过建立一组规则，来描述句子的语法我们通过建立一组规则，来描述句子的语法结构结构。 规定用规定用“:=:=”表示表示“由由组成组成”。 :=:= :=:=| := :=你你| |我我| |他他 := := 王民王民| |大学生大学生| |工人工人| |英语英语 :=:= :=:=是是| |学习学习 :=:=| 第二章第二章 编译基础（

8、编译基础（1515） 由规则推导句子：由规则推导句子：有了一组规则之后，可以按照一定有了一组规则之后，可以按照一定 的方式用它们去推导或产生句子。的方式用它们去推导或产生句子。 推导方法：从一个要识别的符号开始推导，即用相应规则的推导方法：从一个要识别的符号开始推导，即用相应规则的 右部右部来替代规则的来替代规则的左部左部，每次仅用一条规则去进行推导。，每次仅用一条规则去进行推导。 = = = :=:= :=:=| := :=你你| |我我| |他他 :=:= 王民王民| |大学生大学生| |工人工人| |英语英语 :=:= :=:=是是| |学习学习 :=:=| 这种推导一直进行下去，直到所

9、有带这种推导一直进行下去，直到所有带的符号都由的符号都由 终结符号替代为止。终结符号替代为止。 第二章第二章 编译基础（编译基础（1616） 推导方法：推导方法：从一个要识别的符号从一个要识别的符号 开始推导，即用相应规则的开始推导，即用相应规则的 右部右部来替代规则的来替代规则的左部左部， 每次仅用一条规则去进行推导。每次仅用一条规则去进行推导。 :=:= :=:=| := :=你你| |我我| |他他 :=:= 王民王民| |大学生大学生| |工人工人| |英语英语 :=:= :=:=是是| |学习学习 :=:=| = = = 我我 =我我 =我我是是 =我是我是 =我是我是大学生大学生

10、第二章第二章 编译基础（编译基础（1717） 2.相关概念 （）非终结符（）非终结符 出现在规则的左部、用出现在规则的左部、用括起来、表示一定的语括起来、表示一定的语 法概念的词法概念的词 V VN N -非终结符的集合非终结符的集合 （）（）终结符终结符 语言中不可再分割的字符串（包括单个字符组成语言中不可再分割的字符串（包括单个字符组成 的串）。注：终结符是组成句子的基本单位的串）。注：终结符是组成句子的基本单位 V VT T-终结符的集合终结符的集合 第二章第二章 编译基础（编译基础（2020） （）开始符号（）开始符号 表示所定义的语法范畴表示所定义的语法范畴非终结符非终结符 注：开始

11、符号又称为识别符号开始符号又称为识别符号 （）产生式（）产生式 是用来定义符号串之间关系的一组是用来定义符号串之间关系的一组 语法规则。语法规则。 形式：形式：A Aa a（A A产生产生a a） A:=aA:=a 第二章第二章 编译基础（编译基础（2121） （）推导（）推导 推导是从开始符号开始，通过使用产生式的右部取代左部，最终能推导是从开始符号开始，通过使用产生式的右部取代左部，最终能 产生语言的一个句子的过程产生语言的一个句子的过程 最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非最左（右）推导：每次使用一个规则，以其右部取代符号串最左（右）非 终结符终结符 注：最左

12、推导和最右推导称为注：最左推导和最右推导称为规范推导规范推导 第二章第二章 编译基础（编译基础（2222） （6 6）归约）归约 归约是推导的逆过程，即，从给定的源语归约是推导的逆过程，即，从给定的源语 言的句子开始，通过规则的左部取代右部，最言的句子开始，通过规则的左部取代右部，最 终达到开始符号的过程。终达到开始符号的过程。 最左（右）归约是最右（左）推导的逆过程最左（右）归约是最右（左）推导的逆过程 注：最左归约和最右归约称为规范规约注：最左归约和最右归约称为规范规约 第二章第二章 编译基础（编译基础（2323） （7 7）句型、句子和语言）句型、句子和语言 句型：句型： -从文法的开始

13、符号从文法的开始符号S S开始，每步推导（包括开始，每步推导（包括0 0步推步推 导）所得到的字符串导）所得到的字符串a a 记作：记作： S S a a , ,其中其中a a (V VN NVVT T) )* * 句子：是仅含终结符的句型句子：是仅含终结符的句型 * 第二章第二章 编译基础（编译基础（2424） 上述推导可写成上述推导可写成 = 我是大学生我是大学生 + 说明：说明： (1) 有若干语法成分同时存在时，我们总是从最左的语法成有若干语法成分同时存在时，我们总是从最左的语法成 分进行推导，这称之为分进行推导，这称之为最左推导最左推导，类似的有，类似的有最右推导最右推导或一般推或一

14、般推 导。导。 (2) 从一组规则可推出不同的句子，如以上规则还可推出从一组规则可推出不同的句子，如以上规则还可推出 “我是英语我是英语”、“英语是你英语是你”等句子，等句子， 它们在语法上都正确，但在语义上都不正确。它们在语法上都正确，但在语义上都不正确。 所谓所谓文法文法是在是在形式上形式上对句子结构的定义与描述，而未对句子结构的定义与描述，而未 涉及涉及语义语义问题。问题。 第二章第二章 编译基础（编译基础（2525） 4.4.语法树语法树：我们用语法树来描述一个句子的语法结构。：我们用语法树来描述一个句子的语法结构。 单词符号（在形单词符号（在形 式语言中又称式语言中又称 “终结符号终

15、结符号”) 语法成分（在形式语法成分（在形式 语言中又称语言中又称“非终非终 结符结符”） 第二章第二章 编译基础（编译基础（2727） 语法规则： Young Young poppop men men musicmusic like like 例如：根据英语的语法例如：根据英语的语法 规则看能否用最左推导规则看能否用最左推导 得出得出“Young men like Young men like pop musicpop music”是个语法正是个语法正 确的句子；在推导过程确的句子；在推导过程 中有哪些句型。中有哪些句型。 第二章第二章 编译基础（编译基础（2828） 对上句的最左推导对上句

16、的最左推导 Young Young men Young men Young men like Young men like Young men like pop Young men like pop music 最左推导 最左推导 最右归约最右归约 第二章第二章 编译基础（编译基础（2929） Youngmen like pop music 用图示化方式表示用图示化方式表示 第二章第二章 编译基础（编译基础（3030） Youngmen likepop music Young men likepop men pop menlikeyoungmusic . 第二章第二章 编译基础（编译基础（31

17、31） （7 7）句型、句子和语言）句型、句子和语言 语言：语言： 语言是由语言是由S S开始通过开始通过1 1步或步或1 1步以上推导所得的步以上推导所得的 句子的集合。句子的集合。 记为：记为：L(G) L(G)= a | S a,L(G) L(G)= a | S a,且且a Va VT T* * （8 8）文法规则的递归定义文法规则的递归定义 -非终结符的定义中包含了非终结符自身非终结符的定义中包含了非终结符自身 -使用文法的递归定义要谨慎使用文法的递归定义要谨慎 + 第二章第二章 编译基础（编译基础（3232） 递归文法递归文法 1.递归规则递归规则：规则右部有与左部相同的符号：规则右

18、部有与左部相同的符号 对于对于 U:= xUy 若若x=, , 即即U:= Uy， 左递归；左递归； 若若y=, , 即即U:= xU， 右递归；右递归； 若若x,y，即，即U:= xUy，自嵌入。，自嵌入。 2.递归文法递归文法：文法文法G，存在，存在U Vn if U=U, 则则G为递归文法；为递归文法； if U=U, 则则G为左递归文法；为左递归文法； if U=U, 则则G为右递归文法。为右递归文法。 + + + 第二章第二章 编译基础（编译基础（3333） 例：无符号整数的文法：例：无符号整数的文法： G=（VN，VT，P，S） VN, VT = 0,1,2,3,9 P = ； ；

19、 ； 0； 1； 9； S = ； 第二章第二章 编译基础（编译基础（3434） 3. 左左递归文法的递归文法的缺点缺点：不能用自顶向下的方法来进行语法分析：不能用自顶向下的方法来进行语法分析 4. 递归文法的递归文法的优点优点：可用有穷条规则，定义无穷语言：可用有穷条规则，定义无穷语言 例：对于前面给出的无符号整数的文法是左递归文法，用例：对于前面给出的无符号整数的文法是左递归文法，用13 条规则就可以定义出所有的无符号整数。若不用递归文法，那条规则就可以定义出所有的无符号整数。若不用递归文法，那 将要用多少条规则呢？将要用多少条规则呢？ 会造成死循环（后面将详细论述）会造成死循环（后面将详

20、细论述） ! 第二章第二章 编译基础（编译基础（3535） 例如：字母表例如：字母表A=0,1A=0,1 语法规则为：语法规则为： 0 01 1 再如：字母表再如：字母表A=0,1A=0,1 语法规则为：语法规则为： 0 01 1 第二章第二章 编译基础（编译基础（3636） （9 9）文法规则的扩充表示）文法规则的扩充表示 扩充的扩充的BNFBNF表示表示 （）（）提因子提因子 - -例：把例：把U ax|ay|azU ax|ay|az改写为改写为U a(x|y|z)U a(x|y|z) 重复次数指定重复次数指定 - -例：把例：把 |5 50 0 任选符号任选符号 - -例：例： +|-

21、+|- 第二章第二章 编译基础（编译基础（3838） （1010）元语言符号）元语言符号 用来说明文法符号之间关系的符号，如用来说明文法符号之间关系的符号，如“ ”和和 “ ” 称为元语言符号称为元语言符号 第二章第二章 编译基础（编译基础（3939） 2.2 2.2 文法和语言的形式定义文法和语言的形式定义 一、一、文法的定义文法的定义 定义定义1. 文法文法G=（VN，VT，P，S） VN：非终结符号集：非终结符号集 VT：终结符号集：终结符号集 P：产生式或规则的集合：产生式或规则的集合 S：开始符号（识别符号）：开始符号（识别符号） SVN VVN VT 称为文法的字汇表 规则：规则：

22、U : x U VN, xV* 规则的定义：规则的定义： 规则是一个有序对规则是一个有序对(U, x), 通常写为通常写为: U : x 或或U x ， | U| = 1 |x| 0 第二章第二章 编译基础（编译基础（4444） 2.2 2.2 文法与语言的形式定义文法与语言的形式定义 二、二、 chomskychomsky对文法的分类对文法的分类 根据对产生式施加的限制，可分为根据对产生式施加的限制，可分为 0 0型文法型文法 1 1型文法型文法 2 2型文法型文法 3 3型文法型文法 第二章第二章 编译基础（编译基础（4545） 2 2、 chomskychomsky对文法的分类对文法的分

23、类 （1 1） 0 0型文法（短语文法或无限制文法）型文法（短语文法或无限制文法） P P中产生式中产生式a a b b 其中其中a aVV+ +并至少含有一个非终结符，并至少含有一个非终结符，b b V V* * 注：注： a)a)识别识别0 0型语言的自动机称为图灵机（型语言的自动机称为图灵机（TMTM） b) 0b) 0型文法是对产生式限制最少的文法。型文法是对产生式限制最少的文法。 c)c)任何任何 0 0型语言都是递归可枚举的。型语言都是递归可枚举的。 d)d)对对0 0型文法产生式的形式作某些限制，可得到其它类型文法定型文法产生式的形式作某些限制，可得到其它类型文法定 义。义。 第

24、二章第二章 编译基础（编译基础（4646） 2 2、 chomskychomsky对文法的分类对文法的分类 （2 2） 1 1型文法型文法 P P中产生式中产生式a a b b ，除可能有，除可能有S S e e外，均有外，均有| |b b|=|=|a a|,|,若有若有 S S e e，规定，规定S S不得出现在产生式右部不得出现在产生式右部 或者，或者， P P中产生式中产生式a a b b ，除可能有，除可能有S S e e外，均有外，均有a aA Ab b a ag g b b，其中，其中， a a，b bVV* *， ， A V A VN , N , g g V V+ + 注：注：a

25、) 1a) 1型文法又称为长度增加文法、上下文有关文法；型文法又称为长度增加文法、上下文有关文法； b) b)识别识别1 1型语言的自动机称为线性界限自动机（型语言的自动机称为线性界限自动机（LBALBA）；）； c) 1 c) 1型文法意味着，对非终结符进行替换时务必考虑上下文，型文法意味着，对非终结符进行替换时务必考虑上下文， 并且，一般不允许替换成并且，一般不允许替换成e e除非是开始符号除非是开始符号 产生产生 e e 第二章第二章 编译基础（编译基础（4747） 1 1型文法举例型文法举例 设文法设文法G=（VN，VT，P，S） VN=S,B,E, VT =a,b,e, 其中其中P为

26、为（0）S aSBE （1）S aBE （2）EB BE （3）aB ab （4）Bb bb （5）bE be （6）eE ee 第二章第二章 编译基础（编译基础（4848） 2 2、 chomskychomsky对文法的分类对文法的分类 （3 3） 2 2型文法型文法 P P中产生式具有形式中产生式具有形式A A b b 其中其中A VA VN N ， ， b b VV* * 注注:a) 2:a) 2型文法对产生式的要求是：产生式的左部型文法对产生式的要求是：产生式的左部 一定是非终结符，产生式的右部可以是一定是非终结符，产生式的右部可以是V VN N，V VT T或或e e ； 非终结符的

27、替换可以不必考虑上下文。非终结符的替换可以不必考虑上下文。 b)b)识别识别2 2型语言的自动机称为下推自动机（型语言的自动机称为下推自动机（PDAPDA） C C）2 2型文法也称上下文无关文法。型文法也称上下文无关文法。 第二章第二章 编译基础（编译基础（4949） 2 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|aBB 第二章第二章 编译基础（编译基础（5050） 2 2、 chomskychomsky对文法的分类对文

28、法的分类 （4 4） 3 3型文法型文法 P P中产生式具有形式中产生式具有形式A A a aB, A B, A a a或者或者 A BA Ba a， A A a a，其中，其中A A，BVBVN N ， ， a a VVT T* * 注：注：a) 3a) 3型文法也称为型文法也称为正规文法正规文法RGRG、右线性文法或左线性文、右线性文法或左线性文 法；法； b) 3b) 3型文法中的产生式要么是右线性产生式，要么是左线性型文法中的产生式要么是右线性产生式，要么是左线性 产生式，不能既有左线性产生式，又有右线性产生式，若所产生式，不能既有左线性产生式，又有右线性产生式，若所 有产生式均是左线

29、性，则称为左线性文法；若所有产生式均有产生式均是左线性，则称为左线性文法；若所有产生式均 是右线性，则称为右线性文法。是右线性，则称为右线性文法。 C)C)识别识别3 3型语言的自动机称为有限状态推自动机型语言的自动机称为有限状态推自动机 第二章第二章 编译基础（编译基础（5151） 3 3型文法举例型文法举例 设文法设文法G=（VN，VT，P，S） VN=S,A,B, VT =0,1, 其中其中P P为为（0）S 0A|1B|0 （1）A 0A|1B|0S （2）B 1B|1|0 第二章第二章 编译基础（编译基础（5252） 2.22.2文法与语言的关系文法与语言的关系 二、文法与语言的的形

30、式定义二、文法与语言的的形式定义 3 3、i i型文法型文法 由由i i型文法生成的语言称为型文法生成的语言称为i i型语言。型语言。 记为：记为：L(G); L(G)=L(G); L(G)=w w| |w wVVT T* * , ,且且S S + + w w 第二章第二章 编译基础（编译基础（5353） 例例1：设文法：设文法G1=（S，a,b, P, S) 其中其中P为为: (0) S aS (1) S a (2) S b L（G1）=ai(a|b) i=0 例例2：设文法：设文法G2=（S，a,b, P, S) 其中其中P为为: (0) S aSb (1) S ab L（G2）=anbn

31、 n=1 一、如何由文法构造语言一、如何由文法构造语言 第二章第二章 编译基础（编译基础（5454） 2.2 2.2文法与语言的关系文法与语言的关系 二、文法与语言的形式定义二、文法与语言的形式定义 注意：在词法分析和语法分析中对产生式有限制注意：在词法分析和语法分析中对产生式有限制 不存在不存在P PP P产生式产生式 产生式中出现的非终结符产生式中出现的非终结符P P必须有用。必须有用。 从开始符号从开始符号S S出发，存在推导出发，存在推导S S * * a aP Pb b P P必须能推导出终结符串。即：必须能推导出终结符串。即：P P + + g g, , g gVVT T* * 第

32、二章第二章 编译基础（编译基础（5555） 2.3 2.3 文法构造与文法简化文法构造与文法简化 二、如何由语言构造文法二、如何由语言构造文法 例例1:1:设设L L1 1 =a=a2n 2nb bn n|n=1 |n=1 且且a,b a,b VVT T 试构造生成试构造生成L L1 1的文法的文法G G1 1 设设n=1, n=1, L L1 1=aab=aab 设设n=2, n=2, L L1 1=aaaabb=aaaabb 设设n=3, n=3, L L1 1=aaaaaabbb=aaaaaabbb 所以得：所以得：S aaSbS aaSb S aab S aab 第二章第二章 编译基础

33、（编译基础（5656） 例例2 2 设设L L2 2 =a=ai ib bj jc ck k|i,j,k=1 |i,j,k=1 且且a,b ,ca,b ,cVVT T 试构造生成试构造生成L L2 2的文法的文法G G2 2 S aS S aBS aS S aB B bB B bCB bB B bC C cC|cC cC|c 2.3 2.3 文法构造与文法简化文法构造与文法简化 二、如何由语言构造文法二、如何由语言构造文法 第二章第二章 编译基础（编译基础（5757） chomskychomsky对文法的分类对文法的分类 根据对产生式施加的限制，可分为根据对产生式施加的限制，可分为 0 0型文

34、法型文法 1 1型文法型文法 2 2型文法型文法 3 3型文法型文法 第二章第二章 编译基础（编译基础（5858） 文法的类型 四种四种文法文法之间之间的的逐级逐级“包含包含”关系关系 3型文法型文法 0型文法型文法 1型文法型文法 2型文法型文法 第二章第二章 编译基础（编译基础（5959） 例例3 3 设设L3L3=w|ww|w(a,b)(a,b)* *且且w w中含有相同个数的中含有相同个数的a a和和b b 试试 构造生成构造生成L3L3的文法的文法G3G3 S e e S bB, S aA A bS , A aAA B aS, B bBB 2.32.3文法构造与文法简化文法构造与文法

35、简化 二、如何由语言构造文法二、如何由语言构造文法 第二章第二章 编译基础（编译基础（6060） 例例3 3 设设L L3 3=w|w=w|w(a,b)(a,b)* *且且w w中含有相同个数的中含有相同个数的a a 和和b , b , 试构造生成试构造生成L L3 3的文法的文法G G3 3 vS e e vS bB, S aA vA bS , A aAA vB aS, B bBB (0)S e e S aSbS S bSaS 第二章第二章 编译基础（编译基础（6161） 例例4 4 设设L L4 4=w w| |w w(0,1)(0,1)* *且且w w中中1 1的个数为偶数的个数为偶数

36、试构造生成试构造生成L L4 4的文法的文法G4G4 S e e S 0S, S 1A A 0A, A 1S 第二章第二章 编译基础（编译基础（6262） 2.3 2.3 文法构造与文法简化文法构造与文法简化 二、文法的简化二、文法的简化 1.1.由于同一语言可以用不同的文法来描述，显然应该选择产由于同一语言可以用不同的文法来描述，显然应该选择产 生式的个数最少，最符合语言特征的来描述。生式的个数最少，最符合语言特征的来描述。 2.2.在文法中，有些产生式对推导不起作用，要删除掉。在文法中，有些产生式对推导不起作用，要删除掉。 如某个产生式在推导过程中永远不会被用到，即由开始如某个产生式在推导

37、过程中永远不会被用到，即由开始 符号推导永远推不到的左部的非终结符。符号推导永远推不到的左部的非终结符。 再如永远导不出终结符串的产生式。再如永远导不出终结符串的产生式。 如形如如形如P PP P的产生式。的产生式。 第二章第二章 编译基础（编译基础（6363） 2.32.3文法构造与文法简化文法构造与文法简化 二、文法的简化二、文法的简化 3.3.简化步骤：简化步骤： 查找有无形如查找有无形如P PP P的产生式，如有则删除。的产生式，如有则删除。 如某个产生式在推导过程中永远不会被用到，删除它。如某个产生式在推导过程中永远不会被用到，删除它。 若某个产生式在推导过程中不能从中导出终结符，删

38、除若某个产生式在推导过程中不能从中导出终结符，删除 它。它。 最后，整理所有的剩余产生式，就得到简化的文法。最后，整理所有的剩余产生式，就得到简化的文法。 第二章第二章 编译基础（编译基础（6464） 2.3 2.3 文法构造与文法简化文法构造与文法简化 二、文法的简化二、文法的简化 例例1010：化简下面的文法：化简下面的文法 (0)S Be (1)S Ec (2)A Ae (3)A e (4)A A (5)B Ce (6)B Af (7)C Cf (8)D f (0)S Be (1)A Ae (2)A e (3)B Af 第二章第二章 编译基础（编译基础（6565） 构造无构造无e e产生

39、式的上下文无关文法产生式的上下文无关文法 1.1.无无e e产生式的上下文无关文法要满足条件：产生式的上下文无关文法要满足条件： P P中要么不含有中要么不含有e e产生式，要么只有产生式，要么只有S S e e； 若若S S e e，则，则S S不出现在任何产生式右部。不出现在任何产生式右部。 2.2.构造无构造无e e产生式的上下文无关文法变换算法：产生式的上下文无关文法变换算法： G= G=（V VN N,V,VT T,P,S,P,S） G G ，= =（ （V VN N ，,V ,VT T ，,P ,P ，,S ,S ，） ） （1 1）由文法）由文法G G找出所有经过若干步推导能推出

40、找出所有经过若干步推导能推出e e的非终结符，的非终结符， 放在放在V V0 0集合中。集合中。 （2 2）再按下列步骤构造）再按下列步骤构造G G ，的产生式集合 的产生式集合P P ，； ； 第二章第二章 编译基础（编译基础（6666） （2 2）再按下列步骤构造）再按下列步骤构造G G ，的产生式集合 的产生式集合P P ， A A）若）若V V0 0集合中的某元素出现在某产生式的右端，则将它变集合中的某元素出现在某产生式的右端，则将它变 成两个产生式：分别以成两个产生式：分别以e e和其原型代入；将新产生式代入和其原型代入；将新产生式代入P P ， B B）不满足上一条的）不满足上一条

41、的P P中其它产生式除去中其它产生式除去e e产生式后也加入产生式后也加入P P ， C C）如果）如果P P中有产生式中有产生式S S e e， 将它在将它在P P 改为 改为S S e e|S,S|S,S是新的开始符号，把它加入是新的开始符号，把它加入V VN N， 形成形成V VN N 构造无构造无e e产生式的上下文无关文法变换算法：产生式的上下文无关文法变换算法： 第二章第二章 编译基础（编译基础（6767） 例：设例：设G G1 1= =（SS，a,b, P, S)a,b, P, S)，其中，其中 P:P:（0 0）S S e e (1) S aSbS(2) S bSaS(1) S

42、 aSbS(2) S bSaS （1 1） V V0 0=S=S （2 2）P P: :（1 1）S abS|aSbS|aSb|abS abS|aSbS|aSb|ab （2) S baS|bSaS|bSa|ba2) S baS|bSaS|bSa|ba （0 0）S S e e|S|S 故：文法故：文法G G1 1= =（SS,S,S，a,b, Pa,b, P, S, S),),其中其中 P P：（：（0 0） S S e e|S|S （1 1） S abS|aSbS|aSb|abS abS|aSbS|aSb|ab （2 2） S baS|bSaS|bSa|baS baS|bSaS|bSa|ba

43、 第二章第二章 编译基础（编译基础（6868） 2.4 2.4 语法树与文法的二义性语法树与文法的二义性 一、语法树一、语法树 1.1.定义：定义： 用来表示语言句子结构的树。用来表示语言句子结构的树。 2.2.作用：作用： 使用语法树可以使语法分析过程直观、形象，使用语法树可以使语法分析过程直观、形象， 易于判断文法二义性。易于判断文法二义性。 第二章第二章 编译基础（编译基础（6969） 2.4 语法树与二义性文法语法树与二义性文法 2.4.1 推导与语法树推导与语法树 （1）语法树：句子结构的图解表示法，它是一种有向图，由）语法树：句子结构的图解表示法，它是一种有向图，由 结点和有向边组

44、成。结点和有向边组成。 结点结点：符号：符号 根结点：根结点：识别符号识别符号 中间结点：中间结点：非终结符非终结符 叶结点：叶结点：终结符或非终结符终结符或非终结符 有向边有向边：表示结点间的派生关系。：表示结点间的派生关系。 Z U V a b c d 第二章第二章 编译基础（编译基础（7070） ( 2 ) 句型的推导及语法树的生成（自顶向下）句型的推导及语法树的生成（自顶向下） 给定给定GSGS，句型，句型w w： 可建立可建立推导序列推导序列，S=w S=w 可建立可建立语法树语法树，以，以S S为树根结点，每步推导生成语法为树根结点，每步推导生成语法 树的一枝，最终可生成句型树的一

45、枝，最终可生成句型w w的语法树。的语法树。 例：例： * G 第二章第二章 编译基础（编译基础（7171） 例：无符号整数的文法：例：无符号整数的文法： G=（VN，VT，P，S） VN, VT = 0,1,2,3,9 P = ； ； ； 0； 1； 9； S = ； 第二章第二章 编译基础（编译基础（7272） 一般推导：一般推导：1010的推导过程的推导过程 (1) (2) (3) 0 (4) 1 (5) 注意一个重要事实注意一个重要事实：文法所能产生的句子，可以文法所能产生的句子，可以 用不同的推导原则（使用产生式顺序不同）将其用不同的推导原则（使用产生式顺序不同）将其 推导出来。语法

46、树的生长规律不同，但最终生成推导出来。语法树的生长规律不同，但最终生成 的语法树形状完全相同。某些文法有此性质，而的语法树形状完全相同。某些文法有此性质，而 某些文法不具此性质。某些文法不具此性质。 第二章第二章 编译基础（编译基础（7373） 2.4 2.4 语法树与文法的二义性语法树与文法的二义性 一、语法树一、语法树 例如，有一个例如，有一个2 2型文法型文法 G G1 1= =（S,A,BS,A,B，a,b, P, S)a,b, P, S)，其中，其中P:P: -(0)S aB|bA (1)A a|aS|bAA -(0)S aB|bA (1)A a|aS|bAA (2)B b|bS|a

47、BB(2)B b|bS|aBB 采用最左推导产生句子采用最左推导产生句子aabbab:aabbab: -S aB aaBB aabSB aabbAB -S aB aaBB aabSB aabbAB aabbaB aabbabaabbaB aabbab 第二章第二章 编译基础（编译基础（7474） S back a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab 第二章第二章 编译基础（编译基础（7575） 2.42.4语法树与文法的二义性语法树与文法的二义性 一、语法树一、语法树 3.3.语法树中的概念语法树中的概念 （1 1）

48、子树子树：除叶子结点以外的任意结点连同它的：除叶子结点以外的任意结点连同它的 所有子孙结点构成子树。所有子孙结点构成子树。 （2 2）修剪子树修剪子树：剪去子树树根的所有孩子。：剪去子树树根的所有孩子。 （3 3）句型句型：在一棵语法树生长过程中的任何时刻，：在一棵语法树生长过程中的任何时刻， 所有那些叶子结点排列起来就是一个句型。所有那些叶子结点排列起来就是一个句型。 第二章第二章 编译基础（编译基础（7676） S back a B a B B b b S b A a S aB aaBB aabSB aabbAB aabbaB aabbab 第二章第二章 编译基础（编译基础（7777） 2

49、.42.4语法树与文法的二义性语法树与文法的二义性 一、语法树一、语法树 3.3.语法树中的概念语法树中的概念 （4 4）短语：子树的末端符号自左至右连成串，相对于子）短语：子树的末端符号自左至右连成串，相对于子 树树根而言称为短语。树树根而言称为短语。 简单短语（直接短语）简单短语（直接短语）：若短语是某子树根经过：若短语是某子树根经过1 1步推步推 导得到的，则称之为该子树根的简单短语。导得到的，则称之为该子树根的简单短语。 句型的短语句型的短语：该句型中哪些符号串可以构成某子树根的：该句型中哪些符号串可以构成某子树根的 短语。短语。 第二章第二章 编译基础（编译基础（7878） （5）定

50、义定义:任一句型的最左简单短语称为该句型的任一句型的最左简单短语称为该句型的句柄句柄 给定句型找句柄的步骤：给定句型找句柄的步骤： 短语短语简单短语简单短语 句柄句柄 注：句柄是最左归约时要寻找的简单短语注：句柄是最左归约时要寻找的简单短语 注意注意：短语、简单短语是相对于：短语、简单短语是相对于 句型而言的，一个句型可能有多句型而言的，一个句型可能有多 个短语、简单短语，句柄只能有个短语、简单短语，句柄只能有 一个。一个。 第二章第二章 编译基础（编译基础（8080） ( 3 ) 子树与短语子树与短语 子树：语法树中的某个结点（子树的根）连子树：语法树中的某个结点（子树的根）连 同它向下派生

51、的部分所组成。同它向下派生的部分所组成。 某子树的末端结点按自左向右顺序某子树的末端结点按自左向右顺序 为句型中的符号串，则该符号串为该句型的为句型中的符号串，则该符号串为该句型的 相对于该子树根的短语。相对于该子树根的短语。 定理定理 只需画出句型的语法树，然后根据只需画出句型的语法树，然后根据 子树找短语子树找短语简单短语简单短语句柄。句柄。 第二章第二章 编译基础（编译基础（8181） S back a B a B B b b S b A a 第二章第二章 编译基础（编译基础（8282） = = = 0 = 10 (1) (2) (4) (3) (5) 0 0,0 0 0 ,0 0 ,

52、,0 0 1 1,0 10 ,1,0 10 = 0 句型句型 短语短语 简单短语简单短语 句柄句柄 第二章第二章 编译基础（编译基础（8383） ( 4 ) 树与推导树与推导 句型推导过程句型推导过程句型语法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树 1 从从识别符号识别符号开始，开始，自左向右自左向右建立建立推导推导序列。序列。 由由根结点根结点开始，开始，自上而下自上而下建立建立语法树语法树。 第二章第二章 编译基础（编译基础（8484） 由语法树构造推导由语法树构造推导 2 自下而上自下而上地修剪子树的末端结点，直至把整棵地修剪子树的末端结点，直至把整棵 树剪掉（

53、留根），每剪一次对应一次树剪掉（留根），每剪一次对应一次归约归约。 从句型开始从句型开始, ,自右向左地逐步进行归约，建立自右向左地逐步进行归约，建立归约归约序列。序列。 第二章第二章 编译基础（编译基础（8585） 2.4 2.4 语法树与文法的二义性语法树与文法的二义性 二、文法的二义性二、文法的二义性 1.1.句子的二义性：句子的二义性： -如果文法的一个句子存在对应的两棵或两棵如果文法的一个句子存在对应的两棵或两棵 以上的语法树，则该句子是二义的。以上的语法树，则该句子是二义的。 2.2.文法的二义性：文法的二义性： -包含二义性句子的文法就是二义文法。包含二义性句子的文法就是二义文法

54、。 第二章第二章 编译基础（编译基础（8686） 2.42.4语法树与文法的二义性语法树与文法的二义性 二、文法的二义性二、文法的二义性 例如：文法例如：文法G=(E，+,*,(,),i, P, E) 其中其中P: E E+E|E*E|(E)|i 对于句子对于句子(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) 第二章第二章 编译基础（编译基础（8787） E ( E ) E E + E ( E ) E * E i E * E i i i E + E i i 第二章第二章 编译基础（编译基础（8888） 定义定义: :若一个文法的某句子存在两个不同的若一个文法的某句子存在两个不同的规范规范 推导推导，则该文法是，则该文法是二义性二义性的，否则是无二义性的。的，否则是无二义性的。 从自底向上的归约过程来看，上例中规范句从