在 Bison（或 yacc）中，是否有语法定义的顺序？

Question

我在 Bisone 文件中有以下语法：

item
    : "ITEM" t_name t_type v_storage t_prefix t_tag ';'
    ;
t_name
    : [$_A-Za-z][$_A-Z0-9a-z]*
    ;
t_type
    : "BYTE"
    | "WORD"
    | "LONG"
    | "QUAD"
    ;
v_storage
    : %empty
    | "TYPEDEF"
    ;
t_prefix
    : %empty
    | "PREFIX" t_name
    ;
t_tag
    : %empty
    | "TAG" t_name
    ;

当我尝试解析以下字符串时 ITEM foobar BYTE PREFIX str_ TAG S TYPEDEF; 我得到一个意外的“TYPEDEF”并且它接受“;”。我需要做些什么来允许指定任何顺序吗？如果是这样，我希望有一个简单的解决方案。否则，我需要做更多的工作。

Answer 1

不可能告诉 bison（或 yacc）顺序无关紧要。规则严格有序。

所以你有两个选择：

列出所有可能的订单。如果这样做，请注意由可选产品引起的歧义。您实际上需要列出所有订单和子集。呈指数增长。
只接受任何组件列表，作为列表。这将接受重复的组件，因此如果您关心的话，您需要在语义操作中捕捉到它。

第二个选项几乎总是你想要的。实现通常很简单，因为您需要将组件存储在某个地方；只要某个地方有一个唯一的值（例如 NULL），这意味着 "not yet set"，那么您只需要在设置之前测试该值。例如，而不是问题中的那个）：

%{
   #include <stdbool>
   enum Type { 
     TYPE_DEFAULT = 0, TYPE_BYTE, TYPE_WORD, TYPE_LONG, TYPE_QUAD
   };
   typedef struct Item Item;
   struct Item {
     const char *name;
     enum Type   type;
     int         storage; /* 0: unset, 1: TYPEDEF */
     const char *prefix;
     const char *tag;
  };
  // ...
  // Relies on the fact that NULL and 0 are converted to boolean 
  // false. Returns true if it's ok to do the set (i.e. thing
  // wasn't set).
  bool check_dup(bool already_set, const char* thing) {
    if (already_set) 
      fprintf(stderr, "Duplicate %s ignored at line %d\n", thing, yylineno);
    return !already_set;
  }
%}

%union {
   const char *str;
   Item  *item;
   // ...
}

%type <item> item item-def
%token <str> NAME STRING

%%
/* Many of the actions below depend on $$ having been set to .
 * If you use a template which doesn't provide that guarantee, you
 * will have to add $$ = ; to some actions.
 */
item: item-def { /* Do whatever is necessary to finalise  */ }
item-def
    : "ITEM" NAME
               { $$ = calloc(1, sizeof *$$); $$->name = ; }
    | item-def "BYTE"
               { if (check_dup($$->type, "type") $$->type = TYPE_BYTE; }
    | item-def "WORD"
               { if (check_dup($$->type, "type") $$->type = TYPE_WORD; }
    | item-def "LONG"
               { if (check_dup($$->type, "type") $$->type = TYPE_LONG; }
    | item-def "QUAD"
               { if (check_dup($$->type, "type") $$->type = TYPE_QUAD; }
    | item-def "TYPEDEF"
               { if (check_dup($$->storage, "storage") $$->storage = 1; }
    | item-def "PREFIX" STRING
               { if (check_dup($$->prefix, "prefix") $$->prefix = ; }
    | item-def "TAG" STRING
               { if (check_dup($$->tag, "tag") $$->tag = ; }

您可以将所有这些 item-def 作品分成如下内容：

item-def: "ITEM" NAME   { /* ... */ }
        | item-def item-option
item-option: type | storage | prefix | tag

但是在操作中您需要获取项目对象，这不是选项生产的一部分。您可以使用 Bison 功能来做到这一点，该功能让您可以查看解析器堆栈：

prefix: "PREFIX" STRING { if (check_dup($<item>0->prefix, "prefix")
                            $<item>0->prefix = ; }

在此上下文中，[=15=] 将指代 prefix 之前的所有内容，即 item-option 之前的所有内容，即 item-def。请参阅 Bison 手册中 this section 的末尾，其中将这种做法描述为 "risky"，确实如此。它还要求您明确指定标签，因为 bison 不会进行必要的语法分析来验证 [=15=] 的使用，这将识别其类型。

在 Bison（或 yacc）中，是否有语法定义的顺序？

In Bison (or yacc for that matter), is there an order defined by a grammar?

grammar

yacc

bison