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

Parser.java

// $Id$

//  myexpr - My Service Expression Engine - Version 1.0 (www.mysvc.it)
//  Copyright (C) 2009 Davide Cucciniello <davide6169@gmail.com>
//
//  This program is free software: you can redistribute it and/or modify
//  it under the terms of the GNU General Public License as published by
//  the Free Software Foundation, either version 3 of the License, or
//  (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program.  If not, see <http://www.gnu.org/licenses/>.

/* **********************************************************************
 *
 *  ***   **        *** **  **  ****
 *   **  **        *  *  *  ** **  *
 *   *** **  **  * ***   *  *  *
 *   * ** *   * **   **   * *  *
 *   * *  *   * *  *  *   **   **
 *  ***  ***   **  ***     *    ****
 *             *
 *            *
 *
 *  My Service
 *
 * ***********************************************************************
 *
 *  ***   **       *****
 *   **  **         *  *
 *   *** **  **  *  ***  ***** ****  ****
 *   * ** *   * **  *     ***   *  *  * *
 *   * *  *   * *   *  *  ***   *  *  *
 *  ***  ***   **  ***** ** **  ***  ***
 *             *                *
 *            *                ***
 *
 *  My Service Expression Engine
 *
 *  File: Parser.java
 *
 *  Description:
 *    class Parser: Parser of an expression
 *    MyExpr: Java library implementing an advanced generic
 *    expression parser based on precedence operator
 *
 * ***********************************************************************
 *
 *  History:
 *    1.0               first version
 *
 * *********************************************************************** */

package it.mysvc.myexpr;

import java.util.Stack;
import java.util.Queue;
import java.util.LinkedList;
import java.util.regex.Pattern;
import java.util.regex.Matcher;

public class Parser
{
    /*
     Operator precedence parser

     <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
       }
  */

  private Operators operators;
  private Lexer lexer;
  private Factory factory;
  private Queue<Token> stream;
  private Precedence precedence;

  private Pattern[] blanks;

  private Pattern[] binaryOperators;
  private Pattern[] unaryOperators;
  private Pattern[] operands;
  private Pattern[] openedParenthesis;
  private Pattern[] closedParenthesis;

  public Parser(Operators operators,Lexer lexer,Factory factory)
  {
    this.operators = operators;
    this.lexer = lexer;
    this.factory = factory;
    this.precedence = new Precedence(operators);

    binaryOperators = new Pattern[lexer.getBinaryOperators().length];

    for(int i=0;i<lexer.getBinaryOperators().length;i++)
      binaryOperators[i] = Pattern.compile(lexer.getBinaryOperators()[i]);

    unaryOperators = new Pattern[lexer.getUnaryOperators().length];

    for(int i=0;i<lexer.getUnaryOperators().length;i++)
      unaryOperators[i] = Pattern.compile(lexer.getUnaryOperators()[i]);

    operands = new Pattern[lexer.getOperands().length];

    for(int i=0;i<lexer.getOperands().length;i++)
      operands[i] = Pattern.compile(lexer.getOperands()[i]);

    openedParenthesis = new Pattern[lexer.getOpenedParenthesis().length];

    for(int i=0;i<lexer.getOpenedParenthesis().length;i++)
      openedParenthesis[i] = Pattern.compile(lexer.getOpenedParenthesis()[i]);

    closedParenthesis = new Pattern[lexer.getClosedParenthesis().length];

    for(int i=0;i<lexer.getClosedParenthesis().length;i++)
      closedParenthesis[i] = Pattern.compile(lexer.getClosedParenthesis()[i]);

    blanks = new Pattern[lexer.getBlanks().length];

    for(int i=0;i<lexer.getBlanks().length;i++)
      blanks[i] = Pattern.compile(lexer.getBlanks()[i]);
  }

  public Expr parse(String expr)
    throws SyntaxException
  {
    return parse(getStream(expr));
  }

  public Expr parse(Queue<Token> stream)
    throws SyntaxException
  {
    this.stream = stream;

    return expr();
  }

  Expr term()
  {
    Expr t;

    Token token,lookahead = stream.peek();

    if(lookahead.getType()==Token.Type.UnaryOperator)
    {
      /* <Term> ::= UnaryOperator <Term> ... */
      token = stream.poll();
      t = getExpr(token.getCode(),token.getInfo(),term());
    }
    else if(lookahead.getType()==Token.Type.Operand)
    {
      /* <Term> ::= Operand ... */
      token = stream.poll();
      t = getExpr(token.getCode(),token.getInfo());
    }
    else
    {
      /* <Term> ::= OpenedParenthesis <Expr> ClosedParenthesis ... */
      stream.poll();
      t = expr();
      stream.poll();
    }

    /* <Term> ::= <Term> UnaryOperator ... */
    while(!(stream.isEmpty()) &&
           ((stream.peek()).type==Token.Type.UnaryOperator))
      t = getExpr(stream.peek().getCode(),stream.poll().getInfo(),t,false);

    return t;
  }

  Expr expr()
  {
    /* <Expr> ::= <Term> ... */
    Expr e = term();
    if(!(stream.isEmpty())&&((stream.peek()).type!=Token.Type.ClosedParenthesis))
    {
      /* <Expr> ::= <Term> BinaryOperator <Expr> ... */
      Stack<Expr> stack = new Stack<Expr>();
      Token token=stream.poll();
      e = getExpr(token.getCode(),token.getInfo(),e,term());
      stack.push(e);

      while(!(stream.isEmpty())&&((stream.peek()).type!=Token.Type.ClosedParenthesis))
      {
        /* <Expr> ::= <Term> BinaryOperator <Expr> ... */
        Expr current;

        int binOp1,
            binOp2 = stream.peek().getCode();

        do
        {
          current = stack.pop();
          binOp1 = current.getCode();
        }while(!(stack.isEmpty())&&(precedence.greaterThan(binOp1,binOp2)));

        if(precedence.greaterThan(binOp1,binOp2))
        {
          token = stream.poll();
          e = getExpr(token.getCode(),token.getInfo(),e,term());
          stack.push(e);
        }
        else
        {
          token = stream.poll();
          current.setRight(getExpr(token.getCode(),token.getInfo(),current.getRight(),term()));
          stack.push(current);
          stack.push(current.getRight());
        }
      }
    }

    return e;
  }

  public Queue<Token> getStream(String expr)
    throws SyntaxException
  {
    Queue<Token> stream = new LinkedList<Token>();

    String e = new String(expr);

    String last = "";

    boolean found = false;

    int i = 0;
    int c = 0;
    int k = 0;
    int m = 0;
    int n = expr.length();

    int t = 0;

    int p = 0;
    int h = 0;

    boolean accept = false;
    boolean error = false;

    if(expr.length() > 0)
    do
    {
      expr = expr.substring(i);

      found = false;

      Token token = new Token();

      String info = "";

      for(int j=0;j<blanks.length;j++)
      {
        Pattern pattern = blanks[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          info = matcher.group(g);
          k = matcher.end(g);
          m = j;
        }
      }

      if(found)
      {
        i = k;

        continue;
      }

      for(int j=0;j<binaryOperators.length;j++)
      {
        Pattern pattern = binaryOperators[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          if(matcher.group(g).length() > info.length())
          {
            token.type = Token.Type.BinaryOperator;
            info = matcher.group(g);
            k = matcher.end(g);
            m = j;
          }
        }
      }

      for(int j=0;j<unaryOperators.length;j++)
      {
        Pattern pattern = unaryOperators[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          if(matcher.group(g).length() > info.length())
          {
            token.type = Token.Type.UnaryOperator;
            info = matcher.group(g);
            k = matcher.end(g);
            m = j;
          }
        }
      }

      for(int j=0;j<operands.length;j++)
      {
        Pattern pattern = operands[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          if(matcher.group(g).length() > info.length())
          {
            token.type = Token.Type.Operand;
            info = matcher.group(g);
            k = matcher.end(g);
            m = j;
          }
        }
      }

      for(int j=0;j<openedParenthesis.length;j++)
      {
        Pattern pattern = openedParenthesis[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          if(matcher.group(g).length() > info.length())
          {
            token.type = Token.Type.OpenedParenthesis;
            info = matcher.group(g);
            k = matcher.end(g);
            m = j;
          }
        }
      }

      for(int j=0;j<closedParenthesis.length;j++)
      {
        Pattern pattern = closedParenthesis[j];

        Matcher matcher = pattern.matcher(expr);

        if(matcher.lookingAt())
        {
          found = true;

          int g = matcher.groupCount()==0?0:1;

          if(matcher.group(g).length() > info.length())
          {
            token.type = Token.Type.ClosedParenthesis;
            info = matcher.group(g);
            k = matcher.end(g);
            m = j;
          }
        }
      }

      if(found)
      {
        i = k;

        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;
        }

        c += i;

        t++;

        if(!accept)
          switch(token.type)
          {
            case BinaryOperator:
              throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidBinaryOperator,t,c);
            case UnaryOperator:
              if(!operators.isPrefix(token.code))
                throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidUnaryOperator,t,c);
              break;
            case Operand:
              accept = true;
              break;
            case OpenedParenthesis:
              p++;
              break;
            case ClosedParenthesis:
              throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidClosedParenthesis,t,c);
          }
        else
          switch(token.type)
          {
            case BinaryOperator:
              accept = false;
              break;
            case UnaryOperator:
              if(!operators.isPostfix(token.code))
                throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidUnaryOperator,t,c);
              break;
            case Operand:
              throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidOperand,t,c);
            case OpenedParenthesis:
              throw new SyntaxException(e,expr,info,SyntaxException.Type.InvalidOpenedParenthesis,t,c);
            case ClosedParenthesis:
              p--;
              break;
          }

        last = info;

        stream.add(lexer.getToken(token));
      }
      else
      {
        throw new SyntaxException(e,expr,info,SyntaxException.Type.UnknownToken,t,c);
      }
    }
    while(found && (i>=0) && (i<expr.length()));

    if(p>0)
      throw new SyntaxException(e,expr,last,SyntaxException.Type.ClosedParenthesisExpected,t,c);
    else if(p<0)
      throw new SyntaxException(e,expr,last,SyntaxException.Type.OpenedParenthesisExpected,t,c);

    return stream;
  }

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

  public Expr getExpr(int code,String info,Expr left)
  {
    return factory.getExpr(code,info,left);
  }

  public Expr getExpr(int code,String info,Expr left,boolean prefix)
  {
    return factory.getExpr(code,info,left,prefix);
  }

  public Expr getExpr(int code,String info,Expr left,Expr right)
  {
    return factory.getExpr(code,info,left,right);
  }

  public Operators getOperators()
  {
    return operators;
  }

  public Lexer getLexer()
  {
    return lexer;
  }

  public Precedence getPrecedence()
  {
    return precedence;
  }
}

/* end of file */