题目1
题干
对以上上下文无关文法与对应的串：
- 给出这个串的一个最左推导
- 给出这个串的一个最右推导
- 给出这个串的一棵语法分析树
答
（1）对于文法S -> + S S | * S S | a和输入字符串+ * a a a
最左推导：
S -> + S S -> + * S S S -> + * a S S -> + * a a S -> + * a a a最右推导：
S -> + S S -> + S a -> + * S S a -> + * S a a -> + * a a a语法分析树：
（2）对于文法S -> S ( S ) S | ε和输入字符串( ( ) ( ) )
最左推导：
S -> S ( S ) S -> ε ( S ) S -> ( S ) S -> ( S ( S ) S ) S -> ( ε ( S ) S ) S -> ( ( S ) S ) S -> ( ( ε ) S ) S -> ( ( ) S ) S -> ( ( ) S ( S ) S ) S -> ( ( ) ε ( S ) S ) S -> ( ( ) ( S ) S ) S -> ( ( ) ( ε ) S ) S -> ( ( ) ( ) S ) S -> ( ( ) ( ) ε ) S -> ( ( ) ( ) ) S -> ( ( ) ( ) ) ε -> ( ( ) ( ) )最右推导：
S -> S ( S ) S -> S ( S ) ε -> S ( S ) -> S ( S ( S ) S ) -> S ( S ( S ) ε ) -> S ( S ( S ) ) -> S ( S ( ε ) ) -> S ( S ( ) ) -> S ( S ( S ) S ( ) ) -> S ( S ( S ) ε ( ) ) -> S ( S ( S ) ( ) ) -> S ( S ( ε ) ( ) ) -> S ( S ( ) ( ) ) -> S ( ε ( ) ( ) ) -> S ( ( ) ( ) ) -> ε ( ( ) ( ) ) -> ( ( ) ( ) )语法分析树：
题目2
题干
为题目1中的每一个文法设计一个预测分析器。你可能先要对文法进行提取左公因子或消除左递归的操作。
答
对于文法S -> + S S | * S S | a：
parse_S() { // S -> + S S | * S S | a token = nextToken(); switch(token) if (token == "+") { move token; parse_S(); parse_S(); } if (token == "*") { move token; parse_S(); parse_S(); } if (token == "a") { move token; } else error("..."); }对于文法S -> S ( S ) S | ε，先消除左递归得到新文法：
S' -> ( S ) S S' | ε S -> S'再写递归下降的预测分析器：
parse_S() { // S -> S' token = nextToken(); switch(token) if (token == "(") { parse_S_prime(); } else if (token in [$, (, )]) { // ε } else error("..."); } parse_S_prime() { // S' -> ( S ) S S' | ε token = nextToken(); switch(token) if (token == "(") { move token; parse_S(); move token; parse_S(); parse_S_prime(); } else if (token in [$, (, )]) { // ε } else error("..."); }题目3
题干
计算题目1中的各个文法的FIRST和FOLLOW集合。你可能先要对文法进行提取左公因子或消除左递归的操作。
答
（1）对于文法S -> + S S | * S S | a
该文法没有左公因子和左递归。
（2）对于文法S -> S ( S ) S | ε
对该文法消除左递归后得到新文法：
S' -> ( S ) S S' | ε S -> S'题目4
判断题目1中的文法是否为LL（1）文法，如果是则填写其LL（1）语法分析表。
答
（1）对于文法S -> + S S | * S S | a
该文法是LL（1）文法，语法分析表如下：
（2）对于文法S -> S ( S ) S | ε
该文法不是LL（1）文法，因为存在左递归。
题目5
为下面的语言设计文法。
（1）所有由0和1组成的并且每个0之后至少跟着一个1的串的集合。
（2）所有由0和1组成的回文（palindrome）的集合，也就是从前面和从后面读结果都相同的串的集合。
答
（1）
S -> 0 1 S | 1 S | ε（2）
S -> 0 S 0 | 1 S 1 | 0 | 1 | ε题目7
（1）对于以上两个文法，分别画出其LR（0）项集的状态转换图（即DFA）。
（2）判断它们是否为LR（0）文法，是否为SLR（1）文法，给出理由。
（3）如果是LR（0）文法或SLR（1）文法，填出其LR语法分析表。
答
（1）对于文法S -> S S + | S S * | a，得到增广文法
0 : S' -> S $ 1 : S -> S S + 2 : | S S * 3 : | a对于文法S -> a S a | a a，得到增广文法
0 : S' -> S $ 1 : S -> a S a 2 : | a a（2）对于文法S -> S S + | S S * | a
LR（0）分析表：
是LR（0）文法，因为LR（0）分析表中无冲突。
SLR（1）分析表：
是SLR（1）文法，因为SLR（1）分析表中无冲突。
对于文法S -> a S a | a a
LR（0）分析表：
不是LR（0）文法，因为LR（0）分析表中，状态4输入符号为a时有移进-规约冲突。
SLR（1）分析表：
不是SLR（1）文法，因为SLR（1）分析表中，状态4输入符号为a时仍有移进-规约冲突。
（3）见（2）。
