Левый фактор грамматики

Question

Так что у меня есть эта грамматика (ниже), и мне нужно построить таблицу разбора. Мне нужно сделать это подходящим для прогнозирующего парсера. Я знаю, что первая мысль состоит в том, чтобы сделать его однозначным, но для меня это уже однозначно (так как я не могу найти строку, для которой я могу нарисовать 2 разных дерева разбора). Во-вторых, мне нужно сделать так, чтобы это осталось факторизованным. Я предполагаю, что ниже исходной грамматики я чувствую, что что-то упускаю, может кто-то указать, если я что-то упускаю

S -> m G | m K p
G -> n G | n
K -> q K r | m n

Моя догадка:

S -> m A
A -> G | K p 
G -> n G'
G' -> n G' | emptyString
K -> q K r | m n

Answer 1

То, что у вас есть, выглядит правильно! Вот пошаговый способ увидеть, как туда добраться, а также, почему необходимо каждое преобразование.

Во-первых, давайте посмотрим на наш S нетерминал. У этого нетерминала есть два производства, которые начинаются с mЭто означает, что мы имеем ПЕРВЫЙ / ПЕРВЫЙ конфликт между этими производствами. Левый факторинг производств S → mG и S → mKp дает нам

S → мА

A → G

A → Kp

Теперь, выявило ли это какие-либо проблемы, которых раньше не было? К счастью, нет. Нетерминал G может создавать только строки, начинающиеся с nи нетерминал K может производить только строки, начинающиеся с q или же m, Это означает, что мы не вводили здесь никаких ПЕРВЫХ / ПЕРВЫХ конфликтов, поэтому нет необходимости что-либо трогать дальше - по крайней мере, пока.

Далее, давайте посмотрим на нетерминал G, который имеет произведения G → nG и G → n. Другими словами, это производит строку из одной или нескольких копий письма n, Как написано в настоящее время, существует конфликт ПЕРВЫЙ / ПЕРВЫЙ. Есть много способов переписать это. Тот, который вы предложили, состоял в том, чтобы разделить это на две части - одна часть, которая генерирует одну nи последующий фрагмент, который генерирует ноль или более копий n, Я буду следовать вашему примеру в этом, что вводит новый нетерминал, который я собираюсь назвать H, чтобы отличить его от G:

G → nH

H → nH | ε

Теперь мы должны спросить - представляет ли это производство какие-либо ПЕРВЫЕ / СЛЕДУЮЩИЕ конфликты? Чтобы ответить на это, нам нужно определить, что СЛЕДУЕТ за (H). Мы видим, что H появляется только в конце произведений H → nH (что не дает нам ничего нового) и G → nH, что говорит нам о том, что все в FOLLOW(G) также будет в FOLLOW(H), А что в следующем (G)? G появляется в конце произведения A → G, которое говорит нам, что все в СЛЕДУЮЩЕМ (A) будет в СЛЕДУЮЩЕМ (H). И A появляется только в S → mA, что означает, что единственным токеном в FOLLOW(A) является маркер конца ввода $. Уф! Итак СЛЕДУЙТЕ (H) = { $ }. И это хорошая новость, потому что это не противоречит производству H → nH.

Это оставляет за собой правила производства для K, которые, к счастью, не имеют с ними проблем.

Собрав все это вместе, мы получаем, что чистая преобразованная грамматика

S & rarr mA

A → G | Kp

G → nH

H → nH | ε

K → qKr | Миннесота

Это происходит LL(1). Вот таблица разбора:

     m      n       q     r      $
  +------+------+------+------+------+
S |  mA  |      |      |      |      |
  +------+------+------+------+------+
A |  Kp     G      Kp  |      |      |
  +------+------+------+------+------+
G |      |  nH  |      |      |      |
  +------+------+------+------+------+
H |      |  nH  |      |      | eps  |
  +------+------+------+------+------+
K |  mn  |      | qKr  |      |      |
  +------+------+------+------+------+

Смотри, мама! Никаких конфликтов!