javascript - 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 表达式。

我的问题是，如果第二个表达式仅包含一个标记(如字符串)，则生成的解析器似乎只能识别一个或两个完整的表达式。例如:

File Version: 1.0

将被解析，或者

File Version: 1.0 "My String"

也会被解析，但是对于

File Version: 1.0 "My String" "Not parsed string"

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

我已经用 jison debugger 尝试过此代码并在jison page上本身，但两个页面显示相同的结果。

我对这个问题的建议是:

1. 一些词法分析器错误(正则表达式)
2. 一些语法错误(左右递归)
3. 解析器中缺少某些操作(类似于 { $$ = $1;} )
4. 我缺少的其他一些 bison/jison 魔法

我不是 ebnf 解析器大师，所以请让您的答案尽可能简单。

Answer 1

眼前的问题是你return来自FILEID生产。 return返回，因此解析以返回值终止。通常，语义规则应通过分配给变量$$来提供其结果。 。 (对于“单元规则”来说，这不是必需的，因为右侧只有一个符号；在执行操作之前，解析器会执行 $$ = $1 ，因此如果这就是您想要的，您可以将操作保留为您在两条 FILEID 规则中执行此操作。)

此外，您的expressions生产对 $2 没有任何作用，所以即使你解决了第一个问题，你仍然只会看到一个 e在结果中。

您的expressions生产也是不正确的，因为它需要一个 EOF每个 e 的 token ，除了来自基本情况的 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将首先使用\\.匹配 \"，但一旦这样做，它将找不到任何结束引号。然后它将回溯并尝试与 [^"] 匹配，这将匹配 \，允许报价被识别为收盘报价。