编译原理：计算Follow集合常见问题与解答

"计算Follow集合时容易出现的问题-西安交大“编译原理”答疑、作业、问题汇总" 在编译原理中，计算Follow集合是一项关键任务，它涉及到语法制导的解析过程。Follow集合用于确定在语法分析时，某个非终结符后面可能接续的符号。以下是针对计算Follow集合时可能出现的问题的详细解释： 1. **为什么要在某些情况下将FOLLOW(A)添加到FOLLOW(B)中？** 当文法中存在产生式`A → αB`或`A → αBβ`，且`β = *ε`（即`ε`属于`FIRST(β)`）时，我们需要将`FOLLOW(A)`添加到`FOLLOW(B)`中。这是因为如果`a`属于`FOLLOW(A)`，这意味着在解析过程中，非终结符`A`后面可能出现`a`。根据上下文无关文法的规则，`A`的出现可能导致`B`后面紧跟着`a`。 - 对于`A → αB`的情况，如果在输入串中`A`后面没有其他产生式能匹配，那么`B`后面必须是`a`，因为`A`的结束意味着`α`之后没有符号了。因此，`a`应该属于`FOLLOW(B)`。 - 对于`A → αBβ`，由于`β = *ε`，`β`可以为空，即`B`后面可以直接跟`a`。所以`a`同样应该被加入到`FOLLOW(B)`中。 2. **奇数集文法的构造** 题目要求构造一个文法，使得其语言为所有不以0开头的奇数集。一种可能的解决方案是这样的文法： ```markdown G[S]: S → A | BA | BCA B → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 C → B | 0 | CC A → 1 | 3 | 5 | 7 | 9 ``` 这里，`S`是起始符号，`A`生成奇数，`B`生成单个数字，而`C`用于处理`0`的出现。这样，通过`B`和`C`的组合，可以确保没有以0开头的奇数。 3. **最左推导和最右推导** 最左推导和最右推导是自底向上的解析方法。以文法`G[E]: E → T | E + T | E - T`, `T → F | T * F | T / F`, `F → (E) | i`为例，`i + i * i`的最左推导是： ```markdown E => E + T => T + T => F + T => i + T => i + T * F => i + F * F => i + i * F => i + i * i ``` 而最右推导是： ```markdown i + i * i => i + i * => i + i * F => i + F * F => i + T * F => i + T + T => i + E + T => i + E => E ``` 在最左推导中，我们总是优先替换最左边的非终结符。错误1)中，推导中混淆了推导规则和推导运算符号。 4. **构造语言文法** 给定语言`L4={1n0m1m0n|n,m≥0}`，可以使用以下文法来描述： ```markdown G[S]: S → 1S0 | A A → 0A1 | ε ``` 这个文法确保了`1`和`0`的交替出现，以及`m`与`n`的匹配。错误1)和错误2)的文法不能正确描述语言，因为它们没有强制`1`和`0`的正确分布，或者导致了不必要的符号序列。 5. **正规式到DFA的构造** 给定正规式`1(0|1)*101`，可以通过转换系统构造NFA再转化为DFA。正规式到NFA的构造通常涉及 Kleene 星号操作，然后通过子集构造法得到DFA。 这些例子涵盖了编译原理中的核心概念，如Follow集合的计算、文法构造、最左推导和最右推导，以及正规式到DFA的转换，这些都是编译器设计的基础部分。理解并掌握这些知识点对于学习编译原理至关重要。