ricorsione sinistra e factoring di sinistra - che si va per primo?

Question

se ho una grammatica con una produzione che contiene sia la ricorsione sinistra e factoring sinistra come

$ \ qquad \ displaystyle F \ a FBA \ metà CDS \ metà c $

che si ha la priorità, la ricorsione sinistra o di factoring sinistra?

Answer 1

Le trasformazioni come il factoring sinistra o la rimozione di ricorsione sinistra non hanno regole di precedenza. Ovviamente, le grammatiche risultanti possono essere diversi, ma riconosceranno la stessa lingua.

esempio la grammatica del problema è più difficile di quanto il tipico problema compiti undergrad. Quindi, mostrando il nostro lavoro sarà utile.

Sinistra ricorsione

definiamo una trasformazione che rimuove lasciato ricorsione.

Data

$ \ qquad \ displaystyle A \ A \ alpha_0 \ mid A \ alpha_1 \ metà \ dots \ mid A \ alpha_n \ mid B \ beta_0 \ mid B \ beta_1 \ metà \ dots \ mid B \ beta_n $,

togliamo la ricorsione sinistra in questo modo:

$ \ qquad \ displaystyle \ begin {align} A_h & \ per beta_0 B \ \ mid B \ beta_1 \ metà \ dots \ mid B \ beta_n \\ A_t & \ per \ alpha_0 \ metà \ alpha_1 \ metà \ dots \ metà \ alpha_n \\ A_ {t ^ +} e \ a A_t A_ {t ^ +} \ mid A_t \\ A & \ per A_h A_ {t ^ +} \ mid A_h \ End {align} $

La generalità di cui sopra è in genere non dato nei testi del compilatore, ma i testi parsing come Grune & Jacobs non copre questo. factoring Sinistra può essere applicato alla grammatica sopra trasformata, ma sarà solo introdurre regole extra che non cambieranno la risposta. Quindi ci sarà Semplifica la presentazione senza factoring in più a sinistra in corso di esecuzione.

In questa risposta noi non coprire i problemi indiretti ricorsione sinistra perché ci occupiamo soltanto con un unico regole di non terminali. Si noti che la ricorsione indiretta sinistra può essere affrontata, però. (Aprire una domanda separata, se ciò che è importante.)

Sinistra Factoring

La rimozione di factoring a sinistra è nella maggior parte dei testi introduttivi del compilatore fatto in questo modo. Dato

$ \ qquad \ displaystyle A \ a x y \ x metà z $

rendimenti factoring sinistra:

$ \ qquad \ displaystyle \ begin {align} A_S e \ y \ metà z \\ A & \ ax A_S \ End {align} $

Ora che eseguono le trasformazioni in entrambe ordinamento.

factoring sinistra prima

fattore di sinistra di Let grammatica della domanda

$ \ qquad \ displaystyle \ begin {align} F_s & \ a D S \ metà \ varepsilon \\ F & \ F B un \ mid c F_s \ End {align} $

e quindi rimuovere la ricorsione sinistra:

$ \ qquad \ displaystyle \ begin {align} F_h & \ ac F_s \\ F_t & \ a B un \\ F_ {t ^ +} e \ a F_t F_ {t ^ +} | F_t \\ F_s & \ a D S \ metà \ varepsilon \\ F & \ per F_h F_ {t ^ +} \ mid F_h \ End {align} $

Rimozione sinistra-ricorsione prima

E per l'altro ordine, cerchiamo di rimuovere la ricorsione sinistra dalla grammatica della domanda

$ \ qquad \ displaystyle \ begin {align} F_h & \ a C D S \ mid c \\ F_t & \ a B un \\ F_ {t ^ +} e \ a F_t F_ {t ^ +} \ mid F_t \\ F & \ per F_h F_ {t ^ +} \ mid F_h \ End {align} $

e fattore poi a sinistra del terminale $ c $:

$ \ qquad \ displaystyle \ begin {align} F_ {} hs e \ a D S \ metà \ varepsilon \\ F_h & \ ac F_ {} \\ hs F_t & \ a B un \\ F_ {t ^ +} e \ a F_t F_ {t ^ +} \ mid F_t \\ F & \ per F_h F_ {t ^ +} \ mid F_h \ End {align} $

Ah, le grammatiche risultanti sono gli stessi!

In generale, dimostrando che due grammatiche sono equivalenti è indecidibile. Quindi, se una serie di grammatica trasformazioni potrebbero influenzare la lingua che è riconosciuta , allora, sarebbe disastroso.