Perché alcuni compilatori preferiscono il parser fatto a mano sui generatori di parser?

Question

Secondo la documentazione di Vala: "Prima di 0.3.1, il parser di Vala era il classico scanner per scanner flex e Bison LALR, ma a partire da commit eba85a, il parser è un parser di discesa ricorsivo realizzato a mano." La mia domanda è: perché?

La domanda può essere indirizzata a qualsiasi compilatore che non stia utilizzando il generatore di parser. Quali sono i pro e i contro per tale passaggio dal parser generator al parser fatto a mano? Quali sono gli svantaggi dell'utilizzo di generatori di parser (Bison, ANTLR) per i compilatori?

Come commento a parte: sono interessato a Vala in particolare perché mi piace l'idea di avere un linguaggio con funzionalità moderne e sintassi pulita ma compilabile in linguaggio di alto livello "nativo" e "non gestito" (C in caso di Vala). Ho trovato solo Vala finora. Sto pensando di divertirmi facendo compilare Vala (o un linguaggio simile) in C++ (supportato da Qt libs). Ma dal momento che non voglio inventare un linguaggio completamente nuovo, sto pensando di prendere una grammatica esistente. Ovviamente i parser fatti a mano non hanno una grammatica formale scritta che potrei riutilizzare. I tuoi commenti su questa idea sono ben accetti (l'intera idea è sciocca?).

Answer 1

LR (1) e LALR (1) parser sono davvero, davvero fastidioso per due motivi:

1. generatore Il parser non è molto bravo a produrre messaggi di errore utili.
2. Determinati tipi di ambiguità, come i blocchi in stile C if else, rendono la scrittura della grammatica molto dolorosa.

D'altra parte, la grammatica LL (1) è molto meglio in entrambe queste cose. La struttura delle grammatiche LL (1) li rende molto facili da codificare come parser di discesa ricorsivi, e quindi trattare con un generatore di parser non è davvero una vittoria.

Inoltre, nel caso di Vala, il parser e lo stesso compilatore vengono presentati come una libreria, quindi è possibile creare un backend personalizzato per il compilatore Vala utilizzando la libreria del compilatore Vala e ottenere tutti i controlli di analisi e tipo e gratuito.

Answer 2

Secondo la documentazione Vala: "Prima 0.3.1, parser di Vala è stato il classico scanner flex e la combinazione di parser Bison LALR Ma, come di commit eba85a, il parser è un parser ricorsivo discesa artigianale." La mia domanda è: perché?

Qui sto specificatamente chiedendo di Vala, sebbene la domanda possa essere indirizzata a qualsiasi compilatore che non stia utilizzando il generatore di parser. Che cosa sono i pro e i contro per questo passaggio dal generatore di parser al parser creato a mano ? Quali sono gli svantaggi dell'uso dei generatori di parser (Bison, ANTLR) per i compilatori?

Forse i programmatori hanno individuato alcune vie per l'ottimizzazione che il generatore di parser non ha individuato, e queste vie per l'ottimizzazione richiedevano un algoritmo di analisi completamente diverso. In alternativa, forse il generatore di parser ha generato il codice in C89 e i programmatori hanno deciso che il refactoring per C99 o C11 migliorerebbe la leggibilità.

Come un commento a margine: Sono interessato a Vala proprio perché mi piace l'idea di avere la lingua con caratteristiche moderne e la sintassi pulita ma compilabile in linguaggio di alto livello "nativo" e "non gestito" (C nel caso di Vala).

Solo una breve nota: C non è nativo. Ha le sue radici nella portabilità , in quanto è stato progettato per astrarre i dettagli specifici dell'hardware/sistema operativo che hanno causato così tanto dolore ai programmatori durante il porting. Ad esempio, pensate al dolore nell'usare un diverso fopen per ogni sistema operativo e/o file system; Non intendo semplicemente diverse nella funzionalità, ma anche diverse in termini di aspettative di input e output, ad es. argomenti diversi, diversi valori di ritorno. Allo stesso modo, C11 introduce thread portatili; Il codice che utilizza le discussioni sarà in grado di utilizzare lo stesso codice conforme a C11 per indirizzare tutti i sistemi operativi che implementano i thread.

Ho trovato Vala finora.Sto pensando di divertirmi realizzando Vala (o linguaggio simile) compilabile in C++ (supportato da librerie Qt). Ma dal non voglio inventare un linguaggio completamente nuovo, sto pensando di prendere la grammatica esistente con lo . Ovviamente i parser fatti a mano non hanno la grammatica formale scritta che potrei riutilizzare. I tuoi commenti su questa idea sono benvenuto (l'intera idea è sciocca?).

Potrebbe essere possibile utilizzare il parser manuale per produrre codice C++ con poco sforzo, quindi non getteremo questa opzione da parte così rapidamente; Il vecchio generatore di parser flex/bison può o non può essere più utile. Tuttavia, questa non è la tua unica opzione. In ogni caso, sarei tentato di studiare the specification estensivamente.

Answer 3

È curioso che questi autori siano passati da bisonti a RD. La maggior parte delle persone andrebbe nella direzione opposta.

L'unica vera ragione che posso vedere per fare ciò che gli autori Vala hanno fatto sarebbe stato un migliore recupero degli errori, o forse la loro grammatica non è molto pulita.

Penso che scoprirete che la maggior parte delle nuove lingue inizia con parser scritti a mano mentre gli autori hanno un'idea del loro nuovo linguaggio e capiscono esattamente cosa vogliono fare. Inoltre, in alcuni casi, gli autori imparano a scrivere compilatori. C è un esempio classico, come lo è C++. Più avanti nell'evoluzione un parser generato può essere sostituito. I compilatori per lingue standard esistenti invece possono essere sviluppati più rapidamente tramite un generatore di parser, possibilmente anche tramite una grammatica esistente: il time to market è un parametro aziendale critico di questi progetti.

Answer 4

So che questo non sta per essere definitiva, e se le vostre domande non erano specificamente Vala-correlati Non mi preoccuperei, ma dal momento che sono ...

non ero troppo pesantemente coinvolto con il progetto allora non sono chiaro su alcuni dettagli, ma la ragione principale per cui ricordo quando Vala è passato è stata dogfooding. Non sono sicuro che sia stata la motivazione principale, ma ricordo che è stato un fattore.

Anche la manutenzione era un problema. Quella patch sostituiva un parser più grande scritto in C/Bison/YACC (relativamente poche persone hanno una significativa esperienza con questi ultimi due) con un parser più piccolo in Vala (che praticamente chiunque sia interessato a lavorare su Valac probabilmente conosce e si trova a suo agio).

Anche la segnalazione degli errori migliori era un obiettivo, IIRC.

Non so se fosse un fattore, ma il parser scritto a mano è un parser di discesa ricorsivo. So che ANTLR genera quelli, l'ANTLR è scritto in Java, che è una dipendenza piuttosto pesante (sì, lo so che non è una dipendenza run-time, ma ancora).

Come un commento a margine: Sono interessato a Vala proprio perché mi piace l'idea di avere la lingua con caratteristiche moderne e la sintassi pulito ma compilabile in "nativo" e "non gestito" linguaggio di alto livello (C nel caso in cui di Vala). Ho trovato solo Vala finora. Sto pensando di divertirmi facendo compilare Vala (o un linguaggio simile) in C++ (supportato da Qt libs). Ma dal momento che non voglio inventare un linguaggio completamente nuovo, sto pensando di prendere una grammatica esistente. Ovviamente i parser fatti a mano non hanno una grammatica formale scritta che potrei riutilizzare. I tuoi commenti su questa idea sono ben accetti (l'intera idea è sciocca?).

Un sacco di Vala è davvero un riflesso delle decisioni prese da GObject, e le cose possono o non possono funzionare allo stesso modo in C++/Qt. Se il tuo obiettivo è quello di sostituire GObject/C in valac con Qt/C++, probabilmente avrai più lavoro di quanto ti aspetti. Se, tuttavia, si desidera rendere accessibili le librerie C++ e Qt da Vala, ciò dovrebbe essere certamente possibile. Infatti, Luca Bruno ha iniziato a lavorarci circa un anno fa (vedi il ramo wip/cpp). Non ha visto attività per un po 'a causa della mancanza di tempo, non di problemi tecnici.

Answer 5

Ho scritto una mezza dozzina di parser fatti a mano (nella maggior parte dei casi parser di discesa ricorsivo, un parser top-down AKA) nella mia carriera e ho visto parser generati da generatori di parser e devo ammettere che sono prevenuto sui generatori di parser.

Ecco alcuni pro e contro per ciascun approccio.

generatori Parser

Pro:

• ottenere rapidamente un parser di lavoro (almeno se non si sa come il codice è a mano).

Contro:

• codice generato è difficile da capire ed eseguire il debug.
• Difficile implementare la corretta gestione degli errori. Il generatore creerà un parser corretto per il codice sintatticamente corretto ma si soffocherà su un codice errato e nella maggior parte dei casi non sarà in grado di fornire i messaggi di errore corretti.
• Un errore nel generatore di parser può interrompere il progetto. È necessario correggere l'errore nel codice di qualcun altro (se il codice sorgente è disponibile), attendere che l'autore lo risolva o risolvere il problema (se possibile).

realizzata a mano discesa ricorsiva parser

Pro:

• codice generato è facile da capire. I parser ricorsivi di solito hanno una funzione corrispondente a ciascun costrutto linguistico, ad es. parseWhile per analizzare un'istruzione 'while', parseDeclaration per analizzare una dichiarazione e così via. Capire e fare il debug del parser è facile.
• È facile fornire messaggi di errore significativi, ripristinare gli errori e continuare l'analisi nel modo più appropriato in una situazione particolare.

Contro:

• Ci vorrà del tempo per il codice a mano il parser, soprattutto se non si dispone di un'esperienza con questa roba.

• Il parser potrebbe essere un po 'lento. Questo vale per tutti i parser ricorsivi, non solo per quelli scritti a mano. Avendo una funzione corrispondente a ciascun costrutto di linguaggio per analizzare un semplice valore letterale numerico, il parser può effettuare una dozzina o più chiamate nidificate a partire da es. parseExpression attraverso parseAddition, parseMultiplication, ecc. parseLiteral. Le chiamate di funzione sono relativamente poco costose in un linguaggio come C, ma rappresentano comunque un tempo significativo.

Una soluzione per accelerare un parser ricorsivo è quello di sostituire le parti del parser ricorsivo da un sub-parser bottom-up, che spesso è molto più veloce. I candidati naturali per tale sub-parser sono le espressioni che hanno una sintassi quasi uniforme (cioè espressioni binarie e unarie) con diversi livelli di precedenza. Il parser dal basso verso l'alto per un'espressione è in genere anche codice semplice da manipolare, spesso è solo un ciclo che riceve token di input dal lexer, una pila di valori e una tabella di ricerca delle precedenze dell'operatore per i token operatore.