1

这是我问过的上一个问题How to encode FIRST & FOLLOW sets inside a compiler的后续问题，但这个问题更多的是关于我的程序的设计。

我正在通过编写递归下降解析器来实现编译器的语法分析阶段。我需要能够利用 FIRST 和 FOLLOW 集，以便更有效地处理源程序语法中的错误。我已经为我的所有非终端计算了 FIRST 和 FOLLOW，但是我无法决定将它们逻辑地放置在我的程序中的哪个位置以及这样做的最佳数据结构是什么。

注意：所有代码都是伪代码

选项 1) 使用映射，并将所有非终端按其名称映射到包含其 FIRST 和 FOLLOW 集的两个集合：

class ParseConstants
    Map firstAndFollowMap = #create a map .....
    firstAndFollowMap.put("<program>", FIRST_SET, FOLLOW_SET)
end

这似乎是一个可行的选择，但是在我的解析器内部，我需要像这样的丑陋代码来检索 FIRST 和 FOLLOW 并传递给错误函数：

#processes the <program> non-terminal
def program
    List list    = firstAndFollowMap.get("<program>")
    Set FIRST    = list.get(0)
    Set FOLLOW   = list.get(1)  

   error(current_symbol, FOLLOW)
end

选项 2) 为每个非终端创建一个类并具有 FIRST 和 FOLLOW 属性：

class Program
    FIRST    = .....
    FOLLOW = .... 
end

这导致代码看起来更好一点：

#processes the <program> non-terminal
def program
   error(current_symbol, Program.FOLLOW)
end

这是我想到的两个选项，我很想听听任何其他关于如何编码这两个集合的建议，以及对我发布的两种方式的任何批评和补充都会有所帮助。谢谢

我也在这里发布了这个问题：http: //www.coderanch.com/t/570697/java/java/Encode-FIRST-FOLLOW-sets-recursive

4

1 回答 1

2

您实际上并不需要 FIRST 和 FOLLOW 集。您需要计算这些以获取解析表。那是一个 if LL(k) 表（这意味着在堆栈和输入中{<non-terminal, token> -> <action, rule>}看到 a ，取哪个，如果应用，哪个应用），或者一个if (C|LA|)LR(k) 表（其中表示在堆栈和输入中给出，取哪个并转到哪个。non-terminaltokenactionrule{<state, token> -> <action, state>}statetokenactionstate

拿到这张表后，就不再需要 FIRST 和 FOLLOWS 了。

如果您正在编写语义分析器，则必须假设解析器工作正常。短语级错误处理（意味着处理解析错误）与语义分析完全正交。

这意味着在解析错误的情况下，短语级错误处理程序 (PLEH) 将尝试修复错误。如果不能，解析停止。如果可以的话，语义分析器不应该知道是否存在已修复的错误，或者根本没有任何错误！

您可以查看我的编译器库以获取示例。

关于短语级别的错误处理，您再次不需要 FIRST 和 FOLLOW。现在让我们谈谈 LL(k)（只是因为关于 LR(k) 我还没有考虑太多）。构建语法表后，您有很多条目，就像我说的那样：

<non-terminal, token> -> <action, rule>

现在，当您解析时，您将获取堆栈中的任何内容，如果它是一个终端，那么您必须将它与输入匹配。如果不匹配，短语级错误处理程序将启动：

角色一：处理丢失的终端——只需在词法分析器中生成您需要的类型的假终端，然后让解析器重试。你也可以做其他事情（例如在输入中提前检查，如果你有你想要的标记，从词法分析器中删除一个标记）

如果您从堆栈中得到的是非终结符 ( T)，则必须查看您的词法分析器，获取lookahead并查看您的表。如果该条目<T, lookahead>存在，那么您就可以开始了。按照操作并从堆栈中推入/弹出。但是，如果不存在这样的条目，则短语级错误处理程序将再次启动：

作用二：处理意外的终端——你可以做很多事情来通过这个。你做什么取决于什么T和lookahead是什么以及你对语法的专业知识。

你可以做的事情的例子是：

  • 失败！你无能为力
  • 忽略此终端。这意味着您推入lookahead堆栈（T再次推回之后）并让解析器继续。解析器将首先匹配lookahead，将其丢弃并继续。示例：如果您有这样的表达式：*1+2/0.5，您可以通过这种方式删除意外*。
  • 更改lookahead为可以接受的内容，推T后重试。例如，这样的表达式：5id = 10;可能是非法的，因为您不接受以数字开头的 id。您可以将其替换_5id为例如以继续
于 2012-03-18T19:20:01.760 回答