使用 YACC 移位的日期时间解析器可减少冲突

Question

我有以下 YACC 解析器

%start          Start
%token          _DTP_LONG         // Any number; Max upto 4 Digits.  
%token          _DTP_SDF          // 17 Digit number indicating SDF format of Date Time
%token          _DTP_EOS          // end of input
%token          _DTP_MONTH        //Month names e.g Jan,Feb
%token          _DTP_AM            //Is A.M
%token          _DTP_PM            //Is P.M
%%

Start           :   DateTimeShortExpr
                |   DateTimeLongExpr
                |   SDFDateTimeExpr EOS
                |   DateShortExpr EOS
                |   DateLongExpr EOS
                |   MonthExpr EOS
                ;
DateTimeShortExpr   :  DateShortExpr TimeExpr   EOS         {;}
                    |  DateShortExpr AMPMTimeExpr   EOS     {;}
                    ;

DateTimeLongExpr    :  DateLongExpr TimeExpr EOS           {;}
                    |  DateLongExpr AMPMTimeExpr EOS       {;}
                    ;
DateShortExpr   :  Number                                                          {                                       rc = vDateTime.SetDate ((Word) $1,  0,  0);
                                                                    }   

                |  Number Number                                {     rc = vDateTime.SetDate ((Word) $1, (Word) $2,  0); }

                |  Number Number Number                    {     rc = vDateTime.SetDate ((Word) $1, (Word) $2, (Word) $3); }
                ;
DateLongExpr        :   Number AbsMonth                    {     // case : number greater than 31, consider as year
                                                                     if ($1 > 31) {
                                                                        rc = vDateTime.SetDateFunc (1, (Word) $2, (Word) $1);
                                                            }
                                                            // Number is considered as days
                                                            else {
                                                                   rc = vDateTime.SetDateFunc ((Word) $1, (Word) $2,  0);
                                                                 }
                                                            }
                |   Number AbsMonth Number              {rc = vDateTime.SetDateFunc((Word) $1, (Word) $2, (Word) $3);}

                ;                                 
TimeExpr        :   Number                                      {     rc = vDateTime.SetTime ((Word) $1,  0,  0);}
                |   Number Number                               {     rc = vDateTime.SetTime ((Word) $1, (Word) $2,  0); }
                |   Number Number Number                    {     rc = vDateTime.SetTime ((Word) $1, (Word) $2, (Word) $3); }
                ;                                                                                    

AMPMTimeExpr    : TimeExpr _DTP_AM                     {     rc = vDateTime.SetTo24hr(TP_AM)     ; }
                | TimeExpr _DTP_PM                     {     rc = vDateTime.SetTo24hr(TP_PM)     ; }
                | _DTP_AM TimeExpr                     {     rc = vDateTime.SetTo24hr(TP_AM)     ; }
                | _DTP_PM TimeExpr                     {     rc = vDateTime.SetTo24hr(TP_PM)     ; }
                ;

SDFDateTimeExpr   : SDFNumber                          { rc = vDateTime.SetSDF ($1);}
               ;
MonthExpr           : AbsMonth                         {     rc = vDateTime.SetNrmMth ($1);}
                   | AbsMonth Number                   {     rc = vDateTime.Set ($1,$2);}
                ;           
Number              : _DTP_LONG                               {     $$ = $1; }
                ;               
SDFNumber           : _DTP_SDF                              {     $$ = $1; }
                ;               
EOS                 : _DTP_EOS                              {     $$ = $1; }
                ;
AbsMonth            : _DTP_MONTH                            {      $$ = $1;  }
                ;               

%%

它正在减少三班倒减少冲突。如何删除它们????

Answer 1

移位-归约冲突是语法描述的"小语言"所固有的。 考虑输入令牌流

_DTP_LONG _DTP_LONG _DTP_LONG EOS

每个_DTP_LONG都可以减少为Number。 但应该

Number Number Number

被简化为 1 个数字DateShortExpr后跟一个 2 个数字

TimeExpr还是一个 2 个数字DateShortExpr后跟一个 1 个数字TimeShortExpr？ 歧义是内置的。

如果可能的话，通过添加额外的符号来重新设计你的语言来区分日期和时间 - 例如，冒号来衬托时间的各个部分，斜杠来衬托日期的各个部分。

更新

我不认为你可以在这里使用 yacc/bison 的优先功能，因为令牌是无法区分的。

当 yacc/bison 遇到 shift/reduce 冲突时，您将不得不依赖它的默认行为，即 shift 而不是减少。 在输出中考虑以下示例：

+-------------------------     STATE 9     -------------------------+
+ CONFLICTS:
? sft/red (shift & new state 12, rule 11) on _DTP_LONG
+ RULES:
  DateShortExpr :  Number^    (rule 11)
  DateShortExpr :  Number^Number
  DateShortExpr :  Number^Number Number
   DateLongExpr :  Number^AbsMonth
   DateLongExpr :  Number^AbsMonth Number
+ ACTIONS AND GOTOS:
      _DTP_LONG : shift & new state 12
     _DTP_MONTH : shift & new state 13
                : reduce by rule 11
         Number : goto state 26
       AbsMonth : goto state 27

解析器将要做的是移动并应用规则 12，而不是按规则 11 (DateShortExpr : Number (减少。 这意味着解析器永远不会将单个Number解释为DateShortExpr;它总是会改变的。

依赖默认行为的一个困难是，当您修改语法时，它可能会发生变化。