Exercises for Chapter 2

2.1 Consider the context-free grammar
S → S S + | S S * | a
a) Show how the string aa+a* can be generated by this grammar

1. a是S，因为S→ a
2. aa+是S，因为 S → S S +，而a 是S
3. aa+a*是S，因为 S → S S *,而且aa+是S , a是S
   

b) Construct a parse tree for the string


c) What language is generated by this grammar? Justify your answer.

应该是任意数目a和+＊相互交叉，但是+*的数目之和永远比a少1，另外+*不可能出现在字符串的最开始，但可以出现在最后。

最简单的情况a，+*比a少一，不管采用哪一种产生式，永远是多了2个a,再多了一个+或者*，因此还是a比+*多一个。




2.2 What language is generated by the following grammars? In each case justify your answer.

a) S → 0 S 1 | 0 1

任意个0后跟相同数目的1，S -> 0 1 ，如果用它去替换 S → 0 S 1中右边的S，得到 0 0 1 1 ，继续替换，每次前面增加一个0，后面同时增加一个1

b) S → + S S | - S S | a
类似于第一题，但是+-只能出现字符串最开始，而不能出现在最后

c) S → S ( S ) S | ε
任意括号组合
1. S可以是一个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S ) ，第一个S可以取ε，S → ( S ), S可以取ε，S → ()
2. S可以是两个括号，因为S可以取ε，则S → S ( S ) S 得到 S → S ( S )，S → S( ),此时如果S取一个括号，则得到两个括号
3.同理,S可以取任意多个的括号连接
4.S → ( S )可以取得一层嵌套，又根据S → ( S )，依次可以知道可以任意增加嵌套，每一层内部根据3可以得到任意数目的嵌套
5.因此，任意嵌套、任意数目的括号可以得到
该文法具有二义性，例如，对token字符串()()，可以有两棵解析树：




d) S → a S b S | b S a S | ε
相同的数目的a b任意组合，因为字符串可以为空，或者是ab,ba，这个时候ab的数目还是一样。不管选择S → a S b S还是b S a S，总是在原先的S上插入a和 b，因此ab字符的数目永远一样，由于可以选择，a或者b在前，所以可以任意组合，只要字符数目一样


e) S → a | S + S | S S | S * | ( S )
任意数目的连续的a中间(可以用括号括起）穿插+或者*，其中+和*不连续。可以看作一个+或者*的表达式，其中+和*的操作数可以是任意数目的a或者是()括起的子表达式。但是*可以出现在结尾。这个文法显然是具有二义性的，例如字符串aaaaa就可以有很多解析树。同样aa+aaa+aaaaa这样的字符串也可以有很多解析树。

2.3 which of the grammar in Exercise 2.2 are ambiguous?

如上

2.4 Construct unambiguous context-free grammars for each of the following languages. In each case show that your grammar is correct.

a) Arithmetic expressions in postfix notation.
expr → expr expr + | expr expr - | expr expr * | expr expr /| (expr) | digit

对后缀表达式来说，不可能产生结合性的问题，也没有优先级的问题，对四则运算总是两个操作数加上一个操作符，例如12+3+，3肯定属于它后面一个加号所要应用的操作数，不可能属于前面一个加号，优先级问题也一样。



b) Left-associative lists of identifiers separated by commas.
list → list , id | id


c) right-associative lists of identifiers separated by commas.
list → id , list | id

d) Arithmetic expressions of integers and identifiers with the four binary operators +,-,*,/
expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → integer | id | (expr)


e) Add unary plus and minus to the arithmetic operators of (d).

expr → expr + term | expr - term | term
term → term * factor | term / factor | factor
factor → + integer | - integer | integer | id | (expr)

*2.5 a) Show that all binary string generated by the following grammar hava values divisible by 3. Hint. Use induction on the number of nodes in a parse tree.

num → 11 | 1001 | num 0 | num num

写出计算数字值的语意动作

num → 11 {num.value = 3;} （1）
| 1001 {num.value = 9;} （2）
| num 0 {num2.value = num1.value*2;} （3）
| num num {num3.value = num1.value*2n + num2.value;} （4）

<1>
我们可以看到，如果一个字符串是通过（1）产生的，那么则为3，所以num为3的倍数，如果一个字符串是通过（2）产生的，即为9，所以也是3的倍数

<2>

现在假设现有的任何num字符串全部都是3的倍数，那么还有两种方法可以产生新的字符串
产生式(3) :由于现有所有的num都是3的倍数，因此num1.value是3的倍数，num1.value*2也是3的倍数，也就是说用产生式（3）产生的所有新的字符串都是3的倍数
产生式(4):由于现有所有的num都是3的倍数，因此num1.value和num2.value都是3的倍数，因此num1.value*2n也是3的倍数（n代表num2的长度），num1.value*2n + num2.value也是3的倍数，也就是说用产生式（4）产生的所有新的字符串都是3的倍数

<3>
从<1>得知，（1）和（2）产生的字符串都是3的倍数，从<2>得知，任何在3倍数的字符串基础上产生的新字符串都是3的倍数，所以所有该文法产生的字符串都是3的倍数，也就是能够被3整除。


b) Does the grammar generate all binary strings with values divisible by 3?

3的7倍为21=16+4+1，二进制表达方式为10101,无法用上面的文法产生