Scrivere un parser [chiuso]

La soluzione migliore per impostare un parser semplice è un generatore di parser.

Il codice di parsing non banale può essere complicato rapidamente, e farlo correttamente senza renderlo orribilmente lento può facilmente trasformarsi in un gran casino, quindi la soluzione standard è scrivere una struttura di base del tipo di grammatica che si desidera analizzare in un linguaggio specifico del dominio e consente a un generatore di parser di convertirlo nell'effettiva logica di analisi.

Se lavori in C #, darei un'occhiata a Antlr4CS , un generatore di parser molto flessibile che produce Codice C #. Come ogni nuovo concetto di codifica, l'uso di ANTLR ci vorrà un po 'di tempo per abituarsi, ma funziona abbastanza bene una volta che hai capito le basi.

L'idea di base è che genererà la logica per te, creando una classe parser che restituisca un albero di analisi semplice, e potrai quindi utilizzare un Listener o Observer per rifinire quell'albero di analisi in base alle tue esigenze. (La familiarità con il pattern Visitor è utile.)

Non puoi sbagliare se impari a scrivere un parser di discesa ricorsivo .

Sono veloci, facili da scrivere e non sono necessari strumenti speciali.

Questo è ciò che fanno i professionisti. Ad esempio il Parser GCC è una discendenza ricorsiva scritta a mano.

AGGIUNTO, perché sei confuso:
Ecco alcuni pseudo-codice per provare a darti un'idea generale. Ho intenzionalmente omesso i dettagli e ho lasciato dei problemi per te da capire e / o modificare come ritieni opportuno:

parsValues(){
    if (parsLiteral()){
    } else if (parsChar('('){
        do {
            if (!parsLiteral()) ERROR...
        } while (parsChar(','));
        if (!parsChar(')')) ERROR...
    } else {
        ERROR...
    }
}

parsAnyAll(){
    if (parsWord("any") || parsWord("all")){
        parsValues()
    } else {
        ERROR...
    }
}

parsAnd(){
    parsAnyAll()
    while(parsWord("and")){
        parsAnyAll()
    }
}

parsOr(){
    parsAnd()
    while(parsWord("or")){
        parsAnd()
    }
}

parsSelect() {
    do {
        if (!parsColName()) ERROR("colname expected");
    } while (parsChar(','));
    if (!parsWord("from")) ERROR ...
    if (!parsTableName()) ERROR ...
    if (parsWord("where")){
        parsOr()
    }
}

Sono d'accordo con il consiglio di scrivere un parser di discesa ricorsivo. Anche se alla fine si finisce per usare strumenti di generazione del parser per lavori come questo, vale la pena scrivere almeno un parser a mano usando la discesa ricorsiva (e probabilmente almeno un'altra ancora usando l'algoritmo del cortile di smistamento per almeno parte del lavoro). / p>

Almeno nella mia mente, scrivere un parser di discesa ricorsivo inizia a dare una solida realizzazione di un paio di punti importanti:

1. Svolgere un'attività che inizialmente sembra quasi insormontabile e definire una soluzione in un modo che sia alquanto accessibile e trattabile.
2. Scrivere codice in modo veramente sistematico in modo che un insieme di funzioni funzioni insieme come un sistema senza soluzione di continuità.

Potrebbero non essere strettamente necessari, ma entrambi sono estremamente utili per passare da "hacker" a "software engineer".

Un sacco di codice scritto da persone che non hanno avuto questa esperienza mi ricorda la vecchia linea di un aereo che è "una collezione di pezzi di ricambio che volano in formazione ravvicinata" - codice che è uno accanto all'altro, ma non lo fa in realtà formano un sistema coerente (anche se, ovviamente, solo la scrittura di un parser non garantisce che il codice futuro necessariamente sarà molto meglio, ovviamente).