Wie schreibe ich einen Befehlsinterpreter / Parser?

22

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.

alfa64
quelle
Ich verstehe überhaupt nicht, wie das speziell mit PHP zusammenhängt. Es gibt bereits viele Threads zu diesem Interpreter / Compiler-Thema auf SO und SE.
Raffael
3
Niemand hat getopt erwähnt?
Anton Barkovsky
@ AntonBarkovsky: Ich habe. Siehe meine Links. Ich denke, Antworten wie die von Ubermensch sind einfach zu kompliziert für das, was die OP versucht.
Quentin-Starin
1
Ich habe auch einen einfachen Ansatz mit RegExp zitiert. Die Antwort ist auch aktualisiert
Ubermensch
Hat kein spezifisches Programm erwähnt. lang. Sie könnten ein "c" -Tag, "ruby" -Tag, "php" -Tag hinzufügen, vielleicht gibt es eine OpenSource-Bibliothek, eine Standard-Bibliothek oder eine "häufig verwendete, noch keine Standard-Bibliothek". für ihre progr. lang.
umlcat

Antworten:

14

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.

Übermensch
quelle
2
Dies ist einer der schwierigsten Wege. Trennen von Lexing- und Parsing-Durchläufen usw. - Dies ist wahrscheinlich hilfreich, um einen Hochleistungsparser für eine sehr komplexe, aber archaische Sprache zu implementieren. In der modernen Welt ist lexerloses Parsen die einfachste Standardoption. Parsing-Kombinatoren oder eDSLs sind einfacher zu verwenden als dedizierte Präprozessoren wie Yacc.
SK-logic
Ich stimme der SK-Logik zu, aber da eine allgemeine detaillierte Antwort erforderlich ist, schlug ich Lex und Yacc sowie einige Parser-Grundlagen vor. Von Anton vorgeschlagene getopts sind auch eine einfachere Option.
Ubermensch
Das habe ich gesagt - Lex und Yacc gehören zu den schwierigsten Methoden zum Parsen und sind nicht einmal generisch genug. Lexerloses Parsen (z. B. Packrat oder einfaches Parsec-ähnliches Parsen) ist für einen allgemeinen Fall viel einfacher. Und das Drachenbuch ist keine sehr nützliche Einführung in das Parsen mehr - es ist zu veraltet.
SK-logic
@ SK-logic Kannst du ein besser aktualisiertes Buch empfehlen. Es scheint alle Grundlagen für eine Person abzudecken, die versucht, das Parsen zu verstehen (zumindest in meiner Wahrnehmung). In Bezug auf Lex und Yacc ist es zwar schwierig, aber weit verbreitet, und viele Programmiersprachen bieten seine Implementierung.
Ubermensch
1
@ alfa64: Lass es uns wissen, wenn du tatsächlich eine Lösung basierend auf dieser Antwort
codierst
7

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?

Quentin-Starin
quelle
3
Nutzen Sie immer die Open Source-Community.
Spencer Rathbun
hast du getoptionkit ausprobiert?
Alfa64
Nein, ich habe seit einigen Jahren nicht mehr in PHP gearbeitet. Möglicherweise gibt es auch andere PHP-Bibliotheken. Ich habe die C # -Befehlszeilen-Parser-Bibliothek verwendet, mit der ich verlinkt bin.
Quentin-Starin
4

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.

SK-Logik
quelle
+1 netter Link, ich frage mich, ob es auf Github oder etwas anderem verfügbar ist. Und was ist mit den Nutzungsbedingungen?
Hakre
1

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:

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

hakre
quelle
Ja, ich habe die Grammatik überstürzt, ich werde es jetzt hinzufügen.
Alfa64
1

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.

GroßmeisterB
quelle
0

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.

Räuber
quelle
Ich habe Ihren Code gelesen und es ist genau das gleiche Schema wie mein Code, aber wie ich bereits sagte, wenn Sie möchten, dass andere Leute ihn verwenden, müssen Sie Fehlerprüfungen und
ähnliches
1
@ alfa64 Bitte ergänzen Sie die Frage anstelle von Kommentaren um Erläuterungen. Es ist nicht ganz klar, wonach Sie genau fragen, obwohl es ziemlich klar ist, dass Sie nach etwas wirklich Bestimmtem suchen. Wenn ja, sagen Sie uns genau, was das ist. Ich glaube nicht, dass es sehr einfach ist, von ... I think my implementation is very crude and faultyzu but as i stated, if you want other people to use, you need to add error checking and stuffwechseln. Sagen Sie uns genau, was daran grob ist und was fehlerhaft ist. Es würde Ihnen helfen, bessere Antworten zu erhalten.
Yannis
sicher, ich werde die
frage
0

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 .

Olivier Jacot-Descombes
quelle
Wie würden Sie es mit PHP verwenden?
SK-logic
Ich sehe keinen PHP-Tag oder Verweis auf PHP in der Frage.
Olivier Jacot-Descombes
Ich verstehe, es ging ursprünglich um PHP, aber jetzt umgeschrieben.
SK-logic
0

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.

ming_codes
quelle
0

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".

umlcat
quelle
0

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.

Paul Nathan
quelle
0

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.

SRKX
quelle
0

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.

Stephen Rudolph
quelle