Einführung
In diesem Artikel zeige ich Ihnen, wie Sie einen Vier-Arithmetik-Ausdruck wie einen Allzweckrechner analysieren und berechnen. Wenn wir fertig sind, haben wir einen Rechner, der Ausdrücke im Stil von 1 2*-(-3 2)/5,6 3 verarbeiten kann. Natürlich können Sie es auch erweitern, um mehr Leistung zu erzielen.
Meine ursprüngliche Absicht ist es, einen einfachen und interessanten Kurs zur Erläuterung der grammatikalischen Analyse und der formalen Grammatik (Inhalt der Zusammenstellungsprinzipien) anzubieten. Gleichzeitig möchte ich PlyPlus vorstellen, eine Syntax-Parsing-Schnittstelle, die ich seit mehreren Jahren regelmäßig verbessere. Als Ergänzung zu diesem Kurs erhalten wir am Ende einen sicheren Ersatz für eval().
Wenn Sie die in diesem Artikel aufgeführten Beispiele auf Ihrem Heimcomputer ausprobieren möchten, sollten Sie zuerst PlyPlus mit dem Befehl pip install plyplus installieren. (Anmerkung des Übersetzers: pip ist ein Paketverwaltungssystem, das zum Installieren von in Python geschriebenen Softwarepaketen verwendet wird. Die spezifische Verwendung finden Sie auf Baidu oder Google, daher werde ich nicht auf Details eingehen.)
Dieser Artikel erfordert Verstehen Sie die Verwendung der Vererbung in Python.
Grammatik
Für diejenigen unter Ihnen, die nicht verstehen, wie Parsing und formale Grammatik funktionieren, hier ein kurzer Überblick: Formale Grammatik wird verwendet. Einige Regeln für Parsen von Text auf verschiedenen Ebenen. Jede Regel beschreibt, wie der entsprechende Teil des Eingabetextes zusammengesetzt ist.
Hier ist ein Beispiel, das zeigt, wie man 1 2 3 4 analysiert:
Regel Nr. 1 – Addition besteht aus Additionszahl
ODER Nummer Nummer
add: add' 'number
|. Der Parser sucht nach Fügen Sie jedes Mal eine Zahl oder eine Zahl hinzu, und wenn eine gefunden wird, wird sie in „Hinzufügen“ umgewandelt. Grundsätzlich besteht das Ziel jedes Parsers darin, den höchstmöglichen Grad an Ausdrucksabstraktion zu finden.
Hier sind die einzelnen Schritte des Parsers:
Zahl Zahl Zahl Zahl
Die erste Konvertierung wandelt alle Zahlen in „Zahlen“-Regeln um
[Zahl Zahl ] Zahl Zahl
Der Parser hat sein erstes passendes Muster gefunden!
[Nummer hinzufügen] Nummer
Nach der Konvertierung in ein Muster beginnt die Suche nach der nächsten
[Nummer hinzufügen]
Hinzufügen
Diese geordneten Symbole werden zu zwei einfachen Regeln auf einer Ebene: Zahl Zahl und Zahl addieren. Auf diese Weise müssen Sie dem Computer nur mitteilen, ob Sie diese beiden Probleme gelöst haben, und er kann den gesamten Ausdruck analysieren. Tatsächlich kann die Additionssequenz gelöst werden, egal wie lang sie ist! Das ist die Kraft der formalen Grammatik.
Vorrang der Operatoren
Arithmetische Ausdrücke sind nicht nur lineares Wachstum von Symbolen, Operatoren erzeugen eine implizite Hierarchie, die sich sehr gut für die formale Grammatik eignet:1 2 * 3 / 4 - 5 6
Dies entspricht:
1 (2 * 3 / 4) - 5 6
Wir können das ausdrücken Struktur in dieser Grammatik durch verschachtelte Regeln:
add: add mul
|.
mul: mul '*; 🎜>
|. number'*'number ; Indem wir add so einstellen, dass es mit mul statt mit Zahl arbeitet, erhalten wir Multiplikationsprioritätsregeln. Simulieren wir in unserem Kopf den Prozess der Verwendung dieses magischen Parsers zur Analyse von 1 2*3*4: Zahl Zahl * Zahl * ZahlZahl [ Zahl * Zahl] * ZahlDer Parser kennt das Ergebnis von Zahl Zahl nicht, daher ist dies eine weitere Option für ihn (den Parser)Zahl [mul * Zahl] Zahl mulJetzt haben wir ein kleines Problem! Der Parser weiß nicht, was er mit Zahl mul machen soll. Wir können diese Situation unterscheiden, aber wenn wir weiter forschen, werden wir feststellen, dass es viele verschiedene Möglichkeiten gibt, die nicht berücksichtigt wurden, wie z. B. Multi-Nummer, Add-Nummer, Add-Add usw. Was sollen wir also tun? Glücklicherweise können wir einen kleinen „Trick“ anwenden: Wir können uns eine Zahl selbst als Produkt und ein Produkt selbst als Summe vorstellen! Diese Idee mag zunächst etwas seltsam erscheinen, aber sie macht durchaus Sinn: add: add' 'mul | > |. mulmul: mul'*'Nummer |. Aber wenn mul in add umgewandelt werden kann und number in mul umgewandelt werden kann, werden einige Inhaltszeilen überflüssig. Wenn wir sie verwerfen, erhalten wir: add: add' 'mul | mul ;mul: mul'*'number |. Zahl ;Lassen Sie uns diese neue Syntax verwenden, um die Ausführung von 1 2*3*4 zu simulieren:Zahl Zahl * Zahl * ZahlJetzt gibt es keine Regel, die Zahl*Zahl entspricht, aber der Parser kann „kreativ werden“Zahl [Zahl] * Zahl * ZahlZahl [mul * Zahl] * ZahlAnzahl [mul * Zahl][Anzahl] mul[mul] mul[add mul]addErfolg! ! !
Wenn Sie das erstaunlich finden, dann versuchen Sie es mit einem anderen arithmetischen Ausdruck zu simulieren und sehen Sie dann, wie der Ausdruck das Problem Schritt für Schritt auf die richtige Weise lösen kann. Oder warten Sie und lesen Sie den nächsten Abschnitt, um Schritt für Schritt zu sehen, wie der Computer funktioniert!
Führen Sie den Parser aus
Da wir nun eine ziemlich gute Vorstellung davon haben, wie unsere Grammatik funktioniert, schreiben wir eine tatsächliche Grammatik zur Anwendung:
START: hinzufügen ; // Dies ist die höchste Ebeneadd: add_symbol mul | 🎜>mul_symbol:'*'|'/';// Match * or /add_symbol:' '|'-'; // Match or -Vielleicht möchten Sie auffrischen auf reguläre Ausdrücke, aber trotzdem ist die Syntax ziemlich einfach. Testen wir es mit einem Ausdruck: >>>fromplyplusimportGrammar>>> g=Grammar("""...""") >>>printg .parse('1 2*3-5').pretty()startaddaddadd mul Zahl 1 add_symbol mul mul Zahl 2 mul_symbol * Zahl 3 add_symbol - mulZahl5Tolle Arbeit!Schauen Sie sich den Baum genauer an und schauen Sie sich den Parser an. Welche Ebene wurde ausgewählt? Wenn Sie diesen Parser selbst ausführen und Ihre eigenen Ausdrücke verwenden möchten, benötigen Sie lediglich Python. Fügen Sie nach der Installation von Pip und PlyPlus den obigen Befehl in Python ein (denken Sie daran, „...“ durch die tatsächliche Syntax ~ zu ersetzen). Formen Sie den Baum Plyplus erstellt automatisch einen Baum, der jedoch nicht unbedingt optimal ist. Das Einfügen von Zahlen in mul und mul in add eignet sich hervorragend zum Erstellen einer Hierarchie, aber jetzt, wo wir eine Hierarchie haben, werden sie zu einer Belastung. Wir weisen Plyplus an, die Regeln zu „erweitern“ (d. h. zu löschen), indem wir ihnen ein Präfix voranstellen. Ein @ erweitert eine Regel immer, ein # reduziert sie und ein ? erweitert sie, wenn sie einen untergeordneten Knoten hat. In diesem Fall ist ? das, was wir brauchen. start: add;?add: add add_symbol mul | / Erweitern Sie mul, wenn es nur eine Zahl istnumber:'[d.] ';mul_symbol:'*'|'/';add_symbol:' '| '-';Der Baum sieht unter der neuen Grammatik so aus: >>> g=Grammar("""...""")> > >printg.parse('1 2*3-5').pretty()startaddaddnumber
1 add_symbol mul Zahl 2 mul_symbol * Zahl 3 add_symbol - Zahl 5Oh, das macht es viel einfacher und, ich wage es zu sagen, sehr gut. Klammerverarbeitung und andere Funktionen
Bisher fehlen uns offensichtlich einige notwendige Funktionen: Klammern, Einheitenoperatoren (-(1 2)) und In der Mitte des Ausdrucks sind Nullzeichen zulässig. Tatsächlich sind diese Funktionen sehr einfach zu implementieren. Versuchen wir es unten.
Zuerst muss ein wichtiges Konzept vorgestellt werden: Atome. Alle Operationen, die innerhalb eines Atoms auftreten (in Klammern und Einheitsoperationen), haben Vorrang vor allen Additions- oder Multiplikationsoperationen (einschließlich bitweiser Operationen). Da das Atom nur ein Prioritätskonstruktor ist und keine grammatikalische Bedeutung hat, helfen Sie uns, das „@“-Symbol hinzuzufügen, um sicherzustellen, dass es während der Kompilierung erweitert werden kann.
Die einfachste Möglichkeit, Leerzeichen in Ausdrücken zuzulassen, ist die Verwendung dieser Erklärung: add SPACE add_symbol SPACE mul |. Diese Erklärung führt jedoch zu Ausführlichkeit und schlechter Lesbarkeit. Wir müssen also dafür sorgen, dass Plyplus Leerzeichen immer ignoriert.
Das Folgende ist die vollständige Syntax, einschließlich der oben genannten Funktionen:
start: add;
?add: (add add_symbol)? mul;
WHITESPACE:'[ t] '(%ignore);
Bitte stellen Sie sicher, dass Sie diese Syntax verstehen, bevor Sie mit dem nächsten Schritt fortfahren: der Berechnung!
Operation
Jetzt können wir einen Ausdruck in einen hierarchischen Baum umwandeln. Wir müssen nur noch den Baum Zweig für Zweig scannen .
Wir beginnen jetzt mit dem Schreiben von Code. Vorher muss ich zwei Dinge zu diesem Baum erklären:
1. Jeder Zweig ist eine Instanz, die die folgenden zwei Eigenschaften enthält:
Kopf: der Name der Regel (z. B. add oder number);
Schwanz: eine Liste mit allen Unterregeln, die damit übereinstimmen.
2.Plyplus löscht standardmäßig unnötige Tags. In diesem Beispiel werden '( ' , ')' und '-' entfernt. Aber add und mul haben ihre eigenen Regeln, und Plyplus weiß, dass sie notwendig sind, und löscht sie nicht. Wenn Sie diese Tags beibehalten müssen, können Sie diese Funktion manuell deaktivieren. Meiner Erfahrung nach ist es jedoch besser, dies nicht zu tun, sondern die entsprechende Syntax manuell zu ändern, um bessere Ergebnisse zu erzielen.
Zurück zum Geschäft, jetzt beginnen wir mit dem Schreiben von Code. Wir werden einen sehr einfachen Konverter verwenden, um diesen Baum zu scannen. Es beginnt mit dem Scannen vom äußersten Zweig, bis es den Wurzelknoten erreicht, und unsere Aufgabe ist es, ihm mitzuteilen, wie es scannen soll. Wenn alles gut geht, beginnt der Scanvorgang immer von der äußersten Ebene aus. Mal sehen, wie es funktioniert.
>>>importoperator as op
>>>fromplyplusimportSTransformer
classCalc(STransformer):
def_bin_operator(self, exp):
arg1, Operator_symbol, arg2=exp.tail
Operator_func={' ': op.add,
'/': op.div} [operator_symbol]
returnoperator_func (arg1, arg2)
neg =lambdaself, exp:-exp.tail[0]
__default__=lambdaself , exp: exp.tail[0]
add=_bin_operator
mul=_bin_operator
Jede Methode entspricht einer Regel. Wenn die Methode nicht vorhanden ist, wird die Methode __default__ aufgerufen. Wir haben start, add_symbol und mul_symbol weggelassen, da sie nur ihre eigenen Zweige zurückgeben.
Ich habe float() verwendet, um die Zahlen zu analysieren, was ein langsamer Ansatz ist, aber ich könnte dafür auch einen Parser verwenden.
Um die Aussagen übersichtlich zu gestalten, habe ich das Operatormodul verwendet. Add ist beispielsweise im Grunde „lambda x,y: x y“ oder so ähnlich.
OK, jetzt führen wir diesen Code aus, um die Ergebnisse zu überprüfen.
>>> Calc().transform( g.parse('1 2 * -(-3 2) / 5.6 30'))
31.357142857142858
Dann eval ()Wolltuch? 7
>>>eval('1 2 * -(-3 2) / 5.6 30')
31.357142857142858
Erfolgreich:)
Die letzter Schritt: REPL
Der Schönheit halber kapseln wir es in einen schönen Rechner REPL:
defmain():
calc=Calc()
whileTrue:
try:
s=raw_input('> ')
außer EOFError:
break
ifs=='':
break
tree=calc_grammar.parse(s)
printcalc.transform(tree)
Der vollständige Code ist hier verfügbar:
https://github.com/erezsh/plyplus/blob/master/examples/calc.py
![[Web-Frontend] Node.js-Schnellstart](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
