编译原理第二章

2.3.2 语言的形式定义
S→01 | 0S1
我们应用第二个规则n－1次，然 后再应用第一个规则1次，有：
S 0S100S11…0n-1S1n-10n1n 即S* 0n1n
可见，此文法定义的语言为
L(G[S])={ 0n1n | n≥1}
2.3.2 语言的形式定义
例4 设有文法G[S]：S→0S | 1S |ε 该文法所定义的语言是什么？
2.3.2 语言的形式定义
4. 句型和句子
设有文法G[S]（S是文法G的开始符号） 如果S* x, x ∈(VN∪VT)* 则称符
号串x为文法G[S]的句型。 如果S* x, x ∈VT* 则称符号串x
为文法G[S]的句子。 即：仅含终结符号的句型是一个句子。
2.3.2 语言的形式定义
例1 设有文法G[S]：S→01 | 0S1
2.3.2 语言的形式定义
如2果．存推在导一个直接推导序列：
α0 α1 α2 … αn
则我们称这个序列是一个从0至 n的长度为n的推导，记α0为+ αn 即表示从0 出发，经 一步或若干 步 或者说 使用若干次规则可推导
出 。
2.3.2 语言的形式定义
设有文法G[E]=({E,T,F},{i,+,*,(,)},P,E) 其中P为：E→E+T | T T→T*F | F F→(E) | i 对 i+i*i 有如下直接推导序列: EE+TT+TF+Ti+Ti+T*F i+F*Fi+i*Fi+i*i 我们可记为 E+Baidu Nhomakorabeai+i*i
2.3.2 语言的形式定义
3．广义推导
0* n表示从0出发，经0步或若干步， 可推导出n。
也就是说0* n意味着0+ n或者0=n。 对上例 E→E+T | T T→T*F | F F→(E) | i
我们有： E* E E* i+i*i
2.3.2 语言的形式定义
区别:直接推导的长度大于 等于1，而广义推导的长度大 于等于0。
例如，设有文法G[N1] N1→N N→ND | D
D→0 | 1 | 2
句子12有下列三种不同的推导序列: ① N1N NDN2 D212 ② N1N NDDD1D12 ③ N1N NDDDD212
最左(最右)推导，是指对于 一个推导序列中的每一步直接推 导 αβ , 都是对α 中的最左(最右) 非终结符进行替换。
最右推导也称为规范推导， 用规范推导推导出的句型称为规 范句型。
例 设有文法G[S]: S→AB A→A0 | 1B B→0 | S1
请给出句子101001的最右、最左推导。
分析 最右推导是指在推导过程 中任何一步αβ (α和β是句型)，都是 对α中的最右非终结符进行替换。
S→AB A→A0 | 1B B→0 | S1 句子101001的最右推导为: SABAS1AAB1AA01A1B01 A10011B1001101001
最左推导是指在推导过程中任何 一步αβ (α和β是句型), 都是对α的最 左非终结符进行替换。
S→AB A→A0 | 1B B→0 | S1 句子101001的最左推导为：
由该文法所确定的语言为
L(G[S])={ε, 0, 1, 00, 01, 10, 11, …}
={ x | x∈{0,1}* }
2.3.2 语言的形式定义
例5 设有文法G[A]： A→yB B →xB | x
该文法所定义的语言是什么？ 分析 从文法开始符号A出发可推导
出以y开头后面跟一个或多个x结尾的 符号串，所以该文法定义的语言为
我们有: S* 01 S* 0S1 S* 00S11 S* 000111
显然，符号串01、0S1、00S11和 000111 都是文法G[S]的句型，而01和 000111又是文法G[S]的句子。
2.3.2 语言的形式定义
例2 设有文法G[E]：
E→E+E | E*E | (E) | i 试证明符号串 (i*i+i) 是文法G[E]的一 个句子。 分析 只要证明符号串 (i*i+i) 对文法 G 存在一个推导，就可证明符号串 (i*i+i) 是文法G[E]的一个句子。
第二章
语法描述
定义：称A直接推出，即
A 仅当A 是一个产生式， 且， (VT VN)* 。
如果1 2 n，则我们称这个序 列是从1到n的一个推导。若存在一个从 1到n的推导，则称1可以推导出n 。
对文法G(E)： E i | E+E | E*E | (E)
E (E) (E+E) (i+E) (i+i)
2.3.2 语言的形式定义
E→E+E | E*E | (E) | i
E(E)(E+E)(E*E+E) (i*E+E) (i*i+E) (i*i+i)
即有 E* (i*i+i), 所以符号串(i+i*i)是文法 G[E]的一个句子。
2.3.2 语言的形式定义
5．语言
文法G[S]产生的所有句子的集合称为文 法G所定义的语言,记为L(G[S])：
L(G[A])={ yxn | n≥1}
2.3.2 语言的形式定义
由此可见，从已知文法确定语 言的中心思想是：从文法的开始 符号出发，反复连续地使用规则 替换、展开非终结符，找出句子 的规律，用式子或自然语言描述 出来。
2.3.2 语言的形式定义
形式语言理论可以证明如下两点：
(1) 给定一种语言，能确定其文法， 但这种文法不是唯一的，即：L→G1
L(G[S])={x|S* x且x∈VT*} 由语言定义可知：
（1）当文法给定，语言也就确定。 （2）L(G)是VT* 的子集。即属于VT* 的符 号串 x 不一定属于L(G)。
2.3.2 语言的形式定义
例3 设有文法G[S] ：S→01 | 0S1 求该文法所描述的语言是什么？ 分析 由识别符号S出发，将推出一 些什么样的句子，也就是说，L(G[S]) 将由什么样的一些符号串所组成的集合， 找出其中的规律，用式子或自然语言描 述出来。
或G2或…
(2) 给定一个文法，就能从结构 上唯一确定其语言，即： G→L(G)；
文法和语言是密切相关的， 文法所定义的任一句型和句子, 都可以根据文法推导出来。
我们提出一个问题：
这种推导过程是否唯一？
同一个句型(句子)可以通过不 同的推导序列推导出来，这是因为 在推导过程中与所选择非终结符的 次序有关。