Parser - wie/wann prioritaeten der operatoren bestimmen?

[Shade Of Mine]

Hallo Leute.

Ich habe einen kleinen Parser geschrieben, der mir einen Abstract Syntax Tree generiert.

Nur hat der Parser keine Ahnung von den Prioritaeten der Operatoren...

Als erstes laeuft ein Lexer der ein Array aus Token generiert, dieses wird dann vom Parser uebernommen und der schaut mittels ein paar Regeln was er daraus machen kann.

Nur stehe ich momentan voellig an, was die prioritaeten der operatoren betrifft... Mein Parser versteht die Grammatik ja eigentlich nicht, er wendet auf das Token-Array nur irgendwelche Regeln an...

Und wie sollte man die Prioritaeten im AST darstellen?
momentan sieht es so aus:

aus:

1+2+3;

wird:
STATEMENT
  EXPRESSION
    VALUE
    SUBEXPRSSION
      OPERATOR
      VALUE
    SUBEXPRESSION
      OPERATOR
      VALUE

ist das fuer expressions denn ueberhaupt ok?
eine expression ist bei mir so definiert:

EXPRESSION besteht aus VALUE und optional unendlich vielen SUBEXPRESSIONs
SUBEXPRESSION besteht aus OPERATOR und VALUE

[Michael E.]

Zur Priorität hat volkard mal folgendes gesagt: http://www.c-plusplus.net/forum/viewtopic-var-t-is-95452-and-highlight-is-holzdisketten.html

[Shade Of Mine]

Michael E. schrieb:

Zur Priorität hat volkard mal folgendes gesagt: http://www.c-plusplus.net/forum/viewtopic-var-t-is-95452-and-highlight-is-holzdisketten.html

Cool. Danke.

Bleibt nur die Frage: sollte man die Klammerung vor dem aufbauen des AST, waehrendessen oder danach machen?

Ich denke her danach, weil man dann einfach nur jede EXPRESSION-Node finden muss und 'neu ordnen'. Allerdings waere es irgendwie schoener, wenn der Parser schon die Klammerung so vorfinden wuerde... Also doch eher einen zwischenschritt zwischen Lexer und Parser ?

Bleibt dennoch die Frage: wie sollte

1+2*3+1;  ->  1+(2*3)+1

im AST dann aussehen?

STATEMENT
  EXPRESSION
    VALUE(1)
    SUBEXPRESSION
      OPERATOR(+)
      EXPRESSION
        VALUE(2)
        SUBEXPRESSION
          OPERATOR(*)
          VALUE(3)
    SUBEXPRESSION
      OPERATOR(+)
      VALUE(1)

??

Danke

[virtuell Realisticer]

Tag Shade,

also wenn ich dich richtig verstanden habe, dann hast du im Prinzip das selbe
Problem, vor dem auch ich bei meinem jetztigen Abschlussprojekt stand, mit dem
kleinen Unterschied, dass ich logische und keine mathematischen Ausdruecke
bearbeite.

Nun scheint mir allerdings, dass dein Problem etwas komplexer ist als meins,
aber ich lege einfach mal dar, was mein Problem war und wie ich es geloest
habe, vielleicht kannst du das ein oder andere gebrauchen.

Zu aller erst muss ich sagen, dass ich nicht hingehe und selbst klammern
setze, d. h. wenn ich einen logischen Ausdruck a or b and c habe, dann wird
bei mir nicht erst b and c und das daraus resultierende Ergebnis mit a
or verknuepft, weshalb mir hier die Arbeit etwas einfacher gemacht worden
ist. Ansonsten, wie es in dem anderen Thread, dessen Link hier gepostet
worden ist, bereits erwaehnt: umwandeln in Postfix-Notation.

Aus einem korrekt geklammerten Ausdruck, wir bleiben mal bei mathematischen
Ausdruecken, (a * (((b + c)(d * e)) + f)) wird die Postfix-Notation:
abc*de**f+. Nun kann man daraus einen schoenen Baum erstellen:

Du liest solange den Ausdruck ein und erstellst einen Knoten mit den
Variablen als Informationen und legst diesen auf einen Stack, bis du auf
einen Operator triffst. Nun erstellst du einen Knoten, mit dem Operator
als Information und den letzten beiden Knoten auf dem Stack als rechtes und
linkes Element des "Operator"-Knoten. Diesen legst du zurueck in den Stack
und faengst selbigen Vorgang wieder von vorne an.

Folgender Baum wird hierdurch aus obiger Notation erstellt:

(*)
       /   \
     (a)   (+)
          /   \
        (*)   (7)
       /   \
      /     \
    (+)     (*)
   /   \   /   \
 (b)  (c)(d)  (e)

Den kann man natuerlich sehr schoen durchlaufen und entsprechend auswerten.

So, ich nehme mal an, das ist nichts neues fuer dich und du willst in Grunde
was voellig anderes machen? Ich wollte es nur nicht unerwaehnt lassen :).
Vielleicht ist ja doch was dabei, was dir hilft ;).

mfg
v R

[Shade Of Mine]

virtuell Realisticer schrieb:

So, ich nehme mal an, das ist nichts neues fuer dich und du willst in Grunde
was voellig anderes machen? Ich wollte es nur nicht unerwaehnt lassen :).
Vielleicht ist ja doch was dabei, was dir hilft ;).

Naja, das ganze soll ein parser fuer eine scripsprache werden (nicht um sie auszufuehren, sondern zur analyse von scripten)... matehmatische ausdruecke parsen ist also lediglich ein nebenproblem

einen baum daraus machen ist logisch, auch wenn er bei mir anders aussieht, weil ich ihn ja in den AST einbauen muss

volkards trick mit dem zaehlen ist aber auch recht nett, mal sehen was sich davon besser implementieren laesst...

wie gesagt: die grosse frage die sich stellt ist: wann mache ich das?

1. soll ich den AST aufbauen und nachher die Expressions richtig ordnen
2. soll ich nach dem lexer einen prioritaeten scanner laufen lassen, der die klammern einfuegt.
3. waherend dem aufbauen des AST die prioritaeten checken. das wuerde aber nur gehen, wenn man grammatikalische regeln dafuer aufstellen koennte, weil mein parser nur 'dumm' regeln anwenden kann und sonst nichts.

[virtuell Realisticer]

Shade Of Mine schrieb:

virtuell Realisticer schrieb:

So, ich nehme mal an, das ist nichts neues fuer dich und du willst in Grunde
was voellig anderes machen? Ich wollte es nur nicht unerwaehnt lassen :).
Vielleicht ist ja doch was dabei, was dir hilft ;).

Naja, das ganze soll ein parser fuer eine scripsprache werden (nicht um sie auszufuehren, sondern zur analyse von scripten)... matehmatische ausdruecke parsen ist also lediglich ein nebenproblem

Hab ich mir doch gedacht

einen baum daraus machen ist logisch, auch wenn er bei mir anders aussieht, weil ich ihn ja in den AST einbauen muss

volkards trick mit dem zaehlen ist aber auch recht nett, mal sehen was sich davon besser implementieren laesst...

wie gesagt: die grosse frage die sich stellt ist: wann mache ich das?

1. soll ich den AST aufbauen und nachher die Expressions richtig ordnen

IMHO viel zu aufwendig. Dann musst du naemlich hingehen, den AST durchlaufen
und jede Menge Strukturen umbiegen. Da ist dann...

2. soll ich nach dem lexer einen prioritaeten scanner laufen lassen, der die klammern einfuegt.

...diese Option viel besser und weniger aufwendig, IMHO.

3. waherend dem aufbauen des AST die prioritaeten checken. das wuerde aber nur gehen, wenn man grammatikalische regeln dafuer aufstellen koennte, weil mein parser nur 'dumm' regeln anwenden kann und sonst nichts.

Nicht nur das, hast du diese Konstruktion: a + b * c
so musst du hingehen und dir merken, dass der erste Teilausdruck weniger
Prioritaet besitzt, als der zweite Teilausdruck. Auch hier musst du dann
wieder hingehen, den ersten Knoten aufloesen um alles entsprechend umzumodeln.

IMHO auch etwas zu aufwendig. Wuerde zu Option 2 tendieren.

mfg
v R

[Shade Of Mine]

virtuell Realisticer schrieb:

Wuerde zu Option 2 tendieren.

Ich auch.

Aber ich wuerde trotzdem gerne noch die eine oder andere Meinung hoeren

Schliesslich ist es mein erster grosser Parser und hier spielt Performance nur eine untergeordnete Rolle (lieber leichter zu warten) weil ich nachher sowieso komplexe analysen des codes machen will. da fallen dann ein paar sekunden mehr oder weniger fuers parsen nicht ins gewicht.

[Jester]

Ich würde eher zu Option 3 Tendieren. Also die Prioritäten fest in der Grammatik verankern. Das macht zwar beim aufstellen der Grammatik etwas mehr Mühe, dafür brauchst Du Dir später keine Gedanken mehr darum machen. Der Parser erledigt das sozusagen gleich mit.

MfG Jester

[Shade Of Mine]

Jester schrieb:

Ich würde eher zu Option 3 Tendieren. Also die Prioritäten fest in der Grammatik verankern. Das macht zwar beim aufstellen der Grammatik etwas mehr Mühe, dafür brauchst Du Dir später keine Gedanken mehr darum machen. Der Parser erledigt das sozusagen gleich mit.

Wie wuerde da die grammatik aussehen? Ich kann mir das irgendwie nicht vorstellen

waere super wenn du ein beispiel posten koenntest...

[Jester]

hehe, da klaue ich einfach mal das Beispiel aus der spirit-Doku:

group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

Der Gag daran ist, daß Du sobald Du zu ner höheren Priorität wechelst (hier von +/- nach *,/) Du ein anderes Nichtterminal verwendest. Also statt weiterhin terms zu produzieren läßt Du nur noch factors zu. Wenn jetzt jemand doch wieder was niederpriores bringen möchte, dann geht das nur, wenn er die zweite Regel verwendet und factor->group anwendet. group erzwingt dann aber die Klammern.

Daher kann a*b+c hier nur als (a*b)+c geparsed werden, da für a*(b+c) ja b+c ein term sein müßte, das ist es aber nur wenn man über group geht und dann müßte man aber klammern haben. in a*b+c sind aber halt keine drin.

Das ist zunächst ziemlich verwirrend. Versuch mal ne Stunde damit rumzuspielen. Mit der Zeit kriegste auch raus wie Du's machen mußt, daß manche Operatoren rechts-assoziativ sind und sowas.

MfG Jester

[schnitzl]

So, wegen gerade eben im Chat hier das Ganze nochmal
Nur ein Vorschlag wie man das mit einem einfache recursive-descent-Parser lösen könnte.

Zuerst einmal das "Typsystem". Das Beispiel ist aus meinem aktuellen Projekt, ein Interpreter für eine kleine Sprache. Je nachdem, was du anschließend mit dem Tree machen willst, musst du eben calculate() ändern; es könnte zum Beispiel auch nur die Ausgabe machen, also dass AddNode::calculate() eher AddNode::output(ostream&) sein würde und folgendes machen würde:

left->output(cout);
cout << " + ";
right->output(cout);

oder so. Musst dann mal konkretisieren. Aber jetzt zum Code, ich nehm mal die wichtigsten Stücke raus:

class Node {
public:
	virtual ~Node();
	virtual const boost::shared_ptr<Value> calculate() = 0;
	virtual void assign(const Value& rhs);
	// is it a valid lvalue?
	virtual bool lvalue() const;
	// is it a constant expression (like 5+3 or 7^423)?
	virtual bool constant() const;
};

	class BinaryNode : public Node {
	private:
		bool c;

	protected:
		boost::shared_ptr<Node> left, right;

	public:
		BinaryNode(boost::shared_ptr<Node> l, boost::shared_ptr<Node> r);
		~BinaryNode();

		bool constant() const;
	};

	class AddNode : public BinaryNode {
	public:
		AddNode(boost::shared_ptr<Node> l, boost::shared_ptr<Node> r);
		const boost::shared_ptr<Value> calculate();
	};

	class SubNode : public BinaryNode {
	public:
		SubNode(boost::shared_ptr<Node> l, boost::shared_ptr<Node> r);
		const boost::shared_ptr<Value> calculate();
	};

	class MulNode : public BinaryNode {
	public:
		MulNode(boost::shared_ptr<Node> l, boost::shared_ptr<Node> r);
		const boost::shared_ptr<Value> calculate();
	};

	class DivNode : public BinaryNode {
	public:
		DivNode(boost::shared_ptr<Node> l, boost::shared_ptr<Node> r);
		const boost::shared_ptr<Value> calculate();
	};

In calculate() macht zum Beispiel AddNode:

return left->calculate()->add(*right->calculate());

Aber du willst ja anscheinend nichts konkret berechnen oder doch?

Auf jeden Fall, jetzt zum Parser, der die Operatorenreihenfolge schon fest eingebaut hat.

const boost::shared_ptr<Node> Calculator::add_sub() {
	boost::shared_ptr<Node> left = mul_div_mod();

	while(1) {
		Token token = tokenizer.next_token();

		switch(token.type) {
		case Token::ADD:
			left = boost::shared_ptr<Node>(new AddNode(left, mul_div_mod()));
			break;

		case Token::SUB:
			left = boost::shared_ptr<Node>(new SubNode(left, mul_div_mod()));
			break;

		case Token::END:
			return left;

		default:
			tokenizer.unget();
			return left;
		}
	}

	return left;
}

const boost::shared_ptr<Node> Calculator::mul_div_mod() {
	boost::shared_ptr<Node> left = factor();

	while(1) {
		Token token = tokenizer.next_token();

		switch(token.type) {
		case Token::MUL:
			left = boost::shared_ptr<Node>(new MulNode(left, factor()));
			break;

		case Token::DIV:
			left = boost::shared_ptr<Node>(new DivNode(left, factor()));
			break;

		case Token::END:
			return left;

		default:
			tokenizer.unget();
			return left;
		}
	}

	return left;
}

const boost::shared_ptr<Node> Calculator::factor() {
	NUMERUS_TRACE;

	Token token = tokenizer.next_token();
	boost::shared_ptr<Node> ret;

	switch(token.type) {
	case Token::NUM_INT:
		ret = boost::shared_ptr<Node>(new NumNode(type_controller.integer().create(token.str)));
		break;

	case Token::NUM_REAL:
		ret = boost::shared_ptr<Node>(new NumNode(type_controller.real().create(token.str)));
		break;

	case Token::LPAREN:
		ret = add_sub();
		token = tokenizer.next_token();
		if(token.type != Token::RPAREN)
			throw SyntaxError("closing parenthesis `)' missing");
		break;

	/* usw */
	}

	return ret;
}

Ich hoffe das hilft irgendwie.

[Shade Of Mine]

Jester schrieb:

group       ::= '(' expression ')'
    factor      ::= integer | group
    term        ::= factor (('*' factor) | ('/' factor))*
    expression  ::= term (('+' term) | ('-' term))*

Verzwickt.

Ich fasse es mal so zusammen wie ich es verstanden habe:
(der einfachheit halber nur mit + und * (ohne - und /)

eine expression besteht aus
term oder tem + term
ein besteht aus
factor oder factor * factor
ein factor ist entweder eine normale zahl oder eine geklammerte expression

dadurch ergibt sich, dass
1+2*3+1 zu folgendem evaluiert:

es wird eine expression erwartet, der parser sieht
1
und matcht expression folgendermassen:
1 -> term? -> factor? -> integer? ja
2 -> term? -> factor * factor? ja
1 -> term? -> factor? -> integer? ja

resultat:
term(1) + term(2*3) + term(1)

wenn ich jetzt noch ein ^ (hoch) einbauen will, wuerde es so aussehen

power ::= (integer | group) ('^' (integer | group))*
factor ::= power ('*' power)*

falls ich das richtig verstanden habe, dann ist der trick gut
wird aber ne heiden arbeit das einzubauen

@schnitzl:
ja, das wird dann die naechste aufgabe sein: den knoten inhalt zu geben momentan ist der AST naemlich 'leer', dh, er liefert mir zwar welche regeln er gematcht hat, aber nicht worauf und welchen wert sie jetzt haben das muss ich alles noch einbauen - stehe da erst am anfang. aber ich hoffe dass daraus etwas wird

selber berechen will ich den ausdruck nicht, aber es soll dann fuer die analyse moeglich sein zu checken, ob da konstante ausdruecke drinnen sind, so dass er
$a=2+$b+3;
zu
$a=$b+5;
umwandeln kann.

[otze]

natürlich ist soeine grammatik erstmal eine heidenarbeit, dafür ergeben sich dann aber alle prioritäten und im endeffekt der gesamte sprachbaum vollständig aus der grammatik, was den code ausserhalb der grammatik um einiges vereinfacht.

das tolle an solchen grammatiken ist aber auch, dass man sie sehr schön erweitern kann, wenn man neue sprachfeatures integrieren will, ohne irgendwoanders was ändern zu müssen(boost::spirit bringt dies meiner meinung nach zur perfektion in der anwendung)

[Jester]

Shade: jo, denke Du hast es verstanden. Klar, die Grammatik zu bauen ist ne Menge denkarbeit, aber dafür nicht so viel zu tippen. Für den Rest gibt es dann ja fertige Generatoren. boost::spirit, antLR oder auch lex/yacc, flex/bison.

[Shade Of Mine]

Jester schrieb:

Für den Rest gibt es dann ja fertige Generatoren. boost::spirit, antLR oder auch lex/yacc, flex/bison.

Fuer PHP gibt es soweit ich weiss keines davon. Ist aber auch egal, weil ich es selber machen will. Meine Erlebnisse mit flex/bison waren nicht so berauschend...

[otze]

Fuer PHP gibt es soweit ich weiss keines davon.

nein, aber du kannst mir hilfe von yacc(wars das?) php code generieren lassen. du gibst denen eine grammatik und die passenden code schnipsel, und das programm baut dir daraus dann alles zusammen.