编译原理第2章 编译基础 (2).ppt

第二章编译基础§2.0概述§2.0概述形式化方法：是用一整套带有严格规定的
符号体系来描述问题的方法。2.符号（字符）：字母表中元素。

3.符号串：用字母表中的符号组成的任何有穷序列，也称字。
例如：a,ab,bba,acab,…
注意：
①符号串中符号的顺序是很重要的。
②不包含任何符号的符号串称空串，记为ε。 |ε|=0
③一个字母表上全部符号的集合是无穷的。4.符号串的前缀、后缀以及子串：
设x是一符号串，例如：x=abc

符号串的前缀：从x的尾部删除若干个（>=0）符号后所余下的部分。例如：ε，a，ab，abc
符号串的后缀：从x的头部删除若干个（>=0）符号后所余下的部分。例如：ε，c，bc，abc
子串：从x中删除前缀和后缀之后所余下的部分。
例如：ε，a，b，ab，bc，abc
二.符号串的运算
1．符号串的连接：设x，y是符号串，则串xy称为它们的连接。
例如：设x=my y=computer xy=mycomputer yx=computermy
注意：对任意x Xε=εX=X

2．集合的和与乘积：设A，B是符号串的集合，则：
A∪B={ω|ω∈A或ω∈B}
AB={xy|x∈A且y∈B}
例如：设 A={a,b} B={c,d}
则： A∪B={a,b,c,d} AB={ac,ad,bc,bd}
注意：Φ∪A=A∪Φ=A ΦA=AΦ=Φ {ε}A=A{ε}=A Φ={}≠{ε} 3.符号串的幂运算：若x是符号串，则
x0=ε,x1=x,x2=xx,…
例如：设x=abc
则： x0=ε,x1=abc,x2=abcabc,…
4.集合的幂运算：若A是符号串的集合，则
A0={ε},A1=A,A2=AA,…
例如：设A={a,b}
则： A0={ε},A1={a,b},A2={aa,ab,ba,bb},…
5.集合的A＋(正闭包)和A*（自反传递闭包）:
设A为任一集合，则：
A＋=A1∪A2∪A3∪…∪An∪… （A上所有符号串所组成的集合）
A*=A0∪A＋={ε}∪A＋
例如：设A={a,b,c}
A＋={a,b,c,aa,ab,ac,ba,bb,bc,…}
A*={ε,a,b,c,aa,ab,ac,ba,bb,bc,…}§2.2文法和语言的形式定义 2．用文法描述语言

例如：设有字母表∑={0，1}
∑+={0，1，00，01，11，10，000，100，…}
用A表示∑+，A→0（定义为，生成，导出）
用产生式表示∑+： A→0
A→1
A→A0
A→A1

3．用自动机识别语言：构造一种装置来识别语言，它可以判断某符号串是否是该语言的句子。
例如：
1100→→是（接收）
11ab→→不是（不接收）
三．文法的形式定义 3．文法的形式定义：是规则的非空有穷集合，通常定义为四元组：
G[S]=（Vn，Vt，P，S） 其中：

Vn：规则中非终结符的集合。 Vn={A}
Vt：规则中终结符的集合。 Vt={0，1}
P：文法规则式的集合。 P:A→0
A→1 A→A0 A→A1
S：文法的开始符号（识别符号）
由它开始识别我们所定义的语言。S=A
例1 例2 例3 例4 例5 继续例1．设有字母表 ∑={a，b}，请为语言
L={a2n,b2n|n>=1}设计一个文法。
首先分析语言中串的结构特征：L={aa,bb,aaaa,bbbb,…}（偶数个a或偶数个b组成）
G[S]=（Vn，Vt，P，S）
其中： Vn={A,B,D}
Vt={a，b}
P: A→aa|aaB|bb|bbD
B→aa|aaB
D→bb|bbD
S=A
易错：A→aa|aaA|bb|bbA
会出现句子aabb扩大了语言范围问题：描述是否唯一？（回答不唯一）
P1: A→B|D B→aa|aaB D→bb|bbD

等价文法：
P2: A→B|D
B→aa|aBa
D→bb|bDb

返回例2．已知语言L={w|w是0和1的个数都为偶数的0，1串}。
分析句子结构特征：001100 110000 0101
①S→0A|1B (A,B奇数个0,1)
②A→0 B→1
③推出无穷串：A→0S B→1S
④产生0101串：C→0B|1A A→1CB→0C

文法：G[L]=（{A,B,C,S},{0,1},P，S）
P: S→0A|1B
A→0S|1C|0