编译原理第二章 文法和语言

例子：考虑一个文法
G＝({a, b}, {S}, S，P） 其中 P：SaSb ab。试推导其语言。 SaSb aaSbb a3Sb3 …… an-1Sbn-1 anbn 其语言为：L(G)={anbn |n>=1}
说明：
★ 只用一个产生式并不足以定义一个语法范 畴,在绝大部分情况下都需要用好几个产生式, 特别是需要含有递归的产生式(产生式左部的 符号直接在右部出现). ★ VN∩VT=Φ:即文法中的任意一个符号要么 为非终结符号,要么为终结符号.
A A1 A 2 A 3 ......

定理2.1 若A是符号串集合，则A*=(A*)* 。
证明 显然 A* (A*)* , 现证 (A*)* A* 任给符号串 x∈(A*)*，则存在n，使得 x∈(A*)n， x 必存在n个子串x1 ,…,xn ， 使得x= x1…xn ，且 xi∈A* (i=1,…,n)。 由xi∈A* ，必存在整数pi ,使得xi∈Api ， 令 n
句型、句子和语言
* ，其中 S 是开始符号， ∈ V* ，则称 若S 为文法G的句型。 * 特别地，若 S ，且 ∈ VT* ，则称 为 G 的 句子。 文法G所定义的语言，记作：
L(G)={|∈VT*，且S}
*
同一句型有不同的推导序列
设有文法G[N1]: N1→N N →ND|D D→0|1|2 则句子12可由三种不同的推导序列推导出来： (1) N1 N ND N2 D2 12 (2) N1 N ND DD 1D 12 可见，同一句型（句子）可以通过不同的推导 序列推导出来。

|x|= 2 |y|= 3 |z|= 5
|xy|=|x|+|y|

例如， ∑′={0，1}是一个字母表，由0 和1两个元素组成。 不同的语言有不同的字母表，如英文的字 母表是26个字母、数字和标点符号的集合，C语 言的字母表是由字母、数字和若干专用符号组 成。 2. 符号（字符） 字母表中的元素称为符号，或称为字符。 例如，前述例子中，a，b，c是字母中∑ 中的符号；0和1是字母表∑′中的符号。
例如：用A表示∑ + ，用式子A→0表示符号串 0∈A或A生成符号串0，符号“→”读做“生成”或 “由……组成”。则集合A可表示成 A→0 A→1 A→A0 A→A1 显然，由A生成的符号串属于∑+，这就是用文 法描述语言。
编译原理授课教案
2.2.2 文法的形式定义
1. 规则 规则也称产生式，它是一个符号与一个符号 串的有序对(A，β)，通常写做 A→β(或A::=β) 其中，A是规则左部，它是一个符号；β是 规则右部，它是一个符号串；“→”和“::=”表 示“定义为”或”生成”，意思是左部符号用右 部的符号串定义或左部符号生成右部是集合， 而｛ε｝表示由空符号串ε所组成的集合，但 这样的集合不是集合φ＝｛｝。 ３. 符号串的幂运算 设x是符号串，则x的幂运算定义为 x0=ε X1= x x2 = xx ………… xn = xxxx……xx=xxn-1 ( n > 0)
编译原理授课教案
编译原理授课教案
试设计一个表示所有标识符的文法。 例2.2 ：
分析 题意是用文法定义标识符，必须确 定P中规则。为了设计出一组规则，首先应搞清 楚集合中符号串的结构特征。标识符的定义是 字母或以字母开头的字母数字串，结构如图：
字母 字母或数字串
用I代表标识符，L代表字母，D代表数字， 则定义标识符的方法为 G = (VN ,VT, P , S)

0型(无限制)：G=(VT,VN,S,P) 规则形式 ： , (VTVN)*, 并且至少含有一个非终结符号； 1型（上下文有关） ： A u u (V V )+, A u ，S 除外； 2型（上下文无关）：规则形式 ： A A VN， (VTVN)* ； 3型（右线性）： A B或 A （左线性） A B 或 A ， VT*， A,B VN
S a
A
b b A a
S
a
S
a
关于分析树的几点说明
1. 一个句型推导或分析用一棵树结构图示 出来，它反应了一个句型语法结构的层次。
2. 对于一个句子的多种推导（若文法是无二义 性的），采用各种推导过程，画出的分析树是 一样的。分析树并未描述推导过程，它是不同 推导过程的抽象共性。 3. 在书中，用画分析树的过程解释语法分析过 程，用分析树图解语法结构。
1. 2. 3. 4. 5. • • • • 符号串的连接 εy=yε=y 集合的乘积 {ε}A=A{ε}=A 符号串的幂运算 y0=ε y1=y y2=yy 集合的幂运算 A0={ε} A1=A A2=AA 集合A的闭包A*与正闭包A+ ∑的闭包∑*： ∑上所有符号串的全体 例如，若 ∑={a,b}， 则∑+={a,b,aa,ab,ba,bb,aaa,…} 则∑*={ε，a,b,aa,ab,ba,bb,aaa,…}= ∑0 U ∑+
+
文法对应的语言示例：
见课本p16，例2.7—2.9 S → 01 | 0S1 S → 0S | 1S | ε
A → yB
例
B → xB | x
S → aB | bA A → a | aS B → b | bS | | bAA aBB

第二章 文法和语言p48 4、6（6）、11、 12（2）（6）、18（2）4 证明文法G=（{E,O}，{(，)，+，*，v ，d}，P ，E ）是二义的,其中P 为 E → EOE | (E) | v | d O → + | * 证明：因为E=〉 EOE =〉EOEOE =〉EOEOv =〉EOE+v=〉EOv+v =〉E*v+v =〉v*v+v ， 句子v*v+v 有两棵不同的语法树所以文法G 是二义的。

问题：1）只有文字说明，比如v*v+v 有两棵语法树，但没有画出语法树或者最左（最右）推导过程2）给出的是不同句子（v*v+d v+v*d ）的语法树 6、已知文法G ：EEEE OO v*v+ vE EE E O O v+v* v〈表达式〉∷=〈项〉|〈表达式〉+〈项〉〈项〉∷=〈因子〉|〈项〉*〈因子〉〈因子〉∷=（〈表达式〉）| i试给出下述表达式的推导及语法树（6）i+i*i推导过程：〈表达式〉=〉〈表达式〉+〈项〉E=〉E+T =〉〈表达式〉+〈项〉*〈因子〉=〉E+ T*F=〉〈表达式〉+〈项〉* i =〉E+ T*i=〉〈表达式〉+ 〈因子〉* i =〉E+F*i=〉〈表达式〉+ i* i =〉E+i*i=〉〈项〉+ i* i =〉T +i*i=〉〈因子〉+ i* i =〉F +i*i=〉i +i*i =〉i +i*i 共8步推导语法树：〈表达式〉+〈因子〉〈项〉i 〈因子〉i〈项〉〈项〉〈因子〉i*11、一个上下文无关文法生成句子abbaa的推导树如下：（1）给出该句子相应的最左推导和最右推导（2）该文法的产生式集合P可能有哪些元素？（3）找出该句子的所有短语、简单短语、句柄。

（1）最左推导：S=〉ABS=〉aBS=〉aSBBS=〉aBBS=〉abBS=〉abbS =〉abbAa=〉abbaa最右推导：S =〉ABS=〉ABAa=〉ABaa=〉ASBBaa=〉ASBbaa=〉ASbbaa=〉Abbaa=〉abbaa（2）该文法的产生式集合P可能有下列元素：S→ABS | Aa|εA→a B→SBB|b（3）因为字符串中的各字符有相对的位置关系，为了能相互区别，给相同的字符标上不同的数字。