Lookahead kümesinin kesin tanımı nedir?

Question

Derleyicilerle yazıyorum ve sentaks analizinin arkasındaki teoriyi öğreniyorum. Algılama algoritmalarını anlamak için anahtar bir kavram olmasına rağmen, ağdaki bilginin oldukça zayıf olduğunu buldum. Bu sorunu çözmek için StackOverflow benzersiz bir konumda gibi görünüyor.

Answer 1

Dilbilgisi için göz atma kümeleri, her bir üretim için ayarlanan gözeneğe dayanan terminal olmayan terminallerinin her biri için göz atma kümeleri cinsinden tanımlanır. Lookahead setlerinin belirlenmesi, bir dilbilgisinin LL (1) olup olmadığını belirlememize yardımcı olabilir ve eğer öyleyse, bunun için özyinelemeli bir ayrıştırıcı oluşturmamız gereken bilgiler.

Tanım:ileri yönlü (X -> α) ve ileri yönlü (X):

BİRİNCİ (α) α başlayabilir terminalleri kümesi

LOOKAHEAD(X -> α) = FIRST(α) U FOLLOW(X), if NULLABLE(α) 
LOOKAHEAD(X -> α) = FIRST(α), if not NULLABLE(α) 
LOOKAHEAD(X) = LOOKAHEAD(X -> α) U LOOKAHEAD(X -> β) U LOOKAHEAD(X -> γ) 

, TAKİP (X), gram dilindeki herhangi bir yerde X'dan sonra gelen ve NULLABLE (α)'un α'nın boş bir diziden türetip kaynaklanamayacağıdır. klemensler (belirtilmiş ε). Aşağıdaki tanımlar Torben Mogensen'in Basics of Compiler Design numaralı ücretsiz kitabından alınmıştır. Örnek için aşağıya bakın.

Tanım:NULLABLE (X):

NULLABLE(ε) = true 
NULLABLE(x) = false, if x is a terminal 
NULLABLE(αβ) = NULLABLE(α) and NULLABLE(β) 
NULLABLE(P) = NULLABLE(α_1) or NULLABLE(α_2) or ... or NULLABLE(α_n), 
       if P is a non-terminal and the right-hand-sides 
       of all its productions are α_1, α_2, ..., α_n. 

Tanım:birinci (X):

FIRST(ε) = Ø 
FIRST(x) = {x}, assuming x is a terminal 
FIRST(αβ) = FIRST(α) U FIRST(β), if NULLABLE(α) 
      = FIRST(α), if not NULLABLE(α) 
FIRST(P) = FIRST(α_1) U FIRST(α_2) U ... U FIRST(α_n), 
       if P is a non-terminal and the right-hand-sides 
       of all its productions are α_1, α_2, ..., α_n. 

Tanım:TAKİP (X):

α ve β muhtemelen (vardır gramer öyle ki S ⇒ αX Ap başlangıç ​​şekilde S sembolü, bir türetme vardır, ancak ve ancak bir bitiş simgesi bir TAKİP (X) ' içinde boş) dilbilgisi sembollerinin dizileri.

Sezgi:TAKİP (X): X dilbilgisi meydana nerede

bak. numaralı numaralı tüm terminaller (doğrudan veya herhangi bir yineleme seviyesi ile) FOLLOW (X) numaralı telefondan alınmıştır. X s için azaltabileceğini bir üretim (örneğin A -> foo X) sonunda gerçekleşir, ya da başka bir şey takip eder Ek olarak, (örneğin A -> foo X B ve B -> ε) A tarafından takip edilebilir ne olursa olsun sonra, Xcan ayrıca takip edilir (yani FOLLOW(A) ⊆ FOLLOW(X)).

Torben kitabında FOLLOW (X) ve hemen altında bunun bir gösteri belirlenmesi için yöntem bakınız.

Bir örnek:

E -> n A 
A -> E B 
A -> ε 
B -> + A 
B -> * A 

İlk olarak, NULLABLE ve İLK ve tespit edilir:

NULLABLE(E) = NULLABLE(n A) = NULLABLE(n) ∧ NULLABLE(A) = false 
NULLABLE(A) = NULLABLE(E B) ∨ NULLABLE(ε) = true 
NULLABLE(B) = NULLABLE(+ A) ∨ NULLABLE(* A) = false 

FIRST(E) = FIRST(n A) = {n} 
FIRST(A) = FIRST(E B) U FIRST(ε) = FIRST(E) U Ø = {n} (because E is not NULLABLE) 
FIRST(B) = FIRST(+ A) U FIRST(* A) = FIRST(+) U FIRST(*) = {+, *} 

önce belirlenir TAKİP, üretim E' -> E $, burada ilave edilir $, "dosya sonu" olarak kabul edilir. terminal. (Aynı zamanda sabit nokta yineleme ile elde edilebilir)

FOLLOW(E): Let β = $, so add the constraint that FIRST($) = {$} ⊆ FOLLOW(E) 
      Let β = B, so add the constraint that FIRST(B) = {+, *} ⊆ FOLLOW(E) 
FOLLOW(A): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(E) ⊆ FOLLOW(A). 
      Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A). 
      Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(A). 
      Because NULLABLE(ε), add the constraint that FOLLOW(B) ⊆ FOLLOW(A). 
FOLLOW(B): Let β = ε, so add the constraint that FIRST(ε) = Ø ⊆ FOLLOW(B). 
      Because NULLABLE(ε), add the constraint that FOLLOW(A) ⊆ FOLLOW(B). 

bu kısıtlamaları çözme

{+, *, $} ⊆ FOLLOW(E) 
    FOLLOW(E) ⊆ FOLLOW(A) 
    FOLLOW(A) = FOLLOW(B) 

    FOLLOW(E) = FOLLOW(A) = FOLLOW(B) = {+, *, $}. 

Şimdi, her üretim için ileri yönlü belirlenebilir: Daha sonra TAKİP belirlenir

LOOKAHEAD(E -> n A) = FIRST(n A) = {n}  because ¬NULLABLE(n A) 
LOOKAHEAD(A -> E B) = FIRST(E B)   because ¬NULLABLE(E B) 
        = FIRST(E) = {n}  because ¬NULLABLE(E) 
LOOKAHEAD(A -> ε) = FIRST(ε) U FOLLOW(A) because NULLABLE(ε) 
        = Ø U {+, *, $} = {+, *, $} 
LOOKAHEAD(B -> + A) = FIRST(+ A)   because ¬NULLABLE(+ A) 
        = FIRST(+) = {+}  because ¬NULLABLE(+) 
LOOKAHEAD(B -> * A) = {*}     for the same reason 

Son olarak, LOOKAHEAD fo r, her terminal olmayan belirlenebilir: bu bilgi ile

LOOKAHEAD(E) = LOOKAHEAD(E -> n A) = {n} 
LOOKAHEAD(A) = LOOKAHEAD(A -> E B) U LOOKAHEAD(A -> ε) = {n} U {+, *, $} 
LOOKAHEAD(B) = LOOKAHEAD(B -> + A) U LOOKAHEAD(B -> * A) = {+, *} 

belirleyebiliriz bu gramer LL değildir (1) onun olmayan terminaller üst üste ileri yönlü setleri için. (Yani, her seferinde bir sembolü okuyan ve hangi üretimin kullanılacağını kesin olarak belirleyen bir program oluşturamayız.)