编译原理第二章小结.ppt

本章重点介绍了语言的语法结构的形式描述、语法树以及文法的二义性, 主要内容有： 1. 设计一个文法定义一个已知的语言 (1) 文法是一个四元组 G=(VN,VT, P, S)， 文法四大要素中，关键是一组规则, 它定义（或描述）了一个语言的结构。 从文法定义可知, 文法对于程序设计者来 说，文法给出了语言的精确定义和描述。 第二章小结 (2) 分析已知语言句子的结构特征, 设计 出相应的一组规则，但不唯一。 (4) 若语言是无穷集合, 设计该语言的文 法一定是递归的。 本章小结 (3) 设计的文法必须能定义已知的语言, 不能超出或缩小所定义语言的范围。 分析 根据语言句子的结构特征，设计出相 应规则 例1. 给出语言 L2={an bm| m≥n≥1} 的文法 P2: S→AB L2={ab,abb,abbb, …aabb,aabbb,aabbbb, … aaabbb, aabbbb，…} A→aAb | ab B→bB |ε 本章小结 分析 根据语言句子的结构特征，设计出相 应规则 例2. 给出语言 L1={a2n+1|n≥0} 的文法 P1: A→aB | a P1：A→aAa | a 或 L1={a, aaa, aaaaa, aaaaaaa, aaaaaaaaa，…} B→aa | aBa 本章小结 本章小结 分析 根据语言句子的结构特征，设计出相应规则 例3. 给出语言L3={anbmck| n,m,k≥0}的文法 P3: A→aA | bB | cC |ε L3={ε,a,aa,aaa…,b,bb,bbb…,c,cc,ccc, …, ab,abb, …,bc,bcc，…} C→cC |ε B→bB | cC |ε 本章小结 L4={2,4,6,8,10,12,14,16,18,20,22,24,26,…} 例4. 写一个 文法,使其语言是正偶数的集合,每个偶数不以0开头。 P4: N→E′ | AE 分析 不以0开头的偶数集合中串的结构特征: A→D | AD′ E→0 | 2 | 4 | 6 | 8 D→1 | 2 | 3 | …| 9 D→0 | 1 | 2 | 3 |…| 9 E→2 | 4 | 6 | 8 本章小结 A → 0A1 | ε P : S → 1S0 | 0A1 | ε 例5. 给出语言L={1n0m1m0n | n,m≥0}的文法。 分析 根据语言句子的结构特征, 设计 出相应规则 L={ε,01,0011,…,10,1100,…,1010,100110, 110100} 本章小结 P : S → a | 0S0 | 1S1 例6. 给出语言L={ WaWt | W∈{0|1}* }，其中 Wt表示W的逆的文法。 分析 根据语言句子的结构特征，设计 出相应规则 L={a, 0a0, 1a1, 01a10, 10a01, 00a00, 11a11, 101a101, 110a011, 100a001, …} W={ε,0, 1 ,01, 10, 00, 11, 101, 110, 100, 111, …} 本章小结 2. 已知一个文法，确定该文法所定义的 语言。 (2) 给定一个文法，可根据语言和推导定 义推导出文法的句子，从而确定出该文法 所定义的语言。 (1) 文法所定义的语言 L(G[S])={x|S ?x且x∈VT*} * 本章小结 ①自然语言描述。 例如, L={x|x∈{a,b}+且x中a,b个数相同} ②式子描述。例如 L={a2nbb | n≥0}。 ③正规式描述。 (3) 语言可用 本章小结 例1 文法G[A]=({A},{a,b},{A→bA | a}, A) 所生成的语言是什么？ 分析 ∵ A?bA?bbA?bbbA?…?bnA?bna ∴ L(G[A])={ bna | n≥0 } 本章小结 例2 文法G[N]为: N →ND | D D →0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 (1) G[N]所生成的语言是什么？ (2) 给出句子0127