组合自上而下和自下而上的解析

Question

我正在为一种类似于C#的语言创建一个解析器，我认为自上而下和自下而上的组合是最好的。基本上，我希望在除个别语句之外的任何地方使用自上而下的解析。这样做的原因是操作的顺序--使用自下而上的解析器实现它们要容易得多，而使用自上而下的解析器实现其他所有东西也要容易得多。

它的实际实现如下:从自上而下的解析开始，像正常一样匹配。然后，在其中一个规则中，有一个规则被标记为“自下而上”。X标记从输入lex数组中取出，使用自底向上(也称为shift-reduce)“压缩”成单个标记，然后将该标记放入自上而下的匹配中。自上而下的比赛在剩下的比赛中继续进行。

我的问题/问题是如何获得这个数字X。我应该从输入令牌流中取出多少个令牌来进行shift-reduce操作？我最初的解决方案很简单--使用它们，直到到达分号。但是，像if语句这样的东西呢？在这些表达式的末尾没有分号。

我将举一个例子来说明我最初的计划，因为它可能听起来像是胡言乱语。假设语法集如下所示：

(top-down) statement ::= <expression> ";"
(bottom-up) expression =
    multiplication ::= <number> "*" <number>
    addition ::= <number> "+" <number>

然后它会像这样减少：

3 + 4 * 2 ;
((bottom-up) 3 + 4 * 2) ;
    3 + 4 * 2
    3 + multiplication
    addition
addition ;
statement

同样，我的问题是，如何获得要shift-reduce的令牌数量？我怎么知道我想要把所有的"3 +4* 2“都放入减速箱？

Answer 1

我怀疑，与其为“单个语句”切换策略，不如只为表达式这样做。这样，您不需要从流中取出固定数量的标记；您只需将语法定义为表达式的任何内容视为原子单元，并将其传递给子解析器。