summaryrefslogtreecommitdiff
path: root/lib
diff options
context:
space:
mode:
Diffstat (limited to 'lib')
-rw-r--r--lib/parserel/CMakeLists.txt18
-rw-r--r--lib/parserel/include/parseRel.hh29
-rw-r--r--lib/parserel/src/parseRel.cc120
-rw-r--r--lib/parserel/src/parseRel.ll24
-rw-r--r--lib/parserel/src/parseRel.yy85
5 files changed, 276 insertions, 0 deletions
diff --git a/lib/parserel/CMakeLists.txt b/lib/parserel/CMakeLists.txt
new file mode 100644
index 0000000..adc1d88
--- /dev/null
+++ b/lib/parserel/CMakeLists.txt
@@ -0,0 +1,18 @@
+find_package(BISON)
+find_package(FLEX)
+
+FLEX_TARGET(ExprScanner src/parseRel.ll ${CMAKE_CURRENT_BINARY_DIR}/parseRel.yy.cc COMPILE_FLAGS
+ "--header-file=${CMAKE_CURRENT_BINARY_DIR}/parseRel.ll.hh") # Hack to avoid generating header in root
+BISON_TARGET(ExprParser src/parseRel.yy ${CMAKE_CURRENT_BINARY_DIR}/parseRel.tab.cc COMPILE_FLAGS "-t -d")
+ADD_FLEX_BISON_DEPENDENCY(ExprScanner ExprParser)
+
+include_directories(
+ include
+ ${CMAKE_CURRENT_BINARY_DIR}
+ )
+
+add_library(parseRel
+ src/parseRel.cc
+ ${FLEX_ExprScanner_OUTPUTS}
+ ${BISON_ExprParser_OUTPUTS}
+ )
diff --git a/lib/parserel/include/parseRel.hh b/lib/parserel/include/parseRel.hh
new file mode 100644
index 0000000..8df5871
--- /dev/null
+++ b/lib/parserel/include/parseRel.hh
@@ -0,0 +1,29 @@
+#ifndef CHILL_RUN_UTIL_HH
+#define CHILL_RUN_UTIL_HH
+
+#include <vector>
+#include <map>
+#include <string>
+
+typedef std::map<std::string, int> simap_t;
+typedef std::vector<std::map<std::string, int> > simap_vec_t;
+
+// in chill_run_util.cc
+simap_vec_t* make_prog(simap_vec_t* cond);
+simap_vec_t* make_cond_gt(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_lt(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_ge(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_le(simap_t* lhs, simap_t* rhs);
+simap_vec_t* make_cond_eq(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_add(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_sub(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_mul(simap_t* lhs, simap_t* rhs);
+simap_t* make_cond_item_neg(simap_t* expr);
+simap_t* make_cond_item_number(int n);
+simap_t* make_cond_item_variable(const char* var);
+simap_t* make_cond_item_level(int n);
+
+// in parse_expr.yy
+simap_vec_t* parse_relation_vector(const char* expr);
+
+#endif
diff --git a/lib/parserel/src/parseRel.cc b/lib/parserel/src/parseRel.cc
new file mode 100644
index 0000000..43d7494
--- /dev/null
+++ b/lib/parserel/src/parseRel.cc
@@ -0,0 +1,120 @@
+#include <stdio.h>
+#include <string.h>
+#include "parseRel.hh"
+
+static std::string to_string(int ival) {
+ char buffer[4];
+ sprintf(buffer, "%d", ival);
+ return std::string(buffer);
+}
+
+simap_vec_t* make_prog(simap_vec_t* cond) {
+ return cond;
+}
+
+simap_vec_t* make_cond_gt(simap_t* lhs, simap_t* rhs) {
+ simap_vec_t* nvec = new simap_vec_t();
+ for(simap_t::iterator it = rhs->begin(); it != rhs->end(); it++)
+ (*lhs)[it->first] -= it->second;
+ (*lhs)[to_string(0)] -= 1;
+ nvec->push_back(*lhs);
+ delete rhs;
+ delete lhs;
+ return nvec;
+}
+
+simap_vec_t* make_cond_lt(simap_t* lhs, simap_t* rhs) {
+ return make_cond_gt(rhs, lhs);
+}
+
+simap_vec_t* make_cond_ge(simap_t* lhs, simap_t* rhs) {
+ simap_vec_t* nvec = new simap_vec_t();
+ for(simap_t::iterator it = rhs->begin(); it != rhs->end(); it++)
+ (*lhs)[it->first] -= it->second;
+ nvec->push_back(*lhs);
+ delete rhs;
+ delete lhs;
+ return nvec;
+}
+
+simap_vec_t* make_cond_le(simap_t* lhs, simap_t* rhs) {
+ return make_cond_ge(rhs, lhs);
+}
+
+simap_vec_t* make_cond_eq(simap_t* lhs, simap_t* rhs) {
+ simap_vec_t* nvec = new simap_vec_t();
+ for(simap_t::iterator it = lhs->begin(); it != lhs->end(); it++)
+ (*rhs)[it->first] -= it->second;
+ nvec->push_back(*rhs);
+ for(simap_t::iterator it = rhs->begin(); it != rhs->end(); it++)
+ it->second = -it->second;
+ nvec->push_back(*rhs);
+ delete rhs;
+ delete lhs;
+ return nvec;
+}
+
+simap_t* make_cond_item_add(simap_t* lhs, simap_t* rhs) {
+ for(simap_t::iterator it = lhs->begin(); it != lhs->end(); it++)
+ (*rhs)[it->first] += it->second;
+ delete lhs;
+ return rhs;
+}
+
+simap_t* make_cond_item_sub(simap_t* lhs, simap_t* rhs) {
+ for(simap_t::iterator it = lhs->begin(); it != lhs->end(); it++)
+ (*rhs)[it->first] -= it->second;
+ delete lhs;
+ return rhs;
+}
+
+simap_t* make_cond_item_mul(simap_t* lhs, simap_t* rhs) {
+ (*lhs)[to_string(0)] += 0;
+ (*rhs)[to_string(0)] += 0;
+ if(rhs->size() == 1) {
+ int t = (*rhs)[to_string(0)];
+ for(simap_t::iterator it = lhs->begin(); it != lhs->end(); it++)
+ it->second *= t;
+ delete rhs;
+ return lhs;
+ }
+ else if(rhs->size() == 1) {
+ int t = (*lhs)[to_string(0)];
+ for(simap_t::iterator it = rhs->begin(); it != rhs->end(); it++)
+ it->second *= t;
+ delete lhs;
+ return rhs;
+ }
+ else {
+ fprintf(stderr, "require Presburger formula");
+ delete lhs;
+ delete rhs;
+ // exit(2); <-- this may be a boost feature
+ }
+}
+
+simap_t* make_cond_item_neg(simap_t* expr) {
+ for (simap_t::iterator it = expr->begin(); it != expr->end(); it++) {
+ it->second = -(it->second);
+ }
+ return expr;
+}
+
+simap_t* make_cond_item_number(int n) {
+ simap_t* nmap = new simap_t();
+ (*nmap)[to_string(0)] = n;
+ return nmap;
+}
+
+simap_t* make_cond_item_variable(const char* var) {
+ simap_t* nmap = new simap_t();
+ (*nmap)[std::string(var)] = 1;
+ return nmap;
+}
+
+simap_t* make_cond_item_level(int n) {
+ simap_t* nmap = new simap_t();
+ (*nmap)[to_string(n)] = 1;
+ return nmap;
+}
+
diff --git a/lib/parserel/src/parseRel.ll b/lib/parserel/src/parseRel.ll
new file mode 100644
index 0000000..f0cac81
--- /dev/null
+++ b/lib/parserel/src/parseRel.ll
@@ -0,0 +1,24 @@
+%{
+// some C++ code
+#include "parseRel.hh"
+#include "parseRel.tab.hh"
+%}
+
+%option noyywrap
+
+%%
+[ \t]+ /*ignore*/
+\n /*ignore*/
+L[0-9]+ { yylval.val = atoi(&yytext[1]); return LEVEL; }
+[0-9]+ { yylval.val = atoi(yytext); return NUMBER; }
+\<\= return LE;
+\>\= return GE;
+\=(\=)? return EQ;
+[a-zA-Z_][a-zA-Z_0-9]* {
+ yylval.str_val = new char[yyleng+1];
+ strcpy(yylval.str_val, yytext);
+ return VARIABLE;
+ }
+. return (int)yytext[0];
+%%
+
diff --git a/lib/parserel/src/parseRel.yy b/lib/parserel/src/parseRel.yy
new file mode 100644
index 0000000..98c329f
--- /dev/null
+++ b/lib/parserel/src/parseRel.yy
@@ -0,0 +1,85 @@
+%{
+#include "parseRel.hh"
+#include "parseRel.ll.hh"
+
+extern int yydebug;
+
+void yyerror(const char*);
+int yyparse(simap_vec_t** rel);
+
+static simap_vec_t* return_rel; // used as the return value for yyparse
+
+%}
+
+%union {
+ int val;
+ char* str_val;
+ simap_t* cond_item;
+ simap_vec_t* cond;
+}
+
+%token <val> NUMBER
+%token <val> LEVEL
+%token <str_val> VARIABLE
+
+%left LE GE EQ '<' '>'
+%left '-' '+' '*' '/'
+
+/*the final output from this language should be an Omega Relation object*/
+%type <cond> cond prog
+%type <cond_item> expr add_expr mul_expr neg_expr
+
+%%
+prog : cond { return_rel = make_prog($1); }
+;
+
+cond : expr '>' expr { $$ = make_cond_gt($1, $3); }
+ | expr '<' expr { $$ = make_cond_lt($1, $3); }
+ | expr GE expr { $$ = make_cond_ge($1, $3); }
+ | expr LE expr { $$ = make_cond_le($1, $3); }
+ | expr EQ expr { $$ = make_cond_eq($1, $3); }
+;
+
+expr : add_expr { $$ = $1; }
+;
+
+add_expr : add_expr '+' mul_expr { $$ = make_cond_item_add($1,$3); }
+ | add_expr '-' mul_expr { $$ = make_cond_item_sub($1,$3); }
+ | mul_expr { $$ = $1; }
+;
+
+mul_expr : mul_expr '*' neg_expr { $$ = make_cond_item_mul($1,$3); }
+ | neg_expr { $$ = $1; }
+;
+
+neg_expr : '-' neg_expr { $$ = make_cond_item_neg($2); }
+ | '(' expr ')' { $$ = $2; }
+ | NUMBER { $$ = make_cond_item_number($1); }
+ | LEVEL { $$ = make_cond_item_level($1); }
+ | VARIABLE { $$ = make_cond_item_variable($1); }
+;
+%%
+
+void yyerror(const char* msg) {
+ fprintf(stderr, "Parse error: %s", msg);
+}
+
+simap_vec_t* parse_relation_vector(const char* expr) {
+ yydebug=0;
+ YY_BUFFER_STATE state;
+
+ //if(yylex_init()) {
+ // TODO: error out or something
+ //}
+
+ state = yy_scan_string(expr);
+
+ if(yyparse()) {
+ // TODO: error out or something
+ }
+
+ yy_delete_buffer(state);
+ yylex_destroy();
+ return return_rel;
+}
+
generated by cgit v1.2.3-70-g09d2 (git 2.47.1) at 2025-02-02 02:52:21 +0000