解决Bison解析器中HTTP头语法的移进/归约冲突

在为HTTP定义Bison语法时，处理头字段值末尾的可选空白时遇到多处移进/归约冲突，以下是仅处理头字段部分的简化语法：

%{
  #define YYDEBUG 1
  int yylex(void);
  void yyerror(char *s);
%}
%token X00
%%
/* Reference - RFC 7230 */

headerField : fieldName ':' OWS fieldValue OWS CRLF | fieldName ':' OWS CRLF ;

fieldValue : fieldValueSS | fieldValue fieldValueSS ;

fieldValueSS : fieldContent | obsFold ; 

fieldContent : fieldVChar optFieldContent ;

optFieldContent : /* empty */ | RWS fieldVChar ;

fieldVChar : obsText | VCHAR ;

/* Even though this line fold is obsolete still account for it for consistency with the RFC */
obsFold : CRLF RWS ;

fieldName : token ;

token : tChar | token tChar ;

tChar : '!' | '#' | '$' | '%' | '&' | '\\x27' | '*' | '+' | '-' | '.' | '^' | '_' | '`' | '|' | '~' | DIGIT | ALPHA ;

obsText :     r__1 ;

/* Tokens */
ALPHA : LOALPHA | UPALPHA ;

LOALPHA :     r__2 ;

UPALPHA :     r__3 ;

DIGIT :     r__4 ;

SP : '\\x20' ;

HTAB : '\\x09' ;

WS : SP | HTAB ;

OWS : /* empty */ | OWS WS ;

RWS : WS | RWS WS ;

VCHAR :     r__5 ;

LF : '\\x0a' ;

CR : '\\x0d' ;

CRLF : CR LF ;

/* Range Expansions */
r__1 : 
  '\\x80' | '\\x81' | '\\x82' | '\\x83' | '\\x84' | '\\x85' | '\\x86' | '\\x87' | 
  '\\x88' | '\\x89' | '\\x8a' | '\\x8b' | '\\x8c' | '\\x8d' | '\\x8e' | '\\x8f' | 
  '\\x90' | '\\x91' | '\\x92' | '\\x93' | '\\x94' | '\\x95' | '\\x96' | '\\x97' | 
  '\\x98' | '\\x99' | '\\x9a' | '\\x9b' | '\\x9c' | '\\x9d' | '\\x9e' | '\\x9f' | 
  '\\xa0' | '\\xa1' | '\\xa2' | '\\xa3' | '\\xa4' | '\\xa5' | '\\xa6' | '\\xa7' | 
  '\\xa8' | '\\xa9' | '\\xaa' | '\\xab' | '\\xac' | '\\xad' | '\\xae' | '\\xaf' | 
  '\\xb0' | '\\xb1' | '\\xb2' | '\\xb3' | '\\xb4' | '\\xb5' | '\\xb6' | '\\xb7' | 
  '\\xb8' | '\\xb9' | '\\xba' | '\\xbb' | '\\xbc' | '\\xbd' | '\\xbe' | '\\xbf' | 
  '\\xc0' | '\\xc1' | '\\xc2' | '\\xc3' | '\\xc4' | '\\xc5' | '\\xc6' | '\\xc7' | 
  '\\xc8' | '\\xc9' | '\\xca' | '\\xcb' | '\\xcc' | '\\xcd' | '\\xce' | '\\xcf' | 
  '\\xd0' | '\\xd1' | '\\xd2' | '\\xd3' | '\\xd4' | '\\xd5' | '\\xd6' | '\\xd7' | 
  '\\xd8' | '\\xd9' | '\\xda' | '\\xdb' | '\\xdc' | '\\xdd' | '\\xde' | '\\xdf' | 
  '\\xe0' | '\\xe1' | '\\xe2' | '\\xe3' | '\\xe4' | '\\xe5' | '\\xe6' | '\\xe7' | 
  '\\xe8' | '\\xe9' | '\\xea' | '\\xeb' | '\\xec' | '\\xed' | '\\xee' | '\\xef' | 
  '\\xf0' | '\\xf1' | '\\xf2' | '\\xf3' | '\\xf4' | '\\xf5' | '\\xf6' | '\\xf7' | 
  '\\xf8' | '\\xf9' | '\\xfa' | '\\xfb' | '\\xfc' | '\\xfd' | '\\xfe' | '\\xff' ;
r__2 : 
  '\\x61' | '\\x62' | '\\x63' | '\\x64' | '\\x65' | '\\x66' | '\\x67' | '\\x68' | 
  '\\x69' | '\\x6a' | '\\x6b' | '\\x6c' | '\\x6d' | '\\x6e' | '\\x6f' | '\\x70' | 
  '\\x71' | '\\x72' | '\\x73' | '\\x74' | '\\x75' | '\\x76' | '\\x77' | '\\x78' | 
  '\\x79' | '\\x7a' ;
r__3 : 
  '\\x41' | '\\x42' | '\\x43' | '\\x44' | '\\x45' | '\\x46' | '\\x47' | '\\x48' | 
  '\\x49' | '\\x4a' | '\\x4b' | '\\x4c' | '\\x4d' | '\\x4e' | '\\x4f' | '\\x50' | 
  '\\x51' | '\\x52' | '\\x53' | '\\x54' | '\\x55' | '\\x56' | '\\x57' | '\\x58' | 
  '\\x59' | '\\x5a' ;
r__4 : 
  '\\x30' | '\\x31' | '\\x32' | '\\x33' | '\\x34' | '\\x35' | '\\x36' | '\\x37' | 
  '\\x38' | '\\x39' ;
r__5 : 
  '\\x21' | '\\x22' | '\\x23' | '\\x24' | '\\x25' | '\\x26' | '\\x27' | '\\x28' | 
  '\\x29' | '\\x2a' | '\\x2b' | '\\x2c' | '\\x2d' | '\\x2e' | '\\x2f' | '\\x30' | 
  '\\x31' | '\\x32' | '\\x33' | '\\x34' | '\\x35' | '\\x36' | '\\x37' | '\\x38' | 
  '\\x39' | '\\x3a' | '\\x3b' | '\\x3c' | '\\x3d' | '\\x3e' | '\\x3f' | '\\x40' | 
  '\\x41' | '\\x42' | '\\x43' | '\\x44' | '\\x45' | '\\x46' | '\\x47' | '\\x48' | 
  '\\x49' | '\\x4a' | '\\x4b' | '\\x4c' | '\\x4d' | '\\x4e' | '\\x4f' | '\\x50' | 
  '\\x51' | '\\x52' | '\\x53' | '\\x54' | '\\x55' | '\\x56' | '\\x57' | '\\x58' | 
  '\\x59' | '\\x5a' | '\\x5b' | '\\x5c' | '\\x5d' | '\\x5e' | '\\x5f' | '\\x60' | 
  '\\x61' | '\\x62' | '\\x63' | '\\x64' | '\\x65' | '\\x66' | '\\x67' | '\\x68' | 
  '\\x69' | '\\x6a' | '\\x6b' | '\\x6c' | '\\x6d' | '\\x6e' | '\\x6f' | '\\x70' | 
  '\\x71' | '\\x72' | '\\x73' | '\\x74' | '\\x75' | '\\x76' | '\\x77' | '\\x78' | 
  '\\x79' | '\\x7a' | '\\x7b' | '\\x7c' | '\\x7d' | '\\x7e' ;

查看生成的.output文件，状态321存在2处移进/归约冲突：

State 321

    7 fieldContent: fieldVChar • optFieldContent

    ' '   shift, and go to state 109
    '\\t'  shift, and go to state 110

    ' '       [reduce using rule 8 (optFieldContent)]
    '\\t'      [reduce using rule 8 (optFieldContent)]
    $default  reduce using rule 8 (optFieldContent)

    optFieldContent  go to state 335
    SP               go to state 324
    HTAB             go to state 325
    WS               go to state 336
    RWS              go to state 337

冲突原因：读取若干可见字符后遇到空白时，解析器无法判断是继续累积fieldVChar字符还是归约空的optFieldContent。

状态340同样存在2处移进/归约冲突：

State 340

   12 obsFold: CRLF RWS •
   46 RWS: RWS • WS

    ' '   shift, and go to state 109
    '\\t'  shift, and go to state 110

    ' '       [reduce using rule 12 (obsFold)]
    '\\t'      [reduce using rule 12 (obsFold)]
    $default  reduce using rule 12 (obsFold)

    SP    go to state 324
    HTAB  go to state 325
    WS    go to state 343 

冲突原因：接收CRLF和至少一个空白令牌后，当收到另一个空白令牌时，解析器无法判断是继续累积空白还是归约已完成的obsFold规则。

尝试过的修复方法 #

方法1：整合optFieldContent到fieldContent #

尝试禁用空optFieldContent并将其整合到fieldContent规则中：

fieldContent : fieldVChar | fieldVChar fieldContentSS ;

fieldContentSS : RWS fieldVChar ;

结果：未解决冲突。

方法2：拆分带obsFold和不带obsFold的字段值规则 #

为包含obsFold和不包含obsFold的字段值分别定义规则：

headerField : fieldName ':' OWS fieldValueWS CRLF | fieldName ':' OWS CRLF | fieldName ':' OWS fieldValue OWS CRLF ;

fieldValue : fieldValueSS | fieldValue fieldValueSS ;

fieldValueSS : fieldContent ; 

fieldValueWS : fieldValueSSWS | fieldValueWS fieldValueSSWS ;

fieldValueSSWS : fieldContent | obsFold ; 

结果：解决了移进/归约冲突，但引发大量归约/归约冲突，解析器无法判断归约fieldValueSSWS还是fieldValueSS。

内容的提问来源于stack exchange，提问作者Josh Meise