Open-source image
open-source
Hime logo

Table of content

Tutorial 3 (Rust) - Semantic actions

The previous tutorials demonstrated how to write a grammar, compile it and use the generated lexer and parser. It 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 arithmetic expressions along our parser.

Here we start from the grammar produced a the end of the previous tutorial:

grammar MathExp
{
    options
    {
        Axiom = "exp";
        Separator = "SEPARATOR";
    }
    terminals
    {
        WHITE_SPACE -> U+0020 | U+0009 | U+000B | U+000C ;
        SEPARATOR   -> WHITE_SPACE+;

        INTEGER     -> [1-9] [0-9]* | '0' ;
        REAL        -> INTEGER? '.' INTEGER  (('e' | 'E') ('+' | '-')? INTEGER)?
                    |  INTEGER ('e' | 'E') ('+' | '-')? INTEGER ;
        NUMBER      -> INTEGER | REAL ;
    }
    rules
    {
        exp_atom   -> NUMBER^
                   | '('! exp^ ')'! ;
        exp_factor -> exp_atom^
                   |  exp_factor '*'^ exp_atom
                   |  exp_factor '/'^ exp_atom ;
        exp_term   -> exp_factor^
                   |  exp_term '+'^ exp_factor
                   |  exp_term '-'^ exp_factor ;
        exp        -> exp_term^ ;
    }
}

Semantic Actions

First, semantic actions are pieces of behaviors that are introduced in grammar rules and executed when the parser encountered them. In Hime, 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 specified in the grammar rules, but must be implemented with external code. 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 implemented by 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 Rust, a semantic action is implemented as a function with the following signature:

fn on_number(&mut self, head: Symbol, body: &SemanticBody);

There should be no return value. The semantic action is given two parameters (aside from self):

  • 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 a handle giving access to the symbols found by the parser for the rule so far. In our example, there will be only one, a NUMBER token.

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 grammar

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_factor  -> exp_atom^
           |  exp_factor '*'^ exp_atom @OnMult
           |  exp_factor '/'^ exp_atom @OnDiv;
exp_term  -> exp_factor^
           |  exp_term '+'^ exp_factor @OnPlus
           |  exp_term '-'^ exp_factor @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.

Now let's regenerate the lexer and parser for the new grammar:

  • On Windows:himecc.bat MathExp.gram -t:rust or explicitly withnet461/himecc.exe MathExp.gram -t:rust
  • On Linux and MacOS:./himecc MathExp.gram -t:rust
  • On any OS, explicitly with .Net Core:dotnet netcore20/himecc.dll MathExp.gram -t:rust
  • On any OS, explicitly with Mono:mono net461/himecc.exe MathExp.gram -t:rust

Replace the old files in your test project by the newly generated ones.

Implement semantic actions

Now we have to implement the semantic actions in Rust. Looking at the content of the MathExp.rs source for the parser, you can see the definition has been updated to include an innner Actions trait with methods corresponding to our defined semantic actions:

/// Represents a set of semantic actions in this parser
pub trait Actions {
    /// The OnNumber semantic action
    fn on_number(&mut self, head: Symbol, body: &SemanticBody);
    /// The OnMult semantic action
    fn on_mult(&mut self, head: Symbol, body: &SemanticBody);
    /// The OnDiv semantic action
    fn on_div(&mut self, head: Symbol, body: &SemanticBody);
    /// The OnPlus semantic action
    fn on_plus(&mut self, head: Symbol, body: &SemanticBody);
    /// The OnMinus semantic action
    fn on_minus(&mut self, head: Symbol, body: &SemanticBody);
}

In the same file we can see a new set of parse_*_with functions that can be passed an object implementating the Actions trait. This means that the methods in this passed instance will be called when semantic actions are executed.

pub fn parse_string_with(input: &str, actions: &mut Actions) -> ParseResult

What we want to do is implement the Actions trait and give an instance of it to the parsing function. We will then define an Evaluator object that will implement Actions and implement a stack-based evaluator of arithmetic expression:

use std::str::FromStr;

use hime_redist::symbols::SemanticBody;
use hime_redist::symbols::SemanticElementTrait;
use hime_redist::symbols::Symbol;

struct Evaluator {
    stack: Vec<f32>
}

impl Evaluator {
    pub fn new() -> Evaluator {
        Evaluator {
            stack: Vec::<f32>::new()
        }
    }

    pub fn result(&self) -> f32 {
        self.stack[self.stack.len() - 1]
    }
}

impl MathExp::Actions for Evaluator {
    fn on_number(&mut self, _head: Symbol, body: &SemanticBody) {
        let value = body.get_element_at(0).get_value().unwrap();
        self.stack.push(f32::from_str(&value).unwrap());
    }

    fn on_mult(&mut self, _head: Symbol, _body: &SemanticBody) {
        let right = self.stack.pop().unwrap();
        let left = self.stack.pop().unwrap();
        self.stack.push(left * right);
    }

    fn on_div(&mut self, _head: Symbol, _body: &SemanticBody) {
        let right = self.stack.pop().unwrap();
        let left = self.stack.pop().unwrap();
        self.stack.push(left / right);
    }

    fn on_plus(&mut self, _head: Symbol, _body: &SemanticBody) {
        let right = self.stack.pop().unwrap();
        let left = self.stack.pop().unwrap();
        self.stack.push(left + right);
    }

    fn on_minus(&mut self, _head: Symbol, _body: &SemanticBody) {
        let right = self.stack.pop().unwrap();
        let left = self.stack.pop().unwrap();
        self.stack.push(left - right);
    }
}

Now all we need is to modify the program to use the evaluator.

fn main() {
    let mut evaluator = Evaluator::new();
    let _result = MathExp::parse_string_with("(2+3)*4", &mut evaluator);
    println!("{:}", evaluator.result());
}

Test the evaluator

Then rebuild the test project and run.

cargo build

  • On Windows:target/debug/test_hime.exe
  • On Linux and MacOS:./target/debug/test_hime

The output of the program should be 20.

This conclude this series of tutorial for how to use Hime-generated parsers in C#. For more information about Hime, head to the reference documentation (see the Table of Content on the left).