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

Question

У меня проблемы с созданием коллекции наборов элементов для парсеров LR(1) с грамматикой, содержащей произведения epsilon. Например, учитывая следующую грамматику (где 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., $? Что делать, если у меня есть другой терминал, как lookahead, т.е. X -> .eps, a/$? И если я перееду, то получу набор формы X -> eps., $я уменьшу?

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

Спасибо

Answer 1

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

2. Элемент, связанный с U → (или есть U → ε если вы настаиваете) U → • , Другими словами, оно сводимо и должно инициировать действие сокращения при сопоставлении с запросом на просмотр.

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