[PHP] Shunting-yard algo (Parser) in PHP, Java und JavaScript implementiert

Murdoc · 25. Juli 2012

Shunting-yard algo (Parser) in PHP, Java und JavaScript implementiert

ich dachte mir mal, dass ich aus spaß diesen algo mal in PHP baue.
war gar nicht so leicht, aber hey hat spaß gemacht

was macht dieser algo?
damit lassen sich mathematische ausdrücke ausrechnen.

ich habe auch unäres "-" und "+" mit drin, aus design-gründen aber nicht besonders sauber umgesetzt

zudem ist es möglich funktionen zu nutzen ohne limit von parametern - diese werden zur "compile-time" ermittelt und bei der ausführung entsprechend vom stack genommen.

viel spaß beim lesen des codes

quelltext bei github:

droptable/php-shunting-yard · GitHub

api:

PHP:

print Parser :: parse ( '-2 * 4 + 1 + foo(1, 2 + 1) + bar' );

// update: konstanten werden nun erst zur "laufzeit" ermittelt
// update: der scanner ist nun in der lage direkt zwischen konstanten und funktionen zu unterscheiden
// update: unär + und - werden nun höher gewichtet als * / und %
// update: unär + und - werden nun von rechts nach links ausgewertet ...
// update: (2)(2) oder 2(2) wird nun als multiplikation erkannt.

----------------------------------------

jetzt auch in java wenn jemand interesse daran hat:

quelltext bei github:

droptable/java-shunting-yard · GitHub

binary:

Download: term_parser.jar | www.xup.in

Code:

java -jar term_parser.jar "ausdruck"

----------------------------------------

zu guter letzt auch in javascript (requirejs / node.js kompatibel)

quelltext bei github:

droptable/javascript-shunting-yard · GitHub

ausprobieren:

http://murdoc.eu/rr/shunt/

Code:

Shunt.parse('-2 * 4 + 1 + foo(1, 2 + 1) + bar');
// oder
Shunt.Parser.parse('-2 * 4 + 1 + foo(1, 2 + 1) + bar');

Anzeige

Murdoc · 25. August 2012

AW: Shunting-yard algo (Parser) in PHP, Java und JavaScript implementiert

Update: Die Java Version ist nun in der Lage opcodes zu erstellen (zum Debuggen).

Eingabe:

Code:

1 + 2

Ausgabe:

Code:

:segment0
0: NOOP ; keine weitere aktion für die zahl 1, deswegen NOOP
1: NOOP ; selbiges gilt für die zahl 2
2: %0 = ADD 1.0, 2.0
3: RETURN %0

Erklärung der opcodes:

Code:

NOOP = mach nichts
FETCH_RD = hole variable aus dem context oder erstelle eine neue
FETCH_ID = hole variable aus dem context
FETCH_FN = hole eine funktion aus dem context
CALL = rufe funktion auf. syntax: CALL die_funktion (anzahl argumente) arg1, arg2, argN
STR = speicher einen string. syntax: STR länge_des_strings "der string"
SET = setze den wert einer variablen
ADD = plus
SUB = minus
MOD = modulo
POW = fruchtbarkeit
DIV = division
MUL = multiplikation
RETURN = wert zurückgeben

Weitere Neuerungen:
- Es können Variablen verwendet werden (Zuweisungen wurden eingebaut)
- Der Scanner kann nun Binäre und Hexadezimale Nummern erfassen
- Mehrere Ausdrücke können mit einem ";" getrennt werden.
-> Hierbei wird der zuletzt ermittelte Wert zurückgegeben

Beispiel:

Code:

foo = 1 + 1; foo + 1;

Ergebnis:

Code:

Opcodes:

Code:

:segment0
0: %0 = FETCH_RD "foo"
1: NOOP
2: NOOP
3: %1 = ADD 1.0, 1.0
4: %2 = SET %0, %1
5: RETURN %2

:segment1
0: %0 = FETCH_ID "foo"
1: NOOP
2: %1 = ADD %0, 1.0
3: RETURN %1

Zudem werden nun alle Werte in der Klasse "Symbol" zusammen mit deren Typ gespeichert, was es möglich macht auch andere Werte als Nummern zu speichern.

Code:

foo = "hallo welt"; print(foo);

Nützliche Suchen

[PHP] Shunting-yard algo (Parser) in PHP, Java und JavaScript implementiert

Videos zum Themenbereich