parsing - 述語パーサーLL1パーサーを使用してこれを解決します

Question

述語パーサーLL1パーサーを使用してこの質問を解決します

E-> EOE | （E）| id

O-> + /-/％/

Answer 1

文法

E -> E O E (1)
E -> (E)   (2)
E -> id    (3)
O -> +     (4)
O -> -     (5)
O -> %     (6)
O -> /     (7)

First/Followセットを計算する必要があります。

First(EOE) = First(E) = {'(', 'id'}
First('('E')') = {'('}
First('id') = {'id'}
First('+') = {'+'}
First('-') = {'-'}
First('%') = {'%'}
First('/') = {'/'}
First(O) = {'+', '-', '%', '/'}

Follow(E) = First(O) u {')', $} = {'+', '-', '%', '/', ')', $}
Follow(O) = First(E) = {'(', 'id'}

テーブルの解析：

. '('  ')' 'id' '+' '-' '%' '/'
E (1,2)    (3)
O               (4) (5) (6) (7)

ご覧のとおり、スタックの最上位にある場合、'（'の解析で競合Eが発生します。先読み記号を読み取るときに、または？(を適用する必要があります。したがって、この文法のLLk（1）パーサーを作成することはできません。E->EOEE->(E)

たとえば、文法を次のように書き直すことができます。

E -> (E) O   (1)
E -> id      (2)
O -> +E      (3)
O -> -E      (4)
O -> %E      (5)
O -> /E      (6)
O -> epsilon (7)

この場合、First/Followセットは次のとおりです。

First('('E')') = {'('}
First('id') = {'id'}
First('+')
First('+') = {'+'}
First('-') = {'-'}
First('%') = {'%'}
First('/') = {'/'}
First(O) = {'+', '-', '%', '/'} u Follow(O)

Follow(E) = {')'} u Follow(O)
Follow(O) = {$} u Follow(E)

テーブルの解析：

. '(' ')' 'id' '+' '-' '%' '/' $
E (1)     (2)
O     (7)      (3) (4) (5) (6) (7)

このテーブルには競合がないため、文法はLLk（1）です。

文字列の解析は次の(id)+idとおりです。

Stack  Input     Action
E$     (id)+id$  E/'(':     (1)
(E)O$  (id)+id$  '('/'(':   read
E)O$   id)+id$   E/'id':    (2)
id)O$  id)+id$   'id'/'id': read
)O$    )+id$     ')'/')':   read
O$     +id$      o/'+':     (3)
+E$    +id$      '+'/'+':   read
E$     id$       E/'id':    (2)
id$    id$       'id'/'id': read
$      $         $/$:       accept