HNU 编译系统 作业3

题目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）。