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

《编译原理第二章文法和语言》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第二章文法和语言本章目的为语言的语法描述寻求工具,以便：对源程序给出精确无二义的语法描述。根据语言文法的特点来指导语法分析的过程。从描述语言的文法可以自动构造出可用的分析程序。本章讲述目前广泛使用的上下文无关文法。即用上下文无关文法作为程序设计语言语法的描述工具。阐明语法的一个工具是文法。文法和语言文法的直观概念符号和符号串文法和语言的形式定义文法的类型上下文无关文法及其语法树句型的分析1.向上而下的分析方法2.自下而上的分析方法有关文法实用中的一些说明文法的直观概念语言是由句子组成的集合，是由一组记号所构成的集合。

2、汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体每个句子构成的规律研究语言每个句子的含义每个句子和使用者的关系研究程序设计语言每个程序构成的规律每个程序的含义每个程序和使用者的关系语言研究的三个方面语法语义语用语法--表示构成语言句子的各个记号之间的组合规律。语义--表示按照各种表示方法所表示的各个记号的特定含义。（各个记号和记号所表示的对象之间的关系）语用--表示在各个记号所出现的行为中，它们的来源、使用和影响。如果不考虑语义和语用，即只从语法这一侧面来

3、看语言，这种意义下的语言称作形式语言。形式语言抽象地定义为一个数学系统。“形式”是指这样的事实：语言的所有规则只以什么符号串能出现的方式来陈述。形式语言理论是对符号串集合的表示法、结构及其特性的研究,是程序设计语言语法分析研究的基础。当我们表述一种语言时，无非是说明这种语言的句子，如果语言只含有有穷多个句子，则只需列出句子的有穷集就行了，但对于有无穷句子的语言来讲，存在着如何给出它的有穷表示的问题。以自然语言为例，人们无法列出全部句子，但是人们可以给出一些规则，用这些规则来说明（或者定义）句子的组成结构，比如：“我是

4、大学生”。是汉语的一个句子。汉语句子可以是由主语后随谓语而成，构成谓语的是动词和直接宾语，我们采用EBNF来表示这种句子的构成规则。〈句子〉∷＝〈主语〉〈谓语〉〈主语〉∷＝〈代词〉

5、〈名词〉〈代词〉∷＝我

6、你

7、他〈名词〉∷＝王明

8、大学生

9、工人

10、英语〈谓语〉∷＝〈动词〉〈直接宾语〉〈直接宾语〉∷＝〈代词〉

11、〈名词〉〈动词〉∷＝是

12、学习一旦有了一组规则以后，我们可以按照如下方式用它们去推导或产生句子。〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学

13、生按照上述办法，不仅生成“我是大学生”这样的句子，还可以生成“王明是大学生”，“王明学习英语”，“我学习英语”，“他学习英语”，“你是工人”，“你学习王明”等几十个句子。符号和符号串符号和符号串，在形式语言中和编译技术中是很重要的概念。任何一种语言，都是由许多语言的基本符号组成的符号串的集合。如：英语的基本符号有26个字母和一些标点符号，英语，就是由这些符号所组成的符号串的集合。符号：字母表中的元素称为符号字母表：符号（元素）的非空有穷集合符号串：由字母表中的符号组成的任何有穷序列称为该字母表上的符号串。例如：Σ

14、={a,b}ε,a,b,aa,ab,aabba…都是上的符号串Σ={0,1}ε,0,1,01,11,10,11110000…都是上的符号串符号串的递归定义：1.空符号串ε(没有符号的符号串)是上的符号串。2.若x是上的符号串,a是的元素,则xa是上的符号串。3.y是上的符号串,当且仅当它可以由1和2导出。符号串s的前缀：移走符号串s尾部的零个或多于零个符号得到的符号串。如：b是符号串banana的一个前缀。符号串s的后缀：删去符号串s头部的零个或多于零个符号得到的符号串。如:nana是符号串banana

15、的一个后缀。对于每个符号串s，s和ε两者都是符号串s的前缀，后缀和子串。符号串s的子串：从s中删去一个前缀和一个后缀得到的符号串。如：ana是符号串banana的一个子串。符号和符号串相等：X＝Y当且仅当组成X的诸符号与组成Y的诸符号依次相等，Σ＝{a，b，c}X＝abbcY＝abbcX＝YX＝abY＝baX≠Y符号串的运算：1.符号串的长度：符号串中符号的个数.符号串s的长度记为

16、s

17、。ε的长度为0。2.连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy。如x=ab,y=cd则xy=abcd有ε

18、a=aε3.幂：符号串自身连接n次得到的符号串。an定义为aa…aan个aa1=a,a2=aaa0=ε符号串集合：若集合A中所有元素都是某字母表上的符号串，则称A为字母表上的符号串集合。4.两个符号串集合A和B的乘积定义为AB=xy

19、xA且yB如：若集合A=ab,cdeB=0,1则AB=ab1,ab0,cde0,cde1