第3章 文法和语法

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

1、第3章文法和语言教学要求：本章是编译原理课程的理论基础，要求理解文法、语言、规范推导、规范归约和短语、简单短语、句柄的基本概念；掌握语言的求解方法、文法的二义性的判断方法及句型的分析方法。教学重点：上下文无关文法，语言定义一、语言语言是由句子组成的集合，是由一组记号所构成的集合。汉语--所有符合汉语语法的句子的全体英语--所有符合英语语法的句子的全体程序设计语言--所有该语言的程序的全体“我是大学生”是否是该语言的句子？〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

2、〈名词〉〈代词〉::=你

3、我

4、他〈名词〉::=王明

5、大学生

6、工人

7、英语〈谓语〉::=〈动词

8、〉〈直接宾语〉〈动词〉::=是

9、学习〈直接宾语〉::=〈代词〉

10、〈名词〉二、文法一种语言描述工具，用来定义句子的结构，用有限的规则把语言的全部句子描述出来，是以有穷的集合刻划无穷的集合的工具。〈句子〉〈主语〉〈谓语〉〈代词〉〈谓语〉我〈谓语〉我〈动词〉〈直接宾语〉我是〈直接宾语〉我是〈名词〉我是大学生〈句子〉::=〈主语〉〈谓语〉〈主语〉::=〈代词〉

11、〈名词〉〈代词〉::=你

12、我

13、他〈名词〉::=王明

14、大学生

15、工人

16、英语〈谓语〉::=〈动词〉〈直接宾语〉〈动词〉::=是

17、学习〈直接宾语〉::=〈代词〉

18、〈名词〉三、符号和符号串1、字母表:它是非空

19、有穷集。例如：∑={a,b,c}或∑={1,2,3}2、符号：字母表中的元素称为符号。3、符号串：符号的有穷序列，符号串也称为字。用ε来表示空符号串。例如：a,ab,abc,dsfsd任何一种语言可看成是某个符号集上定义的，按一定规则构成的一切基本符号串组成的集合。4、长度：符号串的长度是指该串所包含的符号个数。用

20、x

21、表示符号串x的长度。例如：

22、a

23、=1，

24、abn

25、=35、连结：设x和y为符号串，则称xy为他们的连结。例如：x=aa,y=bb,则xy=aabb6、空集：不含任何元素的集合,记为。7、乘积：设A和B是符号串集，则用AB表示A和B的乘积。A={a

26、,b},B={c,d},则AB={ac,ad,bc,bd}8、方幂：符号串x自身连接n次得到的符号串xx…xx(n个x)定义为xnx0=ε,x1=x,x2=xx,x3=xxxx=AB,则x0=ε,x1=AB,x2=ABAB,x3=ABABAB对于n>0,xn=xxn-1=xn-1x使用*表示上的所有有穷长的串（包括ε）的集合。Σ*称为Σ的闭包。从*中除去ε得到的集合记为+。Σ+称为Σ的正闭包。Σ*=Σ0∪Σ1∪Σ2…∪Σn…Σ+=Σ1∪Σ2…∪Σn…Σ*=Σ0∪Σ+Σ+=ΣΣ*=Σ*ΣΣ+=Σ*-{ε}例：设Σ={0,1}，则Σ*={ε,0,1,00,0

27、1,10,11,000,001,010,…}例：设Σ={a,b}，则Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}Σ+={a,b,aa,ab,ba,bb,aaa,aab,…}四、文法和语言的形式定义1、文法的形式定义1）规则（重写规则、产生式或生成式）：是一个有序对（α，β）。记为α→β或α∷=β，其中α∈V+，β∈V*。α称为规则的左部(或生成式的左部)。β称为规则的右部(或生成式的右部)。2）文法G[S]：文法为四元组（VN，VT，P，S）VN：非终结符集VT：终结符集P：产生式（规则）集合S：开始符号（识别符号）VN、VT和P是非空有穷集

28、。S至少在一条规则中作为左部出现。VN∩VT=φ，S∈VNV=VN∪VT，称为文法G的字母表（字汇表）例3.1文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号例3.2文法G=（VN，VT，P，S）VN={标识符，字母，数字}VT={a,b,c,…x,y,z,0,1,…,9}P={<标识符>→<字母><标识符>→<标识符><字母><标识符>→<标识符><数字><字母>→a,…,<字母>→z<数字>→0,…,<数字>→9}S=<标识符>习惯上只将产生式写出。并有如下约定：第一条产生式的左部是开始符号用尖括号括起的是

29、非终结符，否则为终结符。或者大写字母表示非终结符，小写字母表示终结符G可写成G[S]，其中S是开始符号例3.1文法G=（VN，VT，P，S）VN={S},VT={0,1}P={S→0S1,S→01}S为开始符号可写成：G：S→0S1S→01或写成：G[S]：S→0S1S→01Mini_C介绍Mini_C语言是在C语言的基础上定义的一种语言（C语言的子集），它的文法定义如下：1<程序>::=MAIN()<语句块>2<语句块>::={<变量声明列表><语句串>}

30、{语句串}3<变量声明列表>::=<变量声明列表><变量声明>

31、<变量声明>4<变量声明>::=<变量类

32、型>;5<变量类