将FIRST和FOLLOW集合编码为递归下降解析器

Question

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

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

注：所有的代码是伪代码

选项1）使用的地图，并通过他们的名字所有非终端映射到包含它们的前两分集和FOLLOW集：

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

这似乎是一个可行的选择，但我的解析器里面我会那么需要几分丑陋这样的代码来获取第一和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）c eate一类每一个非终端和具有第一和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

Answer 1

你并不真正需要的FIRST和FOLLOW集。您需要计算这些以获取分析表。如果LL（k）（表示在堆栈中看到non-terminal，在输入中看到token，其中action要应用并且应用哪个rule），或者如果（C | LA |）表示{<non-terminal, token> -> <action, rule>}， LR（K）（这意味着给state堆栈和输入token，这action拿，去哪个state。

后你得到这个表，你不需要第一，并遵循了。

---

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

这意味着，如果出现语法分析错误，语句级错误处理程序（PLEH）将尝试修复错误。如果无法解析，则停止。如果可以的话，语义分析器不应该知道是否有错误被修正，或者根本没有任何错误！

例如，您可以看看my compiler library。

---

关于短语级错误处理，您再次不需要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替换它以继续