Проблема реализации генератора PAL-LALR

Question

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

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

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 . , $ |<-----+ 
      +---------------+ 

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

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 переложить в состояние х
гх ... уменьшить до состояния х

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

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

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 |  | 

где гх указывает сократить производства х.

Answer 2

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

Answer 3

Rx означает: уменьшить использование продукции с номером x!
Затем все становится понятным! Простая поп-панель корпуса и смещение головы назад!