flex/bison 解析器能否以任何顺序接受一组中的最多一个标记

Question

在我的语言中，在特定点我需要接受一组标记中的至多一个标记。举个例子，一个带括号的表达式后面最多可以跟一个 !^& 以任何顺序，所以下面的两行应该是等价的

(foo)!^
(foo)^!

下面一个是非法的（一个token重复两次）

(foo)^!^

这是否可行，自然地用尽了 CFG 规则的所有可能性？词法 (flex) 或句法 (bison) 级别都可以。

Answer 1

除了枚举所有可能性之外，没有办法使用正则表达式或 CFG 来执行此操作，这是一个阶乘工作量。（通过分组，实际大小可以减小，但仍然是指数级的。）如果你只有一个实例，并且只有三个令牌，那么上市可能是最简单的解决方案。

但是如果有各种标记，并且您将来可能想扩展列表，允许所有标记组合可能更容易，但是将位图与标记列表相关联以便于检查重复，这可能会导致错误消息。

针对您提到的具体情况，这是一个简单的 flex 解决方案。（在我的原文中，我重复了很多代码，但我认为下面的代码更容易阅读。） <MODS> 开始条件由 [&^!] 的第一次出现触发，并用于吸收其余的他们;当遇到任何其他字符时，它被标记为重新扫描 (yyless(0)) 并返回修饰符的当前掩码。

%{
  // The MODS token has %type <ModMask>, and the associated
  // semantic value will be the union of the enum bits.
  typedef unsigned int ModMask;
  enum { MOD_HAT=1, MOD_BANG=2, MOD_AMP=4 };
  // This function maps a character to a modmask value.
  // A real implementation would use a lookup table. I just included
  // this definition so the snippet is usable.
  ModMask tokenToMask(unsigned char c) {
    return c == '^' ? MOD_HAT : 
           c == '!' ? MOD_BANG :
           c == '&' ? MOD_AMP : 0;
%}

%x SC_MODS

%%

[&^!]       { yylval.modmask = tokenToMask(yytext[0]; BEGIN(MODS); }
<MODS>[&^!] { ModMask m = tokenToMask(yytext[0];
              if (yylval.modmask & m) {
                yyerror("Duplicate modifier");
              }
              yylval.modmask |= m;
            }
<MODS>.|\n  { yyless(0); BEGIN(INITIAL); return MODS; }

flex/bison 解析器能否以任何顺序接受一组中的最多一个标记

Can a flex/bison parser accept at most one token from a set in any order

bison

yacc

flex-lexer

lex