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

Question

我正在c#中编写一个shift reduce解析器。我看了一些解释它的文章，但没有一篇详细介绍。有人能给我指一下shift-reduce解析器的详细解释方向吗，比如它如何知道何时减少？

Answer 1

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

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