Bison/flex 语法问题

Question

我无法编写正确的语法来解析此 yaml：

- Name: Qwerty
  Values:
    - Name: qq
    - Name: pp
- Name: Chirik
  Values:
    - Name: zzz
- Name:  Wasd
  Values:
    - Name: yyy
    - Name: aaa
    - Name: jjj

这是我的野牛文件的一部分：

%%
prog: 
   | enum_decl value_list
   ;

enum_decl:
   TKN_DASH TKN_NAME TKN_IDENTIFIER TKN_VALUE  { strcpy (enums_tbl[enums_cnt++], $3); vals_cnt = 0;  }

value_list:
   | value_list TKN_DASH TKN_NAME TKN_IDENTIFIER { strcpy(enum_vals[enums_cnt].enum_val[vals_cnt++], $4);  }
   ;
%%

弯曲：

%%
"-" { return TKN_DASH; }
"Name:" { return TKN_NAME; }
"Values:" { return TKN_VALUE; }


[0-9]+                       {    yylval.integer = atoi (yytext);
                                   return TKN_INTEGER; }

"/*"                          {    RemoveComment (); }

[a-zA-Z0-9]*[a-zA-Z][_a-zA-Z0-9]*  {    strcpy (yylval.string, yytext);
                                   return TKN_IDENTIFIER; }

[ \t] { /* printf("LEX: SPACE parsed and skipped\n"); */ } ;

%%

问题在于语法解析器获取名称（-名称：Chirik）并将其视为 value_list 的一部分。

我不知道如何解决这个问题。

问候，麦克斯

Answer 1

问题在于语法错误地描述了您尝试匹配的模式。 你的语法规定：

program
    enum_decl value_list
    
enum_decl
    TKN_DASH TKN_NAME TKN_IDENTIFIER TKN_VALUE

value_list
    |
    value_list TKN_DASH TKN_NAME TKN_IDENTIFIER
    

将文本转换为终端会导致：

TKN_DASH TKN_NAME TKN_IDENTIFIER
TKN_VALUE
TKN_DASH TKN_NAME TKN_IDENTIFIER
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_VALUE
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_VALUE
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 

解析器将尝试匹配其第一个产生规则：enum_decl value_list。首先尝试构建 enum_decl， 这将消耗代币：

TKN_DASH TKN_NAME TKN_IDENTIFIER TKN_VALUE

请注意，这将导致评估 enum_decl 后剩余的以下标记序列：

TKN_DASH TKN_NAME TKN_IDENTIFIER
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_VALUE
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_VALUE
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 
TKN_DASH TKN_NAME TKN_IDENTIFIER 

由于 enum_decl 不会消耗更多标记，因此解析器会继续构造 value_list 非终结符，这将消耗多个：

TKN_DASH TKN_NAME TKN_IDENTIFIER

请注意，这将与接下来的 3 行匹配，其中包括字符串：“- Name: Chirik”。 这解释了为什么你会在 value_list 非终结符下面看到这个。

此评估表明语法实际上描述了与您尝试实现的模式不同的模式。

由于我没有任何关于您最初尝试实现的目标的信息，我猜测您尝试匹配模式：(NAME VALUE NAME*)* 如果你把它放在上下文无关语法中，你会得到：

prog:
    stmts
    ;

stmts:
    | stmt stmts
    ;
    
stmt:
    TKN_DASH TKN_NAME TKN_IDENTIFIER TKN_VALUE value_list

value_list:
   | value_list TKN_DASH TKN_NAME TKN_IDENTIFIER
   ;

这有 2 个移位/归约冲突，但可以通过使用 Bison 的 GLR 版本（https://www.gnu.org/software/bison/manual/html_node/GLR-Parsers.html）或通过进一步修改语法。 不管怎样，这种见解应该可以帮助您进一步解析文件。

我已经使用 GLR 解析器输出用 bison 对此进行了测试，并且它有效（我简化了标记以使屏幕截图适合）：