3

假设我有一个简单的语法，例如：

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 ();

然后，当我调用parse_T输入时，3 + 4 + 5我会返回如下跟踪：

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

哪个具有错误的关联性。

任何人都可以清除这个吗？一般来说，我如何编写一个手写的自上而下的解析器来保留语法中内置的关联性？

4

1 回答 1

2

一种策略是T用迭代替换替换递归X（一般来说，用对下一个最高优先级运算符的迭代替换对运算符的递归）。在这种情况下，它有助于使用 EBNF 样式的符号

T -> X {+ X}

因为这样需要的迭代就变得很明显了：

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

wherePLUS()代表你为计算加法表达式所做的任何事情，例如构造一个树节点。

如果你把它应用到所有的操作符上，你基本上会得到一个对应的函数EXPRESSION，它只在处理时递归

PRIMARY -> '(' EXPRESSION ')'

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

于 2013-03-07T04:56:41.143 回答