jison语法定义导致错误的token识别

Question

我最近找到了项目jison并修改了它网站上的计算器示例。 (http://zaach.github.io/jison/demos/calc/)

/* lexical grammar */
%lex
%%

"a"                   return 'TOKEN1'
"b"                   return 'TOKEN2'
<<EOF>>               return 'EOF'
.                     return 'INVALID'

/lex

%start letters

%% /* language grammar */

letters
    :
    | letters letter
    ;

letter
    : 'TOKEN1'
    | 'TOKEN2'
    ;

用上述语法定义生成的解析器解析字符串 "aaabbbaaba" 得到

Parse error on line 1:
aaabbbaaba
^
Expecting 'TOKEN1', 'TOKEN2', got 'INVALID'

很遗憾，我不知道为什么找不到 TOKEN1。删除令牌 INVALID 我得到解析错误

Unrecognized text.

我在 Issue with a Jison Grammar, Strange error from generate dparser 上找到了关联错误的描述，导致了类似的错误消息，但我在我的代码中找不到类似的内容。

这个问题的解决方案是什么？

Answer 1

好问题。

jison 的词法分析器生成器有两种模式：默认模式和稍微兼容 flex 的模式。您 select 后者通过将 %options flex 放在 %lex 行之后。

在默认模式下：

第一个匹配的模式获胜，即使后面的模式匹配更长的标记；和
以字母或数字结尾的模式有一个隐含的 \b 添加到它们，这限制了匹配以单词边界结束。

在flex模式下，模式不会改变，并且应用正常的flex first-longest规则。但是，生成的词法分析器会比较慢（见下文）。

所以在你的词法分析器定义中，"a" 不会匹配输入字符串中的第一个 a，因为生成的词法分析器实际上试图匹配 a\b -- 即 a 后跟单词边界。

您可以通过简单地将模式括在括号中来解决此问题：

("a")    { return 'TOKEN1'; }

或者使用字符 class 而不是引号：

[a]      { return 'TOKEN1'; }

或将 %options flex 添加到您的 %lex 部分。

作为解释

与 flex 不同，

jison 不构建单个 DFA 词法分析器。相反，它将每个 lex 模式转换为锚定的 javascript 正则表达式，并且在每次请求令牌时，它都会尝试所有模式，直到找到正确的匹配项。

为了实现 flex 第一个最长匹配规则，jison 生成的词法分析器需要为每个标记尝试每个正则表达式，因为它不知道哪个是最长的匹配直到它尝试了所有这些。 "first-match" 规则可能会快很多，尤其是当常用标记模式放在文件开头附近时。

不幸的是，在令牌可能是关键字或标识符的常见情况下，首次匹配规则很难使用，而恰好以关键字开头的标识符需要作为标识符进行匹配。对于最长匹配，将关键字放在第一位就足够了，因为带有关键字前缀的标识符会更长。但是对于第一次匹配，有必要限制关键字或标识符或两者以单词边界结束。

因此结合了上述两个规则，这意味着在 Identifier 模式之前列出关键字的正常模式仍然有效。单词边界测试可防止关键字模式出现虚假前缀匹配。

但是如果你有很多关键字，那仍然是很多模式，即使它们中的大多数很快就会失败。所以不要使用 flex 约定：

"do"                         { return DO; }
"end"                        { return END; }
/* ... */
[[:alpha:]][[:alnum:]_]*     { return "ID"; }

最好让关键字代表自己（以及其他固定标记，如运算符），因为这样可以将所有关键字和多字符运算符模式组合到一个正则表达式中：

/* Keywords and multicharacter operators in a single enormous pattern */
/* For jison mode, I added a manual \b because it won't be added 
 * automatically. In flex mode, that won't hurt, but it could be
 * removed.
 */
("do"|"else"|"end"|"if"|"then"|"while")\b|[<>!=]"=" { return yytext; }
[[:alpha:]][[:alnum:]_]*                        { return "ID"; }
[[:digit:]]+("."[[:digit:]]*)?                  { return "NUMBER"; }
[[:space:]]+                                    ;
/* All single character tokens use a fallback rule */
.                                               { return yytext; }

`<<EOF>>` 规则

许多 jison 语法有明确的 <<EOF>> 词法规则，return 是一些像 "EOF" 或 "END_OF_FILE" 的标记。此标记由显式增强开始产生式识别，其动作中有 return：

%lex
%%
// ...
<<EOF>> { return "EOF"; }
/lex

%start input
%%
input: start EOF { return ; }

start: /* The real start token */

这是 jison 特有的习语，许多人会认为 flex/bison 中的风格不佳。它允许生成的语法 return 一个实际值，即解析的结果。

不要只是将 <<EOF>> 规则添加到词法规则中。如果您提供自己的 EOF 令牌，您有责任在解析器中识别它。如果解析器没有匹配 EOF 标记的规则，解析将失败。

jison语法定义导致错误的token识别

jison grammar definition leads to wrong token recognition

parsing

yacc

flex-lexer

jison

作为解释

`<<EOF>>` 规则

jison语法定义导致错误的token识别

jison grammar definition leads to wrong token recognition

parsing

yacc

flex-lexer

jison

作为解释

<<EOF>> 规则

`<<EOF>>` 规则