MySVC
an open source UNIX framework for shell script based web services provider
»Home
»Tools
»Man Page
»User Guide
»ChangeLog
»Installation
»Source Code
»Downloads
»FAQ
»Support
»License

»My Apps

Table of Contents

Introduction

MyExpr (My Service Expression Engine) is a Java library (myexpr.jar) implementing a general purpose parser for expressions based on precedence operator parsing, using regular expressions to define lexical analyzer and generating a binary syntax tree as parser output.

The abstract grammar of supported expressions is:

<Expr> ::= <Term> |
           <Term> BinaryOperator <Expr>
<Term> ::= Operand |
           UnaryOperator <Term> |
           <Term> UnaryOperator |
           OpenedParenthesis <Formula> ClosedParenthesis

It’s made from the following source classes and interfaces under package it.mysvc.myexpr:

To implement your expression engine you must implement the interfaces Operators, Lexer, Factory, Writer and (optionally) subclass the class Expr representing the syntax tree of the expression

Operators (interface)

Define:

  • the number and precedence of binary operators

  • if a binary operator is left associative

  • if a unary operator is prefix or postfix

...
public class MyExprOperators implements Operators
{
  // binary operators
  public static final int AND         = 0;
  public static final int OR          = 1;
  public static final int IMPLIES     = 2;
  public static final int EQUIVALENT  = 3;
  public static final int ASSIGN      = 4;

  // unary operator
  public static int NOT               = 0;

  // constants TRUE and FALSE
  public static final int TRUE        = -1;
  public static final int FALSE       = 0;

  public int getBinaryOperators()
  {
    return 5;
  }

  public int getPrecedence(int binaryOperator)
  {
    switch(binaryOperator)
    {
      // AND
      case 0:
        return 5;
      // OR
      case 1:
        return 4;
      // IMPLIES
      case 2:
        return 3;
      // EQUIVALENT
      case 3:
        return 2;
      // ASSIGN
      default:
        return 1;
    }
  }

  public boolean isLeftAssociative(int binaryOperator)
  {
    return true;
  }

  public boolean isPrefix(int unaryOperator)
  {
    return true;
  }

  public boolean isPostfix(int unaryOperator)
  {
    return true;
  }
}
...

The code used to indentify the binary and unary operators corresponds to the code attribute of tokens and syntax tree nodes

Lexer (interface)

Represents the lexical analyzer, used from Parser to get token stream from the string representation of expression.

It defines the following components of the expression grammar:

  • blanks

  • unary operators

  • binary operators

  • opened parenthesis

  • closed parenthesis

These components are defined by an array of regular expressions, where the index of this array represents the token code, used by Writer subclasses to get String representation from the (code,info) values of tokens (copied to nodes of Expr syntax tree)

...
// MyExprLexer:

public String[] getBinaryOperators()
{
  return new String[]
  {
    "&|and|\\*",
    "\\||or|\\+",
    "->|implies",
    "<->|iff",
    "=|is"
  };
}
...
public String[] getUnaryOperators()
{
  return new String[]
  {
    "-|~|!|not",
    "\\[[0-9]*\\]", // box modal unary operator
    "<[0-9]*>" // diamond modal unary operator
  };
}
...
// MyExprWriter:

public String getBinaryOperator(int code,String info)
{
  switch(code)
  {
    case MyExprOperators.AND:
      return "&";
    case MyExprOperators.OR:
      return "|";
    case MyExprOperators.IMPLIES:
      return "->";
    case MyExprOperators.EQUIVALENT:
      return "<->";
    case MyExprOperators.ASSIGN:
      return "=";
   }

   return null;
}
...

Factory (interface)

It’s a simple class for type casting if you have to subclass the Expr class to define a custom class representing the syntax tree of expression (e.g. MyExpr)

...
public Expr getExpr(int code,String info)
{
  return new MyExpr(code,info);
}
...

Writer (interface)

Define the conversion to string of:

  • unary and binary operators

  • operands

  • opened and closed parenthesis

See MyExprWriter.java for an example.

Expr (class)

Represents the binary syntax tree of the expression and is generated by the Parser.

It can be optionally subclassed if you need a custom class with methods implementing custom functions on expression syntax tree

Its main methods are: - to get info of tree nodes and their left and right subtrees, left - to test if a tree node is an operand (a leaf), a unary operator or binary operator - to clone a subtree (using an instance of Factory) - to convert a subtree to its string representation using an instance of Printer)

See MyExpr.java for an example.

The following classes must be not subclassed:

Parser (class)

Is the main class implementing the precedence operator expression parser based on the following grammar:

<Expr> ::= <Term> |
           <Term> BinaryOperator <Expr>
<Term> ::= Operand |
           UnaryOperator <Term> |
           <Term> UnaryOperator |
           OpenedParenthesis <Formula> ClosedParenthesis
Non terminal symbols:
  { <Expr>, <Term> }
Terminal symbols:
  {
    Operand,
    UnaryOperator,
    BinaryOperator,
    OpenedParenthesis,
    ClosedParenthesis
  }

The arguments for Parser constructor are three objects of classes implementing the following interfaces:

  • Operators

  • Lexer

  • Factory

Its main method is Expr parse(String expr) to create from the string representing the expression its corresponding Expr instance as syntax tree.

import it.mysvc.expr.*;
...
Parser parser = new Parser(new MyExprOperators(),new MyExprLexer(),new MyExprFactory());
...
Expr expr = parser.parse("x*(y+-z))");
...

It use lexical analyzer to get stream of tokens from string expression and to get for each token the corresponding code and info

...
switch(token.type)
{
  case BinaryOperator:
    token.code = lexer.getBinaryOperator(m,info);
    token.info = lexer.getBinaryOperator(info);
    break;
  case UnaryOperator:
    token.code = lexer.getUnaryOperator(m,info);
    token.info = lexer.getUnaryOperator(info);
    break;
  case Operand:
    token.code = lexer.getOperand(m,info);
    token.info = lexer.getOperand(info);
    break;
  case OpenedParenthesis:
    token.code = lexer.getOpenedParenthesis(m,info);
    token.info = lexer.getOpenedParenthesis(info);
    break;
  case ClosedParenthesis:
    token.code = lexer.getClosedParenthesis(m,info);
    token.info = lexer.getClosedParenthesis(info);
    break;
}
...

Printer (class)

Created from a Parser and a Writer and used from Expr to convert the syntax tree to corresponding string representation:

...
Writer writer = new MyExprWriter();
Printer printer = new Printer(parser,writer);
...
System.out.println(expr.toString(printer));
...

You don’t have to subclass this class

Token (class)

The lexical analyzer (Lexer) takes in input the string representing the expression and produces a stream of Token as input for Parser

Each token has:

  • a type:

    • Operand

    • UnaryOperator

    • BinaryOperator

    • OpenedParenthesis

    • ClosedParenthesis

    • a code

  • a code (an int representing the index)

  • an info (a String representing the info content of token)

Precedence (class)

Class used by Parser to evaluate the relative precedence of binary operators.

You don’t have to subclass this class

SyntaxException (class)

Implement a syntax exception while parsing the expression string converting it into Expr syntax tree.

Type of syntax errors:

  • EmptyExpression,

  • UnknownToken,

  • InvalidOperand,

  • InvalidUnaryOperator,

  • InvalidBinaryOperator,

  • InvalidOpenedParenthesis,

  • InvalidClosedParenthesis,

  • OpenedParenthesisExpected,

  • ClosedParenthesisExpected

try
{
  ...
  Expr expr = parser.parse("x*(y+-z))");
  ...
}
catch(SyntaxException e)
{
  System.out.println("Syntax Exception");
  System.out.println("expr {" + e.getExpr() + "}");
  System.out.println("queue {" + e.getQueue() + "}");
  System.out.println("token {" + e.getToken() + "}");
  System.out.println("type {" + e.getType() + "}");
  System.out.println("character {" + e.getCharacter() + "}");
  System.out.println("position {" + e.getPosition() + "}");
}

To use myexpr library (myexpr.jar):