Teoria: parser LL (k) vs parser per grammatiche LL (k)

Question

Sono preoccupato per la differenza molto importante tra i termini: " LL(k)parser" e "parser per LL(k)grammatiche". Quando un LL(1)parser di backtracking è in questione, È un parser per LL(k)grammatiche, perché può analizzarli, ma NON è LL(k) analizzatore, perché non usa i ktoken per guardare avanti da una singola posizione nella grammatica, ma sta esplorando con il backtracking il possibile casi, indipendentemente dal fatto che utilizzi ancora i ktoken per esplorare. Ho ragione?

La domanda potrebbe dipendere dal modo in cui viene eseguita la previsione. Se il look-ahead in realtà sta ancora elaborando la grammatica con il backtracking, ciò non lo rende LL(k)parser. Per essere LL(k)parser il parser non deve usare la grammatica con meccanismo di backtracking, perché allora sarebbe " LL(1)parser con backtracking che può analizzare le LL(k)grammatiche". Ho di nuovo ragione?

Penso che la differenza è legata alla aspettativa che LL(1)parser sta usando una constantvolta a gettone, e LL(k)parser sta usando al massimo k * constant(lineare al look-ahead) tempo a gettone, non uno exponential timecome sarebbe nel caso di un parser backtracking.

Aggiornamento 1: per semplificare - per token, l'analisi LL(k)dovrebbe essere eseguita in modo esponenziale rispetto ko in un tempo lineare rispetto a k?

Aggiornamento 2: l'ho cambiato in LL(k)perché la domanda è irrilevante per l'intervallo di cui kè (intero o infinito).

Answer 1

Un parser LL (k) deve eseguire le seguenti operazioni in ogni punto del ciclo interno:

• Raccogli i successivi k simboli di input. Poiché questo viene fatto in ogni punto dell'input, questo può essere fatto in tempo costante mantenendo il vettore di lookahead in un buffer circolare.

• Se la parte superiore dello stack di previsione è un terminale, viene confrontato con il simbolo di input successivo; entrambi vengono scartati o viene segnalato un errore. Questo è chiaramente un tempo costante.

• Se la parte superiore dello stack di previsione è un non terminale, viene consultata la tabella delle azioni, utilizzando come chiavi il non terminale, lo stato corrente e il vettore di lookahead corrente. (Non tutti i parser LL (k) devono mantenere uno stato; questa è la formulazione più generale. Ma non fa differenza per la complessità.) Questa ricerca può anche essere eseguita in tempo costante, sfruttando di nuovo il vantaggio incrementale natura del vettore lookahead.

• L'azione di previsione viene normalmente eseguita spingendo il lato destro della produzione selezionata sullo stack. Un'implementazione ingenua richiederebbe tempo proporzionale alla lunghezza del lato destro, che non è correlato né con il lookahead kné con la lunghezza dell'input N, ma piuttosto è correlato alla dimensione della grammatica stessa. È possibile evitare la variabilità di questo lavoro semplicemente spingendo un riferimento sul lato destro, che può essere utilizzato come se fosse l'elenco dei simboli (poiché l'elenco non può cambiare durante il parse).

  Tuttavia, questa non è la storia completa. L'esecuzione di un'azione di previsione non consuma un input ed è possibile, anzi probabile, che vengano effettuate più previsioni per un singolo simbolo di input. Anche in questo caso, il numero massimo di previsioni è correlato solo alla grammatica stessa, non a kné a N.

  Più specificamente, poiché lo stesso non terminale non può essere previsto due volte nello stesso punto senza violare la proprietà LL, il numero totale di previsioni non può superare il numero di non terminali nella grammatica. Pertanto, anche se si spinge l'intero lato destro nella pila, il numero totale di simboli inseriti tra azioni di spostamento consecutive non può superare la dimensione della grammatica. (Ciascun lato destro può essere spinto al massimo una volta. In effetti, è possibile spingere solo un lato destro per un dato non terminale, ma è possibile che quasi tutti i non terminali abbiano un solo lato destro, quindi ciò non riduce l'asintoto.) Se invece solo un riferimento viene inserito nella pila, il numero di oggetti spinti tra azioni di spostamento consecutive, ovvero,il numero di azioni di previsione tra due azioni di spostamento consecutive - non può superare la dimensione dell'alfabeto non terminale. (Ma, ancora una volta, è possibile che|V|è O(|G|).

La linearità della LL (k) l'analisi è stata fondata, io credo, a Lewis e Stearns (1968), ma non ho che la carta a portata di mano in questo momento quindi vi riferirò alla prova in Sippu & Soisalon-Soininen di Analisi Theory (1988), dove è dimostrato nel Capitolo 5 per Strong LL (K) (come definito da Rosenkrantz & Stearns 1970 ), e nel Capitolo 8 per Canonical LL (K).

In breve, il tempo che l'algoritmo LL (k) trascorre tra lo spostamento di due simboli di input successivi dovrebbe essere O(|G|), che è indipendente da entrambi ke N(e, ovviamente, costante per una data grammatica).

Questo in realtà non ha alcuna relazione con i LL(*)parser, dal momento che un LL(*)parser non prova solo LL(k)analisi successive (cosa che non sarebbe possibile, comunque). Per l' LL(*)algoritmo presentato da Terence Parr (che è l'unico riferimento che conosco e che definisce cosa LL(*)significa), non vi è alcun limite alla quantità di tempo che potrebbe essere impiegata tra le successive azioni di spostamento. Il parser potrebbe espandere il lookahead all'intero input rimanente (il che, quindi, renderebbe la complessità temporale dipendente dalla dimensione totale dell'input), oppure potrebbe eseguire il failover su un algoritmo di backtracking, nel qual caso è più complicato definire cosa si intende per "elaborazione di un simbolo di input".