Tutorial 3: Semantic actions

The previous tutorials demonstrated how to write a grammar, compile it and use the generated lexer and parser. They also demonstrated how to use tree actions in order to improve the produced Abstract Syntax Tree (AST). In this tutorial, we go a step further. In our previous example, we wrote a grammar for simple mathematical expression. But what if we want to describe how the mathematic expressions have to be interpreted? In this tutorial, we see how we can define semantic actions executed during the parsing. Building upon our example, we will use semantic actions to define a simple interpreter of mathematic expressions along our parser.

Semantic actions

First, semantic actions are pieces of behaviors that are introduced in grammar rules and executed when the parser encountered them. In the Hime Parser Generator, we strongly believe in the separation of concerns and we do not write the content of the semantic actions within the grammar rules. Semantic actions are marked in the grammar rules, but must be specified in one of the language for the .Net platform. For example, we now amend the exp_atom rule definition to introduce a semantic action as follow:

 exp_atom-> NUMBER^ {OnNumber}
    | '('! exp^ ')'! ;


Here, the {OnNumber} represents the semantic action. It is placed directly after the NUMBER element in the rule. The new meaning of this rule is that when the parser finds itself in this rule and immediately after it encounters a NUMBER token, it will execute the {OnNumber} semantic action.

The {OnNumber} semantic action is itself a piece of code that you specify and that will be called by the parser in this situation. In a sense, they are callbacks that you define and that are given to the parser. In C#, a semantic action is implemented as a method with the following signature:

void OnNumber(Variable head, Symbol[] body, int length);

There should be no return value. The semantic action is given three parameters:
  • head is the symbol corresponding to the head of the rule in which the parser is in. In our example, this would be the exp_atom symbol.
  • body is an array of the symbols found by the parser for the rule so far. In our example, there will be only one, a NUMBER token.
  • length gives the number of symbols in the body array.

Note that if the semantic action is placed in the middle of the rule, the parser will only give in the body parameter the symbols that are before the semantic action. This is due to the fact that the parser is precisely at this point in the rule.

Updating the example

What we want to do in the case of our example is to implement a stack-based interpreter that will interpret on the fly the mathematical expression that is being parsed. To do so, the first step is to modify the grammar rules in order to introduce semantic actions that tell us what the parser is currently doing. We then amend the grammar rules as follow:

exp_atom  -> NUMBER^ {OnNumber}
    | '('! exp^ ')'! ;
exp_op0  -> exp_atom^
    |  exp_op0 '*'^ exp_atom {OnMult}
    |  exp_op0 '/'^ exp_atom {OnDiv};		
exp_op1  -> exp_op0^
    |  exp_op1 '+'^ exp_op0 {OnPlus}
    |  exp_op1 '-'^ exp_op0 {OnMinus};


With the above semantic actions, the parser will tell us when it encountered a NUMBER token, or any of the operators. Our strategy is to rely on the fact that the above rules also implement the mathematic operators’ precedence. Hence, when we reach the {OnNumber} semantic action we only have to push the value of the NUMBER token found on a stack and when we reach an operator we pop two values, execute the semantic of the operator and push the result back on the stack. This is easily implemented in C# as follow:

private Stack<float> stack;
public void OnNumber(Variable head, Symbol[] body, int length)
{
	TextToken token = body[0] as TextToken;
	stack.Push(Single.Parse(token.Value));
}
public void OnMult(Variable head, Symbol[] body, int length)
{
	float right = stack.Pop();
	float left = stack.Pop();
	stack.Push(left * right);
}
public void OnDiv(Variable head, Symbol[] body, int length)
{
	float right = stack.Pop();
	float left = stack.Pop();
	stack.Push(left / right);
}
public void OnPlus(Variable head, Symbol[] body, int length)
{
	float right = stack.Pop();
	float left = stack.Pop();
	stack.Push(left + right);
}
public void OnMinus(Variable head, Symbol[] body, int length)
{
	float right = stack.Pop();
	float left = stack.Pop();
	stack.Push(left - right);
}

Putting it all together

Now, we only need to gives these semantic actions to the parser. When the Hime Parser Generator is given a grammar that contains semantic actions, it automatically generates within the class of the parser, a nested class called Actions. It serves as a structure to hold the callback for all semantic actions. An instance of this nested class has to be created and passed to the parser in its constructor. This is done as follow:

stack = new Stack<float>();
// create the holder for all delegates and register our semantic actions
MathExpParser.Actions actions = new MathExpParser.Actions();
actions.OnNumber = new SemanticAction(OnNumber);
actions.OnMult = new SemanticAction(OnMult);
actions.OnDiv = new SemanticAction(OnDiv);
actions.OnPlus = new SemanticAction(OnPlus);
actions.OnMinus = new SemanticAction(OnMinus);
// create the lexer and parser and gives the actions
MathExpLexer lexer = new MathExpLexer("(2 + 3) * 4");
MathExpParser parser = new MathExpParser(lexer, actions);
// parse the expression and display the result
Redist.AST.ASTNode root = parser.Parse();
Console.WriteLine("Result = " + stack.Peek());

When the parser has finished we simply have to look at the top of the stack for the result, the semantic actions having been called during the parsing.

Last edited May 14, 2013 at 1:35 PM by lwouters, version 2

Comments

No comments yet.