手写的自上而下的解析器，它保留了语法的关联性/优先级？
手写的自上而下的解析器，它保留了语法的关联性/优先级？
提问于 2013-03-07 02:59:35
假设我有一个简单的语法，比如：
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如果我现在为它写一个解析器(psuedo-code)：
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它的关联性是错误的。
有人能把这事说清楚吗？一般来说，我如何编写一个手写的自上而下的解析器来保留语法中内置的关联性？
Stack Overflow用户
回答已采纳
发布于 2013-03-07 12:56:41
一种策略是将T上的递归替换为X上的迭代(一般来说，将一个运算符上的递归替换为下一个最高优先级运算符上的迭代)。在本例中，使用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只需要一次函数调用。如果你有一些右结合运算符(例如求幂)，你可以对它们使用递归方法。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/15255731
复制相关文章
相似问题
腾讯云开发者
