Parser - wie/wann prioritaeten der operatoren bestimmen?

[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.