Ausdruck analysieren: wie zu tokenisieren

Question

Ich suche Java/Javascript-ähnliche Ausdrücke in Javascript-Code zu tokenisieren. Meine Eingabe ist eine Zeichenfolge, die den Ausdruck enthält, und die Ausgabe muss ein Token-Array sein.

Was ist die beste Vorgehensweise, um so etwas zu tun? Muss ich die Zeichenfolge wiederholen oder gibt es einen regulären Ausdruck, der dies für mich tut?

Ich brauche diese in der Lage sein, zu unterstützen:

• Anzahl und Stringliterale (Einzel- und Doppel zitiert, mit Zitat Flucht)
• Mathematische Grund und Booleschen Operatoren und Komparatoren (+, -, *, /,!, und nicht, <,>, usw.)
• Dot und Klammer-Notation für den Objektzugriff mit Rekursion (foo.bar, foo [ 'bar'], foo [2] [prop])
• Parenthesis mit Verschachtelung
• Ternär Betreiber (foo? Bar: 'baz')
• Funktionsaufrufe (foo (bar))

Ich möchte speziell aus Sicherheitsgründen mit eval() oder etwas Derartiges zu vermeiden. Außerdem würde eval() den Ausdruck für mich sowieso nicht symbolisieren.

Answer 1

Lernen Sie, einen rekursiven Abstiegsparser zu schreiben. Sobald Sie die Konzepte verstanden haben, können Sie dies in jeder Sprache tun: Java, C++, JavaScript, SystemVerilog, ... was auch immer. Wenn Sie mit Zeichenfolgen umgehen können, können Sie sie analysieren.

Rekursives Abstiegs-Parsing ist eine grundlegende Technik für das Parsing, die leicht von Hand codiert werden kann. Dies ist nützlich, wenn Sie keinen Parsergenerator haben (oder nicht damit herumspielen wollen).

In einem rekursiven Abstiegsparser wird jede Regel in Ihrer Grammatik in eine Prozedur übersetzt, die die Regel analysiert. Wenn Sie sich auf andere Regeln beziehen müssen, tun Sie dies, indem Sie sie aufrufen - das sind nur Prozeduren.

Ein einfaches Beispiel: Ausdrücke mit Zahlen, Addition und Multiplikation (dies zeigt die Vorrangstellung des Operators). Zunächst wird die Grammatik:

 
expr ::= term 
     | expr "+" term 

term ::= factor 
     | term "*" factor 

factor ::= /[0-9/+ (I'm using a regexp here) 

nun den Parser schreiben (die die Lexer enthält; mit rekursiven Abstieg Sie die beiden zusammen werfen).Ich habe noch nie JavaScript, verwendet, so wollen wir versuchen, dies in (mein rostiges) Java:

class Parser { 
    string str; 
    int idx; // index into string 

    Node parseExpr() throws ParseException 
    { 
    Node op1 = parseTerm(); 
    Node op2; 

    while (idx < str.size() && str.charAt(idx) == '+') { 
     idx++; 
     op2 = parseTerm(); 
     op1 = new AddNode(op1, op2); 
    } 
    return op1; 
    } 

    Node parseTerm() throws ParseException 
    { 
    Node op1 = parseFactor(); 
    Node op2; 

    while (idx < str.size() && str.charAt(idx) == '*') { 
     idx++; 
     op2 = parseFactor(); 
     op1 = new MultNode(op1, op2); 
    } 
    return op1; 
    } 

    Node parseFactor() throws ParseException 
    { 
    StringBuffer sb = new StringBuffer(); 
    int old_idx = idx; 

    while (idx < str.size() && str.charAt(idx) >= '0' && str.charAt(idx) <= '9') { 
     sb.append(str.charAt(idx)); 
     idx++; 
    } 
    if (idx == old_idx) { 
     throw new ParseException(); 
    } 
    return new NumberNode(sb.toString()); 
    } 
} 

Sie können sehen, wie jede Grammatikregel in einem Verfahren übersetzt. Ich habe das nicht getestet; Das ist eine Übung für den Leser.

Sie müssen sich auch um die Fehlererkennung kümmern. Ein realer Compiler muss von Parse-Fehlern wiederherstellen, um zu versuchen, den Rest seiner Eingabe zu analysieren. Ein einzeiliger Ausdrucksparser wie dieser muss die Wiederherstellung überhaupt nicht durchführen, muss jedoch feststellen, dass ein Parsefehler vorhanden ist, und ihn kennzeichnen. Der einfachste Weg, dies zu tun, wenn Ihre Sprache dies zulässt, ist eine Ausnahme auszulösen und sie am Eingangspunkt des Parsers abzufangen. Ich habe nicht alle möglichen Parsefehler in meinem Beispiel oben entdeckt.

Weitere Informationen finden Sie "LL-Parser" und "rekursive Abstammung Parser" in Wikipedia. Wie ich zu Beginn sagte, wenn Sie die Konzepte verstehen (und sie sind einfach im Vergleich zu den Konzepten hinter LALR (1) State Machine Configuration Closures) dann sind Sie in der Lage, einen Parser für kleine Aufgaben in jeder Sprache zu schreiben, so lange wie Sie einige rudimentäre String-Fähigkeit haben. Genieße die Kraft.

Answer 2

Für einfache Lexer, bei denen die Geschwindigkeit nicht kritisch ist, schreibe ich normalerweise eine Regex für jede Art von Token und wiederhole jedes Mal nacheinander mit dem Beginn der Eingabe. (Stellen Sie sicher, dass Sie nicht mit einem O (n^2) -Algorithmus enden!) Ein Werkzeug wie Lex wird einen effizienteren Lexer ergeben, weil es die Regexes zu einer Zustandsmaschine kombiniert.

Answer 3

Sie müssen einen lexikalischen Analysator implementieren. Sie können js/cc verwenden, um es zu tun, oder Sie können einen endlichen Automaten selbst implementieren.

Da formal die Sprache, die Sie manipulieren, regulär ist, können Sie einen regulären Ausdruck verwenden. Aber ich empfehle es dir nicht.

Ich habe noch nie js/cc benutzt, ich würde es zuerst versuchen, und wenn es nicht funktioniert, würde ich versuchen, einen lexikalischen Analysator von mir selbst zu bauen.