编译原理

第一章文法

字母表(Alphabet)

字母表是形式符号的集合，常用Σ来表示

举例：英文字母表{a,b,c….,z,A,B,C,…,Z}、汉字表{编,译,原,理}
字符串(String)

由字母表Σ中的字符构成的有限序列。空串用ε来表示。

字符串STR的长度可以表示为|STR|，是包含在STR中字符的个数
字符串的连接

设x,y为字符串 x=abcd，y=uio。则可以推导出 xy=abcduio

运算性质： (xy)z=x(yz)、x=xε=εx、|xy|=|x|+|y|
字母表上的运算

Σ为字母表，则Σ的0次={ε}

*闭包 Σ* = Σº∪Σ¹∪Σ²∪Σ³∪………∪Σⁿ

+闭包 Σ+= Σ¹∪Σ²∪Σ³∪………∪Σⁿ
语言

设Σ为字母表，则任何集合L包含于Σ*是字母表Σ上的一个语言

例子：以下都用这个例子

E→EOE
E→(E)
E→v
E→d
O→+
O→*

🌈上下文无关文法的四个基本要素

🌈上下文无关文法的形式定义：表示为CFG

V N:非终结符的集合

V T:终结符的集合

P:产生式的集合

S:开始符号

以上例子的CFG表达式：不仅如此还可以缩写一下产生式

🌈归约与推导

用于推理字符串是否属于文法所定义的语言一种是自下而上的方法，称为递归推理（recursive inference），递归推理的过程习称为归约；另一种是自上而下的方法，称为推导（derivation）.
- 归约过程将产生式的右部（body）替换为产生式的左部（ head ）.
- 推导过程将产生式的左部（ head ）替换为产生式的右部（ body ）.

递归推理出字符串 v *(v＋d) 的一个推导过程为

递归推理出字符串 v *(v＋d) 的一个归约过程为

🌈最左推导

若推导过程的每一步总是替换出现在最左边的非终结符，则这样的推导称为最左推导. 为方便，最左推导关系用表示，其自反传递闭包用表示.如对于文法例子，以下是 v *(v＋d)的最左推导

🌈最右推导

若推导过程的每一步总是替换出现在最右边的非终结符，则这样的推导称为最右推导. 为方便，最右推导关系用表示，其自反传递闭包用表示.如对于文法例子，以下是 v *(v＋d)的最右推导

🌈句型

🌈语法分析树

对于 CFG G = (V N , V T , P, S )，语法分析树是满足下列条件的树：
(1) 每个内部结点由一个非终结符标记.
(2) 每个叶结点或由一个非终结符，或由一个终结符，或由ε来标记. 但标记为ε时，它必是其父结点唯一的孩子.
(3) 如果一个内部结点标记为 A，而其孩子从左至右分别标记为X 1 ,X 2 , …,X k ，则 A → → X 1 X 2 …X k 是 P 中的一个产生式. 注意：只有 k=1 时上述 X i 才有可能为 ε，此时结点 A 只有唯一的孩子，且 A → ε 是P 中的一个产生式.
语法分析树的果实

设 CFG G = (V N , V T , P, S ). 将语法分析树的每个叶结点按照从左至右的次序连接起来，得到一个 (V N∪V T )* 中的字符串，称为该语法树的果实.G 的每个句型都是某个根结点为 S 的分析树的果实；这些分析树中，有些树的果实为句子，所有这些分析树的果实构成了 G 的语言.

🌈归约、推导与分析树之间关系

设 CFG G = (V N , V T , P, S ). 以下命题是相互等价的：

(1) 字符串 w∈ V T * 可以归约（递归推理）到非终结符A；
(2) Aw；
(3) Aw；
(4) Aw；
(5) 存在一棵根结点为 A 的分析树，其果实为 w.

有限自动机的五大要素

1、有限状态集 2、有限输入符号集 3、转移函数 4、一个开始状态 5、一个终态集合

eg：

δ’ (q 0 , ε ) = q 0
δ’ (q 0 , 0)= δ (q 0 , 0)= q 2
δ’ (q 0 , 00)= δ (q 2 , 0)= q 0
δ’ (q 0 , 001)= δ (q 0 , 1)= q 1
δ’ (q 0 , 0010)= δ (q 1 , 0)= q 3

🌈DFA的语言

设一个 DFA A = (K, Σ, δ , q 0 , Z ) ，定义A的语言：满足L(A) ={w |δ’ ( q 0 , w) ∈Z } 就可以证明，如果满足L=L（A），则L是一个正规语言