From e043ee06a51a8d8c68f8cb0984d4f7bd8915bea8 Mon Sep 17 00:00:00 2001 From: Carlo Zancanaro Date: Tue, 29 May 2012 22:42:25 +1000 Subject: First attempt a range parser - likely not correct. --- impl/EquationSystem.g | 10 +++-- impl/main.cpp | 106 ++++++++++++++++++++++++++++++++++++------------ impl/systems/range-test | 1 + impl/systems/size-ten | 6 +-- 4 files changed, 89 insertions(+), 34 deletions(-) create mode 100644 impl/systems/range-test diff --git a/impl/EquationSystem.g b/impl/EquationSystem.g index 3a6598a..6b721bb 100644 --- a/impl/EquationSystem.g +++ b/impl/EquationSystem.g @@ -11,6 +11,7 @@ tokens { SUB = '-' ; MULT = '*' ; COMMA = ';' ; + RANGE = 'range' ; GUARD = 'guard' ; GREATER_EQUAL = '>=' ; QUESTION_MARK = '?' ; @@ -26,14 +27,15 @@ maxExpr : MAXIMUM^ '('! minExpr ( ','! minExpr )* ')'! | minExpr ; minExpr : MINIMUM^ '('! maxExpr ( ','! maxExpr )* ')'! | expr ; expr : '(' expr GREATER_EQUAL expr QUESTION_MARK expr ')' -> ^(GUARD expr expr expr) - | term ( (PLUS | MULT | SUB | COMMA)^ expr )* ; + | term ( (PLUS | MULT | COMMA)^ expr )* ; -term : NUMBER +term : '[' NUMBER ',' NUMBER ']' -> ^( RANGE NUMBER NUMBER ) | VARIABLE - | '('! expr ')'! ; + | '('! expr ')'! + | SUB^ term ; -NUMBER : (DIGIT)+ ; +NUMBER : (SUB) (DIGIT)+ | (DIGIT)+ ; VARIABLE: (LETTER) (LETTER | DIGIT)* ; WHITESPACE : ( '\t' | ' ' | '\u000C' )+ { diff --git a/impl/main.cpp b/impl/main.cpp index 530556f..21be64b 100644 --- a/impl/main.cpp +++ b/impl/main.cpp @@ -19,53 +19,96 @@ extern "C" { using namespace std; template -Expression* treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& system) { +std::pair*, Expression*> treeToExpression(pANTLR3_BASE_TREE node, EquationSystem& system, bool negative=false) { ANTLR3_UINT32 num = node->getChildCount(node); string name = (char*) node->getText(node)->chars; - // leaf node - constant or variable + // leaf node - variable if (num == 0) { - if (name == "inf") { - return system.newExpression(new Constant(infinity())); - } else { - stringstream stream(name); - T output; - if (stream >> output) { - return system.newExpression(new Constant(output)); - } else { - return system.newExpression(system.newVariable(name)); - } + return std::pair*, Expression*>( + system.newExpression(system.newVariable(name + "_l")), + system.newExpression(system.newVariable(name + "_u"))); + } + + // a range itself + if (name == "RANGE") { + pANTLR3_BASE_TREE childNode; + string childName; + T firstValue, secondValue; + + childNode = (pANTLR3_BASE_TREE) node->getChild(node, 0); + childName = (char*) childNode->getText(childNode)->chars; + stringstream firstStream(childName); + if (!(firstStream >> firstValue)) { + throw "Invalid number."; + } + if (negative) firstValue = -firstValue; + + childNode = (pANTLR3_BASE_TREE) node->getChild(node, 1); + childName = (char*) childNode->getText(childNode)->chars; + stringstream secondStream(childName); + if (!(secondStream >> secondValue)) { + throw "Invalid number."; } + if (negative) secondValue = -secondValue; + + return std::pair*, Expression*>( + system.newExpression(new Constant(firstValue)), + system.newExpression(new Constant(secondValue))); } - // other operators - std::vector*> args; + if (name == "-") { + negative = true; + } + + // subexpressions + std::vector*> firstArgs; + std::vector*> secondArgs; pANTLR3_BASE_TREE childNode; for (unsigned int i = 0; i < num; ++i) { childNode = (pANTLR3_BASE_TREE) node->getChild(node, i); - args.push_back(treeToExpression(childNode, system)); + std::pair*, Expression*> expr = treeToExpression(childNode, system, negative); + firstArgs.push_back(expr.first); + secondArgs.push_back(expr.second); + } + + // other operators + if (name == "-") { + //if (firstArgs.size() == 1) { // secondArgs.size() == firstArgs.size() + return std::pair*, Expression*>( + secondArgs[0], + firstArgs[0]); } if (name == "max") { - return system.newMaxExpression(args); + return std::pair*, Expression*>( + system.newMaxExpression(firstArgs), + system.newMaxExpression(secondArgs)); } else { - Operator* op = NULL; + // we need two because expressions delete their operator + // bit of a silly design by me + Operator* firstOp = NULL; + Operator* secondOp = NULL; if (name == "min") { - op = new Minimum(); + firstOp = new Minimum(); + secondOp = new Minimum(); } else if (name == "+") { - op = new Addition(); - } else if (name == "-") { - op = new Subtraction(); + firstOp = new Addition(); + secondOp = new Addition(); } else if (name == ";") { - op = new Comma(); + firstOp = new Comma(); + secondOp = new Comma(); } else if (name == "GUARD") { - op = new Guard(); + firstOp = new Guard(); + secondOp = new Guard(); } else { std::cerr << "Unknown leaf node type: " << name << std::endl; throw "Unknown leaf node type"; } - return system.newExpression(op, args); + return std::pair*, Expression*>( + system.newExpression(firstOp, firstArgs), + system.newExpression(secondOp, secondArgs)); } } @@ -82,12 +125,21 @@ void treeToSystem(pANTLR3_BASE_TREE node, EquationSystem& system) { varNode = (pANTLR3_BASE_TREE) node->getChild(node, i); exprNode = (pANTLR3_BASE_TREE) node->getChild(node, i+1); + Variable* var; + vector*> args; + string varName = (char*) varNode->getText(varNode)->chars; - Variable* var = system.newVariable(varName); + std::pair*, Expression*> exprs = treeToExpression(exprNode, system); - vector*> args; + var = system.newVariable(varName + "_l"); + args.push_back(system.newExpression(new Constant(-infinity()))); + args.push_back(exprs.first); + system[*var] = system.newMaxExpression(args); + + args.clear(); + var = system.newVariable(varName + "_u"); args.push_back(system.newExpression(new Constant(-infinity()))); - args.push_back(treeToExpression(exprNode, system)); + args.push_back(exprs.second); system[*var] = system.newMaxExpression(args); } } diff --git a/impl/systems/range-test b/impl/systems/range-test new file mode 100644 index 0000000..c2ac047 --- /dev/null +++ b/impl/systems/range-test @@ -0,0 +1 @@ +x = max([0, 1], -x + [-1, 1]) diff --git a/impl/systems/size-ten b/impl/systems/size-ten index 71ee74a..9ef3135 100644 --- a/impl/systems/size-ten +++ b/impl/systems/size-ten @@ -1,3 +1,3 @@ -x1 = max(0, min(x1-1, x2)) -x2 = max(0, 5+x1, x1) -x3 = max(0, 1+x3, 0+x1) +x1 = max([0,0], min(x1-[1,1], x2)) +x2 = max([0,0], [5,5]+x1, x1) +x3 = max([0,0], [1,1]+x3, [0,0]+x1) -- cgit v1.2.3