第2章文法和语言

1、第2章文法和语言 第二章 文法和语言的基本知识 形式语言的理论是编译的重要理论基础。有关形式语言的理论是编译的重要理论基础。有关 形式语言的概念包括：形式语言的概念包括： 字母表和符号串字母表和符号串 文法和语言的形式定义文法和语言的形式定义 短语、直接短语和句柄短语、直接短语和句柄 语法树和文法的二义性语法树和文法的二义性 文法和语言的分类文法和语言的分类 第2章文法和语言 第二章 文法和语言的基本知识 2.1 2.1 概述概述 2.2 2.2 字母表和符号串字母表和符号串 2.3 2.3 法和语言的形式定义法和语言的形式定义 2.4 2.4 短语、直接短语和句柄短语、直接短语和句柄 2.5

2、 2.5 语法树与文法的二义性语法树与文法的二义性 2.6 2.6 文法和语言的分类文法和语言的分类 2.7 2.7 自上而下的分析方法自上而下的分析方法 2.8 2.8 有关文法实用中的一些说明有关文法实用中的一些说明 第2章文法和语言 2.1 概述 语言是一个记号系统语言是一个记号系统 汉语汉语-符合汉语语法的句子的全体符合汉语语法的句子的全体 英语英语-符合英语语法的句子的全体符合英语语法的句子的全体 程序设计语言程序设计语言-该语言的程序的全体该语言的程序的全体 第2章文法和语言 2.1 概述 对程序设计语言非形式化的描述：对程序设计语言非形式化的描述： 语法：定义每个程序构成的规则语

3、法：定义每个程序构成的规则 语义：定义每个程序的意义语义：定义每个程序的意义 语用：每个程序语用：每个程序(语句语句)的用途的用途 例例s=2*3.1416*r*(h+r)的非形式化的描述：的非形式化的描述： 语法语法赋值语句有一个变量、一个赋值号后跟表达赋值语句有一个变量、一个赋值号后跟表达 式构成式构成 语义语义计算计算=右部的值，送入左部变量右部的值，送入左部变量 语用语用赋值语句用来计算和保存表达式的值赋值语句用来计算和保存表达式的值 第2章文法和语言 2.1 概述 非形式化描述非形式化描述不清晰不清晰 不准确不准确 形式化描述形式化描述用一整套带有严格规定用一整套带有严格规定 的符号

4、体系来描述问题的方法的符号体系来描述问题的方法 用形式语言描述各种程序设计语言用形式语言描述各种程序设计语言 第2章文法和语言 程序设计语言包括程序设计语言包括:语法和语义语法和语义 q语法语法(syntax) 定义定义: 是一组规则，用它可以形成和产生是一组规则，用它可以形成和产生 一个合适的程序一个合适的程序 描述工具描述工具:文法文法 作用作用: 定义什么样的符号序列是合法的，定义什么样的符号序列是合法的， 与符号的含义无关。与符号的含义无关。 形式语言的基本形式 第2章文法和语言 例例: :“我是大学生我是大学生”是汉语的一个句子是汉语的一个句子 用用EBNFEBNF来表示汉语句子的构

5、成规则：来表示汉语句子的构成规则： 句子句子=主语谓语主语谓语 主语主语=代词名词代词名词 代词代词= = 我你他我你他 名词名词= = 王明大学生工人英语王明大学生工人英语 谓语谓语=动词直接宾语动词直接宾语 动词动词= = 是学习是学习 直接宾语直接宾语=代词名词代词名词 第2章文法和语言 例如例如: :句子句子“我是大学生我是大学生”的推导过程如下：的推导过程如下： 句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生 第2章文法和语言 2.2 字母表和符号串 1 1、字母表和符号、字母

6、表和符号 定义定义: :元素的元素的非空有穷非空有穷集合集合 例：例：=01 =ab,c 元素也称为符号，字母表也称符号集。元素也称为符号，字母表也称符号集。 程序语言的字母表由字母数字和若干程序语言的字母表由字母数字和若干 专用符号组成。专用符号组成。 第2章文法和语言 2、符号串 定义定义: :由字母表中的符号组成的任何有由字母表中的符号组成的任何有 穷序列穷序列 例：例： 字母表字母表=01上的符号串：上的符号串： 0,00,10等等 =ab,c上的符号串：上的符号串： a,ab,aaca等等 第2章文法和语言 2、符号串 在符号串中，符号是有顺序的，顺序不在符号串中，符号是有顺序的，顺

7、序不 同同,代表不同的符号串，如代表不同的符号串，如ab和和ba不同不同 不含任何符号的符号串称为空串，用不含任何符号的符号串称为空串，用表表 示示 注意注意: :并不等于空集合并不等于空集合 符号串长度符号串长度: 符号串中含有符号的个数符号串中含有符号的个数 如如: |abc|=3 |=0 第2章文法和语言 3、符号串的运算 符号串的连接：设符号串的连接：设x、y是符号串是符号串,它们的它们的 连接是把连接是把y的符号写在的符号写在 x的符号之后得到的符号之后得到 的符号串的符号串xy 例如例如 x=ST，y=abu ， 则则 xy=STabu x = x=？ 符号串的方幂：把符号串的方幂

8、：把符号串符号串a a自身连接自身连接n n次次 得到的符号串得到的符号串a an n = = aa aaaaaa a a1 1 a a2 2 a a0 0 a a1 1=a a=a a2 2=aa a=aa a0 0= 第2章文法和语言 4、符号串集合 定义定义: : 若集合若集合A A中所有元素都是某字母表中所有元素都是某字母表 上的符上的符 号串，则称号串，则称A A为字母表为字母表 上的符号串集合。上的符号串集合。 符号串集合的乘积：符号串集合符号串集合的乘积：符号串集合A和和B的乘积定的乘积定 义为义为: AB = xy|xA且且yB ，即即AB是由是由A中的中的 串串x和和B中的串

9、中的串y连接而成的串连接而成的串xy组成的集合。组成的集合。 若集合若集合A = ab,cdeab,cde B = 0,10,1 则则 AB = ab0,ab1,cde0,cde1ab0,ab1,cde0,cde1 显然显然 A = A = ？ 第2章文法和语言 4、符号串集合 符号串集合的方幂符号串集合的方幂: : 设设A A是符号串的集合，是符号串的集合， 则称则称A Ai i为符号串集为符号串集A A的方幂，其中的方幂，其中i i是非是非 负整数。具体定义如下负整数。具体定义如下: : A A0 0 = = A A1 1 = A , A = A , A2 2 = A A = A A A

10、Ak k = AA.A (k = AA.A (k个个)=)=AAAAk-1= k-1=A Ak-1 k-1 A A 例：A=0,1 第2章文法和语言 5、集合的闭包 闭包闭包 集合集合A的闭包的闭包A* (正闭包正闭包A+)定义如下：定义如下： A+ = A1 A2 A3 An A* = A0 A1 A2 A3 An 例：设有字母表例：设有字母表=0,1 + =12 =0,1,00,01,10,11,000, 即即+表示表示上上0 1构成的所有符号串的集合。构成的所有符号串的集合。 *=012 =,0,1,00,01,10,11,000, 第2章文法和语言 字母表字母表 上上的一个语言是的一个

11、语言是 上符合某种规则的一些符号上符合某种规则的一些符号 串的集合串的集合 ，是是 *的一个子集。的一个子集。 例如：例如：=a,b *=,a,b,aa,ab,ba,bb,aaa,aab, 1. 集合集合ab,aabb,aaabbb,anbn,或或 w|w*且且w=anbn,n1为字母表为字母表 上上的一个语言。的一个语言。 集合集合a,aa,aaa,或或w|w*且且w=an,n1为字母表为字母表 上上的一个语言。的一个语言。 是一个语言。是一个语言。 2. 即即 是一个语言。是一个语言。 5、集合的闭包 第2章文法和语言 重点回顾 解释程序解释程序(interpreter)与编译程序与编译程

12、序 编译程序是将源程序翻译成目标程序后再执编译程序是将源程序翻译成目标程序后再执 行该目标程序行该目标程序 解释程序则是逐条读出源程序中的语句并解解释程序则是逐条读出源程序中的语句并解 释执行，即在解释程序的执行过程中并不产释执行，即在解释程序的执行过程中并不产 生目标程序。生目标程序。 编译的基本过程编译的基本过程 第2章文法和语言 源程序源程序 词法分析程序词法分析程序 语法分析程序语法分析程序 语义分析程序语义分析程序 中间代码生成程序中间代码生成程序 代码优化程序代码优化程序 目标代码生成程序目标代码生成程序 表格管理程序表格管理程序 出错处理程序出错处理程序 目标程序目标程序 第2章

13、文法和语言 重点回顾 字母表和符号字母表和符号 符号串符号串 符号串的运算符号串的运算 符号串的连接符号串的连接 符号串的方幂符号串的方幂 符号串集合符号串集合 符号串集合的乘积符号串集合的乘积 符号串集合的方幂符号串集合的方幂 集合的闭包集合的闭包 第2章文法和语言 2.3 文法和语言的形式定义 1形式语言的定义形式语言的定义 2. 文法的定义文法的定义 3文法的简化表示法文法的简化表示法 4推导与归约推导与归约 5句型、句子、语言的定义句型、句子、语言的定义 6规范推导和规范归约规范推导和规范归约 7文法的递归性文法的递归性 第2章文法和语言 1形式语言的定义 q序列的集合称为形式语言（字

14、母表上按某种序列的集合称为形式语言（字母表上按某种 规则构成的所有符号串的集合）规则构成的所有符号串的集合） q形式语言的描述形式语言的描述: 枚举法枚举法当语言为有穷集合时当语言为有穷集合时 文法文法当语言为无穷集合时当语言为无穷集合时 第2章文法和语言 1形式语言的定义 例：例： =a,b L1=a,b,ab； L2=aa,bb,aabb L3=a,b,aa,ab,ba,bb,aab,aba,abb,baa=+ 无穷集不宜用枚举法来描述无穷集不宜用枚举法来描述 自然语言描述（由自然语言描述（由a、b构成的所有符号串）非形式构成的所有符号串）非形式 化描述化描述 文法描述：形式化描述文法描述

15、：形式化描述 A-a A-b A-Aa A-Ab 第2章文法和语言 2文法的定义 q产生式（规则）产生式（规则） 产生式是一个有序对产生式是一个有序对(,)，通常写作，通常写作 （或或:= ）。）。 读作：读作： 定义为定义为。称为产生式称为产生式的左部，的左部， 称为产生式称为产生式的右部。产生式又叫做定义式的右部。产生式又叫做定义式 或者语法规则。或者语法规则。 q一组规则定义了一个语言的语法结构一组规则定义了一个语言的语法结构 q机器识别（语法正确与否）的要求机器识别（语法正确与否）的要求 第2章文法和语言 2文法的定义 例：例： A0 A1 AA 0 AA 1 描述的语言描述的语言 L

16、=0,1,00,01,10,11,100,111,001,000,011 =+ 非终结符号：出现在规则左部能派生出符号非终结符号：出现在规则左部能派生出符号 或符号串的那些，即每个非终结符号表示一定或符号串的那些，即每个非终结符号表示一定 符号串的集合，一般用大写字母表示。符号串的集合，一般用大写字母表示。 终结符号：不属于非终结符号的那些符号，终结符号：不属于非终结符号的那些符号， 他是组成语言的基本符号，是一个语言的不可他是组成语言的基本符号，是一个语言的不可 再分的基本符号，通常用小写字母表示。再分的基本符号，通常用小写字母表示。 第2章文法和语言 q文法定义文法定义: 文法文法G(Gr

17、ammar)定义为四元组（定义为四元组（VN，VT， P，S） VN (Nonterminal)：非终结符集。非终结符集。 VT (Terminal)：终结符集。终结符集。是语言的句子中出是语言的句子中出 现的字符。所以，有现的字符。所以，有VNVT = P (Production)：产生式（规则）集合产生式（规则）集合 S： SVN，开始符号或识别符号，开始符号或识别符号 2文法的定义 第2章文法和语言 q说明说明: V=VNVT，V称为文法称为文法G的词汇表的词汇表 P中产生式形如：中产生式形如：,其中其中V+且至少含一且至少含一 个非终结符，个非终结符，V* VNVT= S是一个非终结符

18、，且至少要在一条产生式的是一个非终结符，且至少要在一条产生式的 左部出现左部出现 2文法的定义 第2章文法和语言 例例1：文法：文法G=(VN,VT,P,S) 其中：其中：VN=S，VT=0，1，P=S0S1,S01 开始符为开始符为S 例例2：文法：文法G=(VN,VT,P,S) VN =标识符，字母，数字标识符，字母，数字， VT =a,b,c,x,y,z,0,1,9， P=， ， a, , z， 0,9 ， S= 2文法的定义 第2章文法和语言 2文法的定义 例例3：以下四元组都是文法。：以下四元组都是文法。 (A，0，1，A01，A0A1，A1A0，A)。 (A，0，1，A0，A0A，

19、A)。 (A，B，0，1，A01，A0A1，A1A0，BAB， B0，A)。 (A，B，0，1，A0，A1，A0A，A1A ， A)。 (S，a，b，S00S，S11S，S00，S11，S)。 第2章文法和语言 3文法的简化表示法 q简化表示法简化表示法: 通常不用将文法的四元组表示出来，通常不用将文法的四元组表示出来， 只写出产生式只写出产生式 q约定：约定： 第一条产生式的左部是开始符号第一条产生式的左部是开始符号 或用或用GS表示表示S是开始符号是开始符号 用大写字母（或用尖括号括起来）表示非终结符用大写字母（或用尖括号括起来）表示非终结符 用小写字母表示终结符用小写字母表示终结符 左部

20、相同的产生式左部相同的产生式A,A可以记为可以记为A|， 其中其中“|”是是“或或”的意思，的意思，,分别称为侯选式分别称为侯选式 第2章文法和语言 例例2可以化简为：可以化简为： 文法文法GS： SA|SA|SD Aa|b|z D0|1|9 字母字母标识标识 符符 数字数字 3文法的简化表示法 例例2：文法：文法G=(VN,VT,P,S) VN =标识符，字母，数字标识符，字母，数字， VT =a,b,c,x,y,z,0,1,9， P=， ， a, , z， 0,9 ， S= 第2章文法和语言 4. 推导(Derivation)与归约(Reduction) q直接推导和直接归约：直接推导和直

21、接归约： AaAa是文法是文法G G的产生式，若有的产生式，若有v v，w w满足：满足： v=xAy,w= xay, v=xAy,w= xay, 则称则称v v直接推导出直接推导出w,w,也称也称w w直接归约到直接归约到v,v, 记作记作 v v w w 直接推导就是用产生式的右部替换产生式的左部的过直接推导就是用产生式的右部替换产生式的左部的过 程（仅使用一次规则）程（仅使用一次规则） 直接归约就是用产生式的左部替换产生式的右部的过直接归约就是用产生式的左部替换产生式的右部的过 程程 第2章文法和语言 例例 文法文法G G：S0S1S0S1，S01 S01 有直接推导：有直接推导： S

22、S 0S10S1（ S0S1S0S1 ） 0S1 0S1 00S1100S11（ S0S1S0S1 ） 00S11 00S11 000S111000S111（ S0S1S0S1 ） 000S111 000S111 0000111100001111（ S01 S01 ） 4. 推导(Derivation)与归约(Reduction) 第2章文法和语言 q推导和归约推导和归约 若存在直接推导序列若存在直接推导序列 0 1 2 . n 则称则称0推导出推导出n，或或n归约到归约到0,记为记为 0 = + n 若有若有0 =+ n ，或或0 = n ，则记作则记作 0 = * n 4. 推导(Deri

23、vation)与归约(Reduction) 第2章文法和语言 例例 文法文法G G： S0S1 S0S1， S01 S01 S S 0 0S S1 1 00 00S S11 11 000111 000111 S =S =+ + 000111 000111 S S =* * S S 4. 推导(Derivation)与归约(Reduction) 第2章文法和语言 4. 推导(Derivation)与归约(Reduction) 例例 文法文法GE： EE+T|T TT*F|F F(E)|i 对对i+i*i的直接推导序列的直接推导序列 E E+T T+T F+T i+T i+T*F i+F*F i+

24、i*Fi+i*i 第2章文法和语言 5句型、句子、语言的定义 q句型和句子句型和句子 设有文法设有文法GSGS，若符号串若符号串是从开始符推导是从开始符推导 出来的出来的, ,即即 S S =* * ， ( (VNVT)* 则称则称是是 文法文法G G的句型。的句型。 若若仅由终结符组成仅由终结符组成, ,即即 S S =+ + ，且且 VVT T* *，则称则称是文法是文法G G的句子。的句子。 例例 文法文法GSGS： S0S1 S0S1， S01 S01 因为因为S S 0 0S S1 1 00 00S S11 11 000 000S S111 111 00001111 00001111

25、 所以所以S,S,0S1 ,00S11 ,000S111,000011110S1 ,00S11 ,000S111,00001111都是都是G G的句型的句型 是是G G的句子的句子 第2章文法和语言 5句型、句子、语言的定义 q句型和句子句型和句子 例例 文法文法GEGE： EE+T|T EE+T|T TT TT* *F|FF|F F(E)|i F(E)|i i+Ti+T* *F F ( (i i* *i+i)i+i) 第2章文法和语言 5句型、句子、语言的定义 q语言的定义语言的定义 由文法由文法G G生成的语言记为生成的语言记为L(G),L(G),它是文法它是文法G G的一的一 切句子的集

26、合切句子的集合, ,即即 L(G)=x|S L(G)=x|S =+ + x x， ，且且 xVxVT T* * 例例 文法文法G G： S0S1 S0S1， S01 S01 S 0S1 00S11 0 3S13 0 n-1S1n-1 0n1n L(G)=0L(G)=0n n1 1n n|n1|n1 第2章文法和语言 文法和语言的关系：文法和语言的关系： 文法文法G G生成的每个串都在生成的每个串都在L(G)L(G)中中 L(G)L(G)中的每个串确实能被中的每个串确实能被G G生成生成 根据语言，可以设计一组规则生成语言中的所根据语言，可以设计一组规则生成语言中的所 以句子而得到该语言相应的文

27、法；但描述该语以句子而得到该语言相应的文法；但描述该语 言的文法不唯一。言的文法不唯一。 根据文法，可以通过推导得到该文法相应的语根据文法，可以通过推导得到该文法相应的语 言；言； 从已知文法确定语言的方法：从文法的开始符从已知文法确定语言的方法：从文法的开始符 号出发，反复连续的使用规则，对非终结符施号出发，反复连续的使用规则，对非终结符施 行替换和展开，找出句子规律行替换和展开，找出句子规律。 5句型、句子、语言的定义 第2章文法和语言 例：GE：EE+T|TTTF|F F(E)|i E E+T T+T F+T i+T i+TF i+FF i+iF i+ii (i+i);i*i*i;(i*

28、i+i) 自然语言描述：一切能用符号自然语言描述：一切能用符号i，+，(，)构构 成的算术表达式成的算术表达式 5句型、句子、语言的定义 第2章文法和语言 小结：小结： 给定一个文法，就能从结构上唯一的确给定一个文法，就能从结构上唯一的确 定其语言，即定其语言，即G GL(G)L(G) 给定一种语言，能确定其文法，但这种给定一种语言，能确定其文法，但这种 文法不是唯一的，即文法不是唯一的，即L LG1G1、G2G2等等 5句型、句子、语言的定义 第2章文法和语言 6规范推导和规范归约 同一个句型（句子）可有不同的推导序列同一个句型（句子）可有不同的推导序列 如果在推导的任何一步如果在推导的任何

29、一步，其中其中、是句型，是句型， 都是对都是对中的最左（最右）非终结符进行替换中的最左（最右）非终结符进行替换, 则称这种推导为最左则称这种推导为最左(最右最右)推导推导 最右推导被称为规范推导最右推导被称为规范推导 由规范推导所得的句型称为规范句型由规范推导所得的句型称为规范句型 规范推导的逆过程，称为最左规约，也称为规规范推导的逆过程，称为最左规约，也称为规 范规约。范规约。 第2章文法和语言 6规范推导和规范归约 例：设有文法例：设有文法GS: S-AB A-A0|1B B-0|S1 请给出句子请给出句子101001的规范推导和规范规约的规范推导和规范规约 S AB AS1 AAB1AA

30、01A1B01 A1001 1B1001101001 . 归约符号表示：归约符号表示： 第2章文法和语言 7文法的递归性 所谓递归规则是指规则的左部和右部具所谓递归规则是指规则的左部和右部具 有相同非终结符的规则有相同非终结符的规则 A-A规则左递归规则左递归 A-A规则右递归规则右递归 A-A规则递归规则递归 文法递归性：文法递归性：A + +A； A + + A ； A + + A 递归规则的使用，可用有限的规则刻画递归规则的使用，可用有限的规则刻画 无穷的语言。无穷的语言。 第2章文法和语言 7文法的递归性 含有递归规则的文法，一定是递归的。不含递含有递归规则的文法，一定是递归的。不含递

31、 归规则的文法也可能是递归的。归规则的文法也可能是递归的。 例：例：U-Vx V-Uy|z U Vx Uyx 规则不递归规则不递归 文法左递归文法左递归 例：例：A-aB|bB B-a|b 是否递归？描述的语言是什么？是否递归？描述的语言是什么？ aa,ab,ba,bb文法无递归性，描述的有穷语言文法无递归性，描述的有穷语言 若描述无穷语言，文法一定递归。若描述无穷语言，文法一定递归。 程序设计语言是无穷集合，描述他们的文法一程序设计语言是无穷集合，描述他们的文法一 定递归。定递归。 第2章文法和语言 2.4 短语、直接短语和句柄 短语：设短语：设S S是文法的开始符，是文法的开始符，是句型是

32、句型( (即有即有S S * *），如果满足条件：），如果满足条件： S S * * A A ; ;A A + + 则称则称 是相对于非终结符是相对于非终结符A A的句型的句型的一个短语。的一个短语。 直接短语（简单短语）：如果满足条件：直接短语（简单短语）：如果满足条件： S S * * A A ; ;A A 则称则称 是句型是句型的一个直接短语。每个直接短语的一个直接短语。每个直接短语 都是某规则的右部。都是某规则的右部。 句柄：一个句型可能有多个直接短语，其中最左的句柄：一个句型可能有多个直接短语，其中最左的 直接短语称之为句柄。直接短语称之为句柄。 短语是相对于某个句型的（即句型的一部

33、分）短语是相对于某个句型的（即句型的一部分） 第2章文法和语言 2.4 短语、直接短语和句柄 例题：文法例题：文法GN1: N1N NND|D D0|1|2 分析句型分析句型ND的短语的短语 对文法，首先建立该句型的推导过程：对文法，首先建立该句型的推导过程： N1=N=ND 第2章文法和语言 2.4 短语、直接短语和句柄 N1=N=ND 从推导过程中，有从推导过程中，有 N1 * * N1 N1 + + ND 句型本身是（相对于 句型本身是（相对于S的）句型的）句型ND的的 短语短语 N1 + + N，但不存在 ，但不存在N1 + + N1D的推导 的推导 N不是该句型的一个短语不是该句型的

34、一个短语 所以句型所以句型ND的短语是自身的短语是自身 短语：设短语：设S是文法的开始符，是文法的开始符，是句型是句型(即有即有S *），如），如 果满足条件：果满足条件：S * A ; A + 则称则称 是相对于非终结符是相对于非终结符A的句型的句型的一个短语。的一个短语。 第2章文法和语言 例题：文法例题：文法GT: TT*F|F F FP|P P(T)|i 分析句型分析句型T*P(T*F)的短语、直接短语和的短语、直接短语和 句柄句柄 2.4 短语、直接短语和句柄 第2章文法和语言 2.5 语法树与文法的二义性 1.语法树语法树(推导树推导树Parse Tree) q 作用作用:直观地描

35、述上下文无关文法的句直观地描述上下文无关文法的句 型推导过程。型推导过程。给定文法给定文法G=(VG=(VN N,V,VT T, P,S), P,S)， 对于对于G G的任何句型都能构造与之关联的的任何句型都能构造与之关联的 语法树语法树 第2章文法和语言 2.5 语法树与文法的二义性 1.语法树语法树(推导树推导树Parse Tree) 构造方法：已知构造方法：已知G=(VG=(VN N,V,VT T,P,S),P,S) q每 个 节 点 都 有 一 个 标 记 ， 此 标 记 为每 个 节 点 都 有 一 个 标 记 ， 此 标 记 为 V=VNVT 中的一个符号中的一个符号 q树根节点是

36、文法的开始符树根节点是文法的开始符S q含分支节点的节点一定属于含分支节点的节点一定属于Vn q对规则对规则AA1A2A3.AK是文法的一条规是文法的一条规 则，则节点则，则节点A有有K个分支节点，其分支节个分支节点，其分支节 点分别为点分别为A1， ，A2，A3.AK 第2章文法和语言 1.语法树(推导树Parse Tree) q例：文法例：文法G：EE+T|TTTF|F F（E）|i 句型句型T+TF的推导过程与语法树的推导过程与语法树 E=E+T E=E+T=E+TF=T+TF =T+T=T+TF E ET+ TFT E ET+ T 从语法树中看不出句型中的符号被替代的顺序从语法树中看不

37、出句型中的符号被替代的顺序 从左到右读出叶子结点从左到右读出叶子结点 得到的符号得到的符号串串，为文法，为文法 的的句型。也把该语法树句型。也把该语法树 称为该句型的语法树。称为该句型的语法树。 FT 第2章文法和语言 例：文法例：文法G： E-E+T|E-T|T T-T*F|T/F|F F-(E)|i 句型句型(T+i)*i-F 最左（右）推导最左（右）推导 1.语法树(推导树Parse Tree) 第2章文法和语言 2.5 语法树与文法的二义性 2.子树与简单子树子树与简单子树 q 语法树的子树是由某一节点连同所有分语法树的子树是由某一节点连同所有分 支组成的部分支组成的部分 q 语法树的

38、简单子树是指只有单层（深度语法树的简单子树是指只有单层（深度 为为1）分支的子树。）分支的子树。 第2章文法和语言 3.子树与短语的关系 短语短语子树的末端节点形成的符号串子树的末端节点形成的符号串 是相对于子树根的短语是相对于子树根的短语 直接短语直接短语简单子树的末端节点形成简单子树的末端节点形成 的符号串是相对于简单子树根的直接短的符号串是相对于简单子树根的直接短 语语 句柄句柄最左简单子树的末端节点形成最左简单子树的末端节点形成 的符号串的符号串 第2章文法和语言 文法文法GT: TT*F|F F FP|PP(T)|i 分析句型分析句型T*P (T*F)的短语、直接短语和句柄的短语、直

39、接短语和句柄 句型句型T*P (T*F)的语法树：的语法树： T TF * ()T 五棵子树对应五个短语五棵子树对应五个短语 两层子树两层子树( (简单子树简单子树) )的末端结点构成直接短语的末端结点构成直接短语 两棵两层子树对应两个直接短语：两棵两层子树对应两个直接短语： P , T*F 位于最左边的两层子树的末端结点构成句柄：位于最左边的两层子树的末端结点构成句柄： P 3.子树与短语的关系 PF P TF * P, T*P (T*F),P (T*F), T*F,(T*F), 第2章文法和语言 重点回顾 产生式（规则）产生式（规则） 非终结符号非终结符号 终结符号终结符号 文法文法G(G

40、rammar)定义为四元组（定义为四元组（VN，VT，P， S） VN (Nonterminal)：非终结符集。非终结符集。 VT (Terminal)：终结符集。终结符集。是语言的句子中出现的是语言的句子中出现的 字符。所以，有字符。所以，有VNVT = P (Production)：产生式（规则）集合产生式（规则）集合 S： SVN，开始符号或识别符号，开始符号或识别符号 第2章文法和语言 重点回顾 推导与归约推导与归约 直接推导、直接归约直接推导、直接归约 推导和归约推导和归约 规范推导、规范归约规范推导、规范归约 句型、句子、语言的定义句型、句子、语言的定义 语法树语法树 子树与简单子

41、树子树与简单子树 第2章文法和语言 重点回顾 子树与短语的关系子树与短语的关系 短语短语子树的末端节点形成的符号串是相子树的末端节点形成的符号串是相 对于子树根的短语对于子树根的短语 直接短语直接短语简单子树的末端节点形成的符简单子树的末端节点形成的符 号串是相对于简单子树根的直接短语号串是相对于简单子树根的直接短语 句柄句柄最左简单子树的末端节点形成的符最左简单子树的末端节点形成的符 号串号串 第2章文法和语言 q短语与语法树短语与语法树 文法文法G：EE+T|T TTF|F F（E）|i 文法文法GE的句型的句型TF+i语法树：语法树： E ET+ T TF F i 五棵子树对应三个短语五

42、棵子树对应三个短语 两层子树两层子树( (简单子树简单子树) )的末端结点构成直接短语的末端结点构成直接短语 两棵两层子树对应两个直接短语：两棵两层子树对应两个直接短语： T TF F，i i 位于最左边的两层子树的末端结点构成句柄：位于最左边的两层子树的末端结点构成句柄： T TF F 3.子树与短语的关系 T F，i，T F+i 第2章文法和语言 E ET+ TFT E=E+T E ET+ TFT E=E+T 句型的左右推导应构造出同一棵语法树句型的左右推导应构造出同一棵语法树 4.文法的二义性(Ambiguity) 文法文法G：EE+T|T TTF|F F（E）|i =E+TF=T+TF

43、 =T+T=T+TF 第2章文法和语言 文法文法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+i i EE+ E EE i i E EE i EE+ i i 4.文法的二义性(Ambiguity) 第2章文法和语言 定义定义:如果一个文法存在某个句子对应两棵不同的语如果一个文法存在某个句子对应两棵不同的语 法树，则说这个文法是二义的。法树，则说这个文法是二义的。二义性文法存在某二义性文法存在某 个句子个句

44、子, ,它它有两个不同的最左（右）推导有两个不同的最左（右）推导 对于一个程序设计语言来说，希望它的文法是无二对于一个程序设计语言来说，希望它的文法是无二 义的，因为希望对它的每个语句的分析是唯一的。义的，因为希望对它的每个语句的分析是唯一的。 文法文法G1： EE+E | EE |（E） | i 文法文法G2： ET|E+T TF|TF F(E)| i 等价的无等价的无 二义文法二义文法 4.文法的二义性(Ambiguity) 第2章文法和语言 2.6 文法和语言的分类 通过对产生式施加不同的限制，乔姆斯基通过对产生式施加不同的限制，乔姆斯基 （ChomskyChomsky）将文法和语言分为

45、四种类型（）将文法和语言分为四种类型（0 0、 1 1、2 2、3 3型型）。）。 q0 0型文法型文法( (无限制文法无限制文法) )： 对任一产生式对任一产生式，都有都有(V(VN NVVT T) )* *且且 至少含有一个非终结符，至少含有一个非终结符， (V(VN NVVT T) )* * q0 0型文法描述的是型文法描述的是0 0型语言（无限制语言）型语言（无限制语言） 第2章文法和语言 2.6 文法和语言的分类 例：例：GS: S-0AB 1B-0 B-SA|01 A1-SB1 A0-S0B 第2章文法和语言 2.6 文法和语言的分类 1 1型文法型文法( (上下文有关上下文有关)

46、 )： 文法文法G G中每一条规则的形式为中每一条规则的形式为 A u，都都 有有、(V(VN NVVT T) )* *, ,AVAVN N ， u(V u(VN NVVT T) )+ +。 称称G G是是1 1型文法。型文法。 它表示当它表示当A的上文为的上文为 且下文为且下文为时可把时可把A替替 换成换成 ，因此称，因此称1型文法为上下文有关文法。型文法为上下文有关文法。 | A|?| u | 1 1型文法描述的是型文法描述的是1 1型语言（上下文有关语言）型语言（上下文有关语言） 第2章文法和语言 例例 文法文法GSGS： SaSBE SaSBE SaBESaBE aBabaBab bB

47、bb bBbb bEbe bEbe eEeeeEee 2.6 文法和语言的分类 第2章文法和语言 2.6 文法和语言的分类 q2 2型文法型文法( (上下文无关文法上下文无关文法) )： 它是它是1型文法的特例，对任一产生式型文法的特例，对任一产生式， 都有都有VN ， (VN VT)*，则则称称G G是是2 2型型 文法。文法。 q2 2型文法描述的是型文法描述的是2 2型语言（上下文无关语型语言（上下文无关语 言）言） 第2章文法和语言 例例 文法文法GS： SAB ABS|0 BSA|1 2型文法产生式的一般形式是型文法产生式的一般形式是: A ，它表示不它表示不 管管A的上下文如何都可

48、把的上下文如何都可把A替换成替换成 ，因此被称为，因此被称为 上下文无关文法。上下文无关文法。 通常程序设计语言的文法，可用通常程序设计语言的文法，可用2型文法来描述，型文法来描述， 因此我们重点研究因此我们重点研究2型文法。型文法。 2.6 文法和语言的分类 第2章文法和语言 2.6 文法和语言的分类 3 3型文法型文法( (正规文法正规文法) )： 它是它是2型文法的特例，型文法的特例，任一产生式任一产生式 的形式都为的形式都为 AaBAaB或或AaAa；（；（ABaABa或或 AaAa）其中其中A A ，BVBVN N ，aVaVT T。 3 3型文法描述的是型文法描述的是3 3型语言（

49、正规语言）。型语言（正规语言）。 在程序设计语言中，在程序设计语言中，3 3型文法通常用来描型文法通常用来描 述单词的结构。述单词的结构。 文法类别文法类别产生式形式产生式形式产生的语言产生的语言 说明说明 0型文法型文法 (短语文法短语文法) VV+ + , ,且至少含一个 且至少含一个 非终结符，非终结符，VV* * 0型语言型语言对产生式对产生式 基本无限基本无限 制制 1型文法型文法 (上下文有关文上下文有关文 法法) ，| |1型语言型语言 （上下文有（上下文有 关语言）关语言） 将将A替换替换 成成 时，必时，必 须考虑须考虑A 的上下文的上下文 2型文法型文法 (上下文无关文上下文无关文 法法) AA，AVAVN N ， VV* * 2型语言型语言 （上下文无（上下文无 关语言）关语言） 无需考虑无需考虑 A在上下在上下 文中的出文中的出 现情况现情况 3型文法型文法 (正规文法正规文法) AaB A