parsing - 使用预测解析器 LL1 解析器解决这个问题

Question

使用预测解析器 LL1 解析器解决这个问题

E-> EOE | (五) | 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)

如您所见，当您在堆栈顶部时，解析 '(' 时会发生冲突：在读取前瞻符号时，您应该应用还是？因此您无法为此语法创建 LLk(1) 解析器。E(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