Modo del libro di testo di informatica per eseguire text / xml / qualunque analisi

Question

È stato ratto nel mio cervello per un po '.

Ho avuto qualche indagine su Compilers / Flex / Byson e roba del genere, ma non ho mai trovato un buon riferimento che abbia parlato in dettaglio dello "stack di analisi" o di come implementarne uno.

Qualcuno sa di buoni riferimenti su cui potrei recuperare?

Modifica : apprezzo tutti i riferimenti del compilatore e vado a elencare alcuni dei libri, ma il mio obiettivo principale era il Parsing stesso e non quello che fai dopo .

Answer 1

Questo è in risposta alla risposta di Dima che hai accettato come risposta corretta. Sebbene non sia una cattiva risposta affermare che l'analisi è correlata alla teoria degli automi, ritengo che ci sia un malinteso qui.

• In primo luogo, automi a stati finiti sono in grado di riconoscere solo le lingue regolari (ad esempio espressioni regolari). Per riconoscere le lingue senza contesto è necessario pushdown automi , che è più potente. Vedi http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata per ulteriori automata e la loro relazione con le diverse classi di lingue.

• In secondo luogo, analisi è diversa da riconoscimento . Riconoscere una stringa ti dice solo se quella stringa è nella lingua generata dalla tua grammatica. Lo scopo di un parser è di produrre un albero di sintassi concreto che sia sia più duro che generalmente più utile.

Esiste un'ampia varietà di metodi di analisi là fuori, quindi è difficile darti un riferimento specifico che ti dirà ciò che devi sapere ... In generale, dovresti capire la differenza tra analisi top-down e analisi dal basso verso l'alto . Ma ecco una panoramica di alcune tecniche comuni utilizzate dai generatori di parser nel caso in cui tu sia interessato:

• Gli articoli di Wikipedia per LR Parsing , LL Parsing , Analisi SLR , LALR Parsing , Analisi GLR
• LL (*) di ANTLR
• Monadic Parsing in Haskell (per la creazione di parser nella programmazione funzionale lingue)
• E più Parsing Expression Grammars

Modifica Mi dispiace di aver ripetuto questa domanda, mi sono appena imbattuto in due eccellenti post che descrivono la relazione tra lingue regolari e automi finiti , lingue senza contesto e automi push-down . Potrebbe essere interessante per le persone che trovano questa domanda.

Answer 2

Il Libro del drago ! L'ho usato abbastanza recentemente per scrivere un compilatore (in PHP!) Per un linguaggio di elaborazione per i file modello scritti in RTF ...

Answer 3

Un parser è fondamentalmente una macchina a stati finiti, alias un automa finito. Dovresti trovare un libro sulla teoria del calcolo, che tratta gli automi finiti e cose come le lingue normali, le lingue senza contesto, ecc.

Answer 4

prova amazon

Costruzione di compilatori è solo un buon esempio

Answer 5

Dai un'occhiata " Brinch Hansen su Pascal Compilers " .. è stato scritto nel 1985, ma l'ho usato l'anno scorso per un corso sui compilatori (da parte di Per Brinch Hansen ofcourse.) e l'ho trovato molto conciso e utile per la progettazione del compilatore .