1

（我用的是Yecc，一个类似Yacc的Erlang解析器生成器，所以语法和Yacc不一样）

问题很简单，假设我们想要解析一个 lispy 语法，我想要匹配表达式列表。表达式列表是用空格分隔的表达式列表。

在 Erlang 中，[1,3,4]是一个列表并++连接两个列表。

我们想要匹配这个1 (1+2) 3。expression将匹配 1、(1+2) 和 3。因此，我在列表中匹配，然后再匹配一个表达式，如果没有匹配，我结束匹配单个表达式。这会递归地构建一个列表。

expressionlist -> expressionlist expression : '$1' ++ ['$2'].
expressionlist -> expression : ['$1'].

但我也可以这样做（颠倒顺序）：

expressionlist -> expression expressionlist : ['$1']  ++ '$2'.
expressionlist -> expression : ['$1'].

这两个似乎都有效，我想知道是否有任何区别。

带分隔符

我想匹配{name = albert , age = 43}。propdef匹配name = value。所以这是同样的问题，但有一个额外的分隔符,。与第一个问题有什么区别吗？

proplist -> propdef ',' proplist  :  ['$1'] ++ '$3'.
proplist -> propdef  :  ['$1'].
proplist -> '{' proplist '}' :  '$2'.
proplist -> '{' '}' :  [].

%% Could write this
%% proplist -> proplist ',' propdef :  '$1' ++ ['$3'].

谢谢你。

4

1 回答 1

2

由于 Yecc 是一个 LALR 解析器生成器，因此使用左递归或右递归并不重要。在过去，人们更喜欢 Yacc/Bison 和类似工具中的左递归，因为它允许解析器不断减少而不是将所有内容都移到堆栈上，直到列表末尾，但是现在，堆栈空间和速度不是那样很重要，所以你可以选择最适合你的东西。（请注意，在 LL 解析器中，左递归会导致无限循环，因此对于此类解析器，右递归是必要的。）

对于上面的示例，更重要的是左递归版本中的 '$1' ++ ['$2'] 将导致二次时间复杂度，因为“表达式列表”部分将会越来越长。当您使用 ++ 运算符时，您永远不应该在左侧有增长的组件。如果您解析包含数千个元素的列表，这种复杂性会伤害您。使用正确的递归版本， ['$1'] ++ '$2' 将为您提供线性时间，即使解析器必须在开始减少之前将整个列表转移到堆栈上。您可以尝试这两个版本并解析一个非常长的列表以查看差异。

在“propdef ',' proplist”中使用分隔符不会改变问题。

于 2013-07-09T09:10:07.857 回答