1.字母表
字母表∑是一个有穷符号集合,符号可以是: 字母 数字 标点符号等
常见的字母表有
二进制字母表 {0 ,1}
ASCII字符集
Unicode 字符集
2.字母表的运算
1. 字母表∑1和∑2的乘积
∑1∑2 = {ab | a ∈ ∑1, b ∈ ∑2 } {0 ,1} {a, b} = {0a, 0b, 1a, 1b}
2.字母表∑的n次幂
∑^0 = { ε } 表示空串 ∑^n = { ∑^n-1 ∑ } {0 ,1}^3 = {0, 1} {0, 1} {0, 1} ={000, 001, 010, 011, 100, 101, 110, 111}
3.字母表∑的正闭包
∑+ = ∑ ∪ ∑^2 ∪ ∑^3 ∪ ........ {a, b, c, d}+ = {a, b , c, d, aa, ab, ac, ad,..... aaa, aab, aac, aad, .....}
正闭包就是长度为正数的字符串的集合
4.字母表∑的克林闭包
∑* = ∑^0 ∪ ∑+ = ∑^0 + ∑^1 ∪ ∑^2 ∪ ∑^3 ∪.......
克林闭包是任意符号串(长度可以为零)构成的集合
3.串
设∑是一个字母表, 任意x∈ ∑*, 那么x称作∑上的一个串
串是字母表中符号的一个有穷序列
串s的长度,通常记作|s| 就是指s中符号的个数
空串就是长度为零的串
4.串上的运算
1.串的基本运算
如果x 和y是串,那么x 和 y的链接,就是把y追加到x的后边,记作xy
x = hello y = world xy = helloworld
任何串链接空串,结果都不变
设x,y,z是三个字符串,如果x = yz, 那么y是x的前缀,z是x的后缀
2.串s的幂运算
s^0 = ε s^n = s^n-1 s s^1 = s^0 s s = ε s s ^ 2 = s s s ^ 3 = s s s
例如:s = hello
则: s1 = hello
s ^ 2 = hellohello s ^ 3 = hellohellohello
5.文法定义–句子的构成规则
G = (Vt, Vn, P, S)
1.Vt表示 终结符集合 是文法定义语言的基本符号,也称作 token
例:
Vt = {apple, boy, eat, little}
2.Vn表示 非终结符集合 用来表示语法成分的符号, 也称作 语法变量
Vn = {<句子>, <名词短语>, <动词短语>...} Vt ∩ Vn = ∅ Vt ∪ Vn: 表示 文法符号集
3.p表示产生式集合
产生式描述了将终结符和非终结符组合成串的方法
一般形式 a -> b
读作 a 定义为b
a ∈ (Vt ∪ Vn)+ 且 a中至少包含一个非终结符 a也称为产生式的头或者左部
b ∈ (Vt ∪ Vn)* 称作产生式的体或者右部
4.s表示开始符号
开始符号表示的是该文法中最大的语法成分
例 : s = <句子>
5. 文法举例
G = ( Vt, Vn, P, E ) Vt = {id, +, *, (, ) } Vn = {E} P = { E -> E + E, E -> E * E, E -> (E), E -> id }
我们约定在不引起歧义的情况下,可以只写产生式:
G: E -> E + E, E -> E * E, E -> (E), E -> id
6.产生式简写
对于一组有相同左部的a产生式
a -> b1, a->b2 a->b3 a->b4
可以简写为
a -> b1 | b2 | b3 | b4
读作a定义为b1 或者b2 或者b3 或者b4
b1 b2 b3 b4为候选式
7.符号约定
下述符号是终结符
字母表中的排在前边的小写字母比如 a, b, c
运算符 ,比如 + - *
标点符号 逗号,括号
数字 0, 1, 2, … 9
粗体字符串 id if等
下述符号为非终结符
字母表中排在前面的大写字符 A, B, C
字母S 通常表示开始符号
小写斜体的名字 比如 expr stmt等
代表程序够早的大写字母 E(表达式) T(项) F(因子)
下述是文法符号
字母表中排在后边的大写字母 (X, Y, Z)
即可以表示终结符,又可以表示非终结符
下述是终结符号串
字母表中排在后边的小写字母(u, v, …z)表示终结符号串(包括空串)
下述是文法符号串
小写希腊字母 α β 等 表示 文法符号串 也包括空串
若无特殊说明,第一个产生式的左部就是开始符号
