Expression Parsing

LukasBanana
Erstie
Erstie
Beiträge: 19
Registriert: 25. Okt 2010 11:04

Expression Parsing

Beitrag von LukasBanana » 20. Jan 2014 22:43

Hallo aller seits,
in der letzten Vorlesung hatte ich noch mal gefragt, warum zum Thema Expression Parsing in der Vorlesung nicht viel dran kam.
Da in meinem Compiler das Expr. Parsing nun funktioniert, wollte ich hier kurz erklären, wie ich das gelöst habe:

Hier in Pseudo Code:

Code: Alles auswählen


/*
Binary expression order:
 1. Logic OR: ||
 2. Logic AND: &&
 3. Bitwise OR: |
 4. Bitwise XOR: ^
 5. Bitwise AND: &
 6. Equality comparator: =, !=
 7. Relational comparator: <, >, <=, >=
 8. Bit shift: <<, >>
 9. Addition: +
10. Subtraction: -
11. Multiplication: *
12. Division and modulo: /, %
*/

public class Parser {

	/* ... */

	Expression ParseExpression() {
		/*
		Start parsing binary expression
		with highest priority (order #1)
		*/
		return ParseLogicOrExpr();
	}

	Expression ParseLogicOrExpr() {
		/* Parse first expression */
		Expression Expr1 = ParseLogicAndExpr();

		if (TokenType() == Token.Types.LogicOrOp) {
			/* Parse operator and 2nd expression */
			Operator Op = ParseBinaryOperator();
			Expression Expr2 = ParseLogicOrExpr();
			return new BinaryExpression(Expr1, Op, Expr2);
		}

		return Expr1;
	}

	Expression ParseLogicAndExpr() {
		/* Parse first expression */
		Expression Expr1 = ParseLogicAndExpr();

		if (TokenType() == Token.Types.LogicOrOp) {
			/* Parse operator and 2nd expression */
			Operator Op = ParseBinaryOperator();
			Expression Expr2 = ParseBitwiseOrExpr();
			return new BinaryExpression(Expr1, Op, Expr2);
		}

		return Expr1;
	}

	Expression ParseBitwiseOrExpr() { /* ... first expr. ParseBitwiseXorExpr ... */ }
	Expression ParseBitwiseXorExpr() { /* ... first expr. ParseBitwiseAndExpr ... */ }
	Expression ParseBitwiseAndExpr() { /* ... first expr. ParseEqualityExpr ... */ }
	Expression ParseEqualityExpr() { /* ... first expr. ParseRelationExpr ... */ }
	Expression ParseRelationExpr() { /* ... first expr. ParseShiftExpr ... */ }
	Expression ParseShiftExpr() { /* ... first expr. ParseAddExpr ... */ }
	Expression ParseAddExpr() { /* ... first expr. ParseSubExpr ... */ }

	/*
	This works a little different:
	Consider the expression "a - b - c" and you build your tree like this:
	
	     -
	    / \
	   a   -
	      / \
	     b   c
	
	The expression can not be evaluated correctly when you traverse the tree
	from bottom-up (which is the easiest way, particular in combination with the 'visitor' pattern).
	In that case you have to build your tree 'backwards', so that the tree looks like that:
	
	       -
	      / \
	     -   c
	    / \
	   a   b
	*/
	Expression ParseSubExpr() {
		ArrayList<Expression> ExprList = new ArrayList<Expression>();
		ArrayList<BinaryOperator> OpList = new ArrayList<BinaryOperator>();
		
		/* Parse expressions and binary opertors iterative */
		while (true) {
			ExprList.add(ParseMulExpr(Flags));
			
			if (TokenType() == Token.Types.SubOp)
				OpList.add(ParseBinaryOperator());
			else
				break;
		}
		
		/* See "BuildBinExprTree" implementation below */
		return BuildBinExprTree(ExprList, OpList);
	}

	Expression ParseMulExpr() { /* ... first expr. ParseDivExpr ... */ }
	Expression ParseDivExpr() { /* ... same as in "ParseSubExpr" but next expr. is "ParseValueExpr" ... */ }

	// Here we parse a final value, bracket expressions etc.
	Expression ParseValueExpr() {
		switch (TokenType()) {
			/* Integer, floating-point, boolean, string literals */
			case Token.Types.Literal:
				return ParseLiteralExpr();
				
			/* Variable memory object */
			case Token.Types.Identifier:
				return ParseVariableExpr();
				
			/* Here we can parse unary expressions */
			case Token.Types.Sub: // <-- Unary arithmetic negation (e.g. "-3")
			case Token.Types.LogicNot: // <-- Logic boolean negation (e.g. "!(x > 3)" or "!true")
				return ParseUnaryExpr();
				
			/* Here we also parse a bracket expression */
			case Token.Types.LBracket:
				return ParseBracketExpr();
				
			default:
				Error("Unexpected token");
				break;
		}
		return null;
	}
	
	LiteralExpression ParseLiteralExpr() {
		switch (TokenType()) {
			case Token.Types.IntLiteral:
			case Token.Types.FloatLiteral:
			case Token.Types.BoolLiteral:
			case Token.Types.StringLiteral:
				return new LiteralExpression(new Literal(AcceptIt()));
			default:
				Error("Unexpected token");
				break;
		}
		return null;
	}
	
	ObjectExpression ParseVariableExpr() {
		return new ObjectExpression(AcceptIt());
	}
	
	Expression ParseUnaryExpr() {
		/* Parse unary operator and value expression */
		Operator Op = ParseUnaryOperator();
		Expression Expr = ParseValueExpr();
		return new UnaryExpression(Op, Expr);
	}
	
	BracketExpression ParseBracketExpr() {
		/* Parse brackets and inner expression */
		Accept(Token.Types.LBracket);
		
		Expression Expr = ParseExpression();
		BracketExpression BracketExpr = new BracketExpression(Expr);
		
		Accept(Token.Types.RBracket);
		
		return BracketExpr;
	}
	
	/* Build the reverse binary expr. tree (for SUB and MUL operators) */
	Expression BuildBinExprTree(List<Expression> ExprList, List<BinaryOperator> OpList) {
		if (ExprList.size() != OpList.size() + 1)
			Error("Number of operator and sub-expression mismatch");
		
		if (OpList.empty())
			return ExprList.front();
		
		/* Create AST nodes right-to-left */
		Iterator<Expression> itExpr = ExprList.begin();
		Expression Expr1 = *itExpr;
		++itExpr;
		
		for (BinaryOperator Op : OpList) {
			auto Expr2 = *itExpr;
			Expr1 = std::make_shared<BinaryExpression>(Expr1, Op, Expr2);
			++itExpr;
		}
		
		return Expr1;
	}

	/* ... */

}
Wichtig ist, die Reihenfolge der Operatoren zu beachten.
Ich habe mich bei meiner Sprache da an C++ orientiert, aber in Java dürften die Operatoren ähnlich behandelt werden.

In allen "Parse...Expr" Funktionen am Anfang (bis zur "ParseValueExpr") wird zuerst die Sub-Expr. geparst, die in der Operator Reihenfolge als nächstes kommt.
Daher geht es auch mit dem logischen ODER los.

Hier mal ein Beispiel AST für folgende Expression:

Code: Alles auswählen

bool b1 := a := 5 != 5 && a > b = c || (5 + a < c = true) != false
Unr hier der AST:

Code: Alles auswählen

Variable Definition Cmd
  Variable Obj "b1"
	Type Denoter "bool"
	Memory Object Expr "a"
	  Assignment
		Assign Expr ":="
		  Binary Expr "||"
			Binary Expr "&&"
			  Binary Expr "!="
				Literal Expr
				  Integer Literal "5"
				Literal Expr
				  Integer Literal "5"
			  Binary Expr "="
				Binary Expr ">"
				  Memory Object Expr "a"
				  Memory Object Expr "b"
				Memory Object Expr "c"
			Binary Expr "!="
			  Bracket Expr
				Binary Expr "="
				  Binary Expr "<"
					Binary Expr "+"
					  Literal Expr
						Integer Literal "5"
					  Memory Object Expr "a"
					Memory Object Expr "c"
				  Literal Expr
					Boolean Literal "true"
			  Literal Expr
				Boolean Literal "false"
Hoffe es hilft ein paar Leuten :-)

Gruß,
Lukas

simon.r
Mausschubser
Mausschubser
Beiträge: 59
Registriert: 4. Okt 2010 16:13

Re: Expression Parsing

Beitrag von simon.r » 21. Jan 2014 19:47

Man kann die Operatorpriorität gegebenenfalls auch direkt in die Grammatik mit aufnehmen, wie zum Beispiel bei http://www.lysator.liu.se/c/ANSI-C-grammar-y.html, was aber mehr Nichtterminale erfordert.

LukasBanana
Erstie
Erstie
Beiträge: 19
Registriert: 25. Okt 2010 11:04

Re: Expression Parsing

Beitrag von LukasBanana » 21. Jan 2014 20:46

Ach so ja, hab ich ganz vergessen zu posten:
Hier meine Grammtik zu den Expressions (die Commands etc. habe ich nicht weiter spezifiziert, aber zu den Expressions brauchte ich eine Gedankenstütze).
Danke für den Link, interessant sich mal die Grammatik von ANSI C anzuschauen.

LukasBanana
Erstie
Erstie
Beiträge: 19
Registriert: 25. Okt 2010 11:04

Re: Expression Parsing

Beitrag von LukasBanana » 26. Jan 2014 16:56

Noch mal ein kleiner Hinweis, wann Expression Parsing echt hässlich wird, wenn u.A. Templates wie in C++ oder Generics wie in Java unterstützt werden:

Code: Alles auswählen

// Könnte man auch abkürzen mit b = a < c;
bool b = a < c == true;
Mein Parser hat bis eben noch das "a < c == true" als den Beginn einer Template Instance interpretiert.
Also z.B. so was:

Code: Alles auswählen

template <bool b> struct a { /* ... */ };
a<c == true> /* ... */
Für solche Fälle habe ich den Parser etwas umkonstruiert:
Ich habe drei folgende Funktionen im Parser:

Code: Alles auswählen

// Speicher die aktuelle Scanner-Position auf einem Stack
void PushScannerPos();

// Holt die vorherige Scanner Position vom Stack und nimmt diese als neue Scanner position
void PopScannerPosAndRestore();

// Verwirft die vorherige Scanner Position vom Stack
void PopScannerPosAndIgnore();
Damit kann ich (an den Stellen wo es sich nur schwer vermeiden lässt) 'auf Verdacht parsen'. Falls dann ein Fehler passiert, fange ich diesen mittels try/catch ab und parse die als nächsten in Frage kommende Situation.
Das sieht dann in etwa so aus:

Code: Alles auswählen

try
{
	PushScannerPos();
	FirstParsingTry();
	PopScannerPosAndIgnore();
}
catch (const SyntaxError& UnusedHere)
{
	PopScannerPosAndRestore();
	SecondParsingTry();
}
Es wird nicht wirklich die Scanner-Position gespeichert, damit ich mir das erneute scannen aus der Datei sparen kann, aber ich zeichne die Tokens auf, während ein Eintrag auf dem Scanner-Pos-Stack liegt.

Antworten

Zurück zu „Archiv“