编译原理第二章(2-构造文法).ppt

前述内容回顾 第二章 文法和语言的基本知识 本章主要介绍形式语言理论中的一些最基本的概念和基础知识，它是学习以后各章节的基石。 本章内容简介 形式语言理论 2.2.1 字母表与符号串 字母表与符号串 2.2.2符号串运算 符号串的连接 设x和y是符号串，则称xy是他们的连接。 例如：x=abc , y=1a 则 xy=abc1a , yx=1aabc 即 |x|=3, |y|=2, |xy|=3+2=5 注意：对任意一个符号串x 我们有εx = x ε= x 符号串集合的乘积 设A和B是符号串的集合，则A和B的乘积定义为 AB={xy | x∈A,y ∈B} 例如： A={a,b} B={c,d} 则AB={ac,ad,bc,bd} 集合的乘积是满足于x∈A , y ∈B 的所有符号串xy所构成的集合。 注意： 1、对于任何集合A , 有{ε}A = A {ε}= A 2、 {ε}= ? ?≠ { } 符号串的方幂 设x是符号串，xn 是x自身连结n次。并且x0＝ ε 则 x1＝ x x2＝ xx xn＝ xx……x= x xn-1 n个 例如, 设 x=abc，则 x1＝ abc x2＝ abcabc …… 符号串集合的方幂 A是符号串的集合， An 是集合A自身n次相乘， 并且A0＝ {ε} 则 A1＝ A A2＝ AA An＝ AA……A= A An-1 (n0) n个A 例1 A={a,b} A0＝ {ε} A1 ＝ {a,b} A2＝ {aa,ab,ba,bb} A3＝ {aa,ab,ba,bb}· {a,b} ＝ { aaa,aab,aba,abb,baa,bab,bba,bbb } 符号串集合的正闭包A+ 与 闭包A* A是集合 A的正闭包 A＋＝ A1∪A2 ∪ …… ∪ An A的闭包 A*＝ A0 ∪ A1∪A2 ∪ …… ∪ An ＝ {ε} ∪ A+ A={a,b} A＋ ＝ { a, b, aa, ab, ba, bb, aaa, aab,…..} A* ＝ {ε, a , b, aa , ab, ba, bb, aaa, aab,…..} A＋表示A上元素a,b构成的所有符号串的集合。 2.3 文法和语言的形式定义 2.3 文法和语言的形式定义 例如：1）句子 → 主语 谓语 2）主语 → 冠词 名词 3）谓语 → 动词 宾语 4）宾语 → 冠词 名词 5）名词 → man | car 6）冠词 → the 7）名词 → drive The man drive the car The car drive the man 一组规则规定一个语言 The car drive the car 的语法结构 The man drive the man 2.3.2文法的形式定义 例1 定义标识符的文法 2.3.3 和语言有关的几个概念 直接推导举例 2.3.3 和语言有关的几个概念 2.3.3 和语言有关的几个概念 2.3.3 和语言有关的几个概念 P15 【例1】设有文法G[S]： S→01∣0S1 S,01，0S1，00S11,000111 都是句型。 01和000111 又是句型。 2.3.3 和语言有关的几个概念 2.3.3 和语言有关的几个概念 P17 2.3.3 和语言有关的几个概念 递归举例 2.3 文法的分类 2.3 文法的分类 0型文法（无限制文法或短语结构文法） 产生式为 ： α→β 其中：α? (VN∪VT)* 且至少包含一个非终结符 β? (VN∪VT)*， 0型文法没有其他任何限制条件，故称无限制文法。 0型文法所生成的语言称为无限制语言。 例如 有0型文法G=(VN,VT,P,S) ,其中 P={S→0AB 1B→0 B→SA|01 A1→SB1 A0→S0B} 其描述的0型语言为 L(G[S])={ } 对0型文法的产生式做些限制，可得到其它三种类型的文法。 1型文法（上下文有关文法） 产生式为 ：