Jison解析器在第一条规则后停止

Question

我有一个简单的文件格式，我想用jison解析器生成器解析。这个文件可以由任意顺序和数量的多个表达式组成。这是解析器的jison文件：

/* lexical grammar */
%lex

%%

\s+                   /* skip whitespace */
\"(\\.|[^"])*\"          return 'STRING'

File\s*Version\s*\:      return 'FILEVERSION'
[0-9]+("."[0-9]+)?\b     return 'NUMBER'
<<EOF>>                  return 'EOF'
.                        return 'INVALID'

/lex

%start expressions

%% /* language grammar */

expressions
    : EOF
    | e expressions EOF
    ;

e
    : STRING
    | FILEID 
    ;

FILEID
    : FILEVERSION NUMBER { return $1 + $2; }
    ;

为了简单起见，我将文件缩短为只有字符串和文件id表达式。

我的问题是，如果第二个表达式只包含一个类似令牌的字符串，那么生成的解析器似乎只能识别一个或两个完整的表达式。例如：

文件版本： 1.0

将被解析，或者

文件版本：1.0“我的字符串”

也将被解析，但对于

文件版本：1.0"我的字符串""未解析的字符串"

最后一个字符串不会被解析。

我用jison调试器和jison页面本身尝试了这段代码，但两个页面都显示了相同的结果。

我对这个问题的建议是：

1. 一些lexer错误（regex）
2. 一些语法错误（左-右-递归）
3. 解析器中缺少一些操作（有点 { $$ = $1；}）
4. 我错过了其他野牛/吉森魔法

我不是ebnf解析器大师，所以请尽可能简单地回答。

Answer 1

直接的问题是，您从FILEID产品中返回return返回，因此解析将以返回的值终止。通常，语义规则应该通过分配给变量$来提供结果。（对于右边只有一个符号的“单元规则”来说，这是不必要的；在执行操作之前，解析器会执行$=$1，因此如果这是您想要的，您可以像在两个FILEID规则中一样将操作省略。）

此外，你的表达式产品对$2没有任何作用，因此即使你解决了第一个问题，你仍然只能在结果中看到一个e。

您的表达式产品也不正确，因为除了基本案例中的EOF外，每个e都需要一个EOF标记。考虑产品是如何工作的：

expressions -> e expressions EOF
            -> e e expressions EOF EOF
            -> e e e expressions EOF EOF EOF
            -> e e e EOF EOF EOF EOF

就个人而言，我建议使用左递归而不是右递归。像jison这样的自底向上的解析器更喜欢左递归，它通常会导致更自然的语义规则，如本例所示。

最后，当您实际到达输入的末尾时，需要返回最终值。在jison中，这通常需要一个明确的开始规则，其语义动作是return。

因此，考虑到所有这些，让我们尝试一下：（我更改了一些非终端的名称，并使用小写的FILEID，因为传统上，非终端使用小写，终端使用大写）

%start prog
%%
prog   : exprs EOF          { return $1; }
       ;
exprs  :                    { $$ = []; }
       | exprs expr         { $$.push($2); }
       ;
expr   : file_id
       | STRING
       ;
file_id: FILEVERSION NUMBER { $$ = $1 + $2; }
       ;

关于匹配字符串的正则表达式，请注意：

\"(\\.|[^"])*\"          return 'STRING'

虽然它显然在javascript中工作（主要是；见下文），但它在flex（或与Posix兼容的正则表达式库）中会出现错误。它主要在javascript中工作，因为javascript正则表达式替换操作符|是有序的；如果第一个备选方案匹配，则永远不会尝试第二个备选方案，除非模式的其余部分无法匹配（在这种情况下，将触发错误）。

但在（f）lex中，交替操作符会注意到所有匹配的替代项，并最终选择可能最长的匹配项。结果是当匹配“\\”时。。。“，flex将使用[^”]匹配第一个\，然后使用\\，匹配令牌直到第三个引号 以匹配\“。这样它就可以继续寻找收盘报价。

编写正则表达式很容易，这样它就可以使用任意一种语义，我强烈建议您这样做，以防您想要迁移到另一个解析器生成器，只需确保\与[^]不匹配即可：

\"(\\.|[^\\"])*\"        return 'STRING'

此更改还将修复一个微妙的错误，即使在javascript中，“\”如果是输入中的最后一个字符串，则被视为有效的字符串标记。在本例中，javascript将首先使用\\匹配\“，但一旦匹配，它将找不到任何收盘报价。然后，它将回溯并尝试与[^”]匹配，后者将匹配\，从而允许该报价被识别为收盘报价。