解決這個使用predicitive解析器LL1分析器

Question

使用predicitive解析器LL1分析器

E->電子產地證電子解決這個問題| （E）| ID

Ø - > +/- /％/

Answer 1

語法

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

你需要計算首先/跟蹤集：

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在堆棧的頂部：在閱讀前瞻符號(，你應該應用E->EOE或E->(E)？所以你不能爲這個語法創建一個LLk（1）解析器。

你可以語法重新寫，例如：

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

在這種情況下，第一/跟蹤集：

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