Есть ли способ сделать эту грамматику LALR (1)?

Question

У меня есть грамматики с правилами, как этот

A -> pq 
B -> pr 

Block -> { Astar Bstar } 

Astar -> Astar A 
     | epsilon 

Bstar -> Bstar B 
     | epsilon 

Есть ли способ, чтобы превратить эту грамматику в LALR (1)? Из того, что я могу разобрать, если парсер видит p внутри блока, возникает конфликт shift/educe.

Answer 1

Ваш язык является регулярным и эквивалентен регулярному выражению \{(pq)*(pr)*\}. Проблема заключается в том, что любое простое преобразование в грамматике будет требовать двухсимвольный предпросмотр, чтобы увидеть, является ли там q или r после p

Теперь вы это помечено как yacc и parsing поэтому его не ясно, будет ли ищет ваш практический ответ «как вы справляетесь с этим с yacc» или теоретический ответ «есть ли грамматика LALR (1) для этого языка».

Для практического ответа, решением является то, что вы Пунт - вы перемещаете признание A и B в лексер, где вы распознать характер последовательность pq и pr в качестве маркеров A и B. Так как lex/flex использует DFA и обращается к самому длинному совпадающему токену, у них нет проблем с произвольным просмотром.

Для теоретического ответа вам необходимо преобразовать грамматику, чтобы удалить необходимость просмотра. Проблематичной конструкт (pq)*(pr)* (фигурные скобки не имеют значения), что эквивалентно p(qp)*(rp)*r | p(qp)*q | epsilon, который наводит на мысль грамматику как:

Block -> { p Astar Bstar r } 
     | { p Astar q } 
     | { } 
A -> q p 
B -> r p 
Astar -> Astar A | epsilon 
Bstar -> Bstar B | epsilon 

Альтернативный подход unfactoring в star правила, чтобы они не соответствуют пустые строки:

Block -> { Aplus Bplus } 
     | { Aplus } 
     | { Bplus } 
     | { } 
A -> p q 
B -> p r 
Aplus -> Aplus A | A 
Bplus -> Bplus B | B 

дает вам две разные LALR (1) грамматики для одного языка.

Answer 2

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

Чтобы понять, почему грамматика не LALR (1), давайте начнем вычислив LR (1) конфигурированием наборов для грамматики:

(1) 
S'  -> .Block [$] 
Block -> .{ Astar Bstar } [$] 

(2) 
S'  -> Block. [$] 

(3) 
Block -> { . Astar Bstar } [$] 
Astar -> .Astar A [ }p ] 
Astar -> .epsilon [ }p ] 

(4) 
Block -> { Astar . Bstar } [$] 
Astar -> Astar .A [ }p] 
A  -> .pq [}p] 
Bstar -> .epsilon [ }p ] 
Bstar -> . Bstar B [ }p ] 

На данный момент, мы можем остановиться, потому что у нас есть shift/reduce confict в состоянии (4) на символе p: смещаете ли вы p для A -> .pq [ {p ], или вы уменьшаете BStar -> .epsilon [ }p ]? Поскольку в грамматике LR (1) есть конфликт сдвига/уменьшения, грамматика вообще не является LR (1), что означает, что она не может быть LALR (1) (поскольку каждая грамматика LALR (1) также является LR (1) грамматика).

В принципе, проблема в том, что когда анализатор видит p, он не может сказать, является ли он смотрит на старте с A (это означает, что нужно переместить его), или если нет более A «s левых и он смотрит на начало B (что означает, что ему необходимо уменьшить Bstar -> epsilon).

Чтобы исправить это, давайте посмотрим, что произойдет, если мы сделаем небольшую настройку. Проблема, с которой мы столкнулись, заключается в том, что парсеру необходимо немедленно определить, увидев p, следует ли сдвигать или уменьшать.Что, если мы дадим ему время отложить решение, посмотрев на p, а затем на последующий символ? Чтобы сделать это, давайте немного изменить свою грамматику, переписав

Bstar -> epsilon 
Bstar -> Bstar B 

в

Bstar -> epsilon 
Bstar -> B Bstar 

Теперь анализатор получает смотреть на более лексем, прежде чем решить, что делать. Если он смотрит на pq, он знает, что он не смотрит на что-то связанное с B. Если он видит pr, он знает, что он смотрит на B, и поэтому может начать делать постановки второго сорта. Давайте посмотрим, что происходит с нашим LR (1) заявляет, если мы делаем это:

(1) 
S'  -> .Block [$] 
Block -> .{ Astar Bstar } [$] 

(2) 
S'  -> Block. [$] 

(3) 
Block -> { . Astar Bstar } [$] 
Astar -> .Astar A [ }p ] 
Astar -> .epsilon [ }p ] 

(4) 
Block -> { Astar . Bstar } [$] 
Astar -> Astar .A [ }p] 
A  -> .pq [}p] 
Bstar -> .epsilon [ } ] 
Bstar -> . B Bstar [ } ] 
B  -> .pr [}] 

(5) 
Block -> { Astar Bstar . } [$] 

(6) 
Block -> { Astar Bstar } . [$] 

(7) 
A  -> p.q [}p] 
B  -> p.r [}] 

(8) 
A  -> .pq [}p] 

(9) 
B  -> pr. [}] 

(10) 
Bstar -> B . Bstar [ } ] 
Bstar -> . B Bstar [ } ] 
B  -> .pr [}] 

(11) 
B  -> p.r [}] 

Обратите внимание, что наш первоначальный сдвиг/свертка конфликт исчез, и эта новая грамматика больше не имеет каких-либо конфликтов сдвиг/свёртка на всех. Более того, поскольку нет пар состояний с одним и тем же ядром, вышеуказанное множество состояний также является совокупностью состояний, которые мы имели бы в нашей таблице LALR (1). Поэтому приведенная выше грамматика действительно является ЛАЛР (1), и мы вообще не изменили значение грамматики.

Надеюсь, это поможет!