Linee guida di progettazione per parser e lexer?

Question

Sto scrivendo un lexer (con re2c) ed un parser (con limone) per un formato di dati un po 'contorto: CSV-like, ma con specifici tipi di stringhe in luoghi specifici (caratteri alfanumerici, caratteri alfanumerici e segni meno, eventuali char tranne virgolette e virgola ma con parentesi graffe, ecc.), stringhe all'interno di parentesi graffe e stringhe che assomigliano a chiamate di funzione con parentesi di apertura e chiusura che possono contenere parametri.

Il mio primo colpo a era un lexer con molti stati, ciascuno Stato ristorazione al formato stringa specifica. Ma dopo molti messaggi di "inaspettato input" non desiderati dal lexer (che è diventato molto grande) ho capito che forse stava cercando di fare il lavoro del parser. Ho scartato la mia prima prova e sono andato con un lexer con un solo stato, molti token di caratteri e un parser che combina i token con i diversi tipi di stringa. Funziona meglio, ottengo più errori di sintassi utili dal parser quando qualcosa non funziona, ma non sembra ancora abbastanza corretto. Sto pensando di aggiungere uno o due stati al lexer, ma iniziando gli stati dal parser, che ha una "panoramica" molto migliore su quale tipo di stringa è richiesto in una determinata istanza. Complessivamente mi sento un po 'stupido :(

Non ho un background CS formale e timido un po' lontano dalla teoria della matematica.Ma forse c'è un tutorial o un libro da qualche parte che spiega cosa un lexer dovrebbe (e non dovrebbe) fare e quale parte del lavoro del parser dovrebbe fare. Come costruire buoni modelli simbolici, quando utilizzare lexer stati, quando e come utilizzare le regole ricorsive (con un parser LALR), come evitare le regole ambigua. un libro di cucina pragmatico che insegna le nozioni di base: "Lex and YACC primer/HOWTO" è stato bello, ma non abbastanza: dato che voglio solo analizzare un formato dati, i libri sulla compilazione del compilatore (come il libro del drago rosso) sembrano un po 'troppo grandi per me

O forse qualcuno mi può dare alcune regole semplici qui.

Answer 1

Quello che dovresti fare è scrivere una grammatica per la tua lingua. Una volta che avete, il confine è facile:

• Il lexer è responsabile per prendere il vostro input e ti dice che terminale avete.
• Il parser è responsabile di una serie di corrispondenza terminali e nonterminals a una regola di produzione, più volte, finché non si dispone di un albero sintattico o un fallimento di analisi.

Il lexer non è responsabile per la validazione dell'input eccetto quando rifiutare personaggi impossibili, e altri molto semplici bit. Il parser fa tutto questo.

Date un'occhiata a http://www.cs.rochester.edu/~nelson/courses/csc_173/grammars/parsing.html. È una pagina introduttiva del corso di CS sull'analisi.

Answer 2

Un test buono del nove per decidere se qualcosa deve essere fatto da un parser o lexer è quello di porsi una domanda:

Dispone la sintassi ha qualunque, elementi di auto-similari ricorsive, annidati?
(ad esempio parentesi annidate, parentesi graffe, tag, sottoespressioni, subsentenze ecc.).

In caso contrario, semplici espressioni regolari è sufficiente e potrebbe essere fatto dal lexer.
Se sì, dovrebbe essere analizzato da un parser, perché è una grammatica context-free per lo meno.

Lexer è in genere per la ricerca di "parole" della vostra lingua e la loro classificazione (è un sostantivo?un verbo? un aggettivo? eccetera.).
Parser serve per trovare le "frasi" appropriate, strutturandole in un risultato se sono frasi appropriate in una determinata lingua.