Come identificare se una grammatica è LL (1), LR (0) o SLR (1)?

Question

Come si identifica se una grammatica è LL (1), LR (0) o SLR (1)?

Qualcuno può spiegarlo usando questo esempio o un altro esempio?

X → Yz | a

Y → bZ | ε

Z → & epsilon;

Answer 1

Per verificare se una grammatica è LL (1), un'opzione è di costruire la tabella di analisi LL (1) e verificare eventuali conflitti. Questi conflitti possono essere

• conflitti PRIMA/PRIMA, in cui due produzioni diverse dovrebbero essere previste per una coppia non terminale/terminale.
• PRINCIPALE/SEGUI conflitti, in cui sono previste due diverse produzioni, una che rappresenta che alcune produzioni dovrebbero essere prese e si espandono a un numero diverso da zero, e una che rappresenta che una produzione dovrebbe essere utilizzata indicando che alcuni non terminali dovrebbero essere infine espansi fuori alla stringa vuota.
• Conflitti FOLLOW/FOLLOW, in cui due produzioni che indicano che un terminale non terminale deve essere espanso alla stringa vuota sono in conflitto tra loro.

Proviamo questo sulla grammatica costruendo i set FIRST e FOLLOW per ciascuno dei non terminali. Qui, otteniamo che

FIRST(X) = {a, b, z} 
FIRST(Y) = {b, epsilon} 
FIRST(Z) = {epsilon} 

Abbiamo, inoltre, che i set seguono sono

FOLLOW(X) = {$} 
FOLLOW(Y) = {z} 
FOLLOW(Z) = {z} 

Da questo, possiamo costruire la seguente LL (1) Tabella di analisi:

a b z $ 
X a Yz Yz 
Y  bZ eps 
Z    eps 

Dal possiamo costruire questa tabella di analisi senza conflitti, la grammatica è LL (1).

Per verificare se una grammatica è LR (0) o SLR (1), iniziamo creando tutti i set di configurazione LR (0) per la grammatica. In questo caso, supponendo che X è il vostro simbolo iniziale, otteniamo la seguente:

(1) 
X' -> .X 
X -> .Yz 
X -> .a 
Y -> . 
Y -> .bZ 

(2) 
X' -> X. 

(3) 
X -> Y.z 

(4) 
X -> Yz. 

(5) 
X -> a. 

(6) 
Y -> b.Z 
Z -> . 

(7) 
Y -> bZ. 

Da questo, possiamo vedere che la grammatica non è LR (0) perché ci sono turni/ridurre i conflitti nei paesi (1) e (6). In particolare, perché abbiamo gli elementi di riduzione Z →. e Y →., non possiamo dire se ridurre la stringa vuota a questi simboli o spostare qualche altro simbolo. Più in generale, nessuna grammatica con & epsilon; -produzioni è LR (0).

Tuttavia, questa grammatica potrebbe essere SLR (1). Per vedere questo, aumentiamo ogni riduzione con il lookahead impostato per i particolari non terminali. Questo restituisce questa serie di reflex (1) set configurando:

(1) 
X' -> .X 
X -> .Yz [$] 
X -> .a [$] 
Y -> . [z] 
Y -> .bZ [z] 

(2) 
X' -> X. 

(3) 
X -> Y.z [$] 

(4) 
X -> Yz. [$] 

(5) 
X -> a. [$] 

(6) 
Y -> b.Z [z] 
Z -> . [z] 

(7) 
Y -> bZ. [z] 

Ora, noi non abbiamo più Shift-ridurre i conflitti. Il conflitto nello stato (1) è stato eliminato perché riduciamo solo quando il lookahead è z, che non è in conflitto con nessuno degli altri elementi.Allo stesso modo, il conflitto in (6) è sparito per lo stesso motivo.

Spero che questo aiuti!

Answer 2

Se non si hanno conflitti FIRST/FIRST e nessun conflitto FIRST/FOLLOW, la grammatica è LL (1).

Un esempio di un primo conflitto/PRIMO:

S -> Xb | Yc 
X -> a 
Y -> a 

Vedendo solo il primo simbolo di ingresso di una, non si può sapere se applicare la produzione S -> Xb o S -> Yc, perché una è nel primo set di X e Y.

un esempio di un conflitto/SEGUIRE pRIMA:

S -> AB 
A -> fe | epsilon 
B -> fg 

vedendo solo il primo simbolo di ingresso f, non è possibile decidere se applicare la produ zione A -> fe o A -> epsilon, perché f è sia il PRIMO set di A che il set FOLLOW di A (A può essere analizzato come epsilon e B as f).

Si noti che se non si dispone di produzioni epsilon non è possibile avere un conflitto PRIMO/SEGUITO.

Answer 3

Risposta semplice: una grammatica è detta LL (1), se la tabella di analisi LL associata (1) ha almeno una produzione in ciascuna voce di tabella.

Take the simple grammar A -->Aa|b.[A is non-terminal & a,b are terminals] 
    then find the First and follow sets A. 
    First{A}={b}. 
    Follow{A}={$,a}. 

    Parsing table for Our grammar.Terminals as columns and Nonterminal S as a row element. 

     a   b     $ 
    -------------------------------------------- 
S |    A-->a      | 
    |    A-->Aa.     | 
    -------------------------------------------- 

Come [S, b] contiene due produzioni c'è una confusione su quale regola choose.So non è LL (1).

Alcuni semplici controlli per verificare se una grammatica è LL (1) oppure no. Verifica 1: la grammatica non deve essere lasciata ricorsiva. Esempio: E -> E + T. non è LL (1) perché è ricorsivo a sinistra. Verifica 2: la grammatica deve essere lasciata a mano.

Il factoring sinistro è necessario quando due o più scelte di regole grammaticali condividono una stringa di prefisso comune. Esempio: S ->A + int | A.

Controllo 3: La grammatica non deve essere ambiguo.

These are some simple checks. 

Answer 4

LL (1) la grammatica è Contesto grammatica ambigua gratuito che può essere analizzato da LL (1) parser.

In LL (1)

• Prima L sta per la scansione di input da sinistra a destra. La seconda L sta per per la Derivata maggiore. 1 sta per l'utilizzo di un simbolo di input in ciascun passaggio .

Per il controllo della grammatica è LL (1) è possibile disegnare la tabella di analisi predittiva. E se trovi più voci nella tabella, puoi dire che la grammatica non è LL (1).

Loro sono anche scorciatoie per verificare se la grammatica è LL (1) oppure no. Shortcut Technique