5

I'm currently trying to implement a LALR parser generator as described in "compilers principles techniques and tools" (also called "dragon book").

A lot already works. The parser generator is currently able to generate the full goto-graph.

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

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

The goto-graph:

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

I have trubbles with implementing the algorithm to generate the actions-table! My algorithm computes the following output:

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... shift to state x
rx... reduce to state x

The r? means that I don't know how to get the state (the ?) to which the parser should reduce. Does anyone know an algorithm to get ? using the goto-graph above?

If anything is describe no clearly enough, please ask and I will try to explain it better! Thanks for your help!

4

3 に答える 3

4

シフトエントリは次の状態に起因しますが、リデュースエントリは生産を示します。

シフトすると、状態参照がスタックにプッシュされ、次の状態に進みます。

減らすと、これは特定のプロダクション用です。プロダクションは、n個の状態をスタックにシフトする役割を果たしました。ここで、nはそのプロダクション内のシンボルの数です。たとえば、S'用に1つ、S用に2つ、C用に2つまたは1つ（つまり、Cの1番目または2番目の選択肢用）。

n個のエントリがスタックからポップされた後、そのプロダクションの処理を開始した状態に戻ります。その状態と本番環境から生じる非終端記号については、gotoテーブルを検索して次の状態を見つけ、それをプッシュします。

したがって、reduceエントリはプロダクションを識別します。実際、結果の非終端記号とポップするシンボルの数を知っていれば十分かもしれません。

したがって、テーブルは次のようになります。

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による削減を示します。

于 2010-08-02T20:48:16.653 に答える
1

スタックをポップして、そこから次の状態を見つける必要があります。

于 2010-08-02T19:40:11.840 に答える
0

rx の意味: 番号 x の生産を使用して削減!
その後、すべてが明らかになります！プロダクションのボディをポップして、ヘッドをトップに戻すだけ！

于 2010-08-02T20:42:04.293 に答える