Makefile100644 1040 1001 3566 6746504742 10741 0ustar everyone CC = cl LD = link DEBUG = -Zi # Compile try/except EXCEPT = -EHsc CFLAGS = $(EXCEPT) -DWIN32 -Tp OBJ = obj EXE = .exe INCLUDE = -I "e:\antlr\cpp" -I "d:\Program Files\Microsoft Visual Studio\Vc98\Include" LD_DEBUG = /debug ANTLR_LIB = /defaultlib:"e:\antlr\cpp\antlr.lib" LINK_FLAGS = $(LD_DEBUG) $(ANTLR_LIB) FLAGS = $(INCLUDE) $(DEBUG) $(CFLAGS) # # To customize, fill in EXENAME, GRAMMAR, PARSER and LEXER # EXENAME = expr GRAMMAR = expr PARSER = MyExpr LEXER = MyExpr TREE_PRINT = print_tree.$(OBJ) PARSE_SUPPORT = trees.$(OBJ) tree_fact.$(OBJ) globals.$(OBJ) PARSE_OBJ = $(LEXER)Lexer.$(OBJ) $(PARSER)Parser.$(OBJ) main.$(OBJ) all: $(EXENAME)$(EXE) clean: rm -f $(PARSE_OBJ) $(EXENAME)$(EXE) $(LEXER)Lexer.cpp $(LEXER)Lexer.hpp $(PARSER)Parser.cpp $(PARSER)Parser.hpp MyTinyCParserTokenTypes.hpp MyTinyCParserTokenTypes.txt MyTinyCTokenTypes.hpp MyTinyCTokenTypes.txt $(PARSE_SUPPORT) $(TREE_PRINT) $(EXENAME)$(EXE): $(PARSE_OBJ) $(PARSE_SUPPORT) $(TREE_PRINT) $(LD) $(LINK_FLAGS) /out:$@ $(PARSE_OBJ) $(PARSE_SUPPORT) $(TREE_PRINT) $(LEXER)Lexer.cpp $(LEXER)Lexer.hpp $(PARSER)Parser.cpp $(PARSER)Parser.hpp: $(GRAMMAR).g jview antlr.Tool $(GRAMMAR).g $(LEXER)Lexer.$(OBJ): $(LEXER)Lexer.cpp $(LEXER)Lexer.hpp $(CC) -c $(FLAGS) $(LEXER)Lexer.cpp $(PARSER)Parser.$(OBJ): $(PARSER)Parser.cpp $(PARSER)Parser.hpp node_tokens.hpp $(CC) -c $(FLAGS) $(PARSER)Parser.cpp trees.$(OBJ): trees.cpp trees.hpp node_tokens.hpp $(CC) -c $(FLAGS) trees.cpp tree_fact.$(OBJ): tree_fact.cpp tree_fact.hpp trees.hpp $(CC) -c $(FLAGS) tree_fact.cpp globals.$(OBJ): globals.cpp trees.hpp $(CC) -c $(FLAGS) globals.cpp print_tree.$(OBJ): print_tree.cpp print_tree.hpp $(CC) -c $(FLAGS) print_tree.cpp main.$(OBJ): main.cpp $(PARSER)Parser.hpp $(LEXER)Lexer.hpp $(CC) -c $(FLAGS) main.cpp expr.g100644 1040 1001 7624 6746716040 10422 0ustar everyone // // An experimental expression grammer by // Ian Kaplan // header { // include files #include #include #include #include #include "basic_types.hpp" #include "node_tokens.hpp" #include "trees.hpp" #include "tree_fact.hpp" } options { language="Cpp"; } class MyExprParser extends Parser; options { k = 2; exportVocab=MyExpr; } exprlist returns [pNode expr_list] { pNode asign; expr_list = factory.make_node( n_expr_list ); } : ( asign = assignment_statement { factory.add_child( expr_list, asign ); } )* EOF ; assignment_statement returns [pNode asgn_stmt] { pNode a = NULL; } : a = assignment SEMICOLON { asgn_stmt = a; } ; assignment returns [pNode asgn] { pNode e1 = NULL; pNode e2 = NULL; pNode id = NULL; } : e1 = expr { asgn = e1; } | id = identifier ASSIGN e2 = expr { asgn = factory.build_binary( n_assign, id, e2 ); } ; primary_expr returns [pNode prime_expr] { pNode c1 = NULL; pNode e1 = NULL; pNode id = NULL; } : id = identifier { prime_expr = id; } | c1 = constant { prime_expr = c1; } | (LPAREN e1 = expr RPAREN ) { prime_expr = e1; } ; identifier returns [pNode rslt_id] : id:IDENT { std::string str; const char *cstr; str = id->getText(); cstr = str.c_str(); rslt_id = factory.make_id_node( cstr ); } ; sign_expr returns [pNode s_expr] { pNode b1 = NULL; pNode b2 = NULL; pNode minus_op = NULL; } : b1 = primary_expr { s_expr = b1; } | (MINUS { minus_op = factory.build_unary( n_uminus, minus_op ); } )+ b2 = primary_expr { s_expr = factory.add_child( minus_op, b2 ); } ; mul_expr returns [pNode m_expr] { pNode s1 = NULL; pNode s2 = NULL; pNode op = NULL; } : s1 = sign_expr { m_expr = s1; } (op = mulop s2 = sign_expr { m_expr = factory.build_binary( op, m_expr, s2 ); } )* ; mulop returns [pNode mul_node] : TIMES { mul_node = factory.make_node( n_times ); } | DIVIDE { mul_node = factory.make_node( n_divide ); } | MOD { mul_node = factory.make_node( n_mod ); } ; expr returns [pNode a_expr] { pNode m1 = NULL; pNode m2 = NULL; pNode op = NULL; } : m1 = mul_expr { a_expr = m1; } ( op = addop m2 = mul_expr { a_expr = factory.build_binary( op, a_expr, m2 ); } )* ; addop returns [pNode add_node] : PLUS { add_node = factory.make_node( n_plus ); } | MINUS { add_node = factory.make_node( n_minus ); } ; constant returns [pNode const_node] : icon:ICON { std::string str; const char *cstr; str = icon->getText(); cstr = str.c_str(); assert( cstr != NULL ); const val = atoi( cstr ); const_node = factory.make_const_node( val ); } ; class MyExprLexer extends Lexer; options { k = 2; exportVocab=MyExpr; } WS_ : (' ' | '\t' | '\n' | '\r') { _ttype = Token::SKIP; } ; IDENT options { paraphrase = "identifier"; } : ('a'..'z' | 'A'..'Z' | '_' ) ( ('a'..'z' | 'A'..'Z' | '_') | ('0'..'9' ))* ; ICON options { paraphrase = "integer constant"; } : '0'..'9' ('0'..'9')* ; SEMICOLON options { paraphrase = ";"; } : ';' ; LPAREN options { paraphrase = "("; } : '(' ; RPAREN options { paraphrase = ")"; } : ')' ; PLUS options { paraphrase = "+"; } : '+' ; MINUS options { paraphrase = "-"; } : '-' ; TIMES options { paraphrase = "*"; } : '*' ; DIVIDE options { paraphrase = "/"; } : '/' ; MOD options { paraphrase = "%"; } : '%' ; ASSIGN options { paraphrase = "="; } : '=' ; globals.cpp100644 1040 1001 257 6746716257 11410 0ustar everyone #include #include #include "basic_types.hpp" #include "node_tokens.hpp" #include "trees.hpp" #include "tree_fact.hpp" tree_factory factory; main.cpp100644 1040 1001 1735 6746717552 10732 0ustar everyone #include #include #include #include #include "MyExprLexer.hpp" #include "MyExprParser.hpp" #include "basic_types.hpp" #include "trees.hpp" #include "print_tree.hpp" using namespace std; void usage( char *progname ) { printf("usage: %s \n", progname ); } int main(int argc, char *argv[] ) { if (argc == 2) { const char *filename; filename = argv[1]; ifstream str( filename ); if (str.is_open()) { try { pNode top; MyExprLexer lexer( str ); MyExprParser parser(lexer); top = parser.exprlist(); if (top != NULL) { print_tree pr; pr.pr_tree( top ); } else { printf("top is NULL\n"); } } catch(std::exception& e) { std::cerr << "exception: " << e.what() << std::endl; } } else { printf("%s: could not open file %s\n", argv[0], filename ); } } else { usage( argv[0] ); } return 0; } print_tree.cpp100644 1040 1001 4562 6746716552 12161 0ustar everyone #include #include #include "basic_types.hpp" #include "node_tokens.hpp" #include "trees.hpp" #include "print_tree.hpp" /* * pr_node * Print the character string associated with an ANTLR tree node. */ void print_tree::pr_node( pNode node ) { const char *str; str = node->get_name(); printf("%s", str ); if (node->get_node_kind() == non_terminal) { printf(" "); } else { printf("["); if (node->get_node_kind() == id_node) { printf("%s", node->get_id_name() ); } else if (node->get_node_kind() == const_node) { printf("%d", node->get_const_val() ); } printf("] "); } } // pr_node /* * pr_indent * Print indentation for a node. */ void print_tree::pr_indent(void) { const size_t BUFSIZE = 127; char buf[ BUFSIZE+1 ]; int i; for (i = 0; i < indent_level && i < BUFSIZE; i++) { buf[i] = ' '; } buf[i] = '\0'; printf("%s", buf ); } // pr_indent void print_tree::pr_open_angle(void) { if ( indent_level ) printf("\n"); pr_indent(); printf("<"); indent_level += INDENT; } // pr_open_angle /* * pr_close_angle * Print the ">" bracket to show the close of a tree production. */ void print_tree::pr_close_angle(Boolean first) { assert( indent_level > 0 ); indent_level -= INDENT; if (!first) { printf("\n"); pr_indent(); } printf("> "); } // pr_close_angle /* * pr_leaves * Print the leaves of an AST node */ void print_tree::pr_leaves( pNode top ) { pNode t; For_each_kid(t, top) { if (is_nonleaf( t )) pr_top( t ); else pr_node( t ); } } // pr_leaves /* * pr_top * Recursively print a tree (or a sub-tree) from the top down. */ void print_tree::pr_top( pNode top ) { pNode tmp; Boolean first = TRUE; pr_open_angle(); pr_node( top ); if (is_nonleaf( top )) { For_each_kid( tmp, top ) { if (is_nonleaf( tmp )) first = FALSE; } pr_leaves( top ); } pr_close_angle( first ); } // pr_top /* * pr_tree * Main entry point for tree print. */ void print_tree::pr_tree( pNode top ) { pNode t; for (t = top; t != NULL; t = t->get_sib()) { indent_level = 0; pr_top( t ); printf("\n"); } } // pr_tree tree_fact.cpp100644 1040 1001 7621 6746716452 11740 0ustar everyone #include #include #include #include "basic_types.hpp" #include "node_tokens.hpp" #include "trees.hpp" #include "tree_fact.hpp" node *tree_factory::make_node( node_token tok ) { node *top; top = new node( tok ); return top; } node *tree_factory::make_id_node( const char *str ) { node *top; int len; char *new_str; assert( str != NULL ); len = strlen( str ); new_str = new char[ len + 1 ]; strcpy( new_str, str ); top = new ident_node( new_str ); return top; } node *tree_factory::make_const_node( const int val) { node *top; top = new constant_node( val ); return top; } // // node creation rules with a node_token first argument // node *tree_factory::build_unary( node_token tok, node *child1 ) { node *top = make_node( tok ); top->set_kid( child1 ); return top; } // build_unary node *tree_factory::build_binary( node_token tok, node *child1, node *child2 ) { node *top = build_unary( tok, child1 ); top->set_second_kid( child2 ); return top; } // build_binary node *tree_factory::build_ternary( node_token tok, node *child1, node *child2, node *child3 ) { node *top = build_binary( tok, child1, child2 ); top->set_third_kid( child3 ); return top; } // build_ternary node *tree_factory::build_quadnary( node_token tok, node *child1, node *child2, node *child3, node *child4 ) { node *top = build_ternary( tok, child1, child2, child3 ); top->set_fourth_kid( child4 ); return top; } // build_quadnary node *tree_factory::build_pentnary( node_token tok, node *child1, node *child2, node *child3, node *child4, node *child5 ) { node *top = build_quadnary( tok, child1, child2, child3, child4 ); top->set_fifth_kid( child5 ); return top; } // build_pentnary // // node creation rules with a const node * first argument // node *tree_factory::build_unary( node *top, node *child1 ) { assert( top != NULL ); top->set_kid( child1 ); return top; } // build_unary node *tree_factory::build_binary( node *top, node *child1, node *child2 ) { assert( top != NULL ); build_unary( top, child1 ); top->set_second_kid( child2 ); return top; } // build_binary node *tree_factory::build_ternary( node *top, node *child1, node *child2, node *child3 ) { assert( top != NULL ); build_binary( top, child1, child2 ); top->set_third_kid( child3 ); return top; } // build_ternary node *tree_factory::build_quadnary( node *top, node *child1, node *child2, node *child3, node *child4 ) { assert( top != NULL ); build_ternary( top, child1, child2, child3 ); top->set_fourth_kid( child4 ); return top; } // build_quadnary node *tree_factory::build_pentnary( node *top, node *child1, node *child2, node *child3, node *child4, node *child5 ) { assert( top != NULL ); build_quadnary( top, child1, child2, child3, child4 ); top->set_fifth_kid( child5 ); return top; } // build_pentnary node *tree_factory::build_unary( node *top, node_token tok ) { assert( top != NULL ); // don't want to clobber an existing subtree assert( top->get_kid() == NULL ); node *child = make_node( tok ); top->set_kid( child); return top; } // build_unary node *tree_factory::add_child( node *top, node *child ) { assert( top != NULL ); if (top->get_kid() == NULL) { top->set_kid( child ); } else { node *t = top->get_kid(); // traverse the sibling list while (t->get_sib() != NULL) t = t->get_sib(); t->set_sib( child ); } return top; } // add_child trees.cpp100644 1040 1001 1453 6746716127 11122 0ustar everyone #include #include #include "basic_types.hpp" #include "node_tokens.hpp" #include "trees.hpp" const char *node::get_name() { const char *name = "bad name"; const node_token token = get_token(); switch(token) { case n_id: name = "n_id"; break; case n_assign: name = "n_assign"; break; case n_uminus: name = "n_uminus"; break; case n_times: name = "n_times"; break; case n_divide: name = "n_divide"; break; case n_mod: name = "n_mod"; break; case n_plus: name = "n_plus"; break; case n_minus: name = "n_minus"; break; case n_icon: name = "n_icon"; break; case n_expr_list: name = "n_expr_list"; break; } // switch return name; } basic_types.hpp100644 1040 1001 561 6745230327 12261 0ustar everyone #ifndef _BASIC_TYPES_HPP_ #define _BASIC_TYPES_HPP_ typedef enum { #ifndef FALSE FALSE = 0, #endif #ifndef TRUE TRUE = 1, #endif BOGUS} BoolVals; typedef unsigned short int ushort; typedef unsigned int uint; typedef unsigned char uchar; typedef char * pChar; typedef uint Boolean; #endif node_tokens.hpp100644 1040 1001 615 6746673715 12301 0ustar everyone #ifndef _NODE_TOKENS_HPP_ #define _NODE_TOKENS_HPP_ typedef enum { n_bad_node, n_null, // an empty child in the syntax tree n_id, n_assign, n_uminus, n_times, n_divide, n_mod, n_plus, n_minus, n_icon, // integer constant n_expr_list, last_token } node_token; #endif print_tree.hpp100644 1040 1001 1377 6746677733 12176 0ustar everyone #ifndef _PRINT_TREE_HPP_ #define _PRINT_TREE_HPP_ /* print_tree Print an ANTLR abstract syntax tree in operator prefix form. */ #define For_each_kid(t,top) for(t=( (top && is_nonleaf(top)) ? top->get_kid() : (pNode)NULL ); t; t = t->get_sib() ) class print_tree { private: typedef enum { INDENT = 2 } bogus; int indent_level; private: void pr_node( pNode node ); void pr_indent(); void pr_top( pNode top ); void pr_open_angle(void); void pr_close_angle(Boolean first); void pr_leaves( pNode top ); Boolean is_nonleaf( pNode node ) { Boolean rslt; rslt = (Boolean)(node->get_kid() != NULL); return rslt; } public: void pr_tree( const pNode top ); }; // print_tree #endif tree_fact.hpp100644 1040 1001 3062 6746715364 11741 0ustar everyone #ifndef _TREE_FACT_HPP_ #define _TREE_FACT_HPP_ /* * tree_factory * Allocate tree nodes and shaped trees. */ class tree_factory { public: tree_factory() {} // // node creation rules with a node_token first argument // node *make_node( node_token tok ); node *make_id_node( const char *str ); node *make_const_node( const int val ); node *build_unary( node_token tok, node *child1 ); node *build_binary( node_token tok, node *child1, node *child2 ); node *build_ternary( node_token tok, node *child1, node *child2, node *child3 ); node *build_quadnary( node_token tok, node *child1, node *child2, node *child3, node *child4 ); node *build_pentnary( node_token tok, node *child1, node *child2, node *child3, node *child4, node *child5 ); // // node creation rules with a node * first argument // node *build_unary( node *top, node *child1 ); node *build_binary( node *top, node *child1, node *child2 ); node *build_ternary( node *top, node *child1, node *child2, node *child3 ); node *build_quadnary( node *top, node *child1, node *child2, node *child3, node *child4 ); node *build_pentnary( node *top, node *child1, node *child2, node *child3, node *child4, node *child5 ); node *build_unary( node *top, node_token tok ); node *add_child( node *top, node *child ); }; extern tree_factory factory; #endif trees.hpp100644 1040 1001 12541 6746713374 11150 0ustar everyone #ifndef _TREES_HPP_ #define _TREES_HPP_ /* This file contains the class definitions for the compiler intermediate abstract syntax trees (commonly referred to as an AST). */ /* * class node * Base class for the AST node type, which is the building block for the compiler intermediate representation (IR) trees. All other AST node types are derived from this type (e.g., Type and Symbol nodes). A number of compiler writers have used trees like this. These include the developers of lcc and ANTLR. I first saw this kind of tree in Peter Donovan's ANSI C compiler. This kind of tree has proven to be fast and easy to manage, but they take some getting used to. The "kid" pointer points to the first child of the current node. The "sib" pointer points to the next "sibling" child. For example, in the tree shown below, the kid pointer would point to "A". Since "+" has no siblings in the tree shown, the "sib" node of "+" would be NULL. The sibling node of "A" would point to "B". + / \ / \ A B + / \ / kid NULL \ A / sib / \ B NULL A call like "foo( a, b + c, d, e)" would have the structure shown below (here the right pointer is the "kid" pointer and the left pointer is the "sib" pointer). foo / \ NULL a / \ + / \ d b / / e c This scheme for representing trees has several advantages: children can be easily added by simply inserting them into the sibling list; trees with more than two children can be easily represented and a field that reflects the number of children is not required. */ typedef enum { bad_node_kind, non_terminal, id_node, const_node, last_node } NODE_KIND; class node { private: node *kid; node *sib; node_token token; public: node(void) { kid = NULL; sib = NULL; token = n_bad_node; } node( const node_token n ) : token( n ) { kid = NULL; sib = NULL; } void set_token( const node_token n ) { token = n; } const node_token get_token(void) { return token; } void set_kid( const node *k ) { kid = (node *)k; } node *get_kid(void) { return kid; } void set_sib( const node *s ) { sib = (node *)s; }; node *get_sib(void) { return sib; } /* tree "macros" */ Boolean is_leaf(void) { return kid == NULL; } Boolean is_nonleaf(void) { return kid != NULL; } node *get_second_kid(void) { node *child; child = get_kid(); if (child != NULL) { child = child->get_sib(); } return child; } // get_second_kid node *get_third_kid(void) { node *child; child = get_second_kid(); if (child != NULL) { child = child->get_sib(); } return child; } // get_third_kid node *get_fourth_kid(void) { node *child; child = get_third_kid(); if (child != NULL) { child = child->get_sib(); } return child; } // get_fourth_kid node *get_fifth_kid(void) { node *child; child = get_fourth_kid(); if (child != NULL) { child = child->get_sib(); } return child; } // get_fifth_kid node *set_second_kid(node *new_kid ) { node *child; child = get_kid(); if (child != NULL) { child->set_sib( new_kid ); child = new_kid; } return child; } // set_second_kid node *set_third_kid(node *new_kid ) { node *child; child = get_second_kid(); if (child != NULL) { child->set_sib( new_kid ); child = new_kid; } return child; } // set_second_kid node *set_fourth_kid(node *new_kid ) { node *child; child = get_third_kid(); if (child != NULL) { child->set_sib( new_kid ); child = new_kid; } return child; } // set_second_kid node *set_fifth_kid(node *new_kid ) { node *child; child = get_fourth_kid(); if (child != NULL) { child->set_sib( new_kid ); child = new_kid; } return child; } // set_second_kid const char *get_name(void); virtual NODE_KIND get_node_kind(void) { return non_terminal; } virtual const char *get_id_name() { assert( FALSE ); return NULL; } virtual const int get_const_val() { assert( FALSE ); return 0; } }; // node class ident_node : public node { private: const char *id_name; public: ident_node(const char *str) : id_name(str), node( n_id ) { }; NODE_KIND get_node_kind(void) { return id_node; } const char *get_id_name() { return id_name; } }; // ident_node class constant_node : public node { private: const int const_val; public: constant_node(const int val) : const_val(val), node( n_icon ) { } NODE_KIND get_node_kind(void) { return const_node; } const int get_const_val(void) { return const_val; } }; // constant_node typedef node *pNode; #endif