2.2 字母表和符号串的基本概念
2. 符号（字符） 字母表中的元素称为符号或称为 字符。 例如，前述例子中 a、b、c 是字母表Σ中的符号； 0、1 是字母表Σ'中的符号。
2.2 字母表和符号串的基本概念
3. 符号串（字） 符号的有穷序列称为符号串。 例如，设有字母表∑={ a, b, c } 则有符号串 a，b，ab，ba， cba， abc… 符号串总是建立在某个特定字 母表上的且只由字母表上的有穷多 个符号组成。
若将定义标识符的文法设计成： G=(VN，VT，P，S )
其中 VN，VT ，S 同上
P={ I→L | I D L→a | b | c | …|x|y|z D→0 | 1 | 2 | 3 | …|9 }
缩小了所定义语言的范围
2.3.2 文法的形式定义
例3 设字母表 Σ={ a, b } , 试设计一个 文法，描述语言 L={ abna | n≥0 }
2.2 字母表和符号串的基本概念 2. 集合的乘积 设A和B是符号串的集合, 则A和B 的乘积定义为：
AB={xy | x∈A, y∈B}
集合的乘积是满足于 x∈A, y∈B 的所有符号串 xy 所构成的集合。
2.2 字母表和符号串的基本概念
例如：设A={ a, b }, B={ c, d }
则AB={ ac, ad, bc, bd }
2.3.2 文法的形式定义
当n＝1 L={aa, bb}
L={a2n, b2n | n≥1}
当n＝2 L={aaaa, bbbb} 当n＝3 L={aaaaaa, bbbbbb}
……
即语言L是由偶数个a，偶数个b这样 的符号串组成的集合。
2.3.2 文法的形式定义
因此，定义语言L的文法 G=( VN，VT，P，S ) 注意: V 其中： N={A, B, D} VT≠{aa,bb} VT={a, b} P={ A→aa | aaB | bb | bbD B→aa | aaB D→bb | bbD } S=A
={ 0, 1, 00, 10, 11, 01, 000, 100, …}
当语言为无穷集合时，用文法来描述 语言。
2.3 文法和语言的形式定义
∑+=∑1∪∑2∪∑3∪… ={ 0, 1, 00, 10, 11, 01, 000, 100, …}
下面用A表示∑ + ， 用式子A→0表示符 号串0∈A或A生成 符号串0，符号 “”读作“生成” 或“由…组成”。 则集合A可表示成：
L1={ a, b, c } L2={ a, aa, ab, ac } L3={ c, cc } 均表示字母表A上的一个形式语言。由于 这三个语言均是有限符号串的集合，因此， 可枚举出其全部句子来表示该语言。
2.3 文法和语言的形式定义
例如，设字母表∑={ 0, 1 }, 则
∑+=∑1∪∑2∪∑3∪…
使用规则 S0S1 此时 x＝00 , y＝11 000S11100001111 使用规则 S01 此时 x＝000 y＝111
2.3.2 文法的形式定义
G=(VN，VT，P，S) VN={I, L, D} 其中：
VT={a,b,c, … x,y,z,0,1,2,… ,9}
P={ I→L | I L| I D L→a | b | c | … | x | y | z D→0 | 1 | 2 | 3 | … | 9 }
S=I
2.3.2 文法的形式定义
G: A→aBa B→Bb | ε
2.3.2 文法的形式定义
例4 设字母表∑={ (, ) } ,试设计 一个文法描述语言 L={ (n )n | n≥0}
G: S→ ε | ( S )
2.3.3 语言的形式定义
1. 直接推导
令G是一文法，我们称 xAy直接 推导出 xαy ，即 xAyxαy 仅 A→α 是 G 的一条规则, 且 x, y(VN∪VT)*。也就是说从符号串 xAy 直接推导出 xαy 仅使用一次规 则。
2.2 字母表和符号串的基本概念 例如, 设 x＝abc 则 x0= x1=abc
x2=xx=abcabc …
2.2 字母表和符号串的基本概念
4. 集合的幂运算 设A是符号串的集合，则集合A的 幂运算定义为： A0={} A1=A A2=AA … An= AA … A=AAn-1(n>0) n
2.3.2 文法的形式定义
终结符号是不属于非终结符号 的那些符号, 它是组成语言的基本符 号，是一个语言的不可再分的基本 符号，通常用小写字母表示。 例如，上例中的0和1。
2.3.2 文法的形式定义
2. 文法
规则的非空有穷集合，通常表示 成四元组 G={VN,VT, P, S } VN是规则中非终结符号的集合。 VT是规则中终结符号的集合。
2.2 字母表和符号串的基本概念 例如，设A={ a, b }，则 A0={} A1=A={ a, b } A2=AA={ aa, ab, ba, bb } A3=AAA=A2A
={ aaa, aab, aba, abb, baa, bab, bba, bbb }
…
2.2 字母表和符号串的基本概念
2.3.2 文法的形式定义
描述该语言的文法G“是否与前面文 法等价？
G"=( {A}, {a, b}, P", A ) P"={ A→aa | bb | Aaa | Abb }
此文法超出了所定义语言的范围。
2.3.2 文法的形式定义
例2 试设计一个表示所有标识符 的文法
字母 字母或数字串
用I代表标识符；L代表字母； D代表数字; 则定义标识符的文法 为：
可见,集合A的正闭包表示A上元素 a,b构成的所有符号串的集合,集合A 的闭包比集合A的正闭包多含一个空 符号串。
2.3 文法和语言的形式定义
2.3.1形式语言
序列的集合称为形式语言。
每个形式语言都是某个字母表上按 某种规则构成的所有符号串的集合。 反之，任何一个字母表上符号串的集 合均可定义为一个形式语言。
2.3.2 文法的形式定义
提出问题: 描述该语言的文法是 否唯一呢？ P' : A→B | D B→aa | aBa D→bb | bDb
显然，G不同于G'。由此可见， 对于一个给定的语言，描述该语言 的文法是不唯一的。
2.3.2 文法的形式定义
若G和G'是两个不同的文法，如 果它们描述的语言相同，那么，称G 和G' 为等价文法。
A→0 A→1 A→A0 A→A1
2.3.2 文法的形式定义
1. 规则 也称产生式
规则是一个符号与一个符号串的 有序对（A,β），通常写作：
A→β（或A∷＝ β)
规则的作用是告诉我们如何用规 则中的符号串生成语言中的序列。
2.3.2 文法的形式定义
例如，前述例中一组规则
A→0 A→1 A→A0 A→A1
P 是文法规则的集合。
2.3.2 文法的形式定义
S 是一个非终结符号，称为文法 的开始符号或文法的识别符号，它至 少要在一条规则中作为左部出现。由 它开始，识别出我们所定义的语言。 由文法定义可知，文法是对语言 结构的定义和描述，文法四大要素中 关键是规则的集合。
2.3.2 文法的形式定义
为了书写方便，对于若干个左 部相同的规则，如 A→1 A→2 … A→n 将它们缩写为：A→1 | 2 | … | n
2.3.3 语言的形式定义
例如，设有文法G[S]: P为：S→ 0 1 | 0 S 1 有如下直接推导： S01 使用规则 S01 此时 x＝， y＝ S0S1 使用规则 S0S1 此时 x＝， y＝
2.3.3 语言的形式定义
S→ 0 1 | 0 S 1
0S10011 00S11000S111 使用规则 S01 此时 x＝0， y＝1
第二章 文法和语言的基本知识
形式语言理论是编译的重要理论 基础。本章主要介绍编译理论中用到 的有关形式语言理论的最基本概念， 重点介绍如何采用形式化的方法描述 程序设计语言。
第二章 文法和语言的基本知识 字母表和符号串 文法和语言的形式定义 文法和语言的分类 短语、直接短语和句柄 语法树和文法的二义性
2.2 字母表和符号串的基本概念
一、基本概念
1. 字母表 元素的非空有穷集合。 例如，∑={ a, b, c } 根据字母表的定义，Σ是字母表， 它由a、b、c三个元素组成。
2.2 字母表和符号串的基本概念 注意: (1) 字母表中至少包含一个元素。 (2) 字母表中的元素, 可以是字母、 数字或其他符号。 例如，∑' ={0, 1} 是一个字母表，由0、1两个元素 组成。
其中每个i有时也称为是A的一个候选式。
2.3.2 文法的形式定义
前例中描述∑+的文法是: G=(VN，VT，P，S ) VN={A}
VT={0，1} P: A→ 0 | 1 | A0 | A1
S=A
2.3.2 文法的形式定义
我们约定：
第一条规则的左部是识别符号。 对文法G不用四元式显示表示， 仅 只将规则写出。 G: A→ 0 | 1 | A0 | A1
由于对任意的符号串x，总有 x=x=x 所以, 对任意集合A, 我们有: {}A=A{}=A
2.2 字母表和符号串的基本概念 特别指出的是， 是符号串, 不是 集合，而{}表示由空符号串 所组 成的集合, 但这样的集合不是空集合 Φ={} 。
2.2 字母表和符号串的基本概念
3. 符号串的幂运算 设x是符号串, 则x的幂运算定义为： x 0= 注意：x0≠ 1 x 1= x x2= xx x3= xxx … xn= xx … x=x xn-1(n>0) n
2.3.2 文法的形式定义