编译原理作业2

Exercise 2.1

Given the following grammar:

$$S → ( L ) | a\
L → L , S | S$$

Construct a parse tree for the sentence

(a, ((a, a), (a, a)))

Exercise 2.2

Given the following grammar:

• bexpr → bexpr or bterm | bterm

• bterm → bterm and bfactor | bfactor
• bfactor → not bfactor | ( bexpr ) | true | false

Construct a parse tree for the sentence

not (true or false)

Exercise 2.3

Is the grammar:

$S → \ a \ S \ b \ S \ | \ b\ S\ a\ S\ | \epsilon$

ambiguous? Why?

该语法是二义性的，理由如下：

对于sentence abab，我们可以写出两种语法树，如下：

语法树1：

语法树2：

所以可以得到该语法是二义的。