编译原理文法和语言答案

练习1. 文法和语言 1. 文法: Z → U0 | V1 U → Z1 | 1 V → Z0 | 0(1) 请写出全部由此文法描述的只含有四个符号的句子.(2) 该文法是 Chomsky 几型

1. 练习文法和语言 1. : 文法 Z→ U0 |V1 U→ Z1 |1 V→ Z0 |0 (1) . 请写出全部由此文法描述的只含有四个符号的句子 (2) Chomsky ? 该文法是几型文法 Answer ： (1) 1010, 0110, 1001, 0101 (2) 3 型文法 2. G: 给定前缀表示的表达式文法 (1) E→ -EE (2) E→ -E (3) E→ a (4) E→ b (5) E→ c --a-bc L(G) ?,;, 试问是否的句子若是请给出该句子所有可能的分析树若不是请说明理 . 由 Answer :--a-bc L(G) 是的句子。所有可能的分析树如下。 (1) (2) (3) 3. 考虑文法： S→ (L )| a L→ L, S| S (a ,( a, a) ) 写出句型的最左推导和最右推导。 Answer : (1) 最左推导： S(L)(L,S)(S,S)(a,S)(a,(L))(a,(L,S))(a,(S,S))(a,(a,S))(a,(a,a)) (2) 最右推导： S(L)(L,S)(L,(L))(L,(L,S))(L,(L,a))(L,(S,a))(L,(a,a))(S,(a,a))(a,(a,a)) 4. 考虑文法：