Построение Predictive Parser и разбора таблицы

Question

Я пытаюсь создать синтаксический анализатор для следующей грамматики (книга драконов, напр. 4.4.1, стр. 231):

S -> 0 S 1 | 0 1

Итак, сначала я оставил факторинг грамматики и получил:

S  -> 0 S'
S' -> S 1 | 1

И построение таблицы разбора дало:

     +-----------+---------+--------+
     |     0     |    1    |    $   |
-----+-----------+---------+--------+
  S  | S -> 0 S' |         |        |
-----+-----------+---------+--------+
  S' | S' -> S 1 | S' -> 1 |        |
-----+---------------------+--------+

Можно ли не вводить какие-либо записи для символа $ (конец ввода)? Как в этом случае синтаксический анализатор выполняет синтаксический анализ?

Answer 1

ДА, потому что S и S не принимают пустой символ.

рассмотреть следующие вопросы:

S->0S' 
S'->0S|1
S-> empty

Ваш стол будет:

---------------------------------
   | 0     | 1      | $         |
---------------------------------
S  | S->0S'|        | S-> empty |
---------------------------------
S' | S'->S1| S'->1  |           |
---------------------------------

Вы можете посмотреть это видео: http://www.youtube.com/watch?v=E4to0HuZh3Q