Il generatore di parser ANTLR è il migliore per un'applicazione C++ con memoria vincolata?

Question

Sto cercando un buon generatore di parser che possa essere utilizzato per leggere un formato di file di testo personalizzato nella nostra grande app commerciale. Attualmente questo particolare formato di file viene letto con un parser ricorsivo fatto a mano, ma il formato è cresciuto e complessificato al punto in cui tale approccio è diventato ingestibile.

Sembra che la soluzione definitiva sarebbe quella di creare una grammatica corretta per questo formato e quindi utilizzare un generatore di parser reale come yacc per leggerlo, ma ho difficoltà a decidere quale generatore utilizzare o anche se sono " vale la pena il problema. Ho esaminato ANTLR e Spirit, ma il nostro progetto ha vincoli specifici oltre earlier answers che mi fanno chiedere se sono appropriati per noi. In particolare, ho bisogno di:

• Un parser che genera codice C o C++ con MSVC. ANTLR 3 non supporta C++; sostiene di generare una C diritta, ma i documenti su come farlo funzionare effettivamente sono un po 'confusi.
• Utilizzo della memoria gravemente limitato. La memoria ha un enorme vantaggio nella nostra app e anche minuscole perdite sono fatali. Devo essere in grado di sovrascrivere l'allocatore di memoria del parser per usare il nostro malloc() personalizzato, o per lo meno ho bisogno di dargli un pool contiguo da cui attinge tutta la sua memoria (e che posso deallocare in blocco in seguito). Posso risparmiare circa 200kb per l'eseguibile del parser stesso, ma qualunque heap dinamico che assegna all'analisi deve essere liberato in seguito.
• Buona prestazione. Questo è meno critico ma dovremmo essere in grado di analizzare 100kb di testo in non più di un secondo su un processore 3ghz.
• Deve essere privo di GPL. Non possiamo usare il codice GNU.

Mi piacciono gli strumenti IDE e di debug di ANTLRworks, ma sembra che ottenere il proprio target C per funzionare effettivamente con la nostra app sarà un'impresa enorme. Prima che mi imbarchi su questa paletta, ANTLR è lo strumento giusto per questo lavoro?

Il formato di testo in questione sembra qualcosa di simile:

attribute "FluxCapacitance" real constant 

asset DeLorean 
{ 
    //comment foo bar baz 
    model "delorean.mdl" 
    animation "gullwing.anm" 
    references "Marty" 
    loadonce 
} 

template TimeMachine 
{ 
    attribute FluxCapacitance 10  
    asset DeLorean 
} 

Answer 1

ANTLR 3 non supporta C++; afferma che genera il C diritto ma i documenti su che lo fanno funzionare effettivamente sono in ordine di di confusione.

Genera C e, inoltre, funziona con Visual Studio e C++. Lo so perché l'ho già fatto e ho inviato una patch per farlo funzionare con stdcall.

La memoria ha un enorme vantaggio nella nostra app e persino piccole perdite sono fatali. Ho bisogno di essere in grado di ignorare allocatore memoria del parser di utilizzare il nostro personalizzato malloc(), o per lo meno ho bisogno di dargli una piscina contigui da cui trae tutta la sua memoria (e che posso deallocate in blocco in seguito). Posso risparmiare circa 200kb per l'eseguibile del parser stesso, ma lo stack dinamico che alloca nell'assegnazione deve essere liberato in seguito, .

Il runtime antlr3c, l'ultima volta che ho controllato non ha una perdita di memoria e utilizza il paradigma del pool di memoria che descrivi. Tuttavia, ha una lacuna nell'API che l'autore rifiuta di cambiare, ovvero che se richiedi la stringa di un nodo, creerà una nuova copia ogni volta fino a liberare l'intero parser.

Non ho commenti sulla facilità di utilizzo di un malloc personalizzato, ma ha una macro per definire quale funzione di malloc utilizzare nell'intero progetto.

Per quanto riguarda la dimensione dell'eseguibile, la mia compilation aveva una dimensione di circa 100 kb comprendente un piccolo interprete.

Il mio suggerimento è di continuare ad apprendere ANTLR, perché soddisfa ancora le vostre esigenze e probabilmente è necessario sacrificare un po 'più di tempo prima che inizi a funzionare per voi.

Answer 2

parser ANTLR, e di fatto qualsiasi parser costruita con qualcosa LALR o simili, tendono ad essere grande. Hai una grammatica reale per questo? È sembra come potrebbe essere analizzato più facilmente con un parser ricorsivo-discendente scritto a mano, ma non è molto di un campione.

Oops, errore mio, poiché ANTLR genera apparentemente la discesa ricorsiva. Tuttavia, ho avuto problemi con ANTLR generando grandi parser.

Answer 3

Utilizziamo con successo Boost Spirit nella nostra applicazione. Il Boost license è molto liberale, quindi non ci sono problemi nell'utilizzarlo nelle applicazioni commerciali.

Quote from the documentation:

Spirito è un quadro generatore di parser ricorsivo discesa-orientato agli oggetti implementato utilizzando template tecniche di meta-programmazione. I modelli di espressione ci consentono di approssimare la sintassi di Extended Backus-Normal Form (EBNF) completamente in C++. Il framework Spirit consente di scrivere una grammatica di destinazione esclusivamente in C++.Le specifiche grammaticali EBNF in linea possono essere mescolate liberamente con altri codici C++ e, grazie alla potenza generativa dei modelli C++, sono immediatamente eseguibili. In retrospettiva, compilatori-compilatori convenzionali o generatori di parser devono eseguire un ulteriore passaggio di conversione dal codice EBNF di origine al codice C o C++.

Answer 4

Allora perché non usi flex/yacc? Genera codice C, può essere eseguito da MSVC, è stato sviluppato pensando all'efficienza, può avere overrid di malloc (google per yymalloc), sono essi stessi GPL, ma il codice risultante (il codice che usi nel tuo progetto) AFAIK no.

Oppure utilizzare un parser fatto a mano.

Answer 5

Realisticamente, se la grammatica è relativamente piccola e non contiene molte ambiguità o complessità di analisi, non dovrebbe essere importante se si utilizza un parser di discesa ricorsivo o un parser di riduzione del turno.

Direi un'occhiata a ANTLR e Spirit, anche a guardare Flex e Bison. Ci sono anche altri parser meno conosciuti come Coco/R (contiene generatori per molte lingue, incluso C++).

Answer 6

Un parser di discesa ricorsivo codificato manualmente è in realtà piuttosto veloce e può essere molto compatto. L'unico lato negativo è che devi stare attento a per codificare essenzialmente le grammatiche LL (1).[Se usi ANTLR, hai restrizioni simili, quindi questo non è un grosso problema].

È possibile eseguire il codice di tali parser come codice C semplice ricorsivo. (Vedere questa risposta per i dettagli completi: Is there an alternative for flex/bison that is usable on 8-bit embedded systems?)

Se siete veramente a corto di spazio, è possibile definire un parsing macchina virtuale, e costruire un piccolo C interprete per eseguirlo. Ho iniziato a costruire interpreti BASIC così nei primi anni '70.

Attaccando alle semplicissime convenzioni che rendono effettivi questi parser , è possibile garantire che non vi siano perdite di memoria causate dal meccanismo di analisi, ovvero . (Naturalmente, è possibile associare al parser azioni arbitrarie in cui riconosce gli elementi di interesse , indipendentemente dal fatto che tali azioni perdano è una questione di programmazione generale, non il parser).

Le idee provenivano da un documento del 1964 sui metacompilatori di Val Schorre, che mostra come compilare compilatori completi in 10 pagine. Il piccolo generatore di parser di Shorre produce parser ricorsivi in ​​discesa piuttosto buoni . Un sito che descrive questa carta e mostrando esattamente come costruire tali parser può essere trovato alla http://www.bayfronttechnologies.com/metaii.html

ho usato i metodi di Schorre di costruire compilatori di base verso la fine degli anni '70, dopo mi sono stancato di grammatiche complesse codifica manuale.

Answer 7

Si prega di dare un'occhiata al nuovo target C++ che ho pubblicato per ANTLR. Ha anche la possibilità di limitare l'uso della memoria del parser e espone tutte le routine di gestione della memoria necessarie sotto forma di tratti.

http://www.antlr.org/wiki/pages/viewpage.action?pageId=29130826