LL içine dilbilgisi dönüştürme (1) dilbilgisi: bazı sorunlar

Question

Bu tam olarak ödev ama benim çalışmalarla ilgilidir:

örneğin bir gramer gibidir:

E -> E + E | E * E | -E | (E) | o olur belirsizliği çıkardıktan sonra kimliği

E->-F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

(en düşük öncelik operatöründen başlayarak)

Ve sol Rekursif sol faktoring (bu durumda gerekli değildir) nihai LL1 dilbilgisi olduğunu çıkardıktan sonra: iyi çalışır bir hata ücretsiz ayrıştırıcı tablosunu verir

E->-F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

. Şimdi Karşılıklı sorun hakkında, gramer böyle olduğunu varsayalım:

E -> E + E | E * E | id = E | (E) | id

Şimdi çakışmaları olmayan bir ayrıştırma tablosu oluşturamıyorum, bu da son gramerimin LL1 olmadığı anlamına gelir.

belirsizliği çıkardıktan sonra: Şu adımları izleyin:

E->id=F|F 
F->GF' 
F'->+GF'|e 
G->HG' 
B->*HG'|e 
H->(E)|id 

Ama Ayrıştırıcı tablosunda bir çatışma var:

E->id=F|F 
F->F+G|G 
G->G*H|H 
H->(E)|id 

Ve sola Rekursif sol faktoring çıkardıktan sonra, dilbilgisi olur Kaldıramamadığım bir şey var, yani kaçırdığım bir adım var ya da bulamadığım adımlarda bir yanlışlık var. Lütfen bana neyi yanlış yaptığımı ve nasıl düzeltileceğini söyle. Uzun zamandır bu problem üzerinde çalışıyorum.

Answer 1

Şöyle diyelim:

E -> E+E|E*E|id=E|(E)|id 

olacak:

E -> E+E|E*E|(E)|E' 
E' -> id=E|id 

o zaman belirsizlik ve sol Özyinelemeyi çıkarmadan ile gidip alabilirsiniz: Elbette

E -> GF  FIRST(E) = FIRST(G) 
F -> +GF|e 
G -> HG'  FIRST(G) = FIRST(H) 
G' -> *HG'|e 
H -> (E)|E' FIRST(H) = {(} + FIRST(E') = {(, id} 
E' -> idE'' FIRST(E') = {id} 
E'' -> =E|e FIRST(E'') = {=} + {#} 

, Sorun şu ki, verilen operatör önceliğini kaybedersiniz.

gramer LL (1) varsa uç-olmayan N için, N -> a, N -> bN farklı üretimler olduğu için FIRST(N -> a) ve FIRST(N -> b) içinde bir ortak öğeler olacak olmayacaktır. Gördüğünüz gibi, numaralı ürüne N -> id= numaralı bir üretim eklediğinizde, bu kural kuralını ihlal eder.

LL(2) dilbilgisi oluşturabilirsiniz (ancak bu muhtemelen istediğiniz gibi değildir), herhangi bir yerde id=E üretimine sahip olabilirsiniz. (FIRST2 setleri 2 elemanlı dizelerden oluşur). Ayrıca

, sen sunulan dilbilgisi de bir kez daha bakarsak:

E -> E+E|E*E|id=E|(E)|id 

Bu yüksek şansım çözümde yapılan operatör öncelik yukarıda gerçek uygulama için doğru biri olduğunu, bu. Buna bir bak!