// $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 */
»Home
»FAQ
