编译原理（二） 文法和语言
字母表和符号串
-
字母表Σ：符号（元素）的非空有穷集合
字符（符号）：可以相互区别的记号 -
符号串：由字母表Σ中的符号组成的任何有穷序列称为该字母表上的符号串
（1） 空符号串ε：没有符号的符号串
Σ={a，b}
ε,a,b,ab,aa,aabba…都是Σ上的符号串
（2）符号串S的头（前缀）：移走符号串S尾部的0个或多于0个符号得到的符号串。
如：b是符号串banana的一个前缀
符号串S的尾（后缀）：删去符号串S头部的0个或多于0个符号得到的符号串。
如：nana是符号串banana的一个后缀
（3）符号串S的字串：从s中删去一个前缀和一个后缀得到的符号串
如：nan是符号串banana的一个子串
对于每个字符串S，S和ε都是符号串S的前缀、后缀、字串。
- 符号串的运算
（1）符号串的长度：符号串中符号的个数，符号串的长度记为|S|，
ε的长度为0
（2） 连接：符号串x，y的连接是把y符号写在x的符号之后得到的符号串xy，
（3）方幂：符号串自身连接N次得到的符号串
（4）符号串的集合
两个符号串集合A和B的乘积定义为:
若集合A中所有元素都是某字母表E上的符号串， 则称A为字母表E 上的符号串集合。
AB ={xy |x∈A且y∈B}
若集合A={ab,cde} B = {0,1}, 则
AB={ ab1 , ab0, cde0 , cde1}
- 闭包:使用Σ^表示Σ上的一切符号串(包括 ε)组成的集合。Σ*称为Σ的闭包。
Σ上的除ε外的所有符号串组成的集合记为Σ^。Σ称为Z的正闭包。
文法和语言的形式定义
1.终结符:语言中不可再分的基本符号，通常是一个语言的字母表。如程序设计语言中的基本字、常数、运算符、分界符等。
2.非终结符: 它不像终结符代表了语法的最小元素，是一种个体记号，它是一个类、一个集合。一个非终结符代表了一定的语法概念。程序设计语言中常见的语法单位有“过程”、“赋值语句” 、“表达式”等。
3.开始符号:是一个特殊的非终结符。
4.产生式:构造某个语法时应满足的规则
语言是由句子组成的集合。是由一组符号所构成的集合。
语法数和文法的二义性
语法树的构造过程：
以文法开始符号 S为根结点随着推导的逐步展开，对句型中某个非终结符A用相应产生式A- a的右部替换时，为A的结点生成其子结点依次为a的子树，直至推导结束。
文法的二义性:
若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的。
或者， 若一个文法存在某个句子有两个不同的最左(右)推导，则称这个文法是二义的。