第二章文法与语言

1、1第二章文法和语言第二章文法和语言2编译程序必须首先理解高级语言的结构！编译程序必须首先理解高级语言的结构！ 高级语言高级语言书写的程序书写的程序 编译程序编译程序出错信息出错信息低级语言程序低级语言程序3第二章第二章 文法和语言文法和语言2.1 语言的定义语言的定义2.2 形式化语言的基本概念形式化语言的基本概念2.3 文法的定义、分类和构造文法的定义、分类和构造2.4 文法的二义性文法的二义性2.5 语言的形式化定义语言的形式化定义2.6 语言的分类语言的分类42.1语言的定义n语言特征语言特征自然语言自然语言( (Natural Language)Natural Language)是人与

2、人的交流工具是人与人的交流工具不同的语言有不同的语法不同的语言有不同的语法语义语义( (semantics):semantics):环境、背景知识、语气、环境、背景知识、语气、二义性二义性难以形式化难以形式化计算机语言计算机语言( (Computer Language)Computer Language)计算机系统间、人机间通讯工具计算机系统间、人机间通讯工具严格的语法严格的语法( (Grammar)Grammar)、语义语义( (semantics) semantics) 易于形式化易于形式化5n常用的高级语言常用的高级语言 FORTRAN 数值计算数值计算 COBOL事务处理事务处理 PA

3、SCAL基于过程的程序设计基于过程的程序设计 ADA大型程序、嵌入式实时系统大型程序、嵌入式实时系统 ALGOL描述算法的语言描述算法的语言 C/C+系统程序设计系统程序设计 JavaInternet程序设计程序设计 Swift OS X和和IOS的应用程序的应用程序6n与机器语言或汇编语言比较与机器语言或汇编语言比较，高级语言高级语言的优点：的优点： 较接近于自然语言和数学语言较接近于自然语言和数学语言，比较直观、比较直观、自然和易于理解自然和易于理解; 便于验证其正确性便于验证其正确性，易于改错易于改错; 编写效率高编写效率高; 易于移植易于移植.7程序的基本结构程序的基本结构n程序程序=

4、 数据结构数据结构+算法算法n软件软件 = 程序程序+配套文档配套文档语言语言对数据的运算对数据的运算描述数据描述数据8 高级程序语言的组成高级程序语言的组成 语法：由一组规则组成，形成一个符合语法规语法：由一组规则组成，形成一个符合语法规范的程序。规则包括两部分，一部分叫范的程序。规则包括两部分，一部分叫词法规词法规则则，一部分叫，一部分叫语法规则（狭义）语法规则（狭义） 语义：由一组规则组成，定义一个程序的意义语义：由一组规则组成，定义一个程序的意义9 语法语法n词法规则词法规则：单词符号单词符号的形成规则的形成规则。单词符号是语言中具有独立意义的最基本结构单词符号是语言中具有独立意义的最

5、基本结构。包括：常量、标识符、关键字、运算符、分隔符等。包括：常量、标识符、关键字、运算符、分隔符等。（C C语言标识符的词法规则是？）语言标识符的词法规则是？）n语法规则语法规则：语法单位语法单位的形成规则的形成规则。语法单位通常包括：表达式、语句、函数、程序等。语法单位通常包括：表达式、语句、函数、程序等。Conclusion:n语法规则和词法规则定义了程序的的语法规则和词法规则定义了程序的的形式结构形式结构，是判断，是判断输入字符串是否构成一个输入字符串是否构成一个形式上正确形式上正确程序的依据。程序的依据。n定义语法单位的意义属于语义问题。定义语法单位的意义属于语义问题。10语义语义n

6、语义：一组规则语义：一组规则，定义一个程序的意义定义一个程序的意义。n目前，没有一种公认的语义形式系统，借助它目前，没有一种公认的语义形式系统，借助它可以自动的构造出实用的编译程序可以自动的构造出实用的编译程序n目前大多数的编译程序采用的目前大多数的编译程序采用的“基于属性文法基于属性文法的语法制导翻译方法的语法制导翻译方法”，但还不是一种，但还不是一种完全的完全的形式系统形式系统，只是，只是半形式化半形式化的描述。的描述。11形式语言的产生背景：形式语言的产生背景：n语言学家语言学家ChomskyChomsky最初从最初从语言产生语言产生的角度研究语言。的角度研究语言。19561956年，通

7、过抽象，他年，通过抽象，他1 1）将语言形式地定义为是）将语言形式地定义为是由一个字母表中的字母由一个字母表中的字母组成的一些串的集合组成的一些串的集合。2 2）在字母表上按照一定的规则定义一个）在字母表上按照一定的规则定义一个文法文法（Grammar）3 3）该文法所能产生的所有句子组成的集合就是该）该文法所能产生的所有句子组成的集合就是该文法产生的文法产生的语言语言。1.2 形式语言的定义12形式语言的产生背景：形式语言的产生背景：n克林（克林（KleeneKleene）在）在19511951年到年到19561956年间，从年间，从识别语言识别语言的的角度研究语言，给出了语言的另一种描述。

8、角度研究语言，给出了语言的另一种描述。克林是在研究生物的神经细胞中，建立了克林是在研究生物的神经细胞中，建立了自动机自动机模型，模型，他用这种模型来识别语言：他用这种模型来识别语言：1 1）按照一定的规则可以构造一个自动机，该自）按照一定的规则可以构造一个自动机，该自 动机就对应了一个语言动机就对应了一个语言2 2）这个语言由该自动机所能识别的所有句子组成。）这个语言由该自动机所能识别的所有句子组成。1.2 形式语言的定义13n19591959年，年，ChomskyChomsky通过深入研究，将他本人的研究成通过深入研究，将他本人的研究成果与克林的研究成果结合了起来，果与克林的研究成果结合了起

9、来，不仅确定了文法不仅确定了文法和自动机分别从生成和识别的角度去表达语言，而和自动机分别从生成和识别的角度去表达语言，而且证明了文法与自动机的等价性。且证明了文法与自动机的等价性。 形式语言的产生背景（续）14n2020世纪世纪5050年代，用巴科斯范式年代，用巴科斯范式（Backus Nour Form 或或 Backus Normal Form，简记为，简记为BNF）成功地对高成功地对高级语言级语言ALGOL-60ALGOL-60进行了描述，这一成功使得形式语进行了描述，这一成功使得形式语言在言在2020世纪世纪6060年代得到了大力的发展。年代得到了大力的发展。n巴科斯范式就是上下文无关

10、文法巴科斯范式就是上下文无关文法（Context Free Grammar）的一种表示形式。的一种表示形式。形式语言的产生背景（续）15n计算思维的培养计算思维的培养 n连续数学连续数学、离散数学离散数学、计算模型计算模型等三部分内等三部分内容按阶段对应大学学习期间的思维方式和能容按阶段对应大学学习期间的思维方式和能力的变化与提高过程的三个步骤力的变化与提高过程的三个步骤形式语言的意义16计算思维能力的培养过程计算思维能力的培养过程 中学数学中学数学高等数学高等数学 离散数学离散数学 具体具体. .静止静止变量变量. .运动运动离散离散. .抽象抽象 形式形式. .模型模型 ( (基本运算系统

11、基本运算系统) ) ( (计算系统计算系统) ) 实实 数数 抽象抽象 集合集合 单一、具体的计算单一、具体的计算 一般、形式化的计算一般、形式化的计算 （实例计算）（实例计算） （模型化计算）（模型化计算） 形式语言与形式语言与自动机理论自动机理论运算运算范围范围特征特征高水平计算专业人才的计算思维能力的渐进培养高水平计算专业人才的计算思维能力的渐进培养17n字母表字母表n单个符号串单个符号串n符号串集合符号串集合n语言语言1.3 形式语言的专有名词18n字母表字母表（Alphabet）是一个是一个非空有穷非空有穷集合，集合，字母表中的元素称为该字母表的一个字母字母表中的元素称为该字母表的一

12、个字母（Letter），），也叫字符或符号（也叫字符或符号（Character）。）。n例例 以下是不同的字母表：以下是不同的字母表：na，b，c，dna，b，c，zn0，1nASCII码字母表码字母表nC语言字母表语言字母表=字母，数字，其他符号字母，数字，其他符号字母表字母表19a，b ，aa，bb符号串符号串20符号串的运算符号串的运算2122符号串集合的运算符号串集合的运算2324 0,1+ = 0，1，00，01，10，11，000，001，010，011，100， a，b，c，d+ = a，b，c，d，aa，ab，ac，ad，ba，bb，bc，bd，aaa，aab，aac，aad，

13、aba，abb，abc25 0,1 * = ，0，1，00，01，10，11，000，001，010， 011，100， a，b，c，d * = ，a，b，c，d，aa，ab，ac，ad， ba，bb，bc，bd，aaa，aab，aac，aad，aba，abb，abc， 26形式语言理论认为语言是字符串的集合形式语言理论认为语言是字符串的集合设设是一个字母表，是一个字母表， L *（闭包），（闭包），L称为称为字母表字母表上的一个上的一个语言语言（Language） xL x叫做叫做L的一个的一个句子句子。例：例： 字母表字母表0，1上的语言上的语言0，100，110，1，00，110，1，0

14、0，11，01，1000，11*01，10*27如何实现语言的形式化描述？如何实现语言的形式化描述？ - -文法文法28n文法的定义文法的定义n产生式规则产生式规则n语法树的构造语法树的构造n文法的构造文法的构造n文法的分类文法的分类1.4 文法29 1 1）考虑一个英文句子考虑一个英文句子文法要素的提取文法要素的提取分析分析：The grey wolf will eat the goat谓语谓语主语主语形容词形容词名词名词动词动词直接宾语直接宾语助动词助动词句子句子动原动原冠词冠词名词名词The grey wolf will eat the goat冠词冠词30 句子句子 主语主语 谓语谓语

15、 主语主语 冠词冠词 形容词形容词名词名词 冠词冠词the the 形容词形容词 greygrey 谓语谓语 动词动词 直接宾语直接宾语 动词动词 助动词助动词 动词原动词原形形 助动词助动词will will 动词原动词原形形 eat eat 直接宾语直接宾语 冠词冠词 名词名词 名词名词wolf wolf 名词名词goatgoat英语句子的组成规则英语句子的组成规则31终结符号集终结符号集VT = the，grey,wolf,will, eat, goat非终结符号集非终结符号集VN = 句子句子 ， 主语主语 , 谓语谓语 , 冠词冠词 ， 形容词形容词 , 名词名词 , 动词动词 ,

16、直接宾语直接宾语 , 助动词助动词 , 动词原动词原形形 语法规则集语法规则集P = 句子句子 主语主语 谓语谓语 ， 开始符号开始符号S = 句子句子 问题：有了语法，如何判定某一句子是否属于某问题：有了语法，如何判定某一句子是否属于某语言？语言？引入四个符号描述语法引入四个符号描述语法32 句子句子 主语主语 谓语谓语 冠词冠词 形容词形容词 名词名词 谓语谓语 the 形容词形容词 名词名词 谓语谓语 the grey 名词名词 谓语谓语 the grey wolf 谓语谓语 the grey wolf 动词动词 直接宾语直接宾语 . the grey wolf will eat the

17、 goat根据规则：根据规则：推导推导句子句子- -从产生语言的角度从产生语言的角度33 1）the grey wolf will eat the cat 2）the wolf will eat the goat 3）the grey goat will eat the wolf 4）the grey goat will eat the grey wolf下面句子下面句子1 1）是否符合该语法？）是否符合该语法？ 2 2）是否符合语义？）是否符合语义？34既符合语法又符合语义的句子是：既符合语法又符合语义的句子是： the grey wolf will eat the goat352）汉语的产

18、生式规则可以定义如下：）汉语的产生式规则可以定义如下：句子句子 =主语主语谓语谓语主语主语 =代词代词名词名词代词代词 =我我你你他他名词名词 =教师教师大学生大学生医生医生工人工人谓语谓语 =动词动词直接宾语直接宾语动词动词 =是是学习学习劳动劳动直接宾语直接宾语 =代词代词名词名词 判断判断“我是大学生我是大学生”这个句子是否满足汉这个句子是否满足汉语的语法？语的语法？36句子：句子：“我是大学生我是大学生”的的推导推导过程是：过程是：句子句子 主语主语谓语谓语 代词代词谓语谓语 我我谓语谓语 我我动词动词直接宾语直接宾语 我是我是直接宾语直接宾语 我是我是名词名词 我是大学生我是大学生

19、“我是大学生我是大学生” 构成符合上述规则。构成符合上述规则。“我大学生是我大学生是”不符合上述规则。不符合上述规则。（无法根据规则推导）（无法根据规则推导）373）C语言变量说明举例：语言变量说明举例：Grammar: 1. :=2. :=int3. :=float4. :=char5. :=a6. :=b7. :=c8. :=d38考察如何应用文法来生成句子考察如何应用文法来生成句子 推导推导 = (规则规则1) = int (规则规则2) = int a (规则规则5) 推导推导 = (规则规则1) = float (规则规则3) = float c (规则规则7) 两个变量说明：两个变

20、量说明： int a； float c； 符合符合C语言语言【变量说明变量说明】的语法规则。的语法规则。39文法文法G为一个四元组为一个四元组: = (T，N，)nT：终结符终结符(Terminal)集集nN：非终结符非终结符(Variable)集，集，TN= 语法成分语法成分代表某个语言的各种子结构代表某个语言的各种子结构n：开始符号：开始符号(Start Symbol)，SN 代表文法所定义的语言，代表文法所定义的语言，至少至少在产生式左侧在产生式左侧出现一次出现一次文法文法G G的形式定义的形式定义40：产生式：产生式(Product)集合集合产生式：产生式：（或者表示成（或者表示成 :

21、=） 产生式含义：产生式含义：定义定义为为(或者或者表示表示由由组成组成)。(TN)+，且且中至少有一个元素属于中至少有一个元素属于N (TN)*称为产生式称为产生式的的左部左部(Left Part)称为产生式称为产生式的的右部右部(Right Part)Attention：文法的核心是产生式规则集合。：文法的核心是产生式规则集合。文法文法G G 的形式定义的形式定义( (续续) )41产生式规则举例（产生式规则举例（1）42产生式规则举例（产生式规则举例（2）434445例：字符串集合（语言）例：字符串集合（语言）abna|n1,构造其文法构造其文法 G1Z： ZaBa, Bb|bB 右递归

22、文法右递归文法 G2Z： ZaBa, Bb|Bb 左递归文法左递归文法4647推导推导 归约（互逆过程）归约（互逆过程）48推导推导 归约（互逆过程）归约（互逆过程）4950推导的例子推导的例子：1、文法的产生式规则如下：、文法的产生式规则如下： id + id * id ？51E E + E 规则（规则（1） id + E 规则（规则（4） id + E * E 规则（规则（2） id + id * E规则（规则（4） id + id * id规则（规则（4）该推导是最左推导还是最右推导该推导是最左推导还是最右推导?推导的例子：推导的例子：52id+id*id的不同推导的不同推导 EE+E|

23、E*E|(E)|id53 当符号串已没有非终结符号时，推导就必须终止。当符号串已没有非终结符号时，推导就必须终止。 该例子是最左推导还是最右推导？该例子是最左推导还是最右推导？例例2：GN： N ND | D D 0| 1| 2| 3| 4| 5| 6| 7| 8| 9N ND NDD ND9 N09 D09 109 (6) (1) (3)(4) (2)(5) 推导的例子（续）推导的例子（续） ：54S S u uS S u u+ +S S u u+ +55设设GS是给定文法是给定文法, xuyV+为该文法的句型为该文法的句型 如果满足下面两个条件如果满足下面两个条件: S xUy； U u；

24、 则称句型则称句型xuy 中的子串中的子串u是句型是句型xuy的短语。的短语。*56 给定文法给定文法GS, w=xuyV+ 是该文法的句型是该文法的句型, 若若 S xUy, 且且U u, 则则u是句型是句型w相对于相对于U的直接短语。的直接短语。 其中其中U VN，u V+，x,y V* 任一句型的任一句型的最左直接短语最左直接短语称为该句型的称为该句型的句柄句柄。57 给定句型找句柄的步骤：给定句型找句柄的步骤： 短语短语 直接短语直接短语 句柄句柄注意：注意：短语、直接短语是相对于某一个句型而言短语、直接短语是相对于某一个句型而言 一个句型可能有多个短语、直接短语，一个句型可能有多个短

25、语、直接短语， 只有一个句柄只有一个句柄58 句 子 主语 系词 定语 名词 Physics 冠词 the 前置词 of are They 连接词 and 名词 students 名词 teachers 名词 Department. 表语 代词 59语法分析树表示句子语法分析树表示句子结构结构 (文法文法EE+E|E*E|(E)|id ）60如何根据推导过程生成语法树？如何根据推导过程生成语法树？句型推导过程句型推导过程 句型语法树的生长过程句型语法树的生长过程 由推导构造语法树由推导构造语法树1从从开始符号开始符号开始，建立开始，建立推导序列推导序列。由由根结点根结点开始，开始，自上而下自上

26、而下建立建立语法树语法树。61规范推导规范推导R R 0R0 0R110R62 由语法树构造归约由语法树构造归约2自下而上自下而上地修剪子树的末端结点，直至把整棵地修剪子树的末端结点，直至把整棵树剪掉（留根），每剪一次对应一次归约。树剪掉（留根），每剪一次对应一次归约。 从句型开始，逐步进行从句型开始，逐步进行归约归约，建立，建立归约归约序列。序列。63规范归约与规范推导互为逆过程规范归约与规范推导互为逆过程01R R 0R 0R10R64通过规范推导或规范归约所得到的句型是通过规范推导或规范归约所得到的句型是规范句型规范句型。不是规范推导不是规范推导在上例中，在上例中， 就不是规范句型，因为

27、：就不是规范句型，因为： RR656667例：例：给定文法给定文法G： ET | E+T | ET TF | T*F | TF Fi | (E) 符号串（符号串（T+i）*iF F是文法是文法G G的一个句型，求其短语、直接短语和句柄。的一个句型，求其短语、直接短语和句柄。E ET TT TF T*FF F*FF (E) *FF (T +T) *FF (T +F) *FF (T +i) *FF (T +i) *iF (T +i) *iF解：短语有解：短语有8个：个：1. E E，E（T+i）*iF 则有：则有：（T+i）*iF2. E TF，T（T+i）*i 则有：则有：（T+i）*i3. E

28、 T *iF，T（T+i） 则有：则有：（T+i）4. E (E) *iF，ET+i 则有：则有： T+i5. E (E +i) *iF，ET 则有：则有： T6. E (T +F) *iF，Fi 则有：则有： 第一个第一个i7. E (T +i) *FF，Fi 则有：则有： 第二个第二个i8. E (T +i) *FT，TF 则有：则有： F*+*+*+*+*+*+*+*+定义定义: 给定文法给定文法GZ, w=xuyV+，为该文法的句型，为该文法的句型, 若若 ZxUy, 且且U u, 则则u是句型是句型w相对于相对于U的短语；的短语； 若若 ZxUy, 且且U u, 则则u是句型是句型w

29、相对于相对于U的直接短语。的直接短语。 其中其中U VN，u V+，x,y V*68其直接短语有其直接短语有4个：个：1. E (E +i) *iF,EF,ET 则有：则有： T2. E (T +F) *iF,FF,Fi 则有：则有： 第一个第一个i i3. E (T +i) *FF,FF,Fi 则有：则有： 第二个第二个i i4. E (T +i) *FT T,T,TF 则有：则有：F F句柄有句柄有1 1个：个： T TEETT TT* *FF F(E E)F Fi iE+ +TT TF Fi i用语法树求用语法树求短语、直接短语和句柄短语、直接短语和句柄的方法：的方法：1）每个句型都有一

30、棵语法树；）每个句型都有一棵语法树；2）每棵语法树的叶（从左到右）组成一句型；）每棵语法树的叶（从左到右）组成一句型；3）每个子树）每个子树 的叶（从左到右）组成一短语；的叶（从左到右）组成一短语；4）每个简单子树）每个简单子树 的叶（从左到右）组成一直接短语；的叶（从左到右）组成一直接短语；5）最左简单子树）最左简单子树 的叶（从左到右）组成一句柄。的叶（从左到右）组成一句柄。只需画出句型的语法树，然后根据子树找短语只需画出句型的语法树，然后根据子树找短语直接短语直接短语句柄。句柄。69文法的二义性（双关）文法的二义性（双关）70 EE+E a+E a+E*E a+a*E a+a*a E E

31、*EE+E*E a+E*Ea+a*E a+a*aEE+EE*EaaaEE*E+EEaaa最左推导最左推导71 EE+E E+E*E E+E*a E+a*a a+a*a E E*EE*a E+E*aE+a*a a+a*aEE+EE*EaaaEE*E+EEaaa最右推导最右推导72同一个句子有两棵语法分析树同一个句子有两棵语法分析树731)高级程序设计语言存在无二义性文法高级程序设计语言存在无二义性文法对于条件语句，经常使用二义性文法描述它：对于条件语句，经常使用二义性文法描述它：S if expr then S if expr then S else S other该语法是二义性文法，该语法是二

32、义性文法，why? 因为存在二义性的句子因为存在二义性的句子: if e1 then if e2 then s1 else s2 文法二义性的几点说明文法二义性的几点说明74该句子对应两棵语法树（最左推导）该句子对应两棵语法树（最左推导）Sife1thenSife2thens1elses2Sife1thenSife2thens1elseS2即可理解为：即可理解为：if e1 then if e1 then （if e2 then s1 else s2if e2 then s1 else s2） 可理解为：可理解为：if e1 then if e1 then （if e2 then s1if e

33、2 then s1） else s2else s2因此该文法是二义性文法。因此该文法是二义性文法。75 Smatched_s unmatched_s matched_s if expr then matched_s else matched_s other unmatched_s if expr then S if expr then matched_s else unmatched_s 无二义性的文法无二义性的文法比较复杂，比较复杂，因此很多时候，因此很多时候，使用使用二二义性文法义性文法。等价转换的无二义性等价转换的无二义性if-else文法的产生式文法的产生式76文法二义性的判定：文法二

34、义性的判定：1 1）有些文法是非二义性，比如）有些文法是非二义性，比如LLLL（1 1）文法、）文法、LRLR文法、文法、算符优先文法，而且这些文法都是可以判定的，算符优先文法，而且这些文法都是可以判定的，所以只所以只要我们能够证明文法是属于上述某类文法，则该文法必要我们能够证明文法是属于上述某类文法，则该文法必然是非二义性的然是非二义性的；2 2）如果一个文法既有）如果一个文法既有左递归左递归，又有，又有右递归右递归的非终结符号的非终结符号A A，则文法必然是二义性的。，则文法必然是二义性的。3 3）现在的解决办法是：提出一些现在的解决办法是：提出一些限制条件限制条件，称为无二义，称为无二义

35、性的充分条件，当文法满足这些条件时，就可以判定文性的充分条件，当文法满足这些条件时，就可以判定文法是无二义性的。法是无二义性的。 Attention：不存在一种算法，能在有限的步骤内确切的判断一个文不存在一种算法，能在有限的步骤内确切的判断一个文法是否是二义性的。法是否是二义性的。77文法二义性与语言的二义性关系：文法二义性与语言的二义性关系： 如果一个二义性的文法，我们可以把它如果一个二义性的文法，我们可以把它等价变换等价变换成另成另外一个无二义性的文法，那么我们可以认为该二义性文外一个无二义性的文法，那么我们可以认为该二义性文法对应的语言中，某些句子的二义性完全是二义性文法法对应的语言中，

36、某些句子的二义性完全是二义性文法所带来的，而所带来的，而语言本身是非二义性语言本身是非二义性的。的。文法二义性文法二义性 语言二义性语言二义性二义性的语言：不存在非二义性的文法的语言。二义性的语言：不存在非二义性的文法的语言。78文法的分类文法的分类7980含义：只有在含义：只有在x、y这样的上下文环境下才能把这样的上下文环境下才能把U改写为改写为u81即把即把U改写为改写为u时，不必考虑上下文（用于语法分析）时，不必考虑上下文（用于语法分析）8283四种文法四种文法HierarchyAliasProduction formAutomation name 0-typeGrammar witho

37、ut limitation, V Turing Machine1-typeContext-sensitive grammarA , A VNLinear Bound Automation2-typeContext-free grammarA, A VNPushdown automation3-typeRegular grammar A B， A , A，BVN，VT*Finite automation84 四种文法之间的逐级四种文法之间的逐级“包含包含”关系如下：关系如下：2型文法型文法1型文法型文法0型文法型文法3型文法型文法文法对应语言的包含关系文法对应语言的包含关系 L0 L1 L2 L

38、3 0型文法可以产生型文法可以产生L0、L1、L2、L3，但，但2型文法只能产型文法只能产生生L2、L3，不能产生，不能产生L1。85Chomsky体系总结 = ( = (T T，N N，) )是一个文法是一个文法, , P P* * G G是是0 0型文法，型文法，L(G)L(G)是是0 0型语言；型语言； - -其能力相当于图灵机其能力相当于图灵机* * | |:G|:G是是1 1型文法，型文法，L(G)L(G)是是1 1型语言型语言( (除除);); - -其识别系统是线性界限自动机其识别系统是线性界限自动机* * N N : G : G是是2 2型文法，型文法，L(G)L(G)是是2

39、2型语言型语言; ; - -其识别系统是不确定的下推自动机其识别系统是不确定的下推自动机* * AaBAaB或或Aa: Aa: G G是右线性文法，是右线性文法， L(G)L(G)是是3 3型语言型语言ABaABa或或AA: : G G是左线性文法，是左线性文法，L(G)L(G)是是3 3型语言型语言 - -其识别系统是有限自动机其识别系统是有限自动机8687有害规则：造成二义性有害规则：造成二义性 例如存在例如存在U:=U， U:= a | b,则有两棵语法树：则有两棵语法树：UaUUa88多余规则：无用产生式与无用符号多余规则：无用产生式与无用符号E T | E + T | E TT F

40、| T * F | T / FF ( E ) | idE E | H + TT FH | TQ+PF | EQFM ( E ) | id无用符号：无用符号： 1)H、Q、P派生不出终极符号派生不出终极符号 2)从开始符号无法派生出来从开始符号无法派生出来M8990L(G1)=ai(a|b)|i=0 Example：LetG2(S,a,b,P,S) Where P includes: (0) S aSb (1) S abL(G2)=anbn|n=1Example：Let G1(S,a,b,P,S)Where P includes: (0) S aS (1) S a (2) S b文法文法 语言语

41、言91n明确描述对象明确描述对象语言语言合法的语言结构合法的语言结构n确定基本符号集确定基本符号集T Tn引入非终结符引入非终结符n n各种语法成分各种语法成分n定义句子的组成规则定义句子的组成规则BNFBNF范式或产生式范式或产生式语言语言 文法文法 ：文法的构造文法的构造92文法构造举例文法构造举例n基本结构基本结构a an n的构造的构造 1) n=0 SaS| 2) n=1 SaS|a93文法构造举例文法构造举例nx|x是长度为偶数的是长度为偶数的0、1串串 S00S|01S|10S|11S|nanbn |n1 SaSb|ab 什么文法？什么文法？nambn |m,n1 1) SAB

42、AaA|a BbB|b 2) SaS SaB BbB|b 如果改为如果改为m,n0 m,n0 习题习题2.62.694Constructing a grammar from a languageExample1：Let L1=a2nbn|n=1 and a,b VTTry to construct the grammar G1 from L1 Let n=1， L1 =aab n=2， L1 =aaaabb n=3， L1 =aaaaaabbb So we have：S aaSb S aab95Constructing a grammar from a languageExample 2：Le

43、t L2=aibjck | i,j,k=1 and a,b,c VT Try to construct the grammar G2 from L2 S aS S aB B bB B bC C cC | c 如果如果i=j, 如何构造文法？如何构造文法？ S AB A aAb|ab B cB | c96如果如果i=j=k,i=j=k,如何构造文法？如何构造文法？构造语言构造语言L=aL=an nb bn nc cn n|n0|n0的文法的文法SaBC|aSBCCBBCaBabbBbbbCbc Q: 这是什么文法？这是什么文法？97Constructing a grammar from a la

44、nguageExample 3：Let L3= | (a,b)* and there are as many as as bs in Try to construct the grammar G3 from L3 S S bB， S aA A bS|b ，A aAA B aS | a | bBBS S aSbSS bSaS 98Constructing a grammar from a languageExample 4：Let L4= | (0,1)* and the number of 1 appeared in is even Try to construct the grammar G4 from L4 Grammar: S S 0S， S 1A A 0A , A 1S99用文法用文法G1来定义下面的集合：来定义下面的集合：L1=n|n是非负整数是非负整数解题思路：显而易见，该集合不能用枚举法来定义。解题思路：显而易见