/*****************************************************************************/ /* */ /* Projecto de Compiladores ---------------------------------- VSPL */ /* Level 0 */ /* */ /* Bison Parser Specification. */ /* */ /* Salvador Pinto Abreu */ /* */ /*****************************************************************************/ /*****************************************************************************/ /* */ /* Prelude. */ /* */ /*****************************************************************************/ %{ #include #include #include #include #include "types.h" static int guardNo = 0; #define APT(pop, push) \ { \ if (pop) \ printf ("[%s|_Tail] ==> [", pop); \ else \ printf ("_Tail ==> ["); \ printf push; \ printf ("|_Tail].\n"); \ } %} %union { UNION_DEFS(); } /*****************************************************************************/ /* */ /* Terminal declarations. */ /* */ /*****************************************************************************/ %token ID /* An identifier */ %token INT /* The INT reserved word */ %token REAL /* The REAL reserved word */ %token BOOL /* The BOOL reserved word */ %token VOID /* The VOID reserved word */ %token MAP /* The MAP reserved word */ %token CLASS /* The CLASS reserved word */ %token OP /* The OP reserved word */ %token INT_LIT /* An INT literal */ %token REAL_LIT /* A REAL literal */ %token BOOL_LIT /* A BOOL literal */ %token RETURN /* The RETURN reserved word */ %token BREAK /* The BREAK reserved word */ %token SKIP /* The SKIP reserved word */ %token RETRY /* The RETRY reserved word */ %token ELSE /* The ELSE reserved word */ %token COND /* The COND reserved word (?) */ %token WHILE /* The WHILE reserved word (*) */ %token IDENTICAL /* The "==" token */ %token ASSIGN /* The ":=" token */ %token RETURNS /* The "->" token */ %token AND /* The AND operator */ %token OR /* The OR operator */ %token NOT /* The NOT operator */ %token LT /* The "<" operator */ %token LE /* The "<=" operator */ %token EQ /* The "=" operator */ %token NE /* The "~=" operator */ %token GE /* The ">=" operator */ %token GT /* The ">" operator */ /*****************************************************************************/ /* */ /* Operator Precedences. */ /* */ /*****************************************************************************/ %nonassoc ':' ';' /* ID/type separator */ %nonassoc RETURN ASSIGN RETURNS /* Must do it because of */ %right ',' /* Tuple operator */ %left OR %left AND %right NOT %nonassoc LT LE EQ NE GE GT %left '+' '-' %left '*' '/' '%' %nonassoc UMINUS %nonassoc '(' ')' '[' ']' '{' '}' /* Well, not really, but... */ /* Have to list these after "->" */ %left '.' /* Qualified name constructor */ /*****************************************************************************/ /* */ /* Grammar symbol type declarations. */ /* */ /*****************************************************************************/ %type ID %type INT_LIT %type REAL_LIT %type BOOL_LIT /*****************************************************************************/ /* */ /* Start Symbol. */ /* */ /*****************************************************************************/ %start program %% program : globals /* Global declarations */ ; /*****************************************************************************/ /* */ /* Declarations. */ /* */ /*****************************************************************************/ decl : /* Name declaration: */ ids ':' type /* Variable, Explicit type, Undef */ { APT ("T,I", ("decl_list(I, var, T)")); } | ID ':' type /* Variable, Explicit type, Undef */ { APT ("T", ("decl(id('%s'), var, T)", $1)); } | ID ':' type ASSIGN exp /* Variable, Explicit type, Init */ { APT ("V,T", ("V,decl(id('%s'), var, T)", $1)); APT ("V", ("assign(id('%s'), V)", $1)); } | ID ':' type EQ exp /* Constant, Explicit type */ { APT ("V,T", ("decl(id('%s'), const(V), T)", $1)); } | ID EQ exp /* Constant, Implicit type */ { APT ("V", ("decl(id('%s'), const(V), T)", $1)); } ; /******************************************************************************/ formals : /* Formal declarations: */ { APT (NULL, ("[]")); } | formal_list { } ; formal_list : /* List of formal declarations */ formal { APT ("X", ("[X]")); } | formal ';' formal_list { APT ("T,H", ("[H|T]")); } | error { yyerrok; yyclearin; error ("expected s formal declaration."); APT (NULL, ("error(formals)")); } ; formal : /* Formal declaration: */ ids /* Implicit type */ { APT ("I", ("decl_list(I, formal, T)")); } | ID /* Implicit type */ { APT (NULL, ("decl(id('%s'), formal, T)", $1)); } | ids ':' type /* Explicit type */ { APT ("T,I", ("decl_list(I, formal, T)")); } | ID ':' type /* Explicit type */ { APT ("T", ("decl(id('%s'), formal, T)", $1)); } ; /******************************************************************************/ fields : /* Field declarations: */ { APT (NULL, ("[]")); } | field_list { } ; field_list : /* List of field declarations */ field { APT ("H", ("[H]")); } | field ';' field_list { APT ("T,H", ("[H|T]")); } | error { yyerrok; yyclearin; error ("expected s field declaration."); APT (NULL, ("error(fields)")); } ; field : /* Field declaration: */ ids ':' type /* Explicit type */ { APT ("T,I", ("field_list(I, T)")); } | ID ':' type /* Explicit type */ { APT ("T", ("field(id('%s'), T)", $1)); } ; /******************************************************************************/ globals : /* Global declarations: */ { APT (NULL, ("[]")); } | global_list { } ; global_list : global { APT ("T", ("[T]")); } | global ';' global_list { APT ("T,H", ("[H|T]")); } | error { yyerrok; yyclearin; error ("expected a global declaration."); APT (NULL, ("error(decls)")); } ; global : /* Global declaration: */ ids ':' type { APT ("T,I", ("decl_list(I, var, T)")); } | ID ':' type { APT ("T", ("decl(id('%s'), var, T)", $1)); } | ID ':' type ASSIGN exp { APT ("V,T", ("V,decl(id('%s'), var, T)", $1)); APT ("V", ("assign(id('%s'), V)", $1)); } | ID ASSIGN exp { APT ("V", ("decl(id('%s'), const(V), T)", $1)); } | ID ':' global_type EQ global_exp { APT ("V,T", ("decl(id('%s'), const(V), T)", $1)); } | ID EQ global_exp { APT ("V", ("decl(id('%s'), const(V), T)", $1)); } ; /******************************************************************************/ ids : ID ',' ids_aux { APT ("X", ("[id('%s')|X]", $1)); } ; ids_aux : ID { APT (NULL, ("[id('%s')]", $1)); } | ID ',' ids_aux { APT ("T", ("[id('%s')|T]", $1)); } ; /*****************************************************************************/ /* */ /* Type signatures. */ /* */ /*****************************************************************************/ types : /* Type list */ type /* Single type (end of list) */ { APT ("T", ("[T]")); } | type ',' types /* Type tuple (list) */ { APT ("T,H", ("[H|T]")); } ; type : /* Type signature (type expression) */ '(' types ')' /* Type list */ { } | INT /* Integer */ { APT (NULL, ("int")); } | REAL /* Real */ { APT (NULL, ("real")); } | BOOL /* Boolean */ { APT (NULL, ("bool")); } | '[' exp ']' type /* Array type */ { APT ("T,B", ("array(T, B)")); } | '{' fields '}' /* Record/Class type */ { APT ("F", ("class(F)")); } | error { yyerrok; yyclearin; error ("expected a type."); APT (NULL, ("error(type)")); } ; /******************************************************************************/ global_type : /* Type signature valid only at top */ '(' types ')' /* Type list */ { } | INT /* Integer */ { APT (NULL, ("int")); } | REAL /* Real */ { APT (NULL, ("real")); } | BOOL /* Boolean */ { APT (NULL, ("bool")); } | type RETURNS type /* Function type */ { APT ("R,D", ("map(D, R)")); } | '[' exp ']' type /* Array type */ { APT ("T,B", ("array(T, B)")); } | '{' fields '}' /* Record/Class type */ { APT ("F", ("class(F)")); } | error { yyerrok; yyclearin; error ("expected a type."); APT (NULL, ("error(type)")); } ; /*****************************************************************************/ /* */ /* Expressions. */ /* */ /*****************************************************************************/ exp : /* Generic expression */ sexp { } | sexp ',' exp_list { APT ("T,H", ("[H|T]")); } ; exp_list : sexp { APT ("E", ("[E]")); } | sexp ',' exp_list { APT ("T,H", ("[H|T]")); } ; sexp : '(' exp ')' { } | sexp OR sexp /* Boolean operators */ { APT ("R,L", ("or(L, R)")); } | sexp AND sexp { APT ("R,L", ("and(L, R)")); } | NOT sexp { APT ("A", ("not(A)")); } | sexp LT sexp /* Relational operators */ { APT ("R,L", ("lt(L, R)")); } | sexp LE sexp { APT ("R,L", ("le(L, R)")); } | sexp EQ sexp { APT ("R,L", ("eq(L, R)")); } | sexp NE sexp { APT ("R,L", ("ne(L, R)")); } | sexp GE sexp { APT ("R,L", ("ge(L, R)")); } | sexp GT sexp { APT ("R,L", ("gt(L, R)")); } | sexp '+' sexp /* Arithmetic operators */ { APT ("R,L", ("add(L, R)")); } | sexp '-' sexp { APT ("R,L", ("sub(L, R)")); } | sexp '*' sexp { APT ("R,L", ("mul(L, R)")); } | sexp '/' sexp { APT ("R,L", ("div(L, R)")); } | sexp '%' sexp { APT ("R,L", ("mod(L, R)")); } | '-' sexp %prec UMINUS { APT ("A", ("neg(A)")); } | sexp '.' ID /* Qualified names */ { APT ("L", ("name(L, id('%s'))", $3)); } | sexp '[' exp ']' /* Array references */ { APT ("R,L", ("array(L, R)")); } | sexp '(' exp ')' /* Function references */ { APT ("R,L", ("map(L, R)")); } | ID /* Simple names */ { APT (NULL, ("id('%s')", $1)); } | INT_LIT /* Integer constant */ { APT (NULL, ("lit(int, %d)", $1)); } | REAL_LIT /* Real constant */ { APT (NULL, ("lit(real, %g)", $1)); } | BOOL_LIT /* Boolean constant */ { APT (NULL, ("lit(bool, %s)", $1? "true": "false")); } ; /******************************************************************************/ global_exp : sexp /* An ordinary expression */ { } | MAP '(' formals ')' /* Function literal */ '[' stats ']' { APT ("S,F", ("lit(map(TF,TR), map(F,S,Symbols))")); } | MAP '(' formals ')' RETURNS type /* Function literal */ '[' stats ']' { APT ("S,TR,F", ("lit(map(TF,TR), map(F,S,Symbols))")); } ; /******************************************************************************/ primary : /* Restricted expression */ prim { } | prim ',' prim_list { APT ("T,H", ("[H|T]")); } ; prim_list : prim { APT ("P", ("[P]")); } | prim ',' prim_list { APT ("T,H", ("[H|T]")); } ; prim : '(' primary ')' { } | ID { APT (NULL, ("id('%s')", $1)); } | prim '.' prim { APT ("R,L", ("name(L, R)")); } | prim '[' exp ']' { APT ("R,L", ("array(L, R)")); } ; /*****************************************************************************/ /* */ /* Statements. */ /* */ /*****************************************************************************/ stats : /* EMPTY */ { APT (NULL, ("[]")); } | stat_list { } ; stat_list : stat { APT ("S", ("[S]")); } | stat ';' stat_list { APT ("Ss,S", ("[S|Ss]")); } | error { yyerrok; yyclearin; error ("expected a valid statement."); APT (NULL, ("error(stats)")); } ; stat : /* A statement: */ decl /* Declaration */ { } | action /* Assignment or call */ { } | RETURN exp { APT ("E", ("return(E)")); } | BREAK { APT (NULL, ("break(S)")); } | SKIP { APT (NULL, ("skip(S)")); } | RETRY { APT (NULL, ("retry(S)")); } | COND { APT (NULL, ("%d", ++guardNo)); } '[' clauses ']' { APT ("B,G", ("cond(B, G)")); } | WHILE { APT (NULL, ("%d", ++guardNo)); } '[' clauses ']' { APT ("B,G", ("while(B, G)")); } | '[' stats ']' { } ; clauses : exp RETURNS stats { APT ("S,E", ("[clause(E, S)]")); } | exp RETURNS stats '|' clauses { APT ("Cs,S,E", ("[clause(E, S)|Cs]")); } | exp RETURNS stats '|' ELSE RETURNS stats { APT ("ES,S,E", ("[clause(E, S),else(ES)]")); } | error ']' { yyerrok; yyclearin; error ("syntax error in guarded clause."); APT (NULL, ("error(clause)")); } ; action : primary ASSIGN exp /* Assignment */ { APT ("V,P", ("assign(P, V)")); } | primary '(' exp ')' /* Function call */ { APT ("R,L", ("map(L, R)")); } ; %% yyerror(s) char *s; { if (strcmp(s, "parse error")) { error (s); } }