Ex:
设G[E]：EE＋E｜E＊E｜（E）｜i，试证明 符号串( i * i + i )是文法G[E]的一个句子
证明：从E出发，只要证明符号串x = ( i * i + i ) 对 于文法G[E] 存在一个推导。
E（E）（E＋E） （E＊E＋E） （i*E+E） （i*i+E） （i * i + i ）
•A0={ac,bc,ad,bd} •A1＝A＝｛a,b｝ •A2＝AA＝｛aa, ab, ba, bb｝ •A3＝A2A＝｛aaa,aab,aba,abb,baa,bab,bba,bbb｝
• 5、集合的闭包（A+和A＊）
– 设A是任意一个集合，则定义A：的正闭包，其
A+＝A1 ∪ A2 ∪ A3…
2： Σ中可以是字母、数字或其它符号。 – Ex1：C语言的字母表
ΣC＝｛保留字，字母，数字，专用符号，……｝
C语言＝ ΣC 一组规则 – Ex2：汉语的字母表
Σ汉＝｛汉字，数字，标点符号，……}
• 2、符号与符号串
– 符号（字符）：一个符号是字母表中的元素。
– 符号串：是符号的有穷序列。
– EX1： Σ＝{a, b, c}，则a, b, c, ab, ba都是Σ上的符号 串。
复习基本概念
第3讲
1、字母表、符号串、符号串的长度、空串
2、符号串运算：连接、符号串的幂
3、集合的运算：集合乘、集合文的法幂的作、用集是合什的闭
包
么？
4、形式语言的描述：
（1）枚举法描述
（2）用文法描述
5、文法的形式定义
G＝（VT，VN，S，P）
四、语言的形式定义
1、直接推导
设X，Y是符号串，如果使用一次规则式可以 从X推导出Y，则Y为X的直接推导。记为： XY
X0＝
注： X0 ≠1 X1＝X X2＝XX
X0＝
X1＝abc X2＝abcabc Xn＝ abc……abc
Xn＝ XX……X n个X
n个abc
• 4、集合的幂运算
– 设A是符号串的集合，则定义： A0＝{}
A1＝A A2＝AA An＝AA……A＝An-1A
–EX: •A={a, b} ,则有
• 2、集合的乘积
– 设A、B是符号串的集合，则定义A与B的乘 积为：
AB＝{xy | xA, y B}
– EX: • A={a, b}, B={c, d}，则AB ={ac,bc,ad,bd}
• A{}={}A=A
• {} { }, { }=
• 3、符号串的幂运算
– 设X是符号串，则 • 例、设X＝abc，则
一组规则可以描述一个语言的语法结构。
非终结符，一般在左边，它能派生出符号、符号串。 用大写字母表示,如上述中的A。与之对应地，终结 符用小写表示，由它不能派生出任何符号，是一个 不可再分的基本单位，即字母表（∑）中的一个元 素。
2、文法的形式定义
一个文法是规则的非空有穷集合。常用一个四 元组表示，定义为
– Note1：符号串的顺序很重要，如：ab≠ba; 2：不含任何符号的符号串称为空串，用
ε 表示。
– 符号串长度：｜a｜＝1，｜ab｜＝2，｜ ε｜＝0
二、符号串的运算
• 1、连接
– 设X和Y是符号串，则串XY称为它们的连接。 – EX：X＝ABC，Y＝CDF
XY=ABCCDF YX=CDFABC – Note： ε与X的连接或X与ε的连接＝X
3、*推导 (广义推导）
设X，Y是符号串，若使用0次或多次规则可以从 X推导出Y，则Y为X的*推导。 记为：X Y
Ex:
设G[S]：S0S1｜01，则
区别S: S S直01接推导长度＝1 S所以正广0推义SS1导推长 导0000S度 长01111度110000111
即：直接推导正推导广义推导
算符 左操作数 右操作数 结果
第2章 文法和语言
QU：
1、A＝B＊
2、A＝B＊C
在C语言中的，以上 两个符号串是否是合 法的、正确的？
QU：那么，Compiler如 何对语法进行定义？是 基于什么形式进行判断 识别的？
AN：形式语言中的文 法是阐明语法的一个重 要工具。
2.1 引言
• 形式化方法：指用一整套带有严格规定 的符号体系来描述问题的方法。
中无空串
A*＝A0 ∪ A+
＝A0 ∪ A1 ∪ A2……
A的 * 闭包，
–EX:
其中有空串
•A={a, b} ,则有
•A+＝｛a, b, aa, ab, ba, bb, aaa, aab, ……｝
•A*＝A0 ∪ A＋
＝｛ ,a ,b, aa, ……｝
2.3 文法与语言的形式意义
▪ 形式语言 ▪ 形式语言的描述 ▪ 文法的形式定义 ▪ 语言的形式定义 ▪ 最左、最右推导 ▪ 归约 ▪ 递归
第一章第课2讲程复习
编译程序是将高级语言书写的源程序翻译成低级 语言程序。一般包括词法分析，语法分析，中间代 码生成，代码优化，目标代码生成五个部分，还应 该包括表格管理和出错处理。
其中中间代码生成和代码优化并不是每个程序都 需要的。 词法分析器用于识别单词，语法分析器用于发现 源程序中的语法错误。 代码优化一般都是在中间代码级上完成的，对中 间代码的优化可以使目标程序的运行时间更短或所 占的空间更少。
一、形式语言
“定义为”或 “由……组成”
<句子><主语><谓语><间接宾语><直接宾语>
<主语><代词>
<谓语><动词>
<间接宾语><代词>
<直接宾语><冠词><名词>
<代词>He
<代词>me <冠词>a <动词>gave
QU:句子He gave me a book 语法上是否是正确的？
<句子><主语><谓语><间接宾语><直接宾语> <主语><代词> <谓语><动词> <间接宾语><代词> <直接宾语><冠词><名词>
……
2.2 符号串
• 一、字母表和符号串 • 二、符号串的运算
一、字母表和符号串
• 1、字母表（Σ）
– Def：是元素的非空有穷集合。 – Note1： Σ中至少有一个元素；
4、句型、句子
设有文法G[S]，若从文法开始符号S x,则称符 号串x为文法G[S]的句型；仅仅由终结符组成的 句型叫句子。
若x是一个句型，则x （VNVT）＊ 若x是一个句子，则x VT＊
Ex: S0S1｜01
S 01 S 0S1 S 000111
(句型、句子） (句型） (句型、句子）
∴ 文法G＝（VT，VN，S，P）,其中： VT＝｛a, b｝，VN＝｛A，B，D｝，S＝A P＝{Aaa|bb|aaB|bbD, Baa|aaB, Dbb|bbD}
另解：P：AB｜D Baa｜aBa Dbb|bDb
∴ 文法G＝（VT，VN，S，P）,其中： VT＝｛a, b｝，VN＝｛A，B，D｝，S＝A P＝{AB|D, Baa|aBa, Dbb|bDb}
G＝（VT，VN，S，P）
其中：
VT：所有终结符的集合 VN：所有非终结符的集合 S：开始符 P：规则式的集合
EX:
一个文法G＝（VT，VN，S，P）,其中：
VT＝｛0, 1｝
所有终结符的集合
VN＝｛A ｝
所有非终结符的集合
S＝A
开始符
P＝｛A0｜1｜A0｜A1｝ 规则式的集合
Qu: 给定一个语言L，如何求文法G？
Ex1：设∑＝｛a, b｝，试设计一个文法G，定义语言L＝｛a2n,b2n | n≥1｝ 解：由串结构的特征L={aa,bb,aaaa,bbbb,……},可以令P此得序列｛aa,aaaa,……｝，同理
Abb
AbbD
Dbb|bbD
可以得到序列｛bb,bbbb,……｝
以上从文法的开始符E ( i * i + i )，所以符号 串( i * i + i )是G[E]的一个句子。
5、语言L(G[S])
对一个文法G[S]，其句子的全体所组成的集合即 语言L(G[S])。
L(G[S])＝｛x | S x 且 xVT*｝
主语
句子
谓语
间接宾语 直接宾语
代词
动词
代词 冠词 名词
He
gave
me
a
book
Note: 1、形式语言是一种上下文无关的语言，是有别于自然 语言的一种语言。
2、定义语言的一组规则及其有关符号，称为文法。 因此，我们把定义形式语言的规则和有关符号的集合，称为上
下文无关的文法。
二、形式语言的描述
• 方式一：当语言为有穷集合时，用枚举法表示。 • EX：设字母表A＝｛a, b, c｝
以上简记为： G[A]：AB｜D Baa｜aBa Dbb|bDb
Note1：给定一个语言时，文法不是唯一的。 Ex2：2：用用文文法法定描义述一语个言含时＋，，要＊准运确算，符既的不算能术扩表大达也式不。能缩小。 解1：非形式化描述， 解12、：变形量式是化一描个述表：达式；
2、G若[EE]：1和EE2是i 一个表达式，则E1＋E2、E1＊E2、（E1）也是 一个表达式。EE + E｜E ＊ E | ( E )
以上所描述的句子的集合为：