如果 Bison 规则存在递归，如何决定何时更改状态？

Question

我想处理这个字符串：(ads AND qwe) OR zxc ... <KEYWORD> 我在 Flex 中有一个开始条件，它可以捕获 'any name'、OR、AND 和 'any word'（以捕获无效词）。 <KEYWORD>可以是：SLEEP、WIDTH等

Bison 规则是：

stmt:
     one_rule { }
   | one_rule AND stmt { }
   | one_rule OR stmt { }
   | '(' stmt ')' { }

在我的例子中，KEYWORD 也遇到了 'any name' 正则表达式，因为我不更改状态，但是如果我更改其中一个正则表达式中的状态，则只有第一部分有效((ads AND qwe))

更新： 添加了详细示例

有效输入：

1. ((ads AND qwe) OR zxc) SLEEP 
2. ads AND qwe AND zxc WIDTH 
3. ads AND qwe

输入无效：

1. ((ads AND qwe) OR zxc) BAD_KEYWORD 
2. ads AND qwe AND zxc AND
3. ads AND qwe OR

FLEX

<A>AND {
   position += yyleng;
   return AND;
}
<A>OR {
   position += yyleng;
   return OR;
}
<A>{NAME} {
   position += yyleng;
   yylval.str = strdup(yytext);
   return NAME;
}
<A>{ANY_TEXT} {
   position += yyleng;
   yylval.str = strdup(yytext);
   return ANY_TEXT;
}
<B>WIDTH {
   position += yyleng;
   return WIDTH;
}
<B>SLEEP {
   position += yyleng;
   return SLEEP;
}

在我的实现中，关键字 被捕获在 A 状态附近。我需要了解可以将状态更改为 B

的点

Answer 1

您的意图似乎是允许某些词（例如 SLEEP 或 WIDTH）用作关键字或搜索词，具体取决于它们出现的位置。其他词，例如 AND 和 OR，总是特殊的，所以如果它们出现在不应该出现的地方，就会产生语法错误。

如果以上正确，那么语法应该可以识别：

word AND other        -- statement with two rules
word AND SLEEP        -- also a statement with two rules
word AND other SLEEP  -- statement with two rules and a modifier ("keyword")

但是，以下是不合法的：

word AND AND          -- AND cannot be a rule
word AND other AND    -- AND cannot be a modifier

因此，关键字SLEEP和WIDTH就是通常所说的"contextual"或"semireserved"词。

这种语言风格确实给基于 Bison/Flex 的语法带来了一些困难，任何尝试编写 SQL 解析器的人都会知道。解析器生成器 Lemon，其主要用例是生成 Sqlite 解析器，为此特定情况实现了一个特殊的 %fallback 声明。然而，Yacc 和 Bison（或者我知道的任何其他解析器生成器）都没有类似的功能，因此需要在语法中手动实现。

虽然理论上可以将逻辑放入词法分析器中，但正如您似乎正在考虑的那样，经验表明此类解决方案难以编写、调试和维护，主要是因为它们最终会重现很多词法分析器中的解析器逻辑。这种逻辑重复是脆弱的；语法的变化可能需要伴随着词法分析器中复杂的逻辑重新排列，如果这两个部分不同步，有效的句子可能会神秘地被拒绝。

将所有逻辑放在解析器中的替代方案也并非没有问题，但通常更易于维护和调试。基本结构是在词法分析中始终识别关键字本身（因此不需要开始条件），然后在解析器中将关键字折叠回 "identifier" 类别。

这是一个简单的例子，基于上面关于你的语法的理论：（我省略了 "ANY_TEXT" 因为甚至没有暗示它的目的是什么。）

%left OR
%left AND
%token SLEEP WIDTH
%%
expr: name
    | '(' expr ')'
    | expr AND expr
    | expr OR expr
stmt: expr
    | expr WIDTH
    | expr SLEEP
name: NAME
    | WIDTH { $$ = strdup("WIDTH"); }
    | SLEEP { $$ = strdup("SLEEP"); }

最后一组作品可能需要一些解释。第一个简单地允许 NAME 用作 name，这是合乎逻辑的。另外两个将上下文关键字 WIDTH 和 SLEEP 折叠回 name 在它们不能用作关键字的上下文中。（必须注意不要在只有 NAME 合法的产生式中使用 name。这种语法不会发生这种情况，但在一般情况下需要仔细考虑。如果你弄错了，你很可能会得到一个解析冲突错误，然后你可以使用-v报告来帮助你调试语法。）

将关键字转换为name时的语义操作旨在保持不变性，即name的语义值始终是动态分配的字符串。因此，它复制了词法分析器对 NAMEs 的操作，即创建令牌的动态分配副本。如果用作 name 的 SLEEP 的语义值是一个字符串文字，那么当您没有不再需要字符串。另一方面，如果你在词法分析器中执行 strdup，那么你需要记住在任何语法生成中显式 free() SLEEP 和其他关键字标记的语义值它们不会变成 name。上面显示的样式并不常见——大多数人似乎更喜欢跳过各种环节以避免看起来不必要的东西 strdup——但它是迄今为止最容易使用的样式，还有一些额外的 strdup() 调用在你的解析过程中不会被注意到（只要你这样做，事实上，free() 所有动态分配的字符串，当你不再需要它们时）。

如果 Bison 规则存在递归，如何决定何时更改状态？

How to decide when change the state if there is recursion in Bison rule?

c

recursion

bison

flex-lexer