Проблема реализации генератора парсера LALR

Question

В настоящее время я пытаюсь реализовать генератор синтаксического анализатора LALR, как описано в «Принципах и инструментах принципов компиляторов» (также называемых «книга дракона»).

Много уже работает. Генератор синтаксического анализатора в настоящее время может генерировать полный goto-граф.

Example Grammar:
                   S' --> S
                   S  --> C C
                   C  --> c C
                   C  --> d

Nonterminals: S', S, C
Terminals: c, d
Start: S'

Гото-график:

I[0]---------------+      I[1]-------------+
| S' --> . S   , $ |--S-->| S' --> S . , $ |
| S  --> . C C , $ |      +----------------+
| C  --> . c C , c |
| C  --> . c C , d |      I[2]--------------+
| C  --> . d   , c |      | S --> C . C , $ |      I[3]--------------+
| C  --> . d   , d |--C-->| C --> . c C , $ |--C-->| S --> C C . , $ |
+------------------+      | C --> . d   , $ |      +-----------------+
   |  |                   +-----------------+
   |  |           +--c--+   |      |
   |  |           |     |   c      |
   |  |           |     v   v      |
   |  |     I[4]--------------+    |
   |  c     | C --> c . C , c |    |
   |  |     | C --> c . C , d |    |
   |  |     | C --> c . C , $ |    d
   |  |     | C --> . c C , c |    |
   |  +---->| C --> . c C , d |    |
   |        | C --> . c C , $ |    |
   d        | C --> . d   , c |--+ |
   |  +-----| C --> . d   , d |  | |
   |  |     | C --> . d   , $ |  | |
   |  |     +-----------------+  | |
   |  C                          | |
   |  |     I[6]--------------+  | |
   |  |     | C --> c C . , c |  d |
   |  +---->| C --> c C . , d |  | |
   |        | C --> c C . , $ |  | |
   |        +-----------------+  | |
   |                             | |
   |        I[5]------------+    | |
   |        | C --> d . , c |<---+ |
   +------->| C --> d . , d |      |
            | C --> d . , $ |<-----+
            +---------------+

У меня есть проблемы с реализацией алгоритма генерации таблицы действий! Мой алгоритм вычисляет следующий вывод:

state |    action      
      |  c  |  d  |  $   
------------------------
    0 |  s4 |  s5 |
------------------------
    1 |     |     | acc
------------------------
    2 |  s4 |  s5 |
------------------------
    3 |     |     |  r?
------------------------
    4 |  s4 |  s5 |
------------------------
    5 |  r? |  r? |  r?
------------------------
    6 |  r? |  r? |  r?

sx ... переход в состояние x
rx ... уменьшить до состояния x

р? означает, что я не знаю, как получить состояние (?), к которому должен быть обработан синтаксический анализатор. Кто-нибудь знает алгоритм получения? используя приведенный выше гото-график?

Если что-то описано недостаточно четко, пожалуйста, спросите, и я постараюсь объяснить это лучше! Спасибо за вашу помощь!

Answer 1

Запись смены присваивается следующим состоянием, но запись уменьшения указывает на производство.

При перемещении вы помещаете ссылку на состояние в свой стек и переходите к следующему состоянию.

При сокращении это для конкретного производства.Производство отвечало за перенос n состояний в ваш стек, где n - количество символов в этом производстве.Например, один для S ', два для S и два или один для C (т.е. для первой или второй альтернативы для C).

После удаления из стека n записей вы возвращаетесь в состояние, в котором вы начали обработку этого производства.Для этого состояния и нетерминала, полученного в результате производства, вы просматриваете таблицу goto, чтобы найти следующее состояние, которое затем отправляется.

Таким образом, записи сокращения идентифицируют производство.На самом деле может быть достаточно знать итоговый нетерминал и количество символов для всплытия.

Таким образом, ваша таблица должна иметь вид

state |    action       |  goto
      |  c  |  d  |  $  |  C  |  S   
------------------------------------
    0 |  s4 |  s5 |     |  2  |  1
------------------------------------
    1 |     |     | acc |     |
------------------------------------
    2 |  s4 |  s5 |     |  3  |
------------------------------------
    3 |     |     |  r0 |     |
------------------------------------
    4 |  s4 |  s5 |     |     |  6
------------------------------------
    5 |  r3 |  r3 |  r3 |     |
------------------------------------
    6 |  r2 |  r2 |  r2 |     |

, где rx указывает на уменьшение при производстве x.

Answer 2

Вам нужно открыть стек и найти оттуда следующее состояние.

Answer 3

rx означает: уменьшите, используя производство с номером x!
Тогда все станет ясно!Просто выдвиньте тело производства и перенесите голову обратно на вершину!