parsing - 保留语法关联性/优先级的手写自上而下的解析器？

Question

假设我有一个简单的语法:

X -> number
T -> X
T -> T + X

例如 3 + 4 + 5 将解析为:

     +
    / \ 
   +   5
 /  \
3    4

这具有“内置”到语法中的 + 的左右结合性。

它是普通的 LR(1)，但是假设我想对其进行手写自上而下的解析。

我不能这样做，因为它是递归的，所以让我们把它左分解:

X  -> number
T  -> X T'
T' -> + X T'
T' -> e    // empty

如果我现在为它写一个解析器(伪代码):

parse_X:
    if lookahead is number
        return pop_lookahead

parse_T:
    return (parse_X, parse_T')

parse_T':
    if lookahead is +
         pop_lookahead
         return (parse_X, parse_T')
    else
         return ();

然后，当我在 3 + 4 + 5 的输入上调用 parse_T 时，我得到如下跟踪:

parse_T
(parse_X, parse_T')
(3, parse_T')
(3, (parse_X, parse_T'))
(3, (4, parse_T'))
(3, (4, (parse_X, parse_T')))
(3, (4, (5, ())))

看看解析是如何“向后”的。从这样的解析中“天真地”构建的树看起来像:

     +
    / \ 
   3   +
      / \
     4    5

关联性错误。

谁能解决这个问题？一般来说，我如何编写手写的自上而下的解析器来保留语法中内置的关联性？

Answer 1

一种策略是用 X 上的迭代替换 T 上的递归(一般来说，用下一个最高优先级运算符上的迭代替换运算符上的递归) .它有助于使用 EBNF 风格的符号，在这种情况下

T -> X {+ X}

因为那时所需的迭代变得显而易见:

parse_T:
  val = parse_X
  while lookahead is +
     pop_lookahead
     val = PLUS(val, parse_X)
  return val

其中 PLUS() 代表您对加法表达式进行求值的任何操作，例如构造一个树节点。

如果您将此应用于所有运算符，您最终会得到一个与 EXPRESSION 相对应的函数，该函数仅在处理时递归

PRIMARY -> '(' EXPRESSION ')'

这种方法导致了一个相当快的表达式解析器；使用朴素递归下降来解析表达式的常见反对意见之一是，如果您有多个级别的运算符优先级，您可能很容易需要 20 次左右的嵌套函数调用来解析每个 PRIMARY，这可以得到相当慢的。使用迭代方法，通常每个 PRIMARY 只需要一个函数调用。如果您有一些右结合运算符(例如求幂)，您可以对它们使用递归方法。