2

我正在尝试用野牛描述语法，但我不确定是否可以做到。我的预期语法是这样的：

%token A B C D SEP

%%

items          : /* empty */
               | items_nonempty
               ;

items_nonempty : item
               | items_nonempty SEP item
               ;

item           :       B
               |       B       SEP D
               |       B SEP C
               |       B SEP C SEP D
               | A SEP B
               | A SEP B       SEP D
               | A SEP B SEP C
               | A SEP B SEP C SEP D
               ;

" items" 是一个（可能为空的）元素序列item，由SEP标记分隔。

每个项目最多包含 4 个标记 ( A B C D)，按此顺序，以 . 分隔SEP。项目中的A、C和D标记是可选的。

请注意在每个项目内以及项目本身之间重复使用相同的分隔符标记 SEP。

我希望预期的语法很清楚。我认为它是明确的，但我很不确定它是否被限制到可以被野牛解析——不幸的是，我的解析器知识相当生疏。

使用给定的语法，bison 报告 4 个移位/减少冲突。查看“输出”，我了解它们出现的位置以及原因；但我不知道如何（以及是否）可以编写预期的语法来摆脱 S/R 冲突。

我不愿意使用%expect声明。同样，我不愿意让我的扫描仪使用分隔符标记，而不是将它们传递给解析器。

任何有关如何清理此语法的提示将不胜感激。

4

4 回答 4

1

基本问题是，所写的语法需要两个前瞻标记来决定它何时找到 an 的结尾并因此可以减少它，或者在它认为是前瞻的下一个字符item之后是否还有当前项目的另一部分。SEP

您可以尝试多种方法

  • 使用 btyacc 或 bison 的 GLR 支持来有效地获得更多的前瞻。

  • 编写语法以接受单个项目的任意列表，然后使用 post-pass 将它们重新组合成 1-4 个项目的集合，其中至少 1B并拒绝格式错误的集合（这是 Gunther 的建议）

  • 使用扫描仪做更多的前瞻——而不是返回简单的SEP令牌，返回SEP_BEFORE_A_OR_B或SEP_NOT_BEFORE_A_OR_B取决于后面的下一个令牌SEP是什么。

  • 在扫描仪中组合标记——返回SEP_C和SEP_D作为单个标记（分隔符后跟一个C或D）

于 2012-04-06T00:24:11.120 回答
0

语法确实是明确的，它是 LL(7) 并且（未经验证）我相信它是 LR(2)，甚至可能是 LALR(2)。因此，如果您有一个用于其中任何一个的生成器，它就可以完成这项工作。

lookahead-1 冲突源于在项目之间和项目内使用相同的分隔符，如果您放弃分隔符或项目结构，它们将消失。

所以你可以做的是用不同的语法解析两次。在第一遍中，您可以验证分隔符的位置是否正确，语法可能类似于

items          :
               | items_nonempty
               ;
items_nonempty : item
               | items_nonempty SEP item
               ;
item           : A
               | B
               | C
               | D
               ;

在第二个（也是更重要的）阶段，您将验证项目结构。这可能是

items          :
               | items_nonempty
               ;
items_nonempty : item
               | items_nonempty item
               ;
item           : B
               | B D
               | B C
               | B C D
               | A B
               | A B D
               | A B C
               | A B C D 
               ;

词法分析器忽略了分隔符的位置。

上面两个都是 LALR(1)，前者是 LL(1)，后者是 LL(4)，但可以通过一些因式分解得到 LL(1)。

这将是一个独立于 bison 或 lexer 工具提供的特殊产品的解决方案。我期待着了解他们可以做些什么。

于 2012-04-05T20:32:41.220 回答
0

您可以将SEP以下其他标记包含在单个规则中。写得很简洁，你的语法可以这样表达：

%token A B C D SEP
%%
items : /* empty */ | item | itemsSEP item ;
item : a B | a b C | a b c D ;
itemsSEP : itemSEP | itemsSEP itemSEP ;
itemSEP : a b c d ;
a : /* empty */ | A SEP ;
b : B SEP ;
c : /* empty */ | C SEP ;
d : /* empty */ | D SEP ;

所以现在我有itemSEP一个项目后跟一个分隔符，但item最后一个项目后面没有分隔符。它们由小写的单字母非终结符组成，每个非终结符也包括以下分隔符，并注意一些可选参数。只有最后一个参数item始终是一个原始终端，因为后面不会有分隔符。

使用以这种方式表达的语法，您不会遇到任何移位减少冲突，因为现在的语法是 LALR(1)。在每一步，它都会准确地知道要应用什么减少，即使该规则的要点是去掉一个SEP，这样我们就可以进一步向前看一个令牌。

于 2012-07-20T13:23:39.033 回答
0

这有一个转变/减少冲突：

%token A B C D SEP

%%

items
    : /* empty */
    | items_nonempty
    ;

items_nonempty
    : item
    | items_nonempty SEP item
    ;

item
    : opt_a B opt_c_d_list
    ;

opt_a
    :   /* Nothing */
    |   A SEP
    ;

opt_c_d_list
    :   /* Nothing */
    |   opt_c_d_list c_or_d
    ;

c_or_d
    :   SEP C
    |   SEP D
    ;

仅此opt_a规则将 S/R 计数从 4 更改为 2。残余问题是相同的 SEP 在 B 之后分隔 C 或 D，Yacc 无法向前看。您需要进行语义检查才能禁止“B SEP D SEP C”；上述规则将允许这样做。

您是否可以考虑修改您的标记器以在读取 SEP C 时返回 C？，在读取 SEP D 时返回 D？您甚至可以在 中使用词汇反馈和开始条件flex，这样在读取 B 时，您翻转一个开关，以便 SEP C 仅作为 C 返回，而 SEP D 仅作为 D 返回。如果这是可能的，以下是明确的语法可以在没有 S/R 冲突的情况下工作：

%token A B C D SEP

%%

items
    : /* empty */
    | items_nonempty
    ;

items_nonempty
    : item
    | items_nonempty SEP item
    ;

item
    : opt_a B opt_c opt_d
    ;

opt_a
    :   /* Nothing */
    |   A SEP
    ;

opt_c
    :   /* Nothing */
    |   C
    ;

opt_d
    :   /* Nothing */
    |   D
    ;
于 2012-04-05T21:33:25.087 回答