LR (1) парсинговый стол с эпсилонами производства - PullRequest
Новая
       57

LR (1) парсинговый стол с эпсилонами производства

0 голосов
/ 17 мая 2018

У меня проблемы с созданием набора наборов элементов для парсеров LR (1) с грамматикой, содержащей произведения эпсилон. Например, учитывая следующую грамматику (где eps обозначает epsilon) 

S -> a S U
U -> b
  |  eps

State0 будет 

S' -> .S, $
S -> .a S U, $

Перемещение с 'a' из State0 даст следующее состояние, назовем его State2 

S -> a .S U, $
S -> .a S U, $/???

Для просмотра второго элемента State2 мне нужно вычислить FIRST (U $). Я знаю, что ПЕРВЫЙ (U) = {'b', eps}. Мой первый вопрос: предпросмотрами второго элемента State2 являются $ и 'b'? Так как U может быть eps, мой мозг говорит мне, что я также могу видеть $ в качестве предвидения, а не просто «b». Было бы просто 'b', если бы FIRST (U) был бы просто {'b'}. Это правильно?

Второй вопрос: в какой-то момент у меня будет состояние, следующее за 

S -> a S .U, $
U -> .b, $
U -> .eps, $

Что мне здесь делать? Нужно ли переходить с eps и иметь набор с элементом U -> eps., $? Что делать, если у меня есть другой терминал, например, X -> .eps, a/$? И если я перееду, получив набор формы X -> eps., $, я уменьшу?

И еще: нужно ли вставлять eps в таблицу разбора как символ?

Спасибо

1 Ответ

0 голосов
/ 17 мая 2018

  1. FIRST(U$) означает «набор символов, который может быть первым в производной от U$». Ясно, что если U может получить пустую строку, $ должен быть частью этого набора. Маркер конца ввода $ гарантирует, что нам никогда не придется беспокоиться о эпсилонах в наборах FIRST. (Если бы мы делали LR (k) вместо LR (1), мы бы использовали k конечные маркеры, чтобы все строки в FIRST<sub>k</sub> имели длину k.

  2. Элемент, связанный с U &rarr; (или U &rarr; &epsilon;, если вы настаиваете), равен U &rarr; &bull; . Другими словами, оно сводимо и должно вызывать действие сокращения при сопоставлении с упреждением.

  3. ε не является символом; мы используем его (иногда), чтобы сделать пустую строку видимой. Но пустая строка пуста.

...