Wie schreibe ich einen Befehlsinterpreter / Parser?

Problem: Führen Sie Befehle in Form einer Zeichenfolge aus.

• befehlsbeispiel:

  /user/files/ list all; gleichwertig: /user/files/ ls -la;

• noch einer:

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

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

Aktuelle Lösung:

tokenize string(string, array);

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

Die Probleme, die ich in dieser Lösung sehe, sind:

• Keine Fehlerprüfung außer geschachteltem ifs-else in jedem Fall. Das Skript wird sehr groß und schwer zu pflegen.
• Befehle und Antworten sind fest codiert.
• Keine Möglichkeit zu wissen, ob Flags korrekt sind oder ob Parameter fehlen.
• Mangelnde Intelligenz, die andeutet, dass Sie möglicherweise $ command ausführen möchten.

Und das Letzte, was ich nicht ansprechen kann, sind Synonyme in verschiedenen Kodierungen, zum Beispiel:

case command:
case command_in_hebrew:
    do stuff;
break;

Das letzte mag trivial sein, aber was ich sehen möchte, sind die soliden Fundamente für diese Art von Programm.

Ich programmiere dies derzeit in PHP, aber möglicherweise in PERL.

Lassen Sie mich ehrlich zugeben, das Erstellen von Parser ist eine mühsame Aufgabe und kommt der Compilertechnologie sehr nahe, aber das Erstellen eines solchen Parsers würde sich als gutes Abenteuer herausstellen. Und ein Parser kommt mit Dolmetscher. Also musst du beides bauen.

Eine kurze Einführung in Parser und Dolmetscher

Das ist nicht zu technisch. Experten ärgern sich nicht über mich.

Wenn Sie einen Eingang in ein Terminal einspeisen, teilt das Terminal den Eingang in mehrere Einheiten auf. Die Eingabe wird Ausdruck genannt und die mehreren Einheiten werden Token genannt. Diese Token können Operatoren oder Symbole sein. Wenn Sie also 4 + 5 in einen Taschenrechner eingeben , wird dieser Ausdruck in drei Token 4, +, 5 aufgeteilt. Das Plus wird als Operator betrachtet, während 4 und 5 Symbole. Dies wird an ein Programm übergeben (betrachten Sie dies als einen Interpreter), das die Definition für die Operatoren enthält. Basierend auf der Definition (in unserem Fall add) werden die beiden Symbole hinzugefügt und das Ergebnis an das Terminal zurückgegeben. Alle Compiler basieren auf dieser Technologie. Das Programm, das einen Ausdruck in mehrere Token aufteilt, wird als Lexer bezeichnet, und das Programm, das diese Token zur weiteren Verarbeitung und Ausführung in Tags umwandelt, wird als Parser bezeichnet.

Lex und Yacc sind die kanonischen Formen zum Erstellen von Lexern und Parsern auf der Basis der BNF- Grammatik unter C und werden empfohlen. Die meisten Parser sind Klone von Lex und Yacc.

Schritte zum Aufbau eines Parsers / Intrepreters

1. Klassifizieren Sie Ihre Token in Symbole, Operatoren und Schlüsselwörter (Schlüsselwörter sind Operatoren)
2. Erstellen Sie Ihre Grammatik mit dem BNF-Formular
3. Schreiben Sie Parser-Funktionen für Ihre Operationen
4. Kompiliere es und führe es als Programm aus

In dem obigen Fall wären Ihre zusätzlichen Token beliebige Ziffern und ein Pluszeichen mit der Definition, was mit dem Pluszeichen im Lexer zu tun ist

Hinweise und Tipps

• Wählen Sie eine Parser-Technik, die von links nach rechts LALR auswertet
• Lesen Sie dieses Drachenbuch über Compiler , um ein Gefühl dafür zu bekommen. Ich persönlich habe das Buch noch nicht fertiggestellt
• Dieser Link würde einen superschnellen Einblick in Lex und Yacc unter Python geben

Ein einfacher Ansatz

Wenn Sie nur einen einfachen Analysemechanismus mit eingeschränkten Funktionen benötigen, wandeln Sie Ihre Anforderung in einen regulären Ausdruck um und erstellen Sie einfach eine ganze Reihe von Funktionen. Nehmen Sie zur Veranschaulichung einen einfachen Parser für die vier arithmetischen Funktionen an. Sie würden also zuerst den Operator aufrufen und dann die Liste der Funktionen (ähnlich wie bei lisp) im Stil (+ 4 5)oder(add [4,5]) Sie könnten ein einfaches RegExp verwenden, um die Liste der Operatoren und der zu bearbeitenden Symbole abzurufen.

Die meisten gängigen Fälle könnten mit diesem Ansatz leicht gelöst werden. Der Nachteil ist, dass Sie nicht viele verschachtelte Ausdrücke mit einer klaren Syntax haben und keine einfachen Funktionen höherer Ordnung haben können.

Erstens, wenn es um Grammatik geht oder wie man Argumente spezifiziert, erfinde nicht deine eigenen. Der GNU-Style-Standard ist bereits sehr beliebt und bekannt.

Zweitens, da Sie einen akzeptierten Standard verwenden, erfinden Sie das Rad nicht neu. Verwenden Sie eine vorhandene Bibliothek, um dies für Sie zu tun. Wenn Sie Argumente im GNU-Stil verwenden, gibt es mit ziemlicher Sicherheit bereits eine ausgereifte Bibliothek in der Sprache Ihrer Wahl. Zum Beispiel: c # , php , c .

Eine gute Optionsanalysebibliothek gibt sogar formatierte Hilfe zu den verfügbaren Optionen aus.

EDIT 12/27

Es scheint, als ob Sie das komplizierter machen als es ist.

Wenn Sie sich eine Befehlszeile ansehen, ist das ganz einfach. Es sind nur Optionen und Argumente für diese Optionen. Es gibt nur sehr wenige komplizierende Probleme. Option kann Aliase haben. Argumente können Listen von Argumenten sein.

Ein Problem mit Ihrer Frage ist, dass Sie keine Regeln für die Art der Befehlszeile angegeben haben, mit der Sie sich befassen möchten. Ich habe den GNU-Standard vorgeschlagen, und Ihre Beispiele kommen dem sehr nahe (obwohl ich Ihr erstes Beispiel mit dem Pfad als erstem Element nicht wirklich verstehe?).

Wenn es sich um GNU handelt, kann jede einzelne Option nur eine lange Form und eine kurze Form (ein einzelnes Zeichen) als Aliase haben. Argumente, die ein Leerzeichen enthalten, müssen in Anführungszeichen gesetzt werden. Es können mehrere Kurzformoptionen verkettet werden. Kurzformoption (en) müssen mit einem Strich, Langform mit zwei Strichen fortgesetzt werden. Nur die letzten verketteten Kurzformoptionen können ein Argument haben.

Alles sehr unkompliziert. Alles sehr häufig. Wurde auch in jeder Sprache implementiert, die Sie finden können, wahrscheinlich fünfmal.

Schreib es nicht. Verwenden Sie, was bereits geschrieben wurde.

Verwenden Sie nur eine der VIELEN bereits vorhandenen, getesteten Bibliotheken, sofern Sie keine anderen Gedanken als die Standardbefehlszeilenargumente haben.

Was ist die Komplikation?

Hast du schon so etwas wie http://qntm.org/loco ausprobiert ? Dieser Ansatz ist viel sauberer als jeder handgeschriebene Ad-hoc-Ansatz, erfordert jedoch kein eigenständiges Tool zur Codegenerierung wie Lemon.

BEARBEITEN: Ein allgemeiner Trick für den Umgang mit Befehlszeilen mit komplexer Syntax besteht darin, die Argumente wieder in eine einzelne, durch Leerzeichen getrennte Zeichenfolge zu kombinieren und sie dann ordnungsgemäß zu analysieren, als wäre sie ein Ausdruck einer domänenspezifischen Sprache.

Sie haben nicht viele Details zu Ihrer Grammatik angegeben, nur einige Beispiele. Was ich sehen kann, ist, dass es einige Zeichenfolgen, Leerzeichen und eine (wahrscheinlich ist Ihr Beispiel in Ihrer Frage gleichgültig) doppelte Anführungszeichenfolge und dann eine ";" - Zeichenfolge gibt. Am Ende.

Es sieht so aus, als ob dies der PHP-Syntax ähneln könnte. Wenn dies der Fall ist, enthält PHP einen Parser, den Sie wiederverwenden und dann konkreter validieren können. Schließlich müssen Sie sich mit den Token befassen, aber es sieht so aus, als ob dies einfach von links nach rechts ist, also eigentlich nur eine Iteration über alle Token.

Einige Beispiele für die Wiederverwendung des PHP-Token-Parsers ( token_get_all) finden Sie in den Antworten auf die folgenden Fragen:

• Konvertiert zuverlässig Strings mit PHP-Array-Informationen in Arrays
• PHP greift dynamisch auf Variablenwerte zu

Beide Beispiele enthalten ebenfalls einen einfachen Parser, der wahrscheinlich zu Ihrem Szenario passt.

Wenn Ihre Bedürfnisse einfach sind und Sie beide die Zeit haben und sich dafür interessieren, werde ich hier gegen den Strich gehen und sagen, scheuen Sie sich nicht, Ihren eigenen Parser zu schreiben. Es ist eine gute Lernerfahrung, wenn nichts anderes. Wenn Sie komplexere Anforderungen haben - verschachtelte Funktionsaufrufe, Arrays usw. -, beachten Sie bitte, dass dies einige Zeit in Anspruch nehmen kann. Einer der großen Vorteile von Rolling Your Own ist, dass die Integration in Ihr System kein Problem darstellt. Der Nachteil ist natürlich, dass alle Fehler deine Schuld sind.

Arbeiten Sie gegen Token, verwenden Sie jedoch keine hartcodierten Befehle. Dann verschwindet das Problem mit ähnlich klingenden Befehlen.

Jeder empfiehlt das Drachenbuch immer, aber ich fand "Writing Compilers and Interpreters" von Ronald Mak immer ein besseres Intro.

Ich habe Programme geschrieben, die so funktionieren. Einer war ein IRC-Bot mit ähnlicher Befehlssyntax. Es gibt eine riesige Datei mit einer großen switch-Anweisung. Es funktioniert - es funktioniert schnell - aber es ist etwas schwierig zu warten.

Eine andere Option, die mehr OOP-Spin bietet, ist die Verwendung von Event-Handlern. Sie erstellen ein Schlüssel-Wert-Array mit Befehlen und den dazugehörigen Funktionen. Wenn ein Befehl gegeben wird, prüfen Sie, ob das Array den angegebenen Schlüssel hat. Ist dies der Fall, rufen Sie die Funktion auf. Dies wäre meine Empfehlung für neuen Code.

Ich schlage vor, ein Tool zu verwenden, anstatt selbst einen Compiler oder Interpreter zu implementieren. Irony verwendet C #, um die Grammatik der Zielsprache (die Grammatik Ihrer Befehlszeile) auszudrücken. In der Beschreibung zu CodePlex heißt es: "Irony ist ein Entwicklungskit für die Implementierung von Sprachen auf der .NET-Plattform."

Besuchen Sie die offizielle Homepage von Irony unter CodePlex: Irony - .NET Language Implementation Kit .

Mein Rat wäre Google für eine Bibliothek, die Ihr Problem löst.

In letzter Zeit habe ich viel mit NodeJS gearbeitet, und Optimist verwende ich für die Befehlszeilenverarbeitung. Ich ermutige Sie, nach einer Sprache zu suchen, die Sie für Ihre eigene Sprache verwenden können. Wenn nicht ... schreibe einen und öffne ihn: D Du kannst sogar den Optimist-Quellcode durchlesen und in die Sprache deiner Wahl portieren.

Warum vereinfachen Sie nicht ein bisschen Ihre Anforderungen?

Verwenden Sie keinen vollständigen Parser, der für Ihren Fall zu komplex und sogar unnötig ist.

Machen Sie eine Schleife, schreiben Sie eine Nachricht, die Ihre "Eingabeaufforderung" darstellt, kann der aktuelle Pfad sein, den Sie sind.

Warten Sie auf eine Zeichenfolge, "analysieren" Sie die Zeichenfolge und führen Sie je nach Inhalt der Zeichenfolge einen Vorgang aus.

Die Zeichenfolge könnte wie erwartet eine Zeile "parsen", in der die Trennzeichen ("Tokenizer") und die restlichen Zeichen gruppiert sind.

Beispiel.

Das Programm gibt Folgendes aus (und bleibt in derselben Zeile): / user / files / Der Benutzer schreibt (in derselben Zeile), liste alle auf;

Ihr Programm generiert eine Liste, Sammlung oder ein Array wie

list

all;

oder wenn ";" wird wie Leerzeichen als Trennzeichen betrachtet

/user/files/

list

all

Ihr Programm könnte mit einer einzigen Anweisung beginnen, ohne "Pipes" im Unix-Stil und ohne Umleitung im Windowze-Stil.

Ihr Programm könnte ein Wörterbuch mit Anweisungen erstellen, wobei jede Anweisung möglicherweise eine Liste von Parametern enthält.

Das Befehlsentwurfsmuster gilt für Ihren Fall:

http://en.wikipedia.org/wiki/Command_pattern

Dieser Pseudocode "plain c" ist weder getestet noch fertiggestellt, sondern nur eine Vorstellung davon, wie dies geschehen könnte.

Sie könnten es auch objektorientierter gestalten und in der Programmiersprache, die Sie mögen.

Beispiel:

// "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()

Sie haben Ihre Programmiersprache nicht erwähnt. Sie können auch jede Programmiersprache erwähnen, vorzugsweise jedoch "XYZ".

Sie haben mehrere Aufgaben vor sich.

Ihre Anforderungen betrachten ...

• Sie müssen den Befehl analysieren. Das ist eine ziemlich einfache Aufgabe
• Sie benötigen eine erweiterbare Befehlssprache.
• Sie müssen Fehlerüberprüfung und Vorschläge haben.

Die erweiterbare Befehlssprache gibt an, dass ein DSL erforderlich ist. Ich würde vorschlagen, nicht Ihr eigenes zu rollen, sondern JSON zu verwenden, wenn Ihre Erweiterungen einfach sind. Wenn sie komplex sind, ist eine Syntax mit s Ausdrücken nett.

Die Fehlerprüfung impliziert, dass Ihr System auch über die möglichen Befehle informiert ist. Das wäre Teil des Nachkommandosystems.

Wenn ich ein solches System von Grund auf neu implementieren würde, würde ich Common Lisp mit einem abgespeckten Lesegerät verwenden. Jedes Befehlstoken würde einem Symbol zugeordnet, das in einer s-expression-RC-Datei angegeben würde. Nach der Tokenisierung wird es in einem begrenzten Kontext ausgewertet / erweitert, wodurch die Fehler abgefangen werden. Erkennbare Fehlermuster geben Vorschläge zurück. Danach würde der eigentliche Befehl an das Betriebssystem gesendet.

Es gibt eine nette Funktion in der funktionalen Programmierung , die Sie vielleicht interessieren könnte.

Es heißt Mustervergleich .

Hier sind zwei Links für ein Mustervergleichsbeispiel in Scala und F # .

Ich stimme Ihnen zu, dass die Verwendung von switchStrukturen etwas mühsam ist, und es hat mir besonders Spaß gemacht, Patern Matching während der Implementierung eines Compilers in Scala zu verwenden.

Insbesondere empfehle ich Ihnen, sich das Lambda-Kalkül- Beispiel der Scala-Website anzuschauen .

Das ist meiner Meinung nach die klügste Vorgehensweise, aber wenn Sie sich strikt an PHP halten müssen, bleiben Sie bei der "alten Schule" switch.

Schauen Sie sich Apache CLI an . Der Zweck scheint genau das zu sein, was Sie tun möchten. Selbst wenn Sie es nicht verwenden können, können Sie seine Architektur überprüfen und kopieren.