第2章文法和语言

1、第第2 2章章 文法和语言文法和语言 随着高级语言的出现和使用，必然面临编译理论的随着高级语言的出现和使用，必然面临编译理论的研究和编译程序的设计。编译过程是一个十分复杂的信研究和编译程序的设计。编译过程是一个十分复杂的信息加工过程，其加工对象是用高级语言编写的程序。息加工过程，其加工对象是用高级语言编写的程序。1.1.为了顺利完成编译工作，要解决的问题是：为了顺利完成编译工作，要解决的问题是： 如何确切地描述或定义一种程序设计语言？如何确切地描述或定义一种程序设计语言？ 如何识别和分析这些语言？如何识别和分析这些语言？ 2.2.在在2020世纪世纪5050年代，年代，N.choumskyN.

2、choumsky首先对语言的描述进行探首先对语言的描述进行探讨。讨。 提出了用来描述语言的数学系统；定义了四类性质不同提出了用来描述语言的数学系统；定义了四类性质不同的文法和语言（的文法和语言（0 0型文法、型文法、1 1型文法、型文法、2 2型文法和型文法和3 3型文型文法）。法）。主要内容主要内容 2.1 2.1 语言和文法的直观概念语言和文法的直观概念 2.2 2.2 符号和符号串符号和符号串 2.3 2.3 文法和语言的形式定义文法和语言的形式定义 2.4 2.4 文法的类型文法的类型 2.5 2.5 上下文无关文法及其语法树上下文无关文法及其语法树 2.6 2.6 句型的分析句型的分

3、析 2.7 2.7 有关文法中的一些说明有关文法中的一些说明2.1 2.1 语言和文法的直观概念语言和文法的直观概念程序设计语言的定义程序设计语言的定义语言是一个记号系统。语言是一个记号系统。汉语汉语-符合汉语语法的句子的全体符合汉语语法的句子的全体英语英语-符合英语语法的句子的全体符合英语语法的句子的全体程序设计语言程序设计语言-该语言的程序的全体该语言的程序的全体 程序设计语言由语法和语义定义：程序设计语言由语法和语义定义：q语法语法(syntax)定义定义: 是一组规则，用它可以形成和产生是一组规则，用它可以形成和产生一个合适的程序一个合适的程序描述工具描述工具:文法文法作用作用: 定义

4、什么样的符号序列是合法的，定义什么样的符号序列是合法的，与符号的含义无关。与符号的含义无关。q语义语义(semantics)分类分类: 静态语义：一系列限定规则，确定静态语义：一系列限定规则，确定哪些合乎语法的程序是合适的哪些合乎语法的程序是合适的 动态语义：表明程序要做什么动态语义：表明程序要做什么描述工具描述工具: 指称语义指称语义,操作语义等操作语义等作用作用: 检查类型匹配，变量作用域等检查类型匹配，变量作用域等文法的直观概念 如何来描述一种语言？如何来描述一种语言？文法是描述语言的语法（形式）文法是描述语言的语法（形式）结构的形式规则。结构的形式规则。如果语言是有穷的（只含有有穷多个

5、句子），可以将如果语言是有穷的（只含有有穷多个句子），可以将句子逐一列出来表示句子逐一列出来表示如果语言是无穷的，要找出语言的有穷表示。如果语言是无穷的，要找出语言的有穷表示。 有两个途经：有两个途经：生成方式生成方式 （文法）：语言中的每个句子可以用严格定（文法）：语言中的每个句子可以用严格定义的规则来构造义的规则来构造识别方式（自动机）：用一个过程，当输入的一任意识别方式（自动机）：用一个过程，当输入的一任意串属于语言时，该过程经有限次计算后就会停止并回串属于语言时，该过程经有限次计算后就会停止并回答答“是是”，若不属于，要么能停止并回答，若不属于，要么能停止并回答“不是不是”，要么永远继

6、续下去。要么永远继续下去。2.2 2.2 符号和符号串符号和符号串字母表字母表定义定义: :元素的非空有穷集合元素的非空有穷集合例：例：=01 =ab,c元素也称为符号，字母表也称符号集。元素也称为符号，字母表也称符号集。程序语言的字母表由字母数字和若干专用程序语言的字母表由字母数字和若干专用符号组成。符号组成。符号串符号串定义定义: :由字母表中的符号组成的任何有穷序列由字母表中的符号组成的任何有穷序列例：例： 0,00,10是是字母表字母表=0，1上的符号串上的符号串 a,ab,aaca是是=a，b，c上的符号串上的符号串在符号串中，符号是有顺序的，顺序不同在符号串中，符号是有顺序的，顺序

7、不同,代代表不同的符号串，如表不同的符号串，如:ab和和ba不同不同不含任何符号的符号串称为空串，用不含任何符号的符号串称为空串，用表示表示注意注意: :并不等于空集合并不等于空集合 符号串长度符号串长度: 符号串中含有符号的个数符号串中含有符号的个数如如: |abc|=3| |=0 子符号串子符号串v设有非空符号串设有非空符号串u=xvy，其中符号其中符号 串串 则称则称v为符号串为符号串u的的子符子符号串号串。Vv例如例如 符号串符号串x=a+b*(c+d)，则则a，a+b*， 与与(c+d)等都是等都是x的子符号串，的子符号串，且其长度分别且其长度分别|a|=1， |a+b*|=4， |

8、(c+d)|=5符号串的头与尾符号串的头与尾v如果如果z=xy是一个符是一个符号串，则号串，则x是是z的的头头，而而y是是z的的尾尾。如果。如果y非空，则非空，则x是是z的的固固有头有头；如果；如果x非空，非空，则则y是是z的的固有尾固有尾。v例如：字母表例如：字母表A=a,b,c上的符号串上的符号串x=abc, 则则x的的 头：头：, a, ab, abc, 尾尾:, c, bc, abc 固有头固有头: , a, ab, 固有尾固有尾:, c, bc符号串的运算符号串的运算符号串的连接符号串的连接：设设x、y是符号串是符号串,它们它们的连接是把的连接是把y的符号写在的符号写在 x的符号之后

9、的符号之后得到的符号串得到的符号串xy例如例如 x=ST，y=abu ，则，则 xy=STabu 显然显然x = x=x符号串的方幂符号串的方幂：把：把符号串符号串a a自身连接自身连接n n次次得到的符号串得到的符号串a an n = = aaaaaaaa例如例如 a a1 1=a a=a a2 2=aa a=aa a0 0=符号串集合：符号串集合：定义定义: : 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上上的符号串，则称的符号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。符号串集合的乘积：符号串集合符号串集合的乘积：符号串集合A和和B的乘积的乘积定

10、义为定义为:AB = xy|xA且且yB ，即，即AB是由是由A中的串中的串x和和B中的串中的串y连接而成的串连接而成的串xy组成的集合。组成的集合。若集合若集合A = ab,cdeab,cde B = 0,10,1 则则 AB = ab0,ab1,cde0,cde1ab0,ab1,cde0,cde1 显然显然 A = A = A符号串集合的方幂符号串集合的方幂: : 设设A A是符号串的集合，则称是符号串的集合，则称A Ai i为符号串集为符号串集A A的方幂，其中的方幂，其中i i是非负整数。具体是非负整数。具体定义如下定义如下: :vA A0 0 = = vA A1 1 = A , A=

11、 A , A2 2 = A A= A AvA AK K = AA.A(k = AA.A(k个个) )集合的闭包集合的闭包闭包闭包集合集合的闭包的闭包 *定义如下：定义如下： * = 0 1 2 3例：设有字母表例：设有字母表=0，1则则*=012=,0,1,00,01,10,11,000,即即*表示表示上所有有穷长的串的集合。上所有有穷长的串的集合。正闭包正闭包+ = 123称为称为的正闭包。的正闭包。 + 表示表示 上的上的除除外外的所有用穷长串的集合的所有用穷长串的集合* = 0+ = * = * 字母表字母表 上上的一个语言是的一个语言是 上符合某种规则的一些符号上符合某种规则的一些符号

12、串的集合串的集合 ，是是 *的一个子集。的一个子集。例如：例如：=a,b =a,b * *=,a,b,aa,ab,ba,bb,aaa,aab,=,a,b,aa,ab,ba,bb,aaa,aab,1. 集合集合 ab,aabb,aaabbb,aab,aabb,aaabbb,an nb bn n,或或 w|ww|w* *且且w=aw=an nb bn n,n1,n1为为字母表字母表 上上的一个语言。的一个语言。 集合集合 a,aa,aaa,a,aa,aaa,或或 w|ww|w* *且且w=aw=an n,n1,n1为为字母字母表表 上上的一个语言。的一个语言。 是一个语言。是一个语言。小结1 符号

13、与字母表符号与字母表2 符号串符号串3 符号串的运算符号串的运算4 符号串集合符号串集合5 集合的闭包集合的闭包6 字母表的闭包字母表的闭包2.3 文法和语言的形式定义1文法的定义2文法形式上的约定3推导与归约4句型、句子、语言的定义5文法的等价1文法的定义“我是大学生”是汉语的一个句子用:=表示的汉语句子的构成规则：句子=主语谓语主语=代词名词代词= 我你他名词= 王明大学生工人英语谓语=动词直接宾语动词= 是学习直接宾语=代词名词句子句子“我是大学生我是大学生”的推导过程如下：的推导过程如下：从句子出发，反复把规则中的从句子出发，反复把规则中的”:=”:=”左边的左边的成分替换成右边的成分

14、。成分替换成右边的成分。句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我我是是直接宾语直接宾语 我是我是名词名词 我是我是大学生大学生关键思路v从文法的开始符号出发，v反复使用产生式，对非终结符进行替换（展开），v直到整个字符串中不在包含非终结符。v这时，得到了这个文法的一个句子句子（一个程序）v这个过程称为推导推导文法的定义v包括四个组成部分：一组终结符号终结符号（不能被替换的符号，单词符号）一组非终结符号非终结符号（能够被替换为终结符号或非终结符号，语法单位）一个开始符号开始符号（从这个符号开始替换，最大语法单位-程序）一组产生式产生式（替换规则

15、，把左边的字符串替换为右边的字符串）文法的形式定义q产生式（规则）产生式是一个有序对(,)，通常写作 （或:= ）q文法定义:文法G(Grammar)定义为四元组（VN，VT，P，S）VN (Nonternimal)：非终结符集VT (Terminal)：终结符集P (Production)：产生式（规则）集合S：开始符号或识别符号q说明:V=VNVT，V称为文法G的字母表P中产生式形如：,其中V+且至少含一个非终结符，V*VN,VT和P是非空有穷集VNVT=S是一个非终结符，且至少要在一条产生式的左部出现非终结符代表一个语言中的语法成分，如，它是构成程序的一个语法成分，这个符号本身不会在程序

16、中出现，而终结符是组成程序的具体的符号。2. 文法形式定义上的约定文法形式定义上的约定v文法习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号,或用GS表示S是开始符号用尖括号括起的是非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成GS，S是开始符号希腊字母代表由终结符号和非终结符号组成的符号串v 、左部相同的产生式A,A可以记为A|，其中“|”是“或”的意思，,分别称为侯选式v如：对于文法 G：S0S1 可写成 GS：S0S1 S01 S01例：文法G=(VN,VT,P,S)其中：VN=S，VT=0，1，P=S0S1,S01开始符为S例：文法G=(V

17、N,VT,P,S)VN =标识符，字母，数字，VT =a,b,c,x,y,z,0,1,9，P=， ， a, , z，0,9 ，S=q例如:文法GS： SA|SA|SDAa|b|zD0|1|93. 推导(Derivation)与归约(Reduction)q直接推导和直接归约： 是文法G的产生式，若有v，w满足：v=,w=, 其中,V* 则称v直接推导出w,也称w直接归约到v,记作 v w直接推导就是用产生式的右部替换产生式的左部的过程直接归约就是用产生式的左部替换产生式的右部的过程例 文法G： S0S1，S01 有直接推导： S 0S1（ S0S1 ）0S1 00S11（ S0S1 ） 00S1

18、1 000S111（ S0S1 ） 000S111 00001111（ S01 ） 推导例题1v文法G1：S-bA, A-aA|a定义了一个什么样的语言？vS=bA=bavS=bA=baA=baavS=bA=baA=baaA=baaavvS=bA=baA=baavL(G1)=ban|n=1 vL(G1) = 以b开头后跟一个或多个a的串推导例题2e.g. 文法产生的语言文法G4对句子aaabb的推导：S = A B S A B = a A B A a A = a a A B A a A = a a a B A a = a a a b B B b B = a a a b b B bA= aB =

19、 abA= Ab = abe.g. 文法产生的语言文法G5对句子aaaabbbb的推导：S = a S b S a S b = a a S b b S a S b = a a a S b b b S a S b = a a a a b b b b S a b直接推导序列和广义推导v直接推导序列： 或 + 若存在v =u0 u1 . un=w, (n0) 则称v + w，v推导出w，或w归约到v（至少有1步推导），这个直接推导序列的长度为n。v广义推导： 或 * 若有v + w 或 v=w， 则记为v * w，v广义推导出w，w广义规约到v（可以包含0步推导）+*三种推导的比较v直接推导（直接推

20、导（）的长度为）的长度为1v直接推导序列（直接推导序列（ +）的长度）的长度n1v广义推导（广义推导（ *）的长度）的长度0规范推导和规范归约规范推导和规范归约v对于一文法而言，从开始符到某句型的对于一文法而言，从开始符到某句型的推导过程可能不唯一推导过程可能不唯一。例如，文法例如，文法GE中从中从 E 到到 i+i*i 的推导有：的推导有：(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+

21、i*i T+i*i F+i*i i+i*i(4) 规范推导v为了让计算机自动地进行推导，通常我们只考虑最左或最右为了让计算机自动地进行推导，通常我们只考虑最左或最右推导。推导。v最左（右）推导最左（右）推导：在推导序列的每一步直接推导中，被替换在推导序列的每一步直接推导中，被替换的总是当前句型中最左（右）的非终结符。的总是当前句型中最左（右）的非终结符。v例如，上页中的（例如，上页中的（2）、（）、（3）分别是最左、最右推导。）分别是最左、最右推导。v形式上，形式上，从符号串从符号串 到符号串到符号串 的推导序列的推导序列 * xUy xuy * 总有总有 x VT* (y VT*) 时，称为

22、时，称为最左（右）推导最左（右）推导v定义：最左（右）推导所得句型称为定义：最左（右）推导所得句型称为左（右）句型；左（右）句型；最右推最右推导导称为称为规范推导规范推导；右句型右句型称为称为规范句型规范句型。 举例v例例1: 文法文法GS: SAB AA0|1B B0|S1 请给出句子请给出句子101001的最左和最右推导。的最左和最右推导。 最左推导：最左推导： S AB 1B B10B 10S1 10AB1 101BB1 1010B1 101001 最右推导：最右推导： S AB AS1AAB1 AA01 A1B01 A1001 1B1001 101001q例2 文法G：EE+T|T T

23、TF|F F（E）|i句子i+ii的推导过程如下：最左推导：E=E+T=T+T=F+T=i+T=i+TF=i+FF =i+iF=i+ii最右推导：E=E+T=E+TF=E+Ti=E+Fi=E+ii = T+ii=F+ii=i+ii递归规则v借助于自身来定义的规则，称为递归规则。如 := 递归规则的存在，使得能用有穷个规则来定义无穷的语言。v如果一个规则形如U:=U（或UxUy），则该规则是递归的； 如果规则形如U:=U （或UUy），则称左递归的； 如果规则形如U:=U （或UxU），则称右递归的。v例：:=, （左递归规则） :=! （右递归规则）文法的递归性v定义：对于某文法，存在UVN，

24、 如果U + U.， 则称该文法递归于U； 如果U + U，则称该文法左递归于U； 如果U + U，则称该文法右递归于U。v例1：C语言中： + (文法右递归于)v例2： UVx VUy|z （都不递归） 有 U + Uxy，所以该文法是左递归的。v注：描述程序设计语言的文法必定都是递归的。递归文法递归文法文法文法GE：显然，显然，G1，G2都是递归定义的。都是递归定义的。所谓所谓递归定义递归定义，指在定义一个，指在定义一个语法成分时，直接或间接地使用了语法成分自身语法成分时，直接或间接地使用了语法成分自身。例如，文法例如，文法G1G1，含有递归非终结符，含有递归非终结符 ，文法，文法G2 G

25、2 中的中的E E、T T是直接递归的，是直接递归的，F F是间接递归的：是间接递归的：F F(E)(E)(T)(T)( (F F) )注意注意，文法与语言之间无一一对应的关系。一文法可文法与语言之间无一一对应的关系。一文法可唯一地确定一语言，但对一语言而言，产生它的文唯一地确定一语言，但对一语言而言，产生它的文法不止一个。法不止一个。4句型、句子、语言的定义q句型和句子设有文法GS，若符号串是从开始符推导出来的,即 S =* ，则称是文法G的句型。若仅由终结符组成,即 S =* ，且VT*，则称是文法G的句子。例 文法GS： S0S1， S01因为S 0S1 00S11 000S111 00

26、001111所以S,0S1 ,00S11 ,000S111,00001111都是G的句型00001111是G的句子由规范推导所得的句型称为规范句型q语言的定义由文法G生成的语言记为L(G),它是文法G的一切句子的集合,即 L(G)=x|S =* x，且 xVT* 例 文法G： S0S1， S01S0S1 00S11 03S13 0n-1S1n-1 0n1nL(G)=0n1n|n1q文法和语言的关系：文法G生成的每个串都在L(G)中L(G)中的每个串确实能被G生成根据文法，可以通过推导得到该文法相应的语言；例：GE：EE+T|TTTF|F F(E)|aE E+T T+T F+T a+T a+TF

27、 a+FF a+aF a+aa表示一切能用符号a，+，(，)构成的算术表达式有了语言的要求，也可以为该语言设计文法例：若语言由0、1符号串组成，串中0和1的个数相同，构造其文法为：A 0B|1CB 1|1A|0BBC 0|0A|1CC5.文法的等价若L(G1)=L(G2)，则称文法G1和G2是等价的。例如 文法G1A：A0R A01 RA1 G2S：S0S1 S01所定义的语言都是0n1n两文法等价2.4 文法的类型Chomsky对文法中的规则施加不同限制，将文法和语言分为四大类：v0型文法（PSG） 0型语言或短语结构语言v1型文法（CSG） 1型语言或上下文有关语言v2型文法（CFG） 2

28、型语言或上下文无关语言v3型文法（RG）3型语言或正则（正规）语言v文法的四元组表示是由文法的四元组表示是由N.ChomskyN.Chomsky于于19561956年描述形式语言时给出年描述形式语言时给出的。他还对产生式的形式给予不同的限制而定义了的。他还对产生式的形式给予不同的限制而定义了四类基本文法四类基本文法。v0 0型文法型文法: :若若P P中任一产生式都有一般形式中任一产生式都有一般形式 V+ V+ V V* * 且对且对 ， 不加任何限制，则称不加任何限制，则称GG为为0 0型文法型文法（短语结构文法，记为短语结构文法，记为PSG: PSG: Phrase Structure G

29、rammarPhrase Structure Grammar) )。由。由0 0型文法生成（或者说：定义）型文法生成（或者说：定义）的语言称为的语言称为0 0型型（递归可枚举递归可枚举）语言语言。它可由。它可由图灵图灵（TuringTuring）机机识识别。别。v例如：例如：S SACaB CaACaB CaaaC CBaaC CBDB CBDB CBE aDE aDDa Da ADADAC aEAC aEEa AEEa AE 就是一个就是一个0 0型文法型文法，它所产生的语言为，它所产生的语言为,|20aaaaaaaaaaaaaaIiaLi对于程序设计语言来，对于程序设计语言来，0 0型文法

30、型文法有很大的随意性有很大的随意性，还须加以限制，还须加以限制1 1型文法和语言型文法和语言v若一若一0型文法所有产生式具有形式型文法所有产生式具有形式 1A 2 1 2 其中，其中， 1, 2 V* V+ A VN,则称则称G 为为1型型(前后文前后文有关有关)文法文法，记为，记为CSG ( Context Sensitive Grammar) 。v1型文法型文法产生的语言称为产生的语言称为前后文有关前后文有关语言语言CSL，它可由，它可由线性限界自动机线性限界自动机识别。识别。v命名的由来命名的由来：只有当非终结符：只有当非终结符A的的前后分别为前后分别为 1, 2 时，才能将时，才能将A

31、替换替换为为 。v1 型文法还有另一种定义形式：型文法还有另一种定义形式： G的每个产生式形为的每个产生式形为且满足且满足： | | | | , V+ 则则G是是1型文型文法法v上述两种定义形式是等价的。上述两种定义形式是等价的。即任一即任一种形式定义的文法所产生的语言都可种形式定义的文法所产生的语言都可由另一种形式定义的文法产生由另一种形式定义的文法产生v注注：根据定义，含有根据定义，含有 产生式的文法产生式的文法不是不是1型文法。由于实际需要，我们型文法。由于实际需要，我们将将 -产生式作为产生式作为1型文法的特例而接型文法的特例而接受之。受之。v例例 文法文法G：S | A AaABC

32、AabC CBBC bBbb bCbc cCccv因因G含有含有 -产生式产生式，所以它不是一个，所以它不是一个严格意义下的严格意义下的1型文法。它所产生的型文法。它所产生的语言为语言为0|)(icbaGLiii2 2型文法和语言型文法和语言v若一若一1型文法型文法G中所有产生式具有形式中所有产生式具有形式: A V+ A VN 则称则称G为为2型型 (前后文无关前后文无关)文法文法，记为，记为CFG(Context Free Grammar)。v2型文法产生的语言称为型文法产生的语言称为前后文无关语言前后文无关语言CFL，它可由，它可由下下推自动机推自动机识别。识别。v若允许若允许 -产生式

33、存在，则产生式存在，则CFG产生式形式为产生式形式为 A V* A VN v例例：GS=(S,a,b,SaSb Sab,S) 产生的语言为产生的语言为1|)(ibaGLii3 3型文法和语言型文法和语言v若一若一2型文法型文法G中仅含有形如中仅含有形如AaB Aa 的产生式，其的产生式，其中中 A,B VN , a VT 则称则称G为为右线性文法右线性文法。v类似地，若类似地，若G中仅含有形如中仅含有形如 ABa Aa的产生式，则称的产生式，则称G为为左线性文法左线性文法。v通常，把通常，把左线性文法左线性文法和和右线性文法右线性文法都称为都称为3型文法型文法（正规文正规文法法）v3型文法型文

34、法产生的语言称为产生的语言称为3型（型（正规正规）语言）语言，它可由，它可由有限自动有限自动机机识别。识别。正规语言正规语言可用可用正规表达式正规表达式表示。表示。v注：注：若一文法即含若一文法即含左线性左线性又含又含右线性产生式右线性产生式，则它，则它不一定是不一定是3型文法型文法！v3型文法型文法还可拓广定义为还可拓广定义为 AB A （ VT +）由各类文法的定义可知，由各类文法的定义可知，3 3型语言一定是型语言一定是2 2型语言，而反型语言，而反之不一定成立；同理，之不一定成立；同理，2 2型语言是型语言是1 1型的也是型的也是0 0型的，反型的，反之不真。之不真。若把各类语言视为语

35、言族若把各类语言视为语言族L LK K ，K=0,1,2,3 K=0,1,2,3 则它们之间有则它们之间有真包含关系：真包含关系：0123LLLL文法类型文法名称语言名称自动机名称0短语结构递归可枚举图灵机1前后文有关前后文有关线性限界2前后文无关前后文无关下推自动机3正规有限状态有限自动机四种文法之间的逐级四种文法之间的逐级“包含包含”关系关系2型文法型文法1型文法型文法3型文法型文法0型文法型文法2.5 上下文无关文法及其语法树1上下文无关文法(Context-Free Grammar)自然语言是上下文有关的。 上下文无关文法有足够的能力描述现今程序设计语言的语法结构例：算术表达式：Ei|

36、E+E|E*E|（E）i:=Eif then | if then else 我们更关心上下文无关文法产生的句子的分析2.语法树(推导树Parse Tree)作用:直观地描述上下文无关文法的句型推导过程。给定文法G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树语法树的概念v定义：语法树是这样的一个语法结构，它的结点由符号组成。根结点对应于识别符号。只有非终结符号对应的结点有子结点。并且，一个结点和它的子结点分别对应于文法中的一个规则的左部和右部。v引入语法树的意义：作为识别句子的辅助工具，语法树可以表示句子的结构。这一点对于其后的语义分析有非常重要的意义。语法树的相关概念v结

37、点：每个树的结点对应于一个符号。结点的名字就是该符号。v边：两个结点之间的连线。v根结点：没有边进入的结点。v分支：某个结点向下射出的边和其结点称为分支。（父子结点，兄弟结点）v子树：语法树的某个结点和它向下射出的部分v末端结点：没有向下射出的边的结点成为末端结点。在相对于句型的语法树中，末端结点可能是非终结符号。语法树的特征v给定文法G，G=(VN,VT,P,S)，对于G的任何句型都能构造与之关联的语法树（推导树）。这棵树具有下列特征：1、根结点的标记是开始符号S；2、每个结点的标记都是V中的一个符号；3、若一棵子树的根结点为A，且其所有直接子孙的标记从左向右的排列次序为A1A2AR，那么

38、A:=A1A2.AR一定是P中的一条规则；4、若一标记为A的结点至少有一个除它以外的子孙，则AVN5、若树的所有叶结点上的标记从左到右排列为字符串w，则w是文法G的句型；若w中仅含终结符号，则w为文法G所产生的句子。从推导构造语法树v方法：把识别符号做为根结点，对每一个直接推导画一个分支，分支的名字是直接推导中被替换的非终结符号，直到再无分支可画结束。v例如：推导S AB AcBd Accdd abccddSBBdbaAcdc语法树的构造过程S AB AcBd Accdd abccddSSBASBBdAc（1）（2）（3）SBBdAcdcSBBdbaAcdc（5）（4）q例：文法G：EE+T|

39、TTTF|F F（E）|i句型T+TF的推导过程与语法树TFTE=E+TEET+EET+TFTE=E+T=E+TF=T+TF=T+T=T+TF从语法树中看不出句型中的符号被替代的顺序从语法树中看不出句型中的符号被替代的顺序从左到右读出叶子从左到右读出叶子结点得到的符号结点得到的符号串串，为文法的句型。也为文法的句型。也把该语法树称为该把该语法树称为该句型的语法树。句型的语法树。从语法树构造推导v方法：从分支建立直接推导，然后从语法树中剪去之这个分支，直到无分支可剪。v语法树表明了在推导过程中使用了哪条规则和使用在哪个非终结符号上，但它并没有表明使用规则的顺序。v一棵语法树可能对应不止一种推导。

40、从语法树构造推导的过程v例如文法GS： S:=AB A:=aAb|ab B:=cBd|cd 存在下面的推导可能：vS AB AcBd (4) (3) Accdd abccdd (2) (1)vS AB abB abcBd abccdd（从后往前看）SBBdbaAcdc(1)(2)(3)(4)文法G：EE+E|EE|（E）|i句子 ii+i两个不同的最左推导：两个不同的最左推导：推导推导1：E E+E EE+E iE+E ii+E ii+i推导推导2：E EE iE iE+E ii+E ii+i3.文法的二义性文法的二义性(Ambiguity)文法的二义性v存在这样的文法存在这样的文法G，其某个

41、句子，其某个句子w L(G),可对应结构不同可对应结构不同的语法树，即的语法树，即w对应了多个不同的最左（右）推导，这类对应了多个不同的最左（右）推导，这类文法称为文法称为。v例如，例如，G3E：EE+E|E*E|(E)|i 的句型的句型及文法及文法vCif B then C|if B then C else CC S的句型：的句型：if B1 then if B2 then S1 else S2v上面两个句型均有两个不同的语法推导树（见下页），所上面两个句型均有两个不同的语法推导树（见下页），所以，它们是二义性文法以，它们是二义性文法EEEEE+*iiiEEEEE+*iii S1 S2if

42、B1 then C else Cif B2 then CCCif B1 then CS1 S2if B1 then C else C关于二义性文法v应指出应指出，二义性，二义性是一种常见的语法现象，然而，对于编译程是一种常见的语法现象，然而，对于编译程序而言，序而言，二义性文法二义性文法是是有害有害的。的。v为解决二义性文法带来的不确定性问题，通常的方法一是为解决二义性文法带来的不确定性问题，通常的方法一是修修改文法改文法。v二是二是利用附加条件利用附加条件。例如，例如， i+ii+i* *i i的归约过程中，若规定的归约过程中，若规定* *比比+ +优先级高，则可强制性地让系统先按优先级高，

43、则可强制性地让系统先按E E* *E E进行归约，而不进行归约，而不是先按是先按E+EE+E进行归约；进行归约；又比如，若又比如，若强制规定强制规定elseelse只能和距其只能和距其最近的尚未被匹配的最近的尚未被匹配的thenthen进行匹配，就可解决进行匹配，就可解决elseelse悬空的问悬空的问题。题。关于二义性文法关于二义性文法v应指出，任一应指出，任一前后文无关文法前后文无关文法是否是是否是二义性的是不可判定的二义性的是不可判定的。v对于某个对于某个具体的文法具体的文法而言，其而言，其二义性还是可判定的二义性还是可判定的。v存在一些判定文法是否二义性的充分条件：存在一些判定文法是否

44、二义性的充分条件：v若一文法含有若一文法含有既是左递归又是右递归既是左递归又是右递归的文法符号，即有的文法符号，即有A+ AvA v V*或或A+ A或或A+ A 及及 AA则则G必定是二义性的必定是二义性的。v并非所有的文法可消除二义性并非所有的文法可消除二义性。即存在这样的。即存在这样的CFL，定义它的一切文法，定义它的一切文法都是二义性的。这样的语言称为都是二义性的。这样的语言称为先天二义性语言先天二义性语言。例如，。例如，1,|1,|mndcbamndcbaLnmmnmmnn为一先天二义性语言。为一先天二义性语言。CFLCFL的先天二义性也是不可判定的的先天二义性也是不可判定的。为什么

45、要避免文法产生二义性？v二义性的文法将给编译程序的执行带来问题。当编译程序对二义性文法生成的句子结构进行语法分析时，就会产生两种甚至更多种不同的理解。语法结构上的不确定性，必将导致语义处理上的不确定性。因此，希望描述语言的文法是无二义性的。如何消除文法的二义性？v方法二：构造一个等价的无二义性的文法，即把排除二义性的规则合并到原有文法中，改写原有的文法。v如文法 GE: E i E E+E E E*E E (E) 将运算符的优先顺序和结合规则加到原有文法中，则可构造无二义性的文法 GE: E T|E+T T F|T*F F （E）|i二义性文法的改造v注意：文法的二义性性与语言二义性的区别 因

46、为可能有两个不同的文法G1和G2，其中有一个是二义性的，但却有L(G1)=L(G2)。如果产生某上下文无关语言的每个文法都是二义性的，则说明该语言是先天二义性的，即该语言是二义性的。2.6 句型的分析q任务: 句型分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。q对于程序设计语言来说，句型分析就是一个识别输入符号串是否为语法上正确的程序的过程。q它是一种推导或语法树的构造过程。对于一个给定的符号串，试图按照文法的规则构造其对应的推导，或语法树。q句型的分析算法分类自顶向下的语法分析 (Top-Down parsing)自底向上的语法分析自底向上的语法分析(Bottom-Up p

47、arsing)2.6.1 自顶向下的分析方法q定义:对于给定的符号串对于给定的符号串w，采用，采用自顶向下自顶向下的分析来判断的分析来判断w是否是否为为L(GS)的句子的常见方法是：的句子的常见方法是：试图建立从开始符试图建立从开始符 S到到w最左推导最左推导: S* w 显然，每步推导时，对应于最左非终结符相应的产生式显然，每步推导时，对应于最左非终结符相应的产生式可能会有多个，若无特殊的办法，只能一个一个地试探。可能会有多个，若无特殊的办法，只能一个一个地试探。因此，推导过程可能是因此，推导过程可能是带回溯带回溯的的。 为提高效率，就应尽量避免回溯为提高效率，就应尽量避免回溯v语法树的构造

48、：将文法的开始符号作为语法树的根，向下逐步建立语法树，使语法树的末端结点符号串正好是输入符号串。例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子S推导过程：推导过程：cAdab=cabdS =cAdq自上而下方法的主要问题对输入串cabd自上而下构造语法树的另一过程不成功，不成功的原因不成功，不成功的原因是选错产生式是选错产生式Aa自上而下分析的主要问题是选择产生式自上而下分析的主要问题是选择产生式 :假定要被代换的最左非终结符号是假定要被代换的最左非终结符号是B B，且有且有n n条规则：条规则：BABA1 1|A|A2 2|A|An n，那么如何确定用那么如

49、何确定用哪个右部去替代哪个右部去替代B B？ScA dav就是从已给的符号串就是从已给的符号串w出发，试图以相反的方向为出发，试图以相反的方向为w建立一个规建立一个规范推导，最终得到文法的开始符。范推导，最终得到文法的开始符。v推导的逆过程称作推导的逆过程称作归约归约，它是把当前的符号串，它是把当前的符号串中的构成文法中的构成文法某个产生式某个产生式A右部的子串右部的子串 替换成产生式的左部符号替换成产生式的左部符号A，得到，得到一个新的符号串一个新的符号串 A 。这样的一步动作，称为进行了一步。这样的一步动作，称为进行了一步归约归约。v例如，符号串例如，符号串F+i*i中的中的F可按产生式可

50、按产生式TF归约为归约为T，从而得到新，从而得到新的符号串的符号串T+i*i。v若从给定的符号串若从给定的符号串w出发，一步步地将其归约，最终得到文法的出发，一步步地将其归约，最终得到文法的开始符号，则说明开始符号，则说明w是该文法定义的一个句子。归约成功，否则，是该文法定义的一个句子。归约成功，否则，归约失败。归约失败。v若归约的每一步都归约的是当前符号串中最左边的某产生式的右若归约的每一步都归约的是当前符号串中最左边的某产生式的右部，则称该归约是部，则称该归约是规范归约规范归约（即（即最左归约最左归约）。）。v规范归约是规范推导的逆过程规范归约是规范推导的逆过程。v关于最左（右）归约、直接

51、归约、归约等的形式定义不再赘述。关于最左（右）归约、直接归约、归约等的形式定义不再赘述。2.6.2 自底向上的语法分析自底向上的语法分析步序 当前符号串wi 所用的产生式 归约后的符号 0 i+i*i Fi F+i*i 1 F+i*i TF F T+i*i 2 T+i*i E ET T E+i*i 3 E+i*i F Fi i E+F*i 4 E+F*i T TF F E+T*i 5 E+T*i F Fi i E+T*F 6 E+T*F T TT T* *F F E+T 7 E+T E EE E+ +T T E 由上表可以看出，归约过程是由上表可以看出，归约过程是最左最左归约，它恰好是归约，它

52、恰好是规规范推导的逆过程范推导的逆过程。这正是把最左归约定义为规范归约。这正是把最左归约定义为规范归约的原因。的原因。例 文法G：S cAd A ab A a识别输入串w=cabd是否为该文法的句子cabd归约过程：归约过程：用用“|-”表示归表示归约，下划线部分约，下划线部分为被归约符号为被归约符号cabd |-cAd |-SAS关于归约的一点说明v注意，前面例子中归约的第五步中，当前的符号串为注意，前面例子中归约的第五步中，当前的符号串为 E+T*i，除了可将，除了可将i归约成归约成F外，还可将外，还可将E+T或或T归约成归约成E，分别得到符号串分别得到符号串E*i和和E+E*i。但是，若

53、真按这两个方案。但是，若真按这两个方案进行归约，则当我们把其归约成进行归约，则当我们把其归约成E*E或或E+E*E时，就再时，就再也归约不下去了。这就告诉我们在第五步时，唯一正确也归约不下去了。这就告诉我们在第五步时，唯一正确的归约是将的归约是将i归约为归约为F，也就是说，也就是说，i是唯一可被归约的最是唯一可被归约的最左子串。左子串。v对输入串cabd的两种归约过程（1）cabd|-cAd|-S 归约到开始符（2）cabd|-cAbd 不能归约到开始符 那么，对于规范归约的每一步，如何确定符号串中的当那么，对于规范归约的每一步，如何确定符号串中的当前应被归约的最左子串呢？前应被归约的最左子串

54、呢？短语和句柄短语和句柄v问题问题: : 在自底向上在自底向上( (简记为简记为 ) )的语法分析中的语法分析中, ,对对于每一步直接归约于每一步直接归约, ,应如何正确地确定当前句应如何正确地确定当前句型中应被归约的型中应被归约的最左子串最左子串? ?v考虑文法考虑文法G G2 2EE的句型的句型 = E+T= E+T* *F+iF+i, ,从开始符从开始符E E 推导出推导出 的语法树见右图的语法树见右图v该树中含有若干子树该树中含有若干子树, ,如如T T(2)(2)为根的子树对应的为根的子树对应的叶结点为叶结点为T T(3)(3)* *F F(3),(3),由于它是一直接子树由于它是一

55、直接子树, ,文法中文法中必有产生式必有产生式T-TT-T* *F F; ;因此因此, ,称称T T* *F F是句型是句型 相对于相对于产生式产生式T-TT-T* *F F的的直接短语直接短语. .同理同理, ,F F(1)(1)对应的对应的直直接短语接短语为为i i. .v以以E E(1)(1)为根的子树相应的叶结点为为根的子树相应的叶结点为 E E(2)(2)+T+T(3)(3)* *F F(3)(3), ,所以所以, ,称为句型称为句型 相对于非终结符相对于非终结符E E 的的短语短语. .同同理理, ,i i是相对于是相对于T T(1)(1)的的短语短语短语、直接短语及句柄的定义短语

56、、直接短语及句柄的定义定义:设是文法GS中的一个句型，如果有S=*A且A=+，则称是句型相对于非终结符A的短语特别的如有A=，则称是句型相对于规则A的(直接短语直接短语)简单短语。一个句型的最左简单短语称为该句型的句柄(Handle)。句柄就是“可归约串”v例如，对句型例如，对句型 = E+T*F+i，由定义，有：由定义，有：v(1)E* E+T+i( =E+,A=T, =+i)及及TT*F(= ),故故T*F是是 相相对于产生式对于产生式T-T*F的直接短语的直接短语;v(2)E* E+T*F+F Fi,i是是 相对于产生式相对于产生式F-i的直接短语的直接短语;v(3)E* E+i与与 E

57、 + E+T*F,E+T*F是相对于非终结符是相对于非终结符E的短的短语语;v(4)E* E及及E* E+T*F+i(= ), 是是 相对于相对于E的短语的短语v注注:由定义可知由定义可知,直接短语也是短语直接短语也是短语,但短语不一定是直接短语但短语不一定是直接短语.归约时被替换子串的选择v从句型 =E+T=E+T* *F+iF+i的语法树可知,E+T绝不是它的一个直接短语,因为虽然E-E+T是G2的一个产生式,但不存在从E到E*F+i的推导,所以,当判断一符串是否为某一句型的短语时,须检查定义的两个条件是否同时满足.v采用采用 分析时分析时, ,每步每步归约归约就是将一个产生式就是将一个产

58、生式右部右部替换替换其其左部左部, ,也就是把该也就是把该句型的语法树中的句型的语法树中的一棵直接子树的末端结点剪去一棵直接子树的末端结点剪去. .即每次归约的符号串即每次归约的符号串必是当前句型的一个直接短语必是当前句型的一个直接短语. .v但是但是, ,对一句型而言对一句型而言, ,其其直接短语可能不唯一直接短语可能不唯一. .为了让分析能够机械地进为了让分析能够机械地进行行, ,我们只考虑规范归约我们只考虑规范归约( (最左归约最左归约),),即归约过程替换的是归左直接短语即归约过程替换的是归左直接短语. .v我们以L(G2)的句子i+i*i+i为例,给出其最右推导(规范归约的逆过程),

59、来说明每次规范归约的子符号串用语法树求短语、句柄v短语：（子）树的末端结点形成的符号串是相对于(子)树根的短语。v简单短语（直接短语）：简单子树的末端结点形成的符号串是相对于简单子树根的简单短语。v句柄：最左简单子树的末端结点形成的符号串是句柄。例：对于文法例：对于文法GS：S:=AB A:=Aa|bB B:=a|Sb 求句型求句型baSb的全部短语、直接短的全部短语、直接短语和句柄？语和句柄？lbaSb为句型为句型baSb的相对于的相对于S的的短语；短语；lba为句型为句型baSb的相对于的相对于A的短语；的短语；la为句型为句型baSb的相对于的相对于B的短语的短语,且为直接短语和句柄；且

60、为直接短语和句柄；lSb为句型为句型baSb的相对于的相对于B的短的短语语,且为直接短语。且为直接短语。SSABbabSB例：文法GE: EE+T|T TTF|F F（E）| i 的一个句型是 TF+i，相应的语法树见右图：EET+TTFFi . 因为因为E=* T+i 且且 T=TF，所以所以TF是句型相对于是句型相对于T的短语，且是相对的短语，且是相对于于TTF的直接短语的直接短语 . 因为因为E=* TF+F 且且 F=i，所以所以i是句是句型相对于型相对于F的短语，且是相对于的短语，且是相对于Fi的直接短语的直接短语 . 因为因为E=* E 且且E=+ TF+i，所以所以TF+i是句型