Fist commit (WIP)

1 files changed, 247 insertions, 0 deletions

diff --git a/frontend/parser.mly b/frontend/parser.mly
new file mode 100644
index 0000000..f65e6c7
--- /dev/null
+++ b/frontend/parser.mly
@@ -0,0 +1,247 @@
+(*
+  Cours "Sémantique et Application à la Vérification de programmes"
+  
+  Antoine Miné 2014
+  Ecole normale supérieure, Paris, France / CNRS / INRIA
+*)
+
+
+(*
+  Parser for a very simple C-like "curly bracket" language.
+  
+  There should be exactly one shift/reduce conflict, due to nested 
+  if-then-else constructs. The resolution picked by menhir should be correct.
+ *)
+
+%{
+open Abstract_syntax_tree
+%}
+
+/* tokens */
+/**********/
+
+%token TOK_BOOL
+%token TOK_INT
+%token TOK_VOID
+%token TOK_AUTO
+%token TOK_TRUE
+%token TOK_FALSE
+%token TOK_WHILE
+%token TOK_IF
+%token TOK_ELSE
+%token TOK_HALT
+%token TOK_RETURN
+%token TOK_BREAK
+%token TOK_RAND
+%token TOK_GOTO
+%token TOK_ASSERT
+%token TOK_PRINT
+
+%token TOK_LPAREN
+%token TOK_RPAREN
+%token TOK_LCURLY
+%token TOK_RCURLY
+%token TOK_STAR
+%token TOK_PLUS
+%token TOK_MINUS
+%token TOK_EXCLAIM
+%token TOK_DIVIDE
+%token TOK_PERCENT
+%token TOK_LESS
+%token TOK_GREATER
+%token TOK_LESS_EQUAL
+%token TOK_GREATER_EQUAL
+%token TOK_EQUAL_EQUAL
+%token TOK_NOT_EQUAL
+%token TOK_AND_AND
+%token TOK_BAR_BAR
+%token TOK_SEMICOLON
+%token TOK_COLON
+%token TOK_COMMA
+%token TOK_EQUAL
+
+%token <string> TOK_id
+%token <string> TOK_int
+
+%token TOK_EOF
+
+/* priorities of binary operators (lowest to highest) */
+%left TOK_BAR_BAR
+%left TOK_AND_AND
+%left TOK_EQUAL_EQUAL TOK_NOT_EQUAL
+%left TOK_LESS TOK_GREATER TOK_LESS_EQUAL TOK_GREATER_EQUAL
+%left TOK_PLUS TOK_MINUS
+%left TOK_STAR TOK_DIVIDE TOK_PERCENT
+
+
+/* entry-points */
+/****************/
+
+%start<Abstract_syntax_tree.toplevel list Abstract_syntax_tree.ext> file
+
+
+%%
+
+
+/* toplevel */
+/************/
+
+file: t=ext(list(toplevel)) TOK_EOF { t }
+
+toplevel:
+| d=ext(stat)           { AST_stat d }
+| d=ext(fun_decl)       { AST_fun_decl d }
+
+
+/* expressions */
+/***************/
+
+primary_expr:
+| TOK_LPAREN e=expr TOK_RPAREN     { e }
+| e=ext(TOK_id)                    { AST_identifier e }
+| e=ext(TOK_int)                   { AST_int_const e }
+| TOK_TRUE                         { AST_bool_const true }
+| TOK_FALSE                        { AST_bool_const false }
+| TOK_RAND TOK_LPAREN e1=ext(sign_int_literal)  
+           TOK_COMMA  e2=ext(sign_int_literal) TOK_RPAREN
+  { AST_int_rand (e1, e2) }
+| e=ext(TOK_id) TOK_LPAREN l=separated_list(TOK_COMMA,ext(expr)) TOK_RPAREN TOK_SEMICOLON
+   { AST_expr_call (e, l) }
+
+/* integer with optional sign */
+sign_int_literal:
+| i=TOK_int            { i }
+| TOK_PLUS i=TOK_int   { i }
+| TOK_MINUS i=TOK_int  { "-"^i }
+
+
+unary_expr:
+| e=primary_expr                   { e }
+| o=unary_op e=ext(unary_expr)     { AST_unary (o, e) }
+
+%inline unary_op:
+| TOK_PLUS           { AST_UNARY_PLUS }
+| TOK_MINUS          { AST_UNARY_MINUS }
+| TOK_EXCLAIM        { AST_NOT }
+
+
+binary_expr:
+| e=unary_expr                                        { e }
+| e=ext(binary_expr) o=binary_op f=ext(binary_expr)   { AST_binary (o, e, f) }
+
+%inline binary_op:
+| TOK_STAR           { AST_MULTIPLY }
+| TOK_DIVIDE         { AST_DIVIDE }
+| TOK_PERCENT        { AST_MODULO }
+| TOK_PLUS           { AST_PLUS }
+| TOK_MINUS          { AST_MINUS }
+| TOK_LESS           { AST_LESS }
+| TOK_GREATER        { AST_GREATER }
+| TOK_LESS_EQUAL     { AST_LESS_EQUAL }
+| TOK_GREATER_EQUAL  { AST_GREATER_EQUAL }
+| TOK_EQUAL_EQUAL    { AST_EQUAL }
+| TOK_NOT_EQUAL      { AST_NOT_EQUAL }
+| TOK_AND_AND        { AST_AND }
+| TOK_BAR_BAR        { AST_OR }
+
+expr:
+| e=binary_expr { e }
+
+lvalue:
+| i=TOK_id   { i }
+
+
+/* declarations */
+/****************/
+
+var_decl:
+| s=ext(typ) i=separated_list(TOK_COMMA,init_declarator) TOK_SEMICOLON
+  { s, i }
+
+init_declarator:
+| v=ext(TOK_id)                         { v, None }
+| v=ext(TOK_id) TOK_EQUAL i=ext(expr)   { v, Some i }
+
+fun_decl:
+| t=ext(typ_or_void) i=ext(TOK_id)
+        TOK_LPAREN p=separated_list(TOK_COMMA,param_decl) TOK_RPAREN 
+        b=block
+  { { Abstract_syntax_tree.fun_name = i;
+      Abstract_syntax_tree.fun_typ = t;
+      Abstract_syntax_tree.fun_args = p;
+      Abstract_syntax_tree.fun_body = b; }
+  }
+
+param_decl:
+| s=ext(typ) v=ext(TOK_id) { s, v }
+
+typ:
+| TOK_INT    { AST_TYP_INT }
+| TOK_BOOL   { AST_TYP_BOOL }
+| TOK_AUTO   { AST_TYP_AUTO }
+
+%inline typ_or_void:
+| t=typ      { Some t }
+| TOK_VOID   { None }
+
+
+/* statements */
+/**************/
+
+block:
+| TOK_LCURLY l=list(ext(stat)) TOK_RCURLY  { l }
+
+stat:
+| l=block                     
+  { AST_block l }
+
+| e=ext(lvalue) TOK_EQUAL f=ext(expr) TOK_SEMICOLON
+  { AST_assign (e, f) }
+
+| TOK_IF TOK_LPAREN e=ext(expr) TOK_RPAREN s=ext(stat)
+  { AST_if (e, s, None) }
+
+| TOK_IF TOK_LPAREN e=ext(expr) TOK_RPAREN s=ext(stat) TOK_ELSE t=ext(stat) 
+  { AST_if (e, s, Some t) }
+
+| TOK_WHILE TOK_LPAREN e=ext(expr) TOK_RPAREN s=ext(stat)
+  { AST_while (e, s) }
+
+| TOK_ASSERT TOK_LPAREN e=ext(expr) TOK_RPAREN TOK_SEMICOLON
+  { AST_assert e }
+
+| TOK_PRINT TOK_LPAREN l=separated_list(TOK_COMMA,ext(lvalue)) TOK_RPAREN TOK_SEMICOLON
+  { AST_print l }
+
+| v=var_decl
+  { AST_local v }
+
+| e=ext(TOK_id) TOK_LPAREN l=separated_list(TOK_COMMA,ext(expr)) TOK_RPAREN TOK_SEMICOLON
+  { AST_stat_call (e, l) }
+
+| TOK_RETURN e=option(ext(expr)) TOK_SEMICOLON
+  { AST_return e }
+
+| TOK_BREAK TOK_SEMICOLON
+  { AST_BREAK }
+
+| TOK_HALT TOK_SEMICOLON
+  { AST_HALT }
+
+| TOK_GOTO l=ext(TOK_id) TOK_SEMICOLON
+  { AST_goto l }
+
+| l=ext(TOK_id) TOK_COLON
+  { AST_label l }
+
+
+
+/* utilities */
+/*************/
+
+/* adds extent information to rule */
+%inline ext(X): 
+| x=X { x, ($startpos, $endpos) }
+
+
+%%