Shift уменьшает конфликты в счастливой грамматике

Здравствуйте, хорошие программисты.

Я построил следующую грамматику в happy (haskell):

P  :  program  C             {Prog $2}


E  :  int            {Num $1}
   |  ident           {Id $1}
   |  true           {BoolConst True}
   |  false          {BoolConst False}
   |  read           {ReadInput}
   |  '(' E ')'              {Parens $2}
   |  E '+' E                { Add $1 $3 }
   |  E '-' E                { Sub $1 $3 }
   |  E '*' E                { Mult $1 $3 }
   |  E '/' E                { Div $1 $3 }
   |  E '=' E                { Eq $1 $3 }
   |  E '>' E                { Gt $1 $3 }
   |  E '<' E                { Lt $1 $3 }


C  :   '(' C ')'             {$2}
   |  ident assign E         {Assign $1 $3}
   |  if E then C else C     {Cond $2 $4 $6}  
   |  output E               {OutputComm $2}
   |  while E do C           {While $2 $4 }
   |  begin D ';' C end      {Declare $2 $4}
   |  C ';' C                {Seq $1 $3 }


D  :  D ';' D                {DSeq $1 $3 } 
   |  '(' D ')'              {$2}
   |  var ident assign E     {Var $2 $4}

Теперь цикл While включает все команды, которые следуют после «do». Как изменить это поведение? Я уже пробовал %left, %right... :(


haskell grammar happy yacc
person user1422467    schedule 28.05.2012    source источник

Ответы (2)


arrow_upward
2
arrow_downward

Придумайте два вида C, один из которых позволяет секвенировать, а другой нет. Что-то вроде этого, пожалуй:

Cnoseq : '(' Cseq ')'
       | ident assign E
       | while E do Cnoseq

Cseq : Cnoseq ';' Cseq
     | Cnoseq
person Daniel Wagner    schedule 28.05.2012
comment
Это единственное решение? Требует серьезных изменений в коде :( - person user1422467; 29.05.2012
comment
@user1422467 user1422467 Это должно требовать изменений только в синтаксическом анализаторе - код, использующий деревья синтаксического анализа, должен оставаться неизменным. - person Daniel Wagner; 29.05.2012

arrow_upward
2
arrow_downward

Рассмотрим этот фрагмент кода:

while True do output 1 ; output 2

Это может быть проанализировано как

(while True do output 1) ; (output 2)

or

while True do (output 1 ; output 2)

Такого рода двусмысленность является источником конфликта.

Если вы не хотите менять грамматику, как предложил @DanielWagner, вы можете использовать правила приоритета для разрешения двусмысленности. Как именно зависит от того, каким должен быть приоритет, однако, вероятно, это что-то вроде этого:

%right do
%right then else
%right ';'

Приоритеты перечислены от низкого к высокому, поэтому в этом случае приведенный выше пример будет проанализирован последним. Просто добавьте правила приоритета под токенами, но перед строкой %%.

person John L    schedule 29.05.2012