Writing a parser: Calculator example

In many situations, we need to transform user input to machine readable data. Mostly, a regular expression, sscanf or even very simple handling via string functions will be sufficient. For more complex (and forgiving) input, and when we want to tell users what went wrong where these methods may not be enough.

Imagine a situation in which you would like to evaluate mathematical expressions, so, for example, the user would be inputting something like 1 + 2 or -1 / (3 * 6) and you would like output the expression's result. Something like this:

To get started with a parser, we will first have to write a grammar. The XP framework comes with a technology to generate so-called LALR parsers from these - don't worry about its technical details for the moment, though.

  %{
    // Top: Package and uses go here
  %}
  
  // Tokens and associativity definitions
  
  %%
  // Rules go here
  %%

  %{
    $package= 'math';
  
    uses(
      'math.Constant',
      'lang.types.Integer',
      'lang.types.Double'
    );
  %}

  %token T_INTEGER T_DOUBLE

  name:
      rule
    | rule1 token1 { $$= new Rule1($1, $2); }
    | rule2
  ;

  start:
      expression { /* May be omitted: $$= $1; */ }
  ;

  expression:
      T_INTEGER { $$= new math·Constant(new Integer($1)); }
    | T_DOUBLE { $$= new math·Constant(new Double($1)); }  
    | '(' expression ')' { $$= $2; }
  ;

  class  extends AbstractLexer {
    const DELIMITERS= " +-*/()\r\n\t";
    protected $tokenizer= NULL;
  
    public function __construct($expression) {
      $this->tokenizer= new StringTokenizer($expression, self::DELIMITERS, TRUE);
    }
  
    public function advance() {
      do {
        if (!$this->tokenizer->hasMoreTokens()) return FALSE;
        $token= $this->tokenizer->nextToken(self::DELIMITERS);
        
        // Ignore whitespace
        if (FALSE !== strpos(" \n\r\t", $token)) continue;
  
        if (FALSE !== strpos(self::DELIMITERS, $token) && 1 == strlen($token)) {
          $this->token= ord($token);
          $this->value= $token;
        } else if (ctype_digit($token)) {
          $this->token= ::T_INTEGER;
          $this->value= intval($token);
        } else if (2 == sscanf($token, '%d.%d', $whole, $fraction)) {
          $this->token= ::T_DOUBLE;
          $this->value= doubleval($token);
        } else {
          throw new IllegalStateException('Unknown token "'.$token.'"');
        }
        
        break;
      } while (1);

      return TRUE;
    }
  }

expression:
      T_INTEGER { $$= new math·Constant(new Integer($1)); }
    | T_DOUBLE { $$= new math·Constant(new Double($1)); }  
    | expression '+' expression { $$= new math·Addition($1, $3); }
    | expression '-' expression { $$= new math·Subtraction($1, $3); }
    | expression '*' expression { $$= new math·Multiplication($1, $3); }
    | expression '/' expression { $$= new math·Division($1, $3); }
    | '(' expression ')' { $$= $2; }
  ;

  %left '+' '-' 
  %left '*' '/'

This describes the precedence and associativity of the four arithmetic operators. Plus and minus are left associative, and have lower precedence than star and slash, which are also left associative.

  | '-' expression { $$= new math·Multiplication(new math·Constant(new Integer(-1)), $2); }

  + lang.Object
  |--- math.Constant
  `--+ math.Operation
     |--- math.Addition
     |--- math.Subtraction
     |--- math.Multiplication
     `--- math.Division

  class  extends Object implements  {
    protected
      $number= NULL;
      
    public function __construct(Number $number) {
      $this->number= $number;
    }
  
    public function toString() {
      return $this->getClassName().'('.xp::stringOf($this->number).')';
    }
  }

  abstract class  extends Object implements  {
    protected
      $lhs= NULL,
      $rhs= NULL;
      
    public function __construct( $lhs,  $rhs) {
      $this->lhs= $lhs;
      $this->rhs= $rhs;
    }
  
    public function toString() {
      return $this->getClassName().'('.xp::stringOf($this->lhs).', '.xp::stringOf($this->rhs).')';
    }
  }

  class  extends  {
  }

  echo xp::stringOf(create(new ())->parse(new ($input)));

• For the input string "1", we will see math.Constant(lang.types.Integer(1))
• For the input string "1.5", we will see math.Constant(lang.types.Double(1.5))
• Same applies if we surround input by brackets as in "(1)"
• Given an expression "3 * 5", we will read math.Multiplication(math.Constant(lang.types.Integer(3)), math.Constant(lang.types.Integer(5)))
• If we do not pass anything, we'll receive a syntax error reading "Unexpected end-of-file" - our grammar does not allow for empty expressions!

  interface  {
    public function evaluate();
  }

  class  extends Object implements  {
    // ...
    public function evaluate() {
      return $this->number;
    }
  }

  abstract class  extends Object implements  {
    // ...
    protected abstract function perform($lhs, $rhs);
  
    public function evaluate() {
      return Primitive::boxed($this->perform(
        Primitive::unboxed($this->lhs->evaluate()),
        Primitive::unboxed($this->rhs->evaluate())
      ));
    }
  }

  class  extends  {
    protected function perform($lhs, $rhs) {
      return $lhs + $rhs;
    }
  }

  uses('util.cmd.Command', 'math.Lexer', 'math.Parser');
  
  class Calculator extends Command {
  
    #[@arg(position= 0)]
    public function setExpression($expr) {
      $this->expr= $expr;
    }
  
    public function run() {
      $this->out->writeLine(create(new ())->parse(new ($this->expr))->evaluate());
    }
  }

Subscribe

You can subscribe to the XP framework's news by using RSS syndication.

Categories

Related

Find related articles by a search for «Writing».