Gleichungs-(Ausdrucks-)Parser mit Vorrang?
https://stackoverflow.com/questions/28256
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich habe einen Gleichungsparser entwickelt, der einen einfachen Stapelalgorithmus verwendet, der binäre (+, -, |, &, *, / usw.) Operatoren, unäre (!) Operatoren und Klammern verarbeitet.
Wenn ich diese Methode verwende, habe ich jedoch, dass alles die gleiche Priorität hat – es wird unabhängig vom Operator von links nach rechts ausgewertet, obwohl die Priorität durch Klammern erzwungen werden kann.
Im Moment gibt „1+11*5“ also 60 zurück, nicht 56, wie man erwarten könnte.
Obwohl dies für das aktuelle Projekt geeignet ist, möchte ich eine allgemeine Routine haben, die ich für spätere Projekte verwenden kann.
Aus Gründen der Klarheit bearbeitet:
Was ist ein guter Algorithmus zum Parsen von Gleichungen mit Priorität?
Ich interessiere mich für etwas, das einfach zu implementieren ist, und verstehe, dass ich selbst programmieren kann, um Lizenzprobleme mit verfügbarem Code zu vermeiden.
Grammatik:
Ich verstehe die Grammatikfrage nicht – ich habe das von Hand geschrieben.Es ist so einfach, dass ich keine Notwendigkeit für YACC oder Bison sehe.Ich muss lediglich Zeichenfolgen mit Gleichungen wie „2+3 * (42/13)“ berechnen.
Sprache:
Ich mache das in C, aber ich interessiere mich für einen Algorithmus, nicht für eine sprachspezifische Lösung.C ist so niedrig, dass es bei Bedarf problemlos in eine andere Sprache konvertiert werden kann.
Codebeispiel
Ich habe das gepostet Testcode für den einfachen Ausdrucksparser Ich habe oben darüber gesprochen.Die Projektanforderungen änderten sich und so musste ich den Code nie hinsichtlich Leistung oder Platz optimieren, da er nicht in das Projekt integriert war.Es liegt in der ausführlichen Originalform vor und sollte leicht verständlich sein.Wenn ich in Bezug auf die Operatorpriorität noch etwas daran mache, werde ich mich wahrscheinlich entscheiden Der Makro-Hack weil es in seiner Einfachheit zum Rest des Programms passt.Wenn ich dies jedoch jemals in einem echten Projekt verwende, werde ich mich für einen kompakteren/schnelleren Parser entscheiden.
Verwandte Frage
-Adam
Lösung
Der harte Weg
Du willst ein rekursiver Abstiegsparser.
Um Vorrang zu erhalten, müssen Sie rekursiv denken, zum Beispiel unter Verwendung Ihrer Beispielzeichenfolge,
1+11*5
Um dies manuell zu tun, müssten Sie die lesen 1, sehen Sie sich dann das Plus an und starten Sie eine ganz neue rekursive Parse-„Sitzung“, beginnend mit 11...und stellen Sie sicher, dass Sie die Datei analysieren 11 * 5 in seinen eigenen Faktor, was einen Analysebaum mit ergibt 1 + (11 * 5).
Schon der Versuch, es zu erklären, fühlt sich alles so schmerzhaft an, vor allem angesichts der zusätzlichen Ohnmacht von C.Sehen Sie, wenn das * nach dem Parsen der 11 tatsächlich ein + wäre, müssten Sie den Versuch, einen Begriff zu bilden, aufgeben und stattdessen das parsen 11 sich selbst als Faktor.Mein Kopf explodiert schon.Mit der rekursiven, anständigen Strategie ist das möglich, aber es gibt einen besseren Weg ...
Der einfache (richtige) Weg
Wenn Sie ein GPL-Tool wie Bison verwenden, müssen Sie sich wahrscheinlich keine Gedanken über Lizenzprobleme machen, da der von Bison generierte C-Code nicht durch die GPL abgedeckt ist (IANAL, aber ich bin mir ziemlich sicher, dass GPL-Tools die GPL nicht erzwingen). generierter Code/Binärdateien;Apple kompiliert beispielsweise Code wie beispielsweise Aperture mit GCC und verkauft ihn, ohne dass dieser Code einer GPL unterliegen muss.
Laden Sie Bison herunter (oder etwas Äquivalentes, ANTLR usw.).
Normalerweise gibt es einen Beispielcode, den Sie einfach bison ausführen können, um den gewünschten C-Code zu erhalten, der diesen Rechner mit vier Funktionen demonstriert:
http://www.gnu.org/software/bison/manual/html_node/Infix-Calc.html
Schauen Sie sich den generierten Code an und stellen Sie fest, dass dies nicht so einfach ist, wie es sich anhört.Die Vorteile der Verwendung eines Tools wie Bison bestehen außerdem darin, dass 1) Sie etwas lernen (insbesondere, wenn Sie das Dragon-Buch lesen und etwas über Grammatik lernen) und 2) Sie vermeiden NIH versuchen, das Rad neu zu erfinden.Mit einem echten Parser-Generator-Tool können Sie tatsächlich später skalieren und anderen Menschen zeigen, dass Parser die Domäne von Parsing-Tools sind.
Aktualisieren:
Die Leute hier haben viele gute Ratschläge gegeben.Meine einzige Warnung davor, die Parsing-Tools zu überspringen oder nur den Shunting Yard-Algorithmus oder einen handgerollten rekursiven, anständigen Parser zu verwenden, sind diese kleinen Spielzeugsprachen1 könnte sich eines Tages in große tatsächliche Sprachen mit Funktionen (sin, cos, log) und Variablen, Bedingungen und for-Schleifen verwandeln.
Flex/Bison mag für einen kleinen, einfachen Interpreter durchaus übertrieben sein, aber ein einmaliger Parser+Evaluator kann später zu Problemen führen, wenn Änderungen vorgenommen oder Funktionen hinzugefügt werden müssen.Ihre Situation wird unterschiedlich sein und Sie müssen Ihr Urteilsvermögen einsetzen;einfach nicht Bestrafe andere Menschen für deine Sünden [2] und ein nicht ausreichendes Werkzeug bauen.
Mein Lieblingstool zum Parsen
Das beste Werkzeug der Welt für diesen Job ist das Parsec Bibliothek (für rekursive anständige Parser), die mit der Programmiersprache Haskell geliefert wird.Es sieht sehr danach aus BNF, oder wie ein spezielles Tool oder eine domänenspezifische Sprache zum Parsen (Beispielcode [3]), aber es ist tatsächlich nur eine reguläre Bibliothek in Haskell, was bedeutet, dass sie im selben Build-Schritt wie der Rest Ihres Haskell-Codes kompiliert wird, und Sie können beliebigen Haskell-Code schreiben und diesen in Ihrem Parser aufrufen, und Sie können andere Bibliotheken kombinieren und anpassen alles im selben Code.(Das Einbetten einer Parsing-Sprache wie dieser in eine andere Sprache als Haskell führt übrigens zu einer Menge syntaktischer Unordnung.Ich habe das in C# gemacht und es funktioniert ganz gut, aber es ist nicht so schön und prägnant.)
Anmerkungen:
1 Richard Stallman sagt, in Warum Sie Tcl nicht verwenden sollten
Die Hauptstunde von EMACs ist, dass eine Sprache für Erweiterungen keine bloße "Erweiterungssprache" sein sollte.Es sollte eine echte Programmiersprache sein, die für das Schreiben und Aufrechterhalten wesentlicher Programme ausgelegt ist.Weil die Leute das tun wollen!
[2] Ja, ich habe für immer Narben davon, diese „Sprache“ zu verwenden.
Beachten Sie auch, dass die Vorschau korrekt war, als ich diesen Eintrag übermittelte, aber SO's nicht ausreichender Parser hat mein Close-Anker-Tag im ersten Absatz gefressen, Dies beweist, dass mit Parsern nicht zu spaßen ist, denn wenn Sie reguläre Ausdrücke und einmalige Hacks verwenden Sie werden wahrscheinlich etwas Subtiles und Kleines falsch machen.
[3] Ausschnitt eines Haskell-Parsers mit Parsec:ein Rechner mit vier Funktionen, erweitert um Exponenten, Klammern, Leerzeichen für die Multiplikation und Konstanten (wie pi und e).
aexpr = expr `chainl1` toOp
expr = optChainl1 term addop (toScalar 0)
term = factor `chainl1` mulop
factor = sexpr `chainr1` powop
sexpr = parens aexpr
<|> scalar
<|> ident
powop = sym "^" >>= return . (B Pow)
<|> sym "^-" >>= return . (\x y -> B Pow x (B Sub (toScalar 0) y))
toOp = sym "->" >>= return . (B To)
mulop = sym "*" >>= return . (B Mul)
<|> sym "/" >>= return . (B Div)
<|> sym "%" >>= return . (B Mod)
<|> return . (B Mul)
addop = sym "+" >>= return . (B Add)
<|> sym "-" >>= return . (B Sub)
scalar = number >>= return . toScalar
ident = literal >>= return . Lit
parens p = do
lparen
result <- p
rparen
return result
Andere Tipps
Der Rangierbahnhofalgorithmus ist dafür das richtige Werkzeug.Wikipedia ist diesbezüglich wirklich verwirrend, aber im Grunde funktioniert der Algorithmus so:
Angenommen, Sie möchten 1 + 2 * 3 + 4 auswerten.Intuitiv „wissen“ Sie, dass Sie zuerst die 2 * 3 machen müssen, aber wie kommen Sie zu diesem Ergebnis?Der Schlüssel besteht darin, sich darüber im Klaren zu sein, dass Sie beim Scannen der Zeichenfolge von links nach rechts einen Operator auswerten, wenn der Operator that folgt es hat eine niedrigere (oder gleiche) Priorität.Im Kontext des Beispiels möchten Sie Folgendes tun:
- Ansehen:1 + 2, nichts tun.
- Schauen Sie sich jetzt 1 + 2 * 3 an und tun Sie immer noch nichts.
- Schauen Sie sich nun 1 + 2 * 3 + 4 an. Jetzt wissen Sie, dass 2 * 3 ausgewertet werden muss, da der nächste Operator eine niedrigere Priorität hat.
Wie setzen Sie das um?
Sie möchten zwei Stapel haben, einen für Zahlen und einen anderen für Operatoren.Sie schieben ständig Zahlen auf den Stapel.Sie vergleichen jeden neuen Operator mit dem oben auf dem Stapel. Wenn der oben auf dem Stapel höhere Priorität hat, entfernen Sie ihn vom Operatorstapel, entfernen die Operanden vom Zahlenstapel, wenden den Operator an und übertragen das Ergebnis auf den Zahlenstapel.Nun wiederholen Sie den Vergleich mit dem Top-of-Stack-Operator.
Zurück zum Beispiel: Es funktioniert so:
N = [] ops = [
- Lesen Sie 1.N = [1], Ops = [ ]
- Lesen Sie +.N = [1], Ops = [+]
- Lesen Sie 2.N = [1 2], Ops = [+]
- Lesen
*.N = [1 2], Ops = [+ *] - Lesen Sie 3.N = [1 2 3], Ops = [+ *]
- Lesen Sie +.N = [1 2 3], Ops = [+ *]
- Pop 3, 2 und führe 2 aus
*3 und schiebe das Ergebnis auf N.N = [1 6], Ops = [+] +bleibt assoziativ, daher möchten Sie auch 1, 6 entfernen und das + ausführen.N = [7], Ops = [].- Zum Schluss schieben Sie das [+] auf den Operatorstapel.N = [7], Ops = [+].
- Pop 3, 2 und führe 2 aus
- Lesen Sie 4.N = [7 4].Ops = [+].
- Da Ihnen die Eingaben ausgehen, möchten Sie die Stapel jetzt leeren.Daraufhin erhalten Sie das Ergebnis 11.
Das ist doch nicht so schwierig, oder?Und es werden keine Grammatiken oder Parser-Generatoren aufgerufen.
http://www.engr.mun.ca/~theo/Misc/exp_parsing.htm
Sehr gute Erklärung verschiedener Ansätze:
- Erkennung rekursiver Abstammung
- Der Rangierbahnhof-Algorithmus
- Die klassische Lösung
- Vorrangklettern
Geschrieben in einfacher Sprache und Pseudocode.
Ich mag das Vorrangklettern.
Es gibt einen schönen Artikel Hier über die Kombination eines einfachen rekursiven Parsers mit Operator-Prioritäts-Parsing.Wenn Sie kürzlich Parser geschrieben haben, dürfte die Lektüre sehr interessant und lehrreich sein.
Vor langer Zeit habe ich meinen eigenen Parsing-Algorithmus entwickelt, den ich in keinem Buch über Parsing (wie dem Dragon Book) finden konnte.Wenn ich mir die Hinweise auf den Shunting Yard-Algorithmus ansehe, sehe ich die Ähnlichkeit.
Vor ungefähr 2 Jahren habe ich einen Beitrag darüber verfasst, komplett mit Perl-Quellcode http://www.perlmonks.org/?node_id=554516.Die Portierung in andere Sprachen ist einfach:Die erste Implementierung, die ich gemacht habe, war im Z80-Assembler.
Es ist ideal für direkte Berechnungen mit Zahlen, aber Sie können es bei Bedarf auch zum Erstellen eines Parse-Baums verwenden.
Aktualisieren Da mehr Leute Javascript lesen (oder ausführen) können, habe ich meinen Parser in Javascript neu implementiert, nachdem der Code neu organisiert wurde.Der gesamte Parser umfasst weniger als 5 KB Javascript-Code (ca. 100 Zeilen für den Parser, 15 Zeilen für eine Wrapper-Funktion), einschließlich Fehlerberichten und Kommentaren.
Eine Live-Demo finden Sie unter http://users.telenet.be/bartl/expressionParser/expressionParser.html.
// operator table
var ops = {
'+' : {op: '+', precedence: 10, assoc: 'L', exec: function(l,r) { return l+r; } },
'-' : {op: '-', precedence: 10, assoc: 'L', exec: function(l,r) { return l-r; } },
'*' : {op: '*', precedence: 20, assoc: 'L', exec: function(l,r) { return l*r; } },
'/' : {op: '/', precedence: 20, assoc: 'L', exec: function(l,r) { return l/r; } },
'**' : {op: '**', precedence: 30, assoc: 'R', exec: function(l,r) { return Math.pow(l,r); } }
};
// constants or variables
var vars = { e: Math.exp(1), pi: Math.atan2(1,1)*4 };
// input for parsing
// var r = { string: '123.45+33*8', offset: 0 };
// r is passed by reference: any change in r.offset is returned to the caller
// functions return the parsed/calculated value
function parseVal(r) {
var startOffset = r.offset;
var value;
var m;
// floating point number
// example of parsing ("lexing") without aid of regular expressions
value = 0;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
if(r.string.substr(r.offset, 1) == ".") {
r.offset++;
while("0123456789".indexOf(r.string.substr(r.offset, 1)) >= 0 && r.offset < r.string.length) r.offset++;
}
if(r.offset > startOffset) { // did that work?
// OK, so I'm lazy...
return parseFloat(r.string.substr(startOffset, r.offset-startOffset));
} else if(r.string.substr(r.offset, 1) == "+") { // unary plus
r.offset++;
return parseVal(r);
} else if(r.string.substr(r.offset, 1) == "-") { // unary minus
r.offset++;
return negate(parseVal(r));
} else if(r.string.substr(r.offset, 1) == "(") { // expression in parens
r.offset++; // eat "("
value = parseExpr(r);
if(r.string.substr(r.offset, 1) == ")") {
r.offset++;
return value;
}
r.error = "Parsing error: ')' expected";
throw 'parseError';
} else if(m = /^[a-z_][a-z0-9_]*/i.exec(r.string.substr(r.offset))) { // variable/constant name
// sorry for the regular expression, but I'm too lazy to manually build a varname lexer
var name = m[0]; // matched string
r.offset += name.length;
if(name in vars) return vars[name]; // I know that thing!
r.error = "Semantic error: unknown variable '" + name + "'";
throw 'unknownVar';
} else {
if(r.string.length == r.offset) {
r.error = 'Parsing error at end of string: value expected';
throw 'valueMissing';
} else {
r.error = "Parsing error: unrecognized value";
throw 'valueNotParsed';
}
}
}
function negate (value) {
return -value;
}
function parseOp(r) {
if(r.string.substr(r.offset,2) == '**') {
r.offset += 2;
return ops['**'];
}
if("+-*/".indexOf(r.string.substr(r.offset,1)) >= 0)
return ops[r.string.substr(r.offset++, 1)];
return null;
}
function parseExpr(r) {
var stack = [{precedence: 0, assoc: 'L'}];
var op;
var value = parseVal(r); // first value on the left
for(;;){
op = parseOp(r) || {precedence: 0, assoc: 'L'};
while(op.precedence < stack[stack.length-1].precedence ||
(op.precedence == stack[stack.length-1].precedence && op.assoc == 'L')) {
// precedence op is too low, calculate with what we've got on the left, first
var tos = stack.pop();
if(!tos.exec) return value; // end reached
// do the calculation ("reduce"), producing a new value
value = tos.exec(tos.value, value);
}
// store on stack and continue parsing ("shift")
stack.push({op: op.op, precedence: op.precedence, assoc: op.assoc, exec: op.exec, value: value});
value = parseVal(r); // value on the right
}
}
function parse (string) { // wrapper
var r = {string: string, offset: 0};
try {
var value = parseExpr(r);
if(r.offset < r.string.length){
r.error = 'Syntax error: junk found at offset ' + r.offset;
throw 'trailingJunk';
}
return value;
} catch(e) {
alert(r.error + ' (' + e + '):\n' + r.string.substr(0, r.offset) + '<*>' + r.string.substr(r.offset));
return;
}
}
Es wäre hilfreich, wenn Sie die Grammatik beschreiben könnten, die Sie derzeit zum Parsen verwenden.Klingt so, als ob dort das Problem liegen könnte!
Bearbeiten:
Die Tatsache, dass Sie die Grammatikfrage nicht verstehen und „Sie haben dies von Hand geschrieben“ erklärt höchstwahrscheinlich, warum Sie Probleme mit Ausdrücken der Form „1+11*5“ (d. h. mit Operatorpriorität) haben. .Wenn Sie beispielsweise nach „Grammatik für arithmetische Ausdrücke“ googeln, sollten Sie einige gute Hinweise erhalten.Eine solche Grammatik muss nicht kompliziert sein:
<Exp> ::= <Exp> + <Term> |
<Exp> - <Term> |
<Term>
<Term> ::= <Term> * <Factor> |
<Term> / <Factor> |
<Factor>
<Factor> ::= x | y | ... |
( <Exp> ) |
- <Factor> |
<Number>
würde zum Beispiel ausreichen und kann trivial erweitert werden, um einige kompliziertere Ausdrücke (einschließlich Funktionen zum Beispiel oder Potenzen usw.) zu berücksichtigen.
Ich schlage vor, dass Sie einen Blick darauf werfen Das Thread zum Beispiel.
Fast alle Einführungen in Grammatiken/Parsing behandeln arithmetische Ausdrücke als Beispiel.
Beachten Sie, dass die Verwendung einer Grammatik keineswegs die Verwendung eines bestimmten Werkzeugs bedeutet (a la Yacc, Bison,...).Tatsächlich verwenden Sie mit Sicherheit bereits die folgende Grammatik:
<Exp> :: <Leaf> | <Exp> <Op> <Leaf>
<Op> :: + | - | * | /
<Leaf> :: <Number> | (<Exp>)
(oder so etwas in der Art) ohne es zu wissen!
Haben Sie darüber nachgedacht, es zu verwenden? Steigern Sie den Geist?Damit können Sie EBNF-ähnliche Grammatiken in C++ wie folgt schreiben:
group = '(' >> expression >> ')';
factor = integer | group;
term = factor >> *(('*' >> factor) | ('/' >> factor));
expression = term >> *(('+' >> term) | ('-' >> term));
Wenn Sie Ihre Frage stellen, ist keinerlei Rekursion erforderlich.Die Antwort ist drei Dinge:Postfix-Notation plus Shunting Yard-Algorithmus plus Postfix-Ausdrucksauswertung:
1).Postfix-Notation = erfunden, um die Notwendigkeit einer expliziten Angabe der Priorität zu beseitigen.Lesen Sie mehr im Internet, aber hier ist das Wesentliche:Infix-Ausdruck ( 1 + 2 ) * 3 ist zwar für Menschen leicht zu lesen und zu verarbeiten, aber für maschinelle Berechnungen nicht sehr effizient.Was ist?Einfache Regel, die besagt: „Schreiben Sie den Ausdruck neu, indem Sie ihn vorrangig zwischenspeichern, und verarbeiten Sie ihn dann immer von links nach rechts.“So wird aus dem Infix ( 1 + 2 ) * 3 ein Postfix 12+3*.POST, da der Operator immer NACH den Operanden platziert wird.
2).Postfix-Ausdruck wird ausgewertet.Einfach.Zahlen aus der Postfix-Zeichenfolge lesen.Schieben Sie sie auf einen Stapel, bis ein Bediener sichtbar ist.Operatortyp prüfen – unär?binär?Tertiär?Entfernen Sie so viele Operanden vom Stapel, wie zur Auswertung dieses Operators erforderlich sind.Auswerten.Ergebnis zurück auf den Stapel schieben!Und du bist fast fertig.Machen Sie so weiter, bis der Stapel nur noch einen Eintrag = Wert hat, nach dem Sie suchen.
Machen wir ( 1 + 2 ) * 3, das im Postfix „12+3*“ steht.Erste Zahl lesen = 1.Schieben Sie es auf den Stapel.Lesen Sie weiter.Zahl = 2.Schieben Sie es auf den Stapel.Lesen Sie weiter.Operator.Welcher?+.Welche Art?Binär = benötigt zwei Operanden.Stapel zweimal platzen lassen = argright ist 2 und argleft ist 1.1 + 2 ist 3.Schiebe 3 zurück auf den Stapel.Lesen Sie als nächstes den Postfix-String.Es ist eine Zahl.3.Drücken.Lesen Sie weiter.Operator.Welcher?*.Welche Art?Binär = benötigt zwei Zahlen -> Pop-Stapel zweimal.Beim ersten Mal in argright, beim zweiten Mal in argleft.Bewerten Sie die Operation – 3 mal 3 ist 9. Schieben Sie 9 auf den Stapel.Lesen Sie das nächste Postfixzeichen.Es ist null.Ende der Eingabe.Pop Stack Onec = das ist deine Antwort.
3).Shunting Yard wird verwendet, um einen für den Menschen (leicht) lesbaren Infix-Ausdruck in einen Postfix-Ausdruck umzuwandeln (der nach einiger Übung auch für den Menschen leicht lesbar ist).Einfache manuelle Codierung.Siehe Kommentare oben und im Netz.
Gibt es eine Sprache, die Sie verwenden möchten? ANTLR ermöglicht Ihnen dies aus einer Java-Perspektive.Adrian Kuhn hat eine ausgezeichnete Zuschreibung darüber, wie man eine ausführbare Grammatik in Ruby schreibt;Tatsächlich ist sein Beispiel fast genau Ihr Beispiel für einen arithmetischen Ausdruck.
Es hängt davon ab, wie „allgemein“ Sie es haben möchten.
Wenn Sie möchten, dass es wirklich sehr allgemein ist und beispielsweise auch mathematische Funktionen wie sin(4+5)*cos(7^3) analysieren kann, benötigen Sie wahrscheinlich eine Baum analysieren.
Ich glaube jedoch nicht, dass eine vollständige Implementierung hier eingefügt werden sollte.Ich würde vorschlagen, dass Sie sich eines der berüchtigten „Drachenbuch".
Aber wenn Sie nur Vorrangunterstützung wünschen, dann können Sie dies tun, indem Sie zunächst den Ausdruck in ein Postfix-Format konvertieren, in dem ein Algorithmus verfügbar sein sollte, den Sie kopieren und einfügen können Google oder ich denke, Sie können es selbst mit einem Binärbaum codieren.
Wenn Sie es in Postfix-Form haben, ist es von da an ein Kinderspiel, da Sie bereits verstehen, wie der Stapel hilft.
Ich würde vorschlagen, zu schummeln und das zu verwenden Rangierbahnhof-Algorithmus.Es ist eine einfache Methode zum Schreiben eines einfachen Parsers vom Typ Taschenrechner und berücksichtigt die Vorrangstellung.
Wenn Sie Dinge richtig tokenisieren und Variablen usw. haben möchten.beteiligt, dann würde ich weitermachen und einen rekursiven Abstiegsparser schreiben, wie von anderen hier vorgeschlagen. Wenn Sie jedoch einfach einen Parser im Taschenrechnerstil benötigen, sollte dieser Algorithmus ausreichen :-)
Ich habe das auf der PIClist darüber gefunden Rangierbahnhof-Algorithmus:
Harold schreibt:
Ich erinnere mich, dass ich vor langer Zeit einen Algorithmus gelesen habe, der algebraische Ausdrücke zur einfachen Bewertung in RPN konvertierte.Jeder INFIX -Wert oder Operator oder jede Klammung wurde durch ein Eisenbahnauto auf einer Strecke dargestellt.Eine Art von Auto spaltete sich auf eine andere Strecke und die andere setzte sich geradeaus fort.Ich erinnere mich nicht an die Details (offensichtlich!), Dachte aber immer, dass es interessant wäre, zu codieren.Dies ist zurück, als ich 6800 (nicht 68000) Montagecode schrieb.
Dies ist der "Shunting Yard -Algorythmus" und es ist das, was die meisten Maschinenparser verwenden.Siehe den Artikel über Parsen in Wikipedia.Eine einfache Möglichkeit, den Shunting Yard -Algorythmus zu codieren, besteht darin, zwei Stapel zu verwenden.Einer ist der "Push" -Stapel und der andere der "Reduzieren" oder "Ergebnis" -Stapel.Beispiel:
pstack = () // leer rstack = () Eingabe:1+2*3 Vorrang = 10 // niedrigste Reduzierung = 0 // nicht reduzieren
Start:Token '1':IsNumber, in PStack (Push) Token '+' eingeben:Isoperator setzen Vorrang = 2 Wenn Vorrang.Isnumber, in Pstack (Push) Token '*' eingeben:Isoperator, Setzen Sie Vorrang = 1, in PStack (Push) // Vorrang wie // über dem Token '3' überprüfen:IsNumber, in PStack (Push) -Ende der Input eingeben, müssen reduzieren (Ziel ist leer pstack) record () // fertig
Um die Popelemente aus dem Push -Stapel zu reduzieren und in den Ergebnisstapel zu setzen, tauschen Sie immer die Top 2 Elemente gegen PStack aus, wenn sie den Formular "Operator" "Nummer" haben:
pstack:'1' '+' '2' '' '3' Stapel:() ...pstack:() rstack:'3' '2' '' '1' '+'
wenn der Ausdruck gewesen wäre:
1*2+3
Dann wäre der Reduzierungsauslöser das Lesen des Token '+' gewesen, der eine niedrigere Präzision aufweist als die bereits gedrängte '*', sodass es getan hätte:
pstack:'1' '' '2' Stapel:() ...pstack:() rstack:'1' '2' ''
und dann schob '+' und dann '3' und dann schließlich reduziert:
pstack:'+' '3' Stapel:'1' '2' ''...pstack:() rstack:'1' '2' '' '3' '+'
Die Kurzfassung lautet also:Push -Zahlen, wenn die Operatoren pushen, überprüfen Sie den Vorrang des vorherigen Operators.Wenn es höher war als die des Bedieners, die jetzt gedrückt werden sollen, reduzieren Sie zuerst den aktuellen Operator.Um Parens zu bewältigen, retten Sie einfach die Vorrang des "vorherigen" Operators und setzen Sie den PStack eine Marke, die dem Reduzieren von Algorythmus zum Lösen des Innenraums eines Paren -Paares nicht mehr verringert.Das schließende Paren löst eine Reduzierung aus, ebenso wie das Ende des Eingangs und entfernt auch die offene Paren -Marke aus dem PStack und stellt den Vorrang vor dem Vorgang wieder her, sodass die Parsen nach dem engen Pfarrer fortgesetzt werden kann, wo es aufgehört hat.Dies kann mit Rekursion oder ohne erfolgen (Hinweis:Verwenden Sie einen Stapel, um die vorherige Vorrang zu speichern, wenn Sie auf A '(' ...) stoßen.Die verallgemeinerte Version davon besteht darin, einen Parser -Generator zu verwenden, der den Shunting Yard -Algorythmus F.ex implementiert hat.Verwenden von YACC oder Bison oder Taccle (TCL -Analogon von YACC).
Peter
-Adam
Ich habe eine Quelle für ein Ultrakompaktgerät (1 Klasse, < 10 KiB) gepostet. Java Math Evaluator auf meiner Website.Dies ist ein rekursiver Abstiegsparser des Typs, der die Schädelexplosion für das Poster der akzeptierten Antwort verursacht hat.
Es unterstützt vollständige Priorität, Klammern, benannte Variablen und Funktionen mit einem Argument.
Ich habe einen Ausdrucksparser veröffentlicht, der auf basiert Dijkstras Rangierbahnhof Algorithmus, unter den Bedingungen der Apache-Lizenz 2.0:
Eine weitere Ressource für die Prioritätsanalyse ist die Operator-Prioritätsparser Eintrag auf Wikipedia.Behandelt den Rangierbahnhofalgorithmus von Dijkstra und einen alternativen Baumalgorithmus, aber vor allem einen wirklich einfachen Makroersetzungsalgorithmus, der trivial vor jedem Parser ohne Vorrangkenntnisse implementiert werden kann:
#include <stdio.h>
int main(int argc, char *argv[]){
printf("((((");
for(int i=1;i!=argc;i++){
if(argv[i] && !argv[i][1]){
switch(argv[i]){
case '^': printf(")^("); continue;
case '*': printf("))*(("); continue;
case '/': printf("))/(("); continue;
case '+': printf(")))+((("); continue;
case '-': printf(")))-((("); continue;
}
}
printf("%s", argv[i]);
}
printf("))))\n");
return 0;
}
Rufen Sie es auf als:
$ cc -o parenthesise parenthesise.c
$ ./parenthesise a \* b + c ^ d / e
((((a))*((b)))+(((c)^(d))/((e))))
Was in seiner Einfachheit großartig und sehr verständlich ist.
Ich habe eine implementiert rekursiver Abstiegsparser in Java in der MathEclipse-Parser Projekt.Es könnte auch als verwendet werden Google Web Toolkit Modul
Ich arbeite derzeit an einer Artikelserie zum Aufbau eines Parsers für reguläre Ausdrücke als Lernwerkzeug für Entwurfsmuster und lesbare Programmierung.Sie können einen Blick darauf werfen lesbarer Code.Der Artikel stellt eine klare Verwendung des Rangierbahnhofalgorithmus vor.
Ich habe einen Ausdrucksparser in F# geschrieben und habe hier darüber gebloggt.Es verwendet den Rangierbahnhof-Algorithmus, aber anstatt von Infix zu RPN zu konvertieren, habe ich einen zweiten Stapel hinzugefügt, um die Ergebnisse der Berechnungen zu sammeln.Die Operatorpriorität wird korrekt gehandhabt, unäre Operatoren werden jedoch nicht unterstützt.Ich habe dies jedoch geschrieben, um F# zu lernen, nicht um das Parsen von Ausdrücken zu lernen.
Es gibt eine Python-Lösung mit Pyparsing Hier.Das Parsen der Infix-Notation mit verschiedenen Operatoren mit Vorrang ist ziemlich üblich, und daher umfasst Pyparsing auch die infixNotation (früher operatorPrecedence) Ausdrucksgenerator.Damit können Sie ganz einfach boolesche Ausdrücke definieren, beispielsweise mit „AND“, „OR“, „NOT“.Oder Sie können Ihre Vier-Funktionen-Arithmetik erweitern, um andere Operatoren zu verwenden, z. B. !für Fakultät oder „%“ für Modul, oder fügen Sie P- und C-Operatoren hinzu, um Permutationen und Kombinationen zu berechnen.Sie könnten einen Infix-Parser für die Matrixnotation schreiben, der die Verarbeitung von „-1“- oder „T“-Operatoren (für Inversion und Transponierung) umfasst.Das „operatorPrecedence“-Beispiel eines 4-Funktions-Parsers (mit „!“ zum Spaß) ist Hier und ein umfassenderer Parser und Evaluator ist Hier.
Ich weiß, dass dies eine späte Antwort ist, aber ich habe gerade einen kleinen Parser geschrieben, der es allen Operatoren (Präfix, Postfix und Infix-links, Infix-rechts und nichtassoziativ) ermöglicht, eine beliebige Priorität zu haben.
Ich werde dies für eine Sprache mit beliebiger DSL-Unterstützung erweitern, wollte aber nur darauf hinweisen, dass man keine benutzerdefinierten Parser für die Operatorpriorität benötigt, man kann einen generalisierten Parser verwenden, der überhaupt keine Tabellen benötigt, und sucht einfach nach der Priorität jedes angezeigten Operators.Es wurden benutzerdefinierte Pratt-Parser oder Rangierbahnhof-Parser erwähnt, die illegale Eingaben akzeptieren können – dieser muss nicht angepasst werden und (es sei denn, es liegt ein Fehler vor) akzeptiert keine schlechten Eingaben.Es ist in gewissem Sinne nicht vollständig, es wurde geschrieben, um den Algorithmus zu testen, und seine Eingabe liegt in einer Form vor, die eine gewisse Vorverarbeitung erfordert, aber es gibt Kommentare, die es klarstellen.
Beachten Sie, dass einige gemeinsame Arten von Operatoren fehlen, beispielsweise die Art von Operator, die zur Indizierung der IE-Tabelle [Index] oder eine Funktionsfunktion (Parameter-Expression, ...) verwendet wird. Ich werde diese hinzufügen, aber denken Sie beide als Postfix vor Operatoren, wo sich zwischen den Grenzwerten ['und'] 'oder' ('und') '' '' '' '' '' '' 'befindet, wird mit einer anderen Instanz des Ausdrucks Parser analysiert.Es tut mir leid, dass ich das weggelassen habe, aber der Postfix-Teil ist drin – wenn man den Rest hinzufügt, wird sich die Größe des Codes wahrscheinlich fast verdoppeln.
Da der Parser nur aus 100 Zeilen Schlägercode besteht, sollte ich ihn vielleicht einfach hier einfügen. Ich hoffe, dass er nicht länger ist, als es der Stackoverflow zulässt.
Ein paar Details zu willkürlichen Entscheidungen:
Wenn ein Postfix-Operator mit niedriger Priorität um dieselben Infixblöcke konkurriert wie ein Präfix-Operator mit niedriger Priorität, gewinnt der Präfix-Operator.Dies kommt in den meisten Sprachen nicht vor, da die meisten keine Postfix-Operatoren mit niedriger Priorität haben.- zum Beispiel:((Daten a) (links 1 +) (vor 2 nicht) (Daten B) (Post 3!) (Links 1 +) (Daten c)) ist a +nicht b! +c wo nicht ein Präfixoperator und!ist Postfix -Operator und beide haben eine geringere Vorrang Zweitens ist es die Art und Weise, wie es sich analysiert
Nicht-assoziative Infix-Operatoren sind wirklich dazu da, damit Sie nicht so tun müssen, als ob Operatoren, die andere Typen zurückgeben, als sie annehmen, zusammen Sinn machen, aber ohne unterschiedliche Ausdruckstypen für jeden zu haben, ist das ein Kunststück.Daher weigern sich in diesem Algorithmus nicht-assoziative Operatoren, nicht nur mit sich selbst, sondern auch mit anderen Operatoren mit derselben Priorität zu assoziieren.Dies ist ein häufiger Fall, da < <= == >= usw. in den meisten Sprachen nicht miteinander verknüpft sind.
Die Frage, wie unterschiedliche Arten von Operatoren (Links, Präfix usw.) Verknüpfungen hinsichtlich der Vorrangigkeit aufheben, sollte nicht aufgeworfen werden, da es nicht wirklich sinnvoll ist, Operatoren verschiedener Typen den gleichen Vorrang zu geben.In diesen Fällen macht dieser Algorithmus etwas, aber ich mache mir nicht einmal die Mühe herauszufinden, was genau, weil eine solche Grammatik von vornherein eine schlechte Idee ist.
#lang racket
;cool the algorithm fits in 100 lines!
(define MIN-PREC -10000)
;format (pre prec name) (left prec name) (right prec name) (nonassoc prec name) (post prec name) (data name) (grouped exp)
;for example "not a*-7+5 < b*b or c >= 4"
;which groups as: not ((((a*(-7))+5) < (b*b)) or (c >= 4))"
;is represented as '((pre 0 not)(data a)(left 4 *)(pre 5 -)(data 7)(left 3 +)(data 5)(nonassoc 2 <)(data b)(left 4 *)(data b)(right 1 or)(data c)(nonassoc 2 >=)(data 4))
;higher numbers are higher precedence
;"(a+b)*c" is represented as ((grouped (data a)(left 3 +)(data b))(left 4 *)(data c))
(struct prec-parse ([data-stack #:mutable #:auto]
[op-stack #:mutable #:auto])
#:auto-value '())
(define (pop-data stacks)
(let [(data (car (prec-parse-data-stack stacks)))]
(set-prec-parse-data-stack! stacks (cdr (prec-parse-data-stack stacks)))
data))
(define (pop-op stacks)
(let [(op (car (prec-parse-op-stack stacks)))]
(set-prec-parse-op-stack! stacks (cdr (prec-parse-op-stack stacks)))
op))
(define (push-data! stacks data)
(set-prec-parse-data-stack! stacks (cons data (prec-parse-data-stack stacks))))
(define (push-op! stacks op)
(set-prec-parse-op-stack! stacks (cons op (prec-parse-op-stack stacks))))
(define (process-prec min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((>= (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-prec min-prec stacks))))))))
(define (process-nonassoc min-prec stacks)
(let [(op-stack (prec-parse-op-stack stacks))]
(cond ((not (null? op-stack))
(let [(op (car op-stack))]
(cond ((> (cadr op) min-prec)
(apply-op op stacks)
(set-prec-parse-op-stack! stacks (cdr op-stack))
(process-nonassoc min-prec stacks))
((= (cadr op) min-prec) (error "multiply applied non-associative operator"))
))))))
(define (apply-op op stacks)
(let [(op-type (car op))]
(cond ((eq? op-type 'post)
(push-data! stacks `(,op ,(pop-data stacks) )))
(else ;assume infix
(let [(tos (pop-data stacks))]
(push-data! stacks `(,op ,(pop-data stacks) ,tos)))))))
(define (finish input min-prec stacks)
(process-prec min-prec stacks)
input
)
(define (post input min-prec stacks)
(if (null? input) (finish input min-prec stacks)
(let* [(cur (car input))
(input-type (car cur))]
(cond ((eq? input-type 'post)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(process-prec (cadr cur)stacks)
(push-data! stacks (cons cur (list (pop-data stacks))))
(post (cdr input) min-prec stacks))))
(else (let [(handle-infix (lambda (proc-fn inc)
(cond ((< (cadr cur) min-prec)
(finish input min-prec stacks))
(else
(proc-fn (+ inc (cadr cur)) stacks)
(push-op! stacks cur)
(start (cdr input) min-prec stacks)))))]
(cond ((eq? input-type 'left) (handle-infix process-prec 0))
((eq? input-type 'right) (handle-infix process-prec 1))
((eq? input-type 'nonassoc) (handle-infix process-nonassoc 0))
(else error "post op, infix op or end of expression expected here"))))))))
;alters the stacks and returns the input
(define (start input min-prec stacks)
(if (null? input) (error "expression expected")
(let* [(cur (car input))
(input-type (car cur))]
(set! input (cdr input))
;pre could clearly work with new stacks, but could it reuse the current one?
(cond ((eq? input-type 'pre)
(let [(new-stack (prec-parse))]
(set! input (start input (cadr cur) new-stack))
(push-data! stacks
(cons cur (list (pop-data new-stack))))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks)))
((eq? input-type 'data)
(push-data! stacks cur)
(post input min-prec stacks))
((eq? input-type 'grouped)
(let [(new-stack (prec-parse))]
(start (cdr cur) MIN-PREC new-stack)
(push-data! stacks (pop-data new-stack)))
;we might want to assert here that the cdr of the new stack is null
(post input min-prec stacks))
(else (error "bad input"))))))
(define (op-parse input)
(let [(stacks (prec-parse))]
(start input MIN-PREC stacks)
(pop-data stacks)))
(define (main)
(op-parse (read)))
(main)
Hier ist eine einfache, in Java geschriebene Fall-Rekursionslösung.Beachten Sie, dass negative Zahlen nicht verarbeitet werden. Sie können diese jedoch hinzufügen, wenn Sie möchten:
public class ExpressionParser {
public double eval(String exp){
int bracketCounter = 0;
int operatorIndex = -1;
for(int i=0; i<exp.length(); i++){
char c = exp.charAt(i);
if(c == '(') bracketCounter++;
else if(c == ')') bracketCounter--;
else if((c == '+' || c == '-') && bracketCounter == 0){
operatorIndex = i;
break;
}
else if((c == '*' || c == '/') && bracketCounter == 0 && operatorIndex < 0){
operatorIndex = i;
}
}
if(operatorIndex < 0){
exp = exp.trim();
if(exp.charAt(0) == '(' && exp.charAt(exp.length()-1) == ')')
return eval(exp.substring(1, exp.length()-1));
else
return Double.parseDouble(exp);
}
else{
switch(exp.charAt(operatorIndex)){
case '+':
return eval(exp.substring(0, operatorIndex)) + eval(exp.substring(operatorIndex+1));
case '-':
return eval(exp.substring(0, operatorIndex)) - eval(exp.substring(operatorIndex+1));
case '*':
return eval(exp.substring(0, operatorIndex)) * eval(exp.substring(operatorIndex+1));
case '/':
return eval(exp.substring(0, operatorIndex)) / eval(exp.substring(operatorIndex+1));
}
}
return 0;
}
}
Der Algorithmus könnte leicht in C als rekursiver Abstiegsparser codiert werden.
#include <stdio.h>
#include <ctype.h>
/*
* expression -> sum
* sum -> product | product "+" sum
* product -> term | term "*" product
* term -> number | expression
* number -> [0..9]+
*/
typedef struct {
int value;
const char* context;
} expression_t;
expression_t expression(int value, const char* context) {
return (expression_t) { value, context };
}
/* begin: parsers */
expression_t eval_expression(const char* symbols);
expression_t eval_number(const char* symbols) {
// number -> [0..9]+
double number = 0;
while (isdigit(*symbols)) {
number = 10 * number + (*symbols - '0');
symbols++;
}
return expression(number, symbols);
}
expression_t eval_term(const char* symbols) {
// term -> number | expression
expression_t number = eval_number(symbols);
return number.context != symbols ? number : eval_expression(symbols);
}
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
expression_t eval_sum(const char* symbols) {
// sum -> product | product "+" sum
expression_t product = eval_product(symbols);
if (*product.context != '+')
return product;
expression_t sum = eval_sum(product.context + 1);
return expression(product.value + sum.value, sum.context);
}
expression_t eval_expression(const char* symbols) {
// expression -> sum
return eval_sum(symbols);
}
/* end: parsers */
int main() {
const char* expression = "1+11*5";
printf("eval(\"%s\") == %d\n", expression, eval_expression(expression).value);
return 0;
}
Die nächsten Bibliotheken könnten nützlich sein: Yupana - rein arithmetische Operationen; tinyexpr - Arithmetische Operationen + C-Mathefunktionen + eine vom Benutzer bereitgestellte; mpc - Parser-Kombinatoren
Erläuterung
Lassen Sie uns eine Folge von Symbolen erfassen, die einen algebraischen Ausdruck darstellen.Das erste ist eine Zahl, also eine Dezimalziffer, die ein- oder mehrmals wiederholt wird.Wir werden eine solche Notation als Produktionsregel bezeichnen.
number -> [0..9]+
Eine weitere Regel ist der Additionsoperator mit seinen Operanden.Es ist entweder number oder irgendwelche Symbole, die darstellen sum "*" sum Reihenfolge.
sum -> number | sum "+" sum
Versuchen Sie es mit Ersatz number hinein sum "+" sum das wird sein number "+" number was wiederum erweitert werden könnte [0..9]+ "+" [0..9]+ das konnte schließlich auf reduziert werden 1+8 Das ist der korrekte Additionsausdruck.
Auch andere Ersetzungen führen zu einem korrekten Ausdruck: sum "+" sum -> number "+" sum -> number "+" sum "+" sum -> number "+" sum "+" number -> number "+" number "+" number -> 12+3+5
Nach und nach könnten wir Produktionsregeln ähneln auch bekannt als Grammatik die alle möglichen algebraischen Ausdrücke ausdrücken.
expression -> sum
sum -> difference | difference "+" sum
difference -> product | difference "-" product
product -> fraction | fraction "*" product
fraction -> term | fraction "/" term
term -> "(" expression ")" | number
number -> digit+
Um den Vorrang des Bedieners zu kontrollieren, ändern Sie die Position seiner Produktionsregel gegenüber anderen.Schauen Sie sich die Grammatik oben an und beachten Sie die Produktionsregel für * ist unten platziert + das wird erzwingen product vorher bewerten sum.Die Implementierung kombiniert lediglich Mustererkennung mit Auswertung und spiegelt somit eng die Produktionsregeln wider.
expression_t eval_product(const char* symbols) {
// product -> term | term "*" product
expression_t term = eval_term(symbols);
if (*term.context != '*')
return term;
expression_t product = eval_product(term.context + 1);
return expression(term.value * product.value, product.context);
}
Hier bewerten wir term zuerst und senden Sie es zurück, wenn nicht * Charakter danach Dies ist in unserer Produktionsregel frei wählbar andernfalls - Symbole nach auswerten und zurückgeben term.value * product.value Dies ist die richtige Wahl in unserer Produktionsregel, d. h. term "*" product
