Qual è la differenza tra Left Factoring e Left Recursion? Capisco che Left factoring sia una tecnica di analisi top-down predittiva. Ma mi confondo quando sento questi due termini.Differenza tra Left Factoring e Left Recursion
questo è il modo che ho visto i due termini utilizzati:
ricorsione a sinistra: = quando il terminale sinistro non è uguale a quello destro non terminale. Esempio: A-> A & | B dove & è alfa. Possiamo rimuovere la ricorsione sinistra usando riscriviamo questa produzione come mi piace.
A-> BA' A '-> & A' | €
fattore di sinistra significa productn non dovrebbe non deterministico. . Esempio: A-> & A | & B | & C
Left Factoring è una tecnica di trasformazione grammaticale. Consiste nel "factoring out" prefissi che sono comuni a due o più produzioni.
Ad esempio, passando da:
A -> α β | α y
a:
A -> α A '
A' -> β | γ
sinistra ricorsione è una proprietà una grammatica comprende ogniqualvolta è possibile derivare da una data variabile (non terminale) a sd che inizia con la stessa variabile, in uno o più stadi.
Ad esempio:
A -> A α
o
A -> B α
B -> A γ
Esiste una tecnica di trasformazione grammaticale denominata Eliminazione della ricorsione sinistra, che fornisce un metodo per generare, data una grammatica ricorsiva di sinistra, un'altra grammatica che è equivalente e non è ricorsiva di sinistra.
Il rapporto/confusione tra i due termini probabilmente deriva dal fatto che entrambe le tecniche di trasformazione possono avere bisogno di essere applicato ad una grammatica prima di poter trarre un top predittivo giù parser per esso.
Il factoring sinistro rimuove il fattore di sinistra comune che appare in due produzioni dello stesso non terminale. È fatto per evitare il back-tracing da parte del parser. Supponiamo che il parser abbia una previsione, considera questo esempio:
A -> qB | qC
dove A, B, C sono non-terminali e q è una frase. In questo caso, il parser verrà confuso su quale delle due produzioni scegliere e potrebbe essere necessario eseguire il back-trace. Dopo factoring sinistra, la grammatica è convertito to
A -> qD
D -> B | C
In questo caso, un parser con un look-ahead sceglierà sempre la produzione corretta.
La ricorsione a sinistra è un caso in cui il terminale non più a sinistra in una produzione di un non terminale è il non terminale stesso (ricorsione diretta sinistra) o attraverso altre definizioni non terminali, riscrive al non- terminale di nuovo (ricorsione sinistra indiretta). Considerate questi esempi -
(1) A -> Aq (diretta)
(2) A -> Bq B -> Ar (indiretto)
ricorsione sinistra deve essere rimosso se il parser esegue top-down parsing
sinistra ricorsione: una grammatica è lasciato ricorsiva se ha un non terminale a tale che ci sia una derivazione a -> Aα | β dove α e β sono sequenze di terminali e non terminali che non iniziano con A.
Mentre si progetta un parser in alto, se la ricorsione sinistra esiste nella grammatica, il parser cade in un ciclo infinito, qui perché A sta cercando di far corrispondere A stesso, il che non è possibile. Possiamo eliminare la ricorsione in alto a sinistra riscrivendo la produzione offendente.As-
A -> ba '
A' -> αA' | epsilon
Factoring sinistro: Il factoring sinistro è necessario per eliminare il non-determinismo di una grammatica. Supponiamo una grammatica, S -> abS | aSb
Qui, S sta derivando lo stesso terminale a nella regola di produzione (due scelte alternative per S), che segue il non-determinismo. Possiamo riscrivere la produzione di rinviare la decisione di S as-
S -> aS '
S' -> bS | Sb
Così, S' può essere sostituito per la B o Sb
fattore di sinistra:
Diamo la grammatica data: A -> AB1 | ab2 | ab3
1) possiamo vedere che, per ogni produzione, c'è un prefisso comune & se scegliamo qualsiasi produzione qui, non è confermato che non avremo bisogno di tornare indietro.
2) non è deterministico, perché non possiamo scegliere alcuna produzione ed essere certi che raggiungeremo la stringa desiderata facendo l'albero di parsing corretto. ma se riscriviamo la grammatica in un modo che è deterministico e ci lascia anche essere abbastanza flessibili da renderlo qualsiasi stringa possibile senza il backtracking .... sarà:
A -> aA ' , A '-> b1 | b2 | b3 ora se ci viene chiesto di creare l'albero di analisi per la stringa ab2 .... non è necessario il tracciamento posteriore. Perché possiamo sempre scegliere la produzione corretta quando otteniamo A 'così genereremo il corretto albero di analisi.
ricorsione sinistra:
A -> Aa | b qui è chiaro che il figlio sinistro di A sarà sempre A se scegliamo la prima produzione, questa è una ricorsione rimasta. Perché A sta chiamando se stessa più e più volte. la stringa generata da questa grammatica è: ba * dal momento che questo non può essere in una grammatica ... si elimina la ricorsione sinistra scrivendo:
A -> ba ' A' -> E | aA ' ora non avremo ricorsione andata e anche possiamo generare ba *.