Analisi senza scanner - Scannerless parsing

In informatica , l'analisi senza scanner (chiamata anche analisi senza lexer ) esegue la tokenizzazione (spezzando un flusso di caratteri in parole) e l'analisi (disponendo le parole in frasi) in un unico passaggio, piuttosto che suddividerla in una pipeline di un lexer seguita da un parser , in esecuzione contemporaneamente . Una grammatica linguistica è senza scanner se utilizza un unico formalismo per esprimere sia la struttura lessicale (a livello di parola) che quella a livello di frase della lingua.

Dividere l'elaborazione in un lexer seguito da un parser è più modulare; l'analisi senza scanner viene utilizzata principalmente quando una chiara distinzione lexer-parser non è necessaria o non è desiderata. Esempi di quando ciò è appropriato includono TeX , la maggior parte delle grammatiche wiki , makefile , semplici linguaggi di scripting specifici dell'applicazione e Raku .

Vantaggi

  • È necessario un solo metalinguaggio
  • La struttura lessicale non regolare è gestita facilmente
  • La "classificazione dei token" non è necessaria, il che elimina la necessità di adattamenti progettuali come " l'hack lexer " e parole riservate alla lingua (come "while" in C )
  • Le grammatiche possono essere compositive (possono essere unite senza intervento umano)

Svantaggi

  • Poiché la scansione lessicale e l'analisi sintattica sono combinate, il parser risultante tende ad essere più complicato e quindi più difficile da comprendere ed eseguire il debug . Lo stesso varrà per la grammatica associata, se viene utilizzata una grammatica per generare il parser.
  • Il parser risultante tende ad essere significativamente meno efficiente di una pipeline lexer-parser per quanto riguarda sia il tempo che la memoria .

Implementazioni

  • SGLR è un parser per il Formalismo di definizione della sintassi modulare SDF e fa parte del Meta-Ambiente ASF + SDF e del sistema di trasformazione del programma Stratego / XT .
  • JSGLR , un'implementazione Java pura di SGLR, anch'essa basata su SDF .
  • TXL supporta l'analisi a livello di carattere.
  • dparser genera codice ANSI C per analizzatori GLR senza scanner .
  • Spirit consente l'analisi sia senza scanner che basata su scanner.
  • SBP è un parser senza scanner per grammatiche booleane (un superset di grammatiche prive di contesto), scritto in Java.
  • Laja è un generatore di parser senza scanner a due fasi con supporto per mappare le regole grammaticali in oggetti, scritto in Java.
  • La caratteristica Raku Grammars del linguaggio di programmazione generico Raku .
  • PyParsing è un parser senza scanner scritto in puro Python.
  • META II ha funzioni di parser di token incorporate.
  • TREE-META Come META II è anche scannerless con funzioni lexer incorporate.
  • Compilatore CWIC per la scrittura e l'implementazione di compilatori. Ha regole token come parte della sua lingua. Le regole in CWIC sono state compilate in funzioni booleane che restituivano il successo o il fallimento.

Appunti

  • ^ Questo perché l'analisi a livello di carattere rende la lingua riconosciuta dal parser una singola lingua libera dal contesto definita sui caratteri, al contrario di una lingua libera dal contesto di sequenze di stringhe nelle lingue normali . Alcuni parser senza lexer gestiscono l'intera classe di linguaggi privi di contesto, che è chiusa in composizione.

Riferimenti

Ulteriore lettura