编译原理：文法和语言

《编译原理：文法和语言》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章文法和语言2.1文法的直观表示2.2符号和符号串2.3文法和语言的形式定义2.4文法的类型2.5上下文无关文法及语法树2.6句型分析2.7文法的实用限制1第2章文法和语言【学习目标】本章是为语言的语法描述寻求工具◇掌握对程序设计语言给出精确、无二义（严谨、易读）的语法描述的手段之一——文法。◇对形式语言的理论有一个初步基础◇根据文法的特点指导语法分析过程22.1文法的直观表示文法：阐明语法的一个工具，也可以说是以有穷的集合刻画无穷的集合的一个工具。语言：程序设计语言。一、语言概述语言是由符合语法的句子组成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合

2、英语语法的句子的全体程序设计语言--所有该语言的程序的全体每个句子构成的规律——语法研究语言每个句子的含义——语义每个句子和使用者的关系——语用3形式语言：只考虑语法而不考虑语义的符号语言。每种语言具有两个可识别的特性语言的形式与该形式相关联的意义“形式”指语言的所有规则，描述出现什么符号串语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。4表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述例：汉语句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主

3、语〉∷=〈代词〉

4、〈名词〉〈代词〉∷=我

5、你

6、他〈名词〉∷=王明

7、大学生

8、工人

9、英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是

10、学习〈直接宾语〉∷=〈代词〉

11、〈名词〉二、文法的直观概念5推导：“我是大学生”是汉语的一个句子〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生62.2符号与符号串一、相关概念程序设计语言是由程序构成的集合，程序是由基本符号按照一定的规则构成的集合。1.符号、字母表和符号串基本符号：可以相互区别的基本元素，如字母，数字，标点符号。字母表：基本符号的非空有穷集合，常用Σ

12、表示。例：Σ={0,1}，Σ={a,b,c,…,x,y,z}7符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。例如=｛0,1｝上的符号串0,1,00,01,11,10注意：表示空符号串,它表示不包含任何符号串，不是空格符。符号串集合：字母表上若干个符号串组成的集合.例：字母表={0,1}的符号串集合A={1,00,01};约定：小写字母a,b,…,r表示符号.小写字母s,t,…,z表示符号串;8符号串s的头（前缀）和尾（后缀）：如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。前缀

13、：移走符号串s尾部的零个或多个符号得到的串。如：设s=abc,那么s的前缀是ε，a，ab，abc后缀：移走符号串s头部的零个或多个符号得到的串。如：s=abc的后缀是ε，c，bc，abc，s的固有尾是ε，c，bc。9符号串s的子串：从s中删去任何前缀或后缀得到的串.如:bc是符号串abc的一个子串.对符号串s，s和ε两者都是符号串s的前缀、后缀和子串。符号串s的真前缀，真后缀，真子串：任何非空符号串x，是s的前缀，后缀或子串，并且sx102.符号串的运算(1)符号串相等：符号串x，y，如果两者诸符号依次相等，则两符号串相等。(2)符号串的长度：符号串中包含符号的个数。

14、

15、abc

16、=3；

17、

18、=0；(3)符号串的连结：x=abc，y=def则xy=abcdef；yx=defabc；xyyxx=x=x；11(4)符号串集合的乘积：设A、B为两个符号串集合，其乘积为AB={xy

19、xA，yB}；例：A={aa，bb}，B={cc，dd}，则AB={aacc，aadd，bbcc，bbdd}{}A=A{}=A；(5)空集：不含任何元素的集合称为空集。记为；对任何集合A：A=A=;注意：12(6)符号串的方幂：x是字母表上的符号串，则x的幂运算为：x0=;x1=x;x2=xx;…xn=xn-1x=xxn-1(n>0)xn

20、表示n个x相连结。eg：x=ok；则x0=;x1=ok;x2=okok;…(7)符号串集合的方幂：A为符号串集合，则A的幂运算为：A0={};A1=A;A2=AA;...An=An-1A=AAn-1;(n>0)A={aa，bb}，则A0={}；A1={aa，bb}；A2=AA={aaaa，aabb，bbaa，bbbb};...13(8)符号串集合的闭包和正闭包集合A的闭包表示为A*（亦称为自反闭包或星闭包）定义为：A*=A0A1A2A3…=Ak，k0正闭包表示为A+具体定义为A+=A1A2A3…=Ak，k1由定