移位归约解析器如何知道何时进行归约？

Question

我正在用c#编写一个移位归约解析器。我看了一些解释它的文章，但没有一篇涉及太多细节。谁能告诉我shift reduce解析器的详细解释，比如它是如何知道何时进行reduce的？

Answer 1

解析器是一个状态机。每个状态都有一个动作表，它将下一个输入符号("token")映射到一个动作(shift、reduce a production、error或accept)。对于移位动作，有一个将输入符号映射到下一个状态的转换表。这两个表通常是组合在一起的，因为操作表条目中有一个状态编号的空间。

由于可能的令牌数量相对较少，因此令牌通常表示为小整数，而动作表是由当前状态和输入令牌索引的二维数组。如果需要考虑空间问题，则可以压缩表。