c# - shift reduce 解析器如何知道何时减少？

Question

我正在用 c# 编写一个 shift reduce 解析器。我看了一些解释它的文章，但没有一篇详细说明。有人可以指出我对 shift reduce 解析器的详细解释的方向，比如它如何知道何时减少？

Answer 1

解析器是一个状态机。每个状态都有一个动作表，它将下一个输入符号（“令牌”）映射到一个动作（移位、减少生产、错误或接受）。对于移位动作，有一个转换表将输入符号映射到下一个状态。这两个表通常组合在一起，因为在动作表条目中有一个状态编号的空间。

由于可能的标记数量相对较少，因此标记通常表示为小整数，并且动作表是由当前状态和输入标记索引的二维数组。如果空间是一个问题，可以压缩表。