Сдвиг / уменьшение конфликта в грамматике YACC

Question

Я написал грамматику в следующем порядке:

A : B '?'  
  | B
  | A '+' A
  ;

B : "a"
  | "c" A "t" A
  ;

И это дает мне сдвиг / уменьшить конфликт на

A : B . '?'  (96)
A : B .  (98)

Я пробовал несколько способов изменить грамматику, но я, кажется, создаю еще больше конфликтов, когда пытаюсь что-то изменить. Как я могу удалить этот конфликт?

Заранее спасибо, любая помощь будет оценена.

Answer 1

Парсеры LALR(1) разрешают свои конфликты, используя односимвольный просмотр. Когда предвидение не может устранить неоднозначность между различными действиями, конфликт затем показывается пользователю.

В следующем состоянии "?" lookahead означает, что парсер может сдвигаться.

A : B . '?'
A : B .

Но что, если это уменьшает A? Это может привести к следующему состоянию:

B: "c" A "t" A .

Что, уменьшив B, может привести к следующему:

A : B . '?'
A : B .

Следовательно, "?" также является допустимым, чтобы уменьшить.

Так как вы можете решить это?

У вас есть два варианта:

1) Попробуйте переписать грамматику левой рекурсией вместо правой рекурсии. Это может помочь, но это не гарантировано.

2) Сообщите YACC, какой из них выбрать при возникновении этого конфликта (например, используя%left или%right).

Или, возможно, использовать более умный парсер. Например, эльхунд или антлр.