2

我最近找到了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没有正确找到。删除令牌无效后，我收到解析错误

Unrecognized text.

我发现了一个关联错误的描述，导致了类似的错误消息，关于问题与 Jison 语法，来自生成 dparser 的奇怪错误，但我在我的代码中找不到类似的东西。

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

4

1 回答 1

4

好问题。

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

在默认模式下：

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

  2. 以字母或数字结尾的模式\b添加了一个隐式，这将匹配限制在单词边界上。

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

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

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

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

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

[a]      { return 'TOKEN1'; }

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

通过解释

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

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

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

因此，上述两个规则的组合，这意味着在模式之前列出关键字的正常模式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"or的记号"END_OF_FILE"。这个标记被一个明确的增强的开始产生式识别，return它的作用是：

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

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

start: /* The real start token */

这是一个特定的jison成语，许多人会认为flex/bison. 它允许生成的语法返回一个实际值，这是解析的结果。

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

于 2015-02-21T03:30:20.073 回答