编译原理：文法和语言.ppt

第二章文法和语言第2章 文法和语言2.1文法的直观表示形式语言：只考虑语法而不考虑语义的符号语言。
每种语言具有两个可识别的特性
语言的形式
与该形式相关联的意义

“形式”指语言的所有规则，描述出现什么符号串
语言可以看成在一个基本符号集上定义的，按一定规则构成的基本符号串组成的所有集合。

形式语言理论是对符号串集合的表示法、结构及其特性的研究，是程序设计语言语法分析研究的基础。表达语言时，一般无法穷尽语言的所有句子，常用规则加以描述
例：汉语句子的构成规则：〈句子〉∷=〈主语〉〈谓语〉〈主语〉∷=〈代词〉|〈名词〉〈代词〉∷=我|你|他〈名词〉∷=王明|大学生|工人|英语〈谓语〉∷=〈动词〉〈直接宾语〉〈动词〉∷=是|学习〈直接宾语〉∷=〈代词〉|〈名词〉推导：“我是大学生”是汉语的一个句子〈句子〉〈主语〉〈谓语〉
〈代词〉〈谓语〉
我〈谓语〉
我〈动词〉〈直接宾语〉
我是〈直接宾语〉
我是〈名词〉
我是大学生
2.2符号与符号串符号串：由字母表中的符号构成的任何有穷序列称为符号串。符号串中的符号是有顺序的。符号串s的头（前缀）和尾（后缀）：
如果s=xy是一符号串，那么x是s的头，y是s的尾。若x是非空，则y是固有尾；若y非空，则x是固有头。
前缀：移走符号串s尾部的零个或多个符号得到的串。如：设s=abc,那么s的前缀是ε，a，ab，abc
后缀：移走符号串s头部的零个或多个符号得到的串。如：s=abc的后缀是ε，c，bc，abc，s的固有尾是ε，c，bc。
符号串s的子串：
从s中删去任何前缀或后缀得到的串.
如:bc是符号串abc的一个子串.
对符号串s，s和ε两者都是符号串s的前缀、后缀和子串。
符号串s的真前缀，真后缀，真子串：
任何非空符号串x，是s的前缀，后缀或子串，并且sx
2.符号串的运算

(1)符号串相等：
符号串x，y，如果两者诸符号依次相等，则两符号串相等。
(2)符号串的长度：符号串中包含符号的个数。
|abc|=3；||=0；
(3)符号串的连结：
x=abc，y=def则xy=abcdef；yx=defabc；
xyyx x=x=x；
(4)符号串集合的乘积：
设A、B为两个符号串集合，其乘积为AB={xy|xA，yB}；
例：A={aa，bb}，B={cc，dd}，则
AB={aacc，aadd，bbcc，bbdd}
{}A=A{}=A；
(5)空集：
不含任何元素的集合称为空集。记为；
对任何集合A：A=A=;注意：
(6)符号串的方幂：
x是字母表上的符号串，则x的幂运算为：
x0=;x1=x;x2=xx;…xn=xn-1x=xxn-1(n>0)
xn表示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};...(8)符号串集合的闭包和正闭包
集合A的闭包表示为A*（亦称为自反闭包或星闭包）定义为：
A*=A0A1A2A3…=Ak，k0
正闭包表示为A+具体定义为
A+=A1A2A3…=Ak，k1
由定义可以看到A*=A0A+
3、语言

(1)由一组符号所构成的集合。即：字母表上的每个语言是*的一个子集。
例如：字母表Σ={a,b}，Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
集合{ab,aabb,aaabbb,…,anbn,…} 或表示为{w|w∈Σ*且w=anbn,n≥1}为字母表上的一个语言。
集合{a,aa,aaa,…}或表示为{w|w∈Σ*，且w=an，n≥1}为字母表上的一个语言。
(2)ε是一个语言。
(3)即是一个语言。2.3文法和语言的形式定义一、规则（重写规则、产生式或生成式）二、文法的定义文法G习惯上只将规则写出。
如例1还可以写成：G：S→0S1S→01或G[S]：S→0S1S→01
或G[S]：S→0S1|S→01总结一个文法的几种写法
①G=({S,A}，{a,b}，P，S)其中P：S→aAbA→abA→aAbA→ε②G：S→aAbA→abA→aAbA→ε③G[S]：S→aAbA→abA→aAbA→ε④G[S]：S→aAbA→ab|aAb|ε三、推导的定义例3：G：S→0S1，S→01
0S100S11
00S11000S111
000S11100001111
S0S100S11000S11100001111
S0