编译原理第2章.ppt

一、字母表
是符号的非空有穷集合,通常用、V或其它大写字母表示
二、符号
是语言中最基本的、不可再分的单位
三、符号串
是字母表中符号组成的有穷序列。
注:空串是不含任何符号的串,记作。
第二章编译基础知识
第一节字母表与符号串
四、句子
是字母表上符合某种规则构成的串
五、语言
是字母上句子的集合。

注:约定用a,b,c,…表示符号;用,,,…表示符号串;用A,B,C,…表示其集合。
六、符号串集合的运算
1、连结(乘积)运算
设串集A={1, 2,…},B={1, 2,...},
则乘积AB定义为AB={|A 且B}
注:1)串集的自身乘积称作串集的方幂
2)A0={}
3)字母表A的n次方幂是字母表A上所有长度为n的串集
2、闭包与正闭包
1)闭包
A*=A0A1A2…
其含义是由A上符号组成的所有串的集合(包括空串)
2)正闭包
A+=A1A2…=A*-{}
注:字母表上语言是字母表上正闭包的子集。
第二节文法与语言
一、基本概念
1、文法
文法是一组描述语言的语法结构的规则集合。
2、产生式
是用来定义符号串之间关系的一组(语法)规则。
形式:A—>(A产生)
3、非终结符
出现在规则的左部、可以继续分解的部分。
非终结符集合用VN表示。
4、终结符
语言中不可以分解的部分
终结符集合用VT表示。
5、开始符号
表示文法所定义的语法范畴的非终结符,它是文法所描述的对象,通常出现在第一个产生式的左部。
注:开始符号又称为识别符号。
6、推导
推导是从文法开始符号出发,采用产生式的右部取代左部,最终到达一个句子的过程。
最左(右)推导:每次使用一个规则,以其右部取代符号串的最左(右)非终结符。
注:最左推导和最右推导称为规范推导
7、归约
归约是推导的逆过程,即,从给定的源语言的句子开始,通过产生式的左部取代右部,最终达到文法开始符号的过程。
最左(右)归约是最右(左)推导的逆过程。
注:最左归约和最右归约称为规范归约。
8、句型、句子和语言
句型:
句型是从文法的开始符号S开始,每步推导(包括0步推导)所得到的字符串。
记作:S * ,其中( VN VT)*
句子:只含有终结符的句型。
语言:
语言是从文法开始符号S开始通过1步或1步以上的推导所得的句子的集合。
记为:L(G)。L(G)={|S + ,且 VT*}
9、文法规则的递归定义
非终结符的定义中包含了非终结符自身。
10、文法规则的扩充表示
使用扩充的BNF表示
( ) ——提因子
例: Uax|ay|az 改写为Ua(x|y|z)
{ } ——重复次数的指定
例:<标识符><字母>{<字母>|<数字>}
[ ] ——任选符号
例:<整数>[+|-]<数字>{<数字>}
11、元语言符号
用来说明文法符号之间关系的符号,如,“”和“|”称为元语言符号。
二、形式定义
1、文法定义
文法G定义为四元组:(VN,VT, P,S)
2、文法分类
根据对产生式施加的限制,可分为:0型文法、1型文法、2型文法、3型文法