Come scrivere un interprete di comandi / parser?

22

Problema: esegui i comandi sotto forma di stringa.

  • esempio di comando:

    /user/files/ list all; equivalente a: /user/files/ ls -la;

  • un altro:

    post tw fb "HOW DO YOU STOP THE TICKLE MONSTER?;"

equivalente a:      post -tf "HOW DO YOU STOP THE TICKLE MONSTER?;"

Soluzione corrente:

tokenize string(string, array);

switch(first item in array) {
    case "command":
        if ( argument1 > stuff) {
           // do the actual work;
        }
}

I problemi che vedo in questa soluzione sono:

  • Nessun errore durante il controllo se non nested ifs, altrimenti all'interno di ciascun caso. Il la sceneggiatura diventa molto grande e difficile da mantenere.
  • I comandi e le risposte sono hardcoded.
  • Non c'è modo di sapere se i flag sono corretti o mancano i parametri.
  • Mancanza di intelligenza per suggerire "potresti voler eseguire $ command".

E l'ultima cosa che non posso indirizzare sono i sinonimi in diverse codifiche, ad esempio:

case command:
case command_in_hebrew:
    do stuff;
break;

L'ultimo potrebbe essere banale, ma beh, quello che voglio vedere sono le solide basi di questo tipo di programma.

Attualmente sto programmando questo in PHP, ma potrei farlo in PERL.

    
posta alfa64 17.12.2011 - 01:52
fonte

12 risposte

14

Permettetemi di ammettere francamente che la costruzione di parser è un lavoro noioso e si avvicina alla tecnologia del compilatore, ma costruirne uno si rivelerebbe una buona avventura. E un parser arriva con l'interprete. Quindi devi costruire entrambi.

Una breve introduzione a parser e interpreti

Questo non è troppo tecnico. Quindi gli esperti non mi agitano.

Quando si alimenta un input in un terminale, il terminale divide l'input in più unità. L'input è chiamato expression e le unità multiple sono chiamati token. Questi token possono essere operatori o simboli. Quindi se inserisci 4 + 5 in una calcolatrice, questa espressione viene divisa in tre token 4, +, 5. Il vantaggio è considerato un operatore con 4 e 5 simboli. Questo è passato ad un programma (consideralo come un interprete) che contiene la definizione per gli operatori. In base alla definizione (nel nostro caso, aggiungi), aggiunge i due simboli e restituisce il risultato al terminale. Tutti i compilatori sono basati su questa tecnologia. Il programma che divide un'espressione in più token è chiamato lexer e il programma che converte questi token in tag per un'ulteriore elaborazione ed esecuzione è chiamato parser.

Lex e Yacc sono le forme canoniche per costruire i lexer e parser basati su BNF grammatica sotto C ed è l'opzione consigliata. La maggior parte dei parser è un clone di Lex e Yacc.

Passi nella costruzione di un parser / intrepreter

  1. classifica i tuoi token in simboli, operatori e parole chiave (le parole chiave sono operatori)
  2. Crea la tua grammatica utilizzando il modulo BNF
  3. Scrivi le funzioni del parser per le tue operazioni
  4. Compilalo come un programma

Quindi nel caso precedente il tuo token di addizione sarebbe costituito da qualsiasi cifra e un segno più con la definizione di cosa fare con il segno più nel lexer

Note e suggerimenti

  • Scegli una tecnica parser che valuti da sinistra a destra LALR
  • Leggi questo libro del drago su Compilatori per avere un'idea di ciò. Io personalmente non ho finito il libro
  • Questo link fornirebbe una visione super veloce di Lex e Yacc sotto Python

Un approccio semplice

Se hai solo bisogno di un semplice meccanismo di analisi con funzioni limitate, trasforma i tuoi requisiti in un'espressione regolare e crea solo un sacco di funzioni. Per illustrare, si assuma un parser semplice per le quattro funzioni aritmetiche. Quindi tu chiameresti prima l'operatore e poi l'elenco di funzioni (simile a lisp) nello stile (+ 4 5) o (add [4,5]) , quindi potresti usare un semplice RegExp per ottenere l'elenco degli operatori e dei simboli su cui operare .

I casi più comuni potrebbero essere facilmente risolti con questo approccio. Lo svantaggio è che non puoi avere molte espressioni nidificate con una sintassi chiara e non puoi avere funzioni di ordine superiore facili.

    
risposta data 21.12.2011 - 13:31
fonte
7

In primo luogo, quando si parla di grammatica, o come specificare argomenti, non inventare il proprio. Lo standard GNU è già molto popolare e ben noto.

In secondo luogo, dal momento che stai usando uno standard accettato, non reinventare la ruota. Usa una libreria esistente per farlo per te. Se si usano gli argomenti di stile GNU, c'è quasi certamente una biblioteca matura nella propria lingua di scelta già. Ad esempio: c # , php , c .

Una buona libreria di analisi delle opzioni consente persino di stampare una guida formattata sulle opzioni disponibili per te.

MODIFICA 12/27

Sembra che tu lo stia rendendo più complicato di quanto non sia.

Quando guardi una riga di comando, è davvero piuttosto semplice. Sono solo opzioni e argomenti per queste opzioni. Ci sono pochissimi problemi complicati. L'opzione può avere alias. Gli argomenti possono essere elenchi di argomenti.

Un problema con la tua domanda è che non hai realmente specificato alcuna regola per quale tipo di riga di comando vorresti gestire. Ho suggerito lo standard GNU ei tuoi esempi si avvicinano a questo (anche se non capisco il tuo primo esempio con il percorso come primo elemento?).

Se stiamo parlando di GNU, ogni singola opzione può avere solo una forma lunga e una forma breve (carattere singolo) come alias. Qualsiasi argomento contenente uno spazio deve essere racchiuso tra virgolette. Molteplici opzioni di forma breve possono essere concatenate. Le opzioni di forma breve devono essere precedute da un trattino singolo, formato lungo da due trattini. Solo l'ultima delle opzioni concatenate per i moduli brevi può avere un argomento.

Tutto molto semplice. Tutto molto comune. Inoltre è stato implementato in tutte le lingue che puoi trovare, probabilmente cinque volte.

Non scrivere. Usa ciò che è già scritto.

Se non hai in mente qualcosa in più rispetto agli argomenti standard della riga di comando, usa solo una delle MOLTE librerie già esistenti e testate per farlo.

Qual è la complicazione?

    
risposta data 21.12.2011 - 11:47
fonte
4

Hai già provato qualcosa come link ? Questo approccio è molto più pulito di qualsiasi altro scritto a mano, ma non richiede uno strumento autonomo di generazione del codice come Lemon.

EDIT: E un trucco generale per gestire le righe di comando con sintassi complessa consiste nel combinare gli argomenti in una singola stringa separata da spazi bianchi e quindi analizzarli correttamente come se fosse un'espressione di qualche dominio -specific language.

    
risposta data 19.12.2011 - 09:02
fonte
1

Non hai dato molti dettagli sulla tua grammatica, solo alcuni esempi. Quello che posso vedere è che ci sono alcune stringhe, uno spazio bianco e un (probabilmente il tuo esempio è indifferente nella tua domanda) una stringa doppiamente citata e poi una ";" alla fine.

Sembra che questo potrebbe essere simile alla sintassi di PHP. Se è così, PHP viene fornito con un parser, è possibile riutilizzarlo e quindi convalidarlo in modo più concreto. Finalmente hai bisogno di gestire i token, ma sembra che questo sia semplicemente da sinistra a destra, quindi in realtà solo un'iterazione su tutti i token.

Alcuni esempi di riutilizzo del parser di token PHP ( token_get_all ) sono indicati nelle risposte alle seguenti domande:

Entrambi gli esempi contengono anche un semplice parser, probabilmente qualcosa di simile a quello che si adatta al tuo scenario.

    
risposta data 17.12.2011 - 02:05
fonte
1

Se i tuoi bisogni sono semplici, ed entrambi ne hai il tempo e ti interessano, andrò molto contro e dirò di non rifuggire dallo scrivere il tuo parser. È una buona esperienza di apprendimento, se non altro. Se hai requisiti più complessi - chiamate di funzioni nidificate, array, ecc. - tieni presente che fare ciò potrebbe richiedere un bel po 'di tempo. Uno dei grandi aspetti positivi del rolling your own è che non ci sarà un problema di integrazione con il tuo sistema. Il rovescio della medaglia è, naturalmente, tutti i fallimenti sono colpa tua.

Lavorare contro i token, però, non usare comandi codificati. Quindi quel problema con comandi simili sembra scomparire.

Tutti raccomandano sempre il libro del drago, ma ho sempre trovato "Scrittura di compilatori e interpreti" di Ronald Mak per essere una migliore introduzione.

    
risposta data 22.12.2011 - 05:56
fonte
0

Ho scritto programmi che funzionano così. Uno era un bot IRC che ha una sintassi di comando simile. C'è un file enorme che è una grande affermazione dell'interruttore. Funziona - funziona velocemente - ma è un po 'difficile da mantenere.

Un'altra opzione, che ha più spin di OOP, è usare i gestori di eventi. Crei un array di valori-chiave con i comandi e le loro funzioni dedicate. Quando viene dato un comando, si controlla se la matrice ha la chiave data. Se lo fa, chiama la funzione. Questa sarebbe la mia raccomandazione per il nuovo codice.

    
risposta data 17.12.2011 - 02:10
fonte
0

Suggerisco di usare uno strumento, invece di implementare autonomamente un compilatore o un interprete. Irony usa C # per esprimere la grammatica della lingua di destinazione (la grammatica della tua linea di comando). La descrizione su CodePlex dice: "Irony è un kit di sviluppo per l'implementazione di linguaggi su piattaforma .NET."

Consulta la home page ufficiale di Irony su CodePlex: Irony - Kit di implementazione della lingua .NET .

    
risposta data 21.12.2011 - 15:22
fonte
0

Il mio consiglio sarebbe google per una libreria che risolva il tuo problema.

Ultimamente ho usato NodeJS ultimamente e Optimist è ciò che utilizzo per l'elaborazione da riga di comando. Ti incoraggio a cercarne uno che puoi usare per la tua lingua preferita. In caso contrario, scrivine uno e apri la fonte: D Puoi anche leggere il codice sorgente di Optimist e portarlo nella tua lingua preferita.

    
risposta data 21.12.2011 - 18:50
fonte
0

Perché non semplifichi un po 'le tue esigenze?

Non utilizzare un parser completo, è troppo complesso e persino non necessario per il tuo caso.

Crea un ciclo, scrivi un messaggio che rappresenta il tuo "prompt", può essere il percorso corrente che sei.

Attendi una stringa, "analizza" la stringa e fai qualcosa in base al contenuto della stringa.

La stringa potrebbe "analizzare" come se si aspettasse una linea, in cui gli spazi sono i separatori ("tokenizer") e il resto dei caratteri sono raggruppati.

Esempio.

Il programma emette (e rimane sulla stessa riga): / User / files / L'utente scrive (nella stessa riga) elenca tutti;

Il tuo programma genererà un elenco, una raccolta o un array come

list

all;

o, if ";" è considerato un separatore come spazi

/user/files/

list

all

Il tuo programma potrebbe iniziare aspettandosi una singola istruzione, senza "pipe" in stile Unix, né reindirizzamento in stile windowze.

Il tuo programma potrebbe creare un dizionario di istruzioni, ogni istruzione può avere un elenco di parametri.

Il modello di progettazione del comando si applica al tuo caso:

link

Questo è uno pseudocodice "plain c", non testato o finito, solo un'idea di come potrebbe essere fatto.

Potresti anche renderlo più orientato agli oggetti, e nel linguaggio di programmazione, ti piace.

Esempio:

// "global function" pointer type declaration
typedef
  void (*ActionProc) ();

struct Command
{
  char[512] Identifier;
  ActionProc Action; 
};

// global var declarations

list<char*> CommandList = new list<char*>();
list<char*> Tokens = new list<char*>();

void Action_ListDirectory()
{
  // code to list directory
} // Action_ListDirectory()

void Action_ChangeDirectory()
{
  // code to change directory
} // Action_ChangeDirectory()

void Action_CreateDirectory()
{
  // code to create new directory
} // Action_CreateDirectory()

void PrepareCommandList()
{
  CommandList->Add("ls", &Action_ListDirectory);
  CommandList->Add("cd", &Action_ChangeDirectory);
  CommandList->Add("mkdir", &Action_CreateDirectory);

  // register more commands
} // void PrepareCommandList()

void interpret(char* args, int *ArgIndex)
{
  char* Separator = " ";
  Tokens = YourSeparateInTokensFunction(args, Separator);

  // "LocateCommand" may be case sensitive
  int AIndex = LocateCommand(CommandList, args[ArgIndex]);
  if (AIndex >= 0)
  {
    // the command

    move to the next parameter
    *ArgIndex = (*ArgIndex + 1);

    // obtain already registered command
    Command = CommandList[AIndex];

    // execute action
    Command.Action();
  }
  else
  {
    puts("some kind of command not found error, or, error syntax");
  }  
} // void interpret()

void main(...)
{
  bool CanContinue = false;
  char* Prompt = "c\:>";

  char Buffer[512];

  // which command line parameter string is been processed
  int ArgsIndex = 0;

  PrepareCommandList();

  do
  {
    // display "prompt"
    puts(Prompt);
    // wait for user input
      fgets(Buffer, sizeof(Buffer), stdin);

    interpret(buffer, &ArgsIndex);

  } while (CanContinue);

} // void main()

Non hai menzionato il tuo linguaggio di programmazione. Puoi anche menzionare qualsiasi linguaggio di programmazione, ma preferibilmente "XYZ".

    
risposta data 23.12.2011 - 00:27
fonte
0

hai diversi compiti davanti a te.

guardando i tuoi requisiti ...

  • Devi analizzare il comando. È un compito abbastanza facile
  • È necessario avere una lingua di comando estensibile.
  • È necessario avere controllo degli errori e suggerimenti.

Il linguaggio di comando estensibile indica che è richiesto un DSL. Ti suggerirei di non far girare il tuo ma usando JSON se le tue estensioni sono semplici. Se sono complessi, la sintassi dell'espressione s è piacevole.

Il controllo degli errori implica che il tuo sistema sia a conoscenza dei possibili comandi. Sarebbe parte del sistema post-comando.

Se I implementava tale sistema da zero, usavo Common Lisp con un lettore ridotto. Ogni token comando verrebbe mappato a un simbolo, che verrebbe specificato in un file RC di s-expression. Dopo la tokenizzazione, sarebbe valutata / espansa in un contesto limitato, intrappolando gli errori e ogni pattern di errore riconoscibile restituirebbe suggerimenti. Successivamente, il comando effettivo verrà inviato al sistema operativo.

    
risposta data 23.12.2011 - 00:57
fonte
0

C'è una bella funzionalità in programmazione funzionale che potresti essere interessata a esaminare.

Si chiama corrispondenza del modello .

Ecco due link per alcuni esempi di abbinamento di modelli in Scala e in F# .

Sono d'accordo con te sul fatto che l'utilizzo di switch strutture sia un po 'noioso, e mi è particolarmente piaciuto usare durate di parentesi Patern per l'implementazione di un compilatore in Scala.

In particolare, ti consiglierei di esaminare l' lambda calcolo esempio del sito web di Scala.

Questo è, a mio avviso, il modo più intelligente per procedere, ma se devi attenersi strettamente a PHP, allora sei bloccato con il "vecchio-scuola" switch .

    
risposta data 23.12.2011 - 23:47
fonte
0

Controlla Apache CLI , l'intero scopo sembra fare esattamente ciò che vuoi fare quindi, anche se non puoi utilizzarlo, puoi verificarne l'architettura e copiarlo.

    
risposta data 21.12.2011 - 22:38
fonte

Leggi altre domande sui tag