У меня есть грамматика с такими правилами
A -> pq
B -> pr
Block -> { Astar Bstar }
Astar -> Astar A
| epsilon
Bstar -> Bstar B
| epsilon
Есть ли способ превратить эту грамматику в LALR(1)? Из того, что я могу разобрать, если синтаксический анализатор видит p внутри блока, возникает конфликт сдвига/выведения.
Ваш язык является регулярным и эквивалентен регулярному выражению \{(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
Альтернативный подход заключается в нефакторизации правил star, чтобы они не соответствовали пустым строкам:
Block -> { Aplus Bplus }
| { Aplus }
| { Bplus }
| { }
A -> p q
B -> p r
Aplus -> Aplus A | A
Bplus -> Bplus B | B
что дает вам две совершенно разные грамматики LALR(1) для одного и того же языка.
Давайте начнем с того, что точно выясним, почему возникает конфликт 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 ]
На этом мы можем остановиться, потому что у нас есть конфликт сдвига/уменьшения в состоянии (4) символа p: вы сдвигаете p для A -> .pq [ {p ] или уменьшаете BStar -> .epsilon [ }p ]? Поскольку в LR(1)-грамматике присутствует конфликт сдвиг/свертка, эта грамматика вообще не является LR(1), а это означает, что она не может быть LALR(1) (поскольку каждая LALR(1)-грамматика также является LR(1). (1) грамматика).
По сути, проблема в том, что когда синтаксический анализатор видит p, он не может сказать, смотрит ли он на начало A (это означает, что ему нужно сдвинуть его) или A больше не осталось, и он смотрит на начало B (это означает, что нужно уменьшить Bstar -> epsilon).
Чтобы исправить это, давайте посмотрим, что произойдет, если мы сделаем небольшую настройку. Проблема, с которой мы столкнулись, заключается в том, что синтаксический анализатор должен немедленно определить, увидев p, нужно ли сдвигать или уменьшать. Что, если мы дадим ему время отложить решение, взглянув на p, а затем на последующий символ? Для этого давайте немного изменим вашу грамматику, переписав
Bstar -> epsilon
Bstar -> Bstar B
as
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). Таким образом, приведенная выше грамматика действительно является LALR(1), и мы вообще не изменили значение грамматики.
Надеюсь это поможет!
