0

我有以下 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;  }
                ;

%%

它提供了三班减少冲突。我怎样才能删除它们？？？？

4

1 回答 1

1

The shift-reduce conflicts are inherent in the "little language" that your grammar describes. Consider the stream of input tokens

_DTP_LONG _DTP_LONG _DTP_LONG EOS

Each _DTP_LONG can be reduced as a Number. But should

Number Number Number

be reduced as a 1-number DateShortExpr followed by a 2-number TimeExpr or as a 2-number DateShortExpr followed by a 1-number TimeShortExpr? The ambiguity is built in.

If possible, redesign your language by adding additional symbols to distinguish dates from times--colons to set off the parts of a time and slashes to set off the parts of a date, for instance.

Update

I don't think that you can use yacc/bison's precedence features here, because the tokens are indistinguishable.

You will have to rely on yacc/bison's default behavior when it encounters a shift/reduce conflict, that is, to shift rather than reduce. Consider this example in your output:

+-------------------------     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

What the parser will do is to shift and apply rule 12, rather than reduce by rule 11 (DateShortExpr : Number). This means the parser will never interpret a single Number as a DateShortExpr; it will always shift.

And a difficulty with relying on the default behavior is that it might change as you make modifications to your grammar.

于 2013-02-11T14:40:35.227 回答