parsing - 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。删除 token INVALID 后，我收到解析错误

Unrecognized text.

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

这个问题有什么解决方案吗？

Answer 1

好问题。

jison的词法分析器生成器有两种模式:默认模式和稍微多一点的flex - 兼容模式。您可以通过放置 %options flex 来选择后者。 %lex之后线。

在默认模式下:

1. 第一个匹配的模式获胜，即使后面的模式匹配更长的标记；和

2. 以字母或数字结尾的模式具有隐式 \b添加到它们中，这限制了匹配在单词边界上结束。

在 flex模式，模式不会改变，并且应用正常的柔性第一最长规则。但是，生成的词法分析器会较慢(见下文)。

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

您只需用括号将模式括起来即可解决此问题:

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

或者使用字符类而不是带引号的字母:

[a]      { return 'TOKEN1'; }

或添加%options flex给您%lex部分。

---

作为解释

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

实现flex第一个最长匹配规则，jison -生成的词法分析器需要尝试每个标记的每个正则表达式，因为它无法知道哪个是最长的匹配，直到它尝试了所有这些。 “第一个匹配”规则可能会快很多，特别是如果常见的标记模式放在文件开头附近。

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

因此，上述两个规则的组合，这意味着在 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>>词法规则，返回一些标记，如 "EOF"或"END_OF_FILE" 。该 token 由显式增强启动生产方式识别，其中有 return在其行动中:

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

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

start: /* The real start token */

这是一个jison -特定的习语，许多人会认为 flex/bison 中的风格很差。它允许生成的语法返回一个实际值，即解析的结果。

不要只添加 <<EOF>>规则遵循词汇规则。如果您自己提供EOF token，你负责在解析器中识别它。如果解析器没有与 EOF 匹配的规则 token ，解析将失败。