source: Deliverables/D2.2/8051/src/cminor/cminorParser.mly @ 486

Last change on this file since 486 was 486, checked in by ayache, 9 years ago

Deliverable D2.2

File size: 19.1 KB
Line 
1/* Adapted from Leroy's CompCert */
2
3/* tokens ALLOC, DOLLAR, IN, LET, p_let were unused and have been removed */
4/* precedence levels unused were also removed */
5
6/* *********************************************************************/
7/*                                                                     */
8/*              The Compcert verified compiler                         */
9/*                                                                     */
10/*          Xavier Leroy, INRIA Paris-Rocquencourt                     */
11/*                                                                     */
12/*  Copyright Institut National de Recherche en Informatique et en     */
13/*  Automatique.  All rights reserved.  This file is distributed       */
14/*  under the terms of the GNU General Public License as published by  */
15/*  the Free Software Foundation, either version 2 of the License, or  */
16/*  (at your option) any later version.  This file is also distributed */
17/*  under the terms of the INRIA Non-Commercial License Agreement.     */
18/*                                                                     */
19/* *********************************************************************/
20
21%{
22
23  open AST
24  open Cminor
25  open Memory
26
27  (* Function calls are not allowed in the AST of expressions, but function
28     calls in the AST of statements have a special argument which can be used to
29     store the result of the function call in a side-effect manner.
30     Example: the statement
31       x = y + f(z,g(t));
32     will be transformed into the (simplified syntax) AST statements
33       g(_t1,t)
34       f(_t2,y,_t1);
35       x = y + _t2
36     where _t1 and _t2 are fresh temporary variables. *)
37
38
39  (* Thus, to deal with function calls in expressions, we need to create fresh
40     temporary variables *)
41
42  let temp_counter = ref 0
43  let temporaries = ref []
44
45  let mktemp () =
46    incr temp_counter;
47    let id = Printf.sprintf "_t%d" !temp_counter in
48      temporaries := id :: !temporaries;
49      id
50
51
52  (* Expressions with function calls *)
53
54  type rexpr =
55    | RId of ident
56    | RCst of cst
57    | ROp1 of op1 * rexpr
58    | ROp2 of op2 * rexpr * rexpr
59    | RMem of memory_q * rexpr
60    | RCond of rexpr * rexpr * rexpr
61    | RCall of rexpr * rexpr list * signature
62
63  (* [convert_accu] stores the function calls of expressions with function
64     calls being converted to expressions without function calls *)
65  let convert_accu = ref []
66
67  (* [convert_rexpr rexpr] converts the expression with function calls [rexpr]
68     into an expression without function calls. The function calls in [rexpr]
69     are stored in [convert_accu] *)
70  let rec convert_rexpr = function
71    | RId id -> Id id
72    | RCst c -> Cst c
73    | ROp1 (op, e1) -> Op1 (op, convert_rexpr e1)
74    | ROp2 (op, e1, e2) -> Op2 (op, convert_rexpr e1, convert_rexpr e2)
75    | RMem (chunk, e1) -> Mem (chunk, convert_rexpr e1)
76    | RCond (e1, e2, e3) ->
77        Cond (convert_rexpr e1, convert_rexpr e2, convert_rexpr e3)
78    | RCall(e1, el, sg) ->
79        let c1 = convert_rexpr e1 in
80        let cl = convert_rexpr_list el in
81        let t = mktemp() in
82          convert_accu := St_call (Some t, c1, cl, sg) :: !convert_accu;
83          Id t
84
85  and convert_rexpr_list el = List.map convert_rexpr el
86
87  (* [prepend_seq stmts last] reverses and sequences the list of statements
88     [stmts] and puts [last] at the end *)
89  let rec prepend_seq stmts last =
90    match stmts with
91      | [] -> last
92      | s1 :: sl -> prepend_seq sl (St_seq (s1, last))
93
94  (* [mkeval e] creates the AST statement associated to the Cminor instruction
95       e;
96     where [e] is an expression with possible function calls *)
97  let mkeval e =
98    convert_accu := [];
99    match e with
100      | RCall (e1, el, sg) ->
101          let c1 = convert_rexpr e1 in
102          let cl = convert_rexpr_list el in
103            prepend_seq !convert_accu (St_call (None, c1, cl, sg))
104      | _ ->
105          ignore (convert_rexpr e);
106          prepend_seq !convert_accu St_skip
107
108  (* [mkeval id e] creates the AST statement associated to the Cminor
109     instruction
110       id = e;
111     where [e] is an expression with possible function calls *)
112  let mkassign id e =
113    convert_accu := [];
114    match e with
115      | RCall (e1, el, sg) ->
116          let c1 = convert_rexpr e1 in
117          let cl = convert_rexpr_list el in
118            prepend_seq !convert_accu (St_call (Some id, c1, cl, sg))
119      | _ ->
120          let c = convert_rexpr e in
121            prepend_seq !convert_accu (St_assign (id, c))
122
123  (* [mkstore chunk e1 e2] creates the AST statement associated to the Cminor
124     instruction
125       chunk[e1] = e2;
126     where [e1] and [e2] are expressions with possible function calls *)
127  let mkstore chunk e1 e2 =
128    convert_accu := [];
129    let c1 = convert_rexpr e1 in
130    let c2 = convert_rexpr e2 in
131      prepend_seq !convert_accu (St_store (chunk, c1, c2))
132
133  (* [mkifthenelse e s1 s2] creates the AST statement associated to the Cminor
134     instruction
135       if (e) { s1 } else { s2 }
136     where [e] is an expression with possible function calls *)
137  let mkifthenelse e s1 s2 =
138    convert_accu := [];
139    let c = convert_rexpr e in
140      prepend_seq !convert_accu (St_ifthenelse (c, s1, s2))
141
142  (* [mkreturn_some e] creates the AST statement associated to the Cminor
143     instruction
144       return e;
145     where [e] is an expression with possible function calls *)
146  let mkreturn_some e =
147    convert_accu := [];
148    let c = convert_rexpr e in
149      prepend_seq !convert_accu (St_return (Some c))
150
151  (* [mkswitch e (cases, dfl)] creates the AST statement associated to the
152     Cminor instruction
153       switch (e) {
154         case i: exit j_i;
155         ...
156         default: exit j_default; }
157     where [e] is an expression with possible function calls *)
158  let mkswitch e (cases, dfl) =
159    convert_accu := [];
160    let c = convert_rexpr e in
161      prepend_seq !convert_accu (St_switch (c, cases, dfl))
162
163  (* The Cminor instruction
164      match (e) {
165        case 0: s0;
166        case 1: s1;
167        case 2: s2; }
168     is syntaxic sugar for the Cminor instruction
169       block {
170         block {
171           block {
172             block {
173               switch (e) {
174                 case 0: exit 0;
175                 case 1: exit 1;
176                 default: exit 2; }
177             } s0; exit 2;
178           } s1; exit 1;
179         } s2;
180       }
181     Note that matches are assumed to be exhaustive *)
182
183  let mkmatch_aux e cases =
184    let ncases = List.length cases in
185    let rec mktable n = function
186      | [] -> assert false
187      | [key, action] -> []
188      | (key, action) :: rem -> (key, n) :: mktable (n+1) rem in
189    let sw =
190      St_switch (e, mktable 0 cases, pred ncases) in
191    let rec mkblocks body n = function
192      | [] -> assert false
193      | [key, action] -> St_block (St_seq (body, action))
194      | (key, action) :: rem ->
195          mkblocks
196            (St_block (St_seq (body, St_seq (action, St_exit n))))
197            (pred n) rem in
198      mkblocks (St_block sw) (pred ncases) cases
199
200  (* [mkmatch e cases] creates the AST statement associated to the Cminor
201     instruction
202       match (e) {
203         case i: s_i;
204         ... }
205     where [e] is an expression with possible function calls *)
206  let mkmatch e cases =
207    convert_accu := [];
208    let c = convert_rexpr e in
209    let s =
210      match cases with
211        | [] -> St_skip (* ??? *)
212        | [key, action] -> action
213        | _ -> mkmatch_aux c cases in
214      prepend_seq !convert_accu s
215
216  (* [mktailcall f [e1;e2;...] sig] creates the AST statement associated to the
217     Cminor instruction
218     tailcall f(e1,e2,...): sig
219     where [e], [e1], [e2], ... are expressions with possible function calls *)
220  let mktailcall e1 el sg =
221    convert_accu := [];
222    let c1 = convert_rexpr e1 in
223    let cl = convert_rexpr_list el in
224      prepend_seq !convert_accu (St_tailcall (c1, cl, sg))
225
226  (* Parse error handler *)
227  let raise_error (_, pos) s = Error.error "parse error" pos (s ^ "\n")
228
229%}
230
231%token ABSF
232%token AMPERSAND
233%token AMPERSANDAMPERSAND
234%token BANG
235%token BANGEQUAL
236%token BANGEQUALF
237%token BANGEQUALU
238%token BAR
239%token BARBAR
240%token CARET
241%token CASE
242%token COLON
243%token COMMA
244%token DEFAULT
245%token ELSE
246%token EQUAL
247%token EQUALEQUAL
248%token EQUALEQUALF
249%token EQUALEQUALU
250%token EOF
251%token EXIT
252%token EXTERN
253%token FLOAT
254%token FLOAT32
255%token FLOAT64
256%token <float> FLOATLIT
257%token FLOATOFINT
258%token FLOATOFINTU
259%token GREATER
260%token GREATERF
261%token GREATERU
262%token GREATEREQUAL
263%token GREATEREQUALF
264%token GREATEREQUALU
265%token GREATERGREATER
266%token GREATERGREATERU
267%token <string> IDENT
268%token IF
269%token INT
270%token INT16
271%token INT16S
272%token INT16U
273%token INT32
274%token INT8
275%token INT8S
276%token INT8U
277%token <int> INTLIT
278%token INTOFFLOAT
279%token INTUOFFLOAT
280%token LBRACE
281/* %token LBRACELBRACE */
282%token LBRACKET
283%token LESS
284%token LESSU
285%token LESSF
286%token LESSEQUAL
287%token LESSEQUALU
288%token LESSEQUALF
289%token LESSLESS
290%token LOOP
291%token LPAREN
292%token MATCH
293%token MINUS
294%token MINUSF
295%token MINUSGREATER
296%token PERCENT
297%token PERCENTU
298%token PLUS
299%token PLUSF
300%token QUESTION
301%token RBRACE
302/* %token RBRACERBRACE */
303%token RBRACKET
304%token RETURN
305%token RPAREN
306%token SEMICOLON
307%token SLASH
308%token SLASHF
309%token SLASHU
310%token STACK
311%token STAR
312%token STARF
313%token <string> STRINGLIT
314%token SWITCH
315%token TILDE
316%token TAILCALL
317%token VAR
318%token VOID
319%token GOTO BLOCK
320
321/* Unused */
322/* %token ALLOC DOLLAR IN LET p_let */
323
324/* Precedences from low to high */
325
326/* %left COMMA */
327/* %left p_let */
328/* %right EQUAL */
329%right QUESTION COLON
330%left BARBAR
331%left AMPERSANDAMPERSAND
332%left BAR
333%left CARET
334%left AMPERSAND
335%left EQUALEQUAL BANGEQUAL LESS LESSEQUAL GREATER GREATEREQUAL EQUALEQUALU BANGEQUALU LESSU LESSEQUALU GREATERU GREATEREQUALU EQUALEQUALF BANGEQUALF LESSF LESSEQUALF GREATERF GREATEREQUALF
336%left LESSLESS GREATERGREATER GREATERGREATERU
337%left PLUS PLUSF MINUS MINUSF
338%left STAR SLASH PERCENT STARF SLASHF SLASHU PERCENTU
339%nonassoc BANG TILDE p_uminus ABSF INTOFFLOAT INTUOFFLOAT FLOATOFINT FLOATOFINTU INT8S INT8U INT16S INT16U FLOAT32 /* ALLOC */
340%left LPAREN
341
342/* Entry point */
343
344%start program
345%type <Cminor.program> program
346
347%%
348
349%inline position(X): x = X { (x, Position.lex_join $startpos $endpos) }
350
351/* Programs */
352
353program:
354    global_declarations proc_list EOF { { vars   = List.rev $1 ;
355                                          functs = List.rev $2 ;
356                                          main   = Some "main" } }
357;
358
359global_declarations:
360    /* empty */                            { [] }
361  | global_declarations global_declaration { $2 :: $1 }
362;
363
364global_declaration:
365    VAR STRINGLIT init_datas { ($2, List.rev $3) }
366  | pos = position(error)    { raise_error pos
367                                 "Global declaration syntax error" }
368;
369
370init_datas:
371    /* empty */                  { [] }
372  | init_data                    { [$1] }
373  | LBRACE init_data_list RBRACE { $2 }
374;
375
376init_data:
377    INTLIT                         { AST.Data_int32 $1 }
378  | FLOATLIT                       { AST.Data_float32 $1 }
379  | LPAREN INT8 RPAREN INTLIT      { AST.Data_int8 $4 }
380  | LPAREN INT16 RPAREN INTLIT     { AST.Data_int16 $4 }
381  | LPAREN INT32 RPAREN INTLIT     { AST.Data_int32 $4 }
382  | LPAREN FLOAT32 RPAREN FLOATLIT { AST.Data_float32 $4 }
383  | LPAREN FLOAT64 RPAREN FLOATLIT { AST.Data_float64 $4 }
384  | LBRACKET INTLIT RBRACKET       { AST.Data_reserve $2 }
385;
386
387init_data_list:
388    init_data                      { [$1] }
389  | init_data COMMA init_data_list { $1 :: $3 }
390;
391
392proc_list:
393    /* empty */    { [] }
394  | proc_list proc { $2 :: $1 }
395;
396
397/* Procedures */
398
399proc:
400    STRINGLIT LPAREN parameters RPAREN COLON signature
401    LBRACE
402      stack_declaration
403      var_declarations
404      stmt_list
405    RBRACE
406  { let tmp = !temporaries in
407      temporaries := [];
408      temp_counter := 0;
409      ($1, F_int { f_sig = $6 ;
410                   f_params = List.rev $3 ;
411                   f_vars = List.rev (tmp @ $9) ;
412                   f_ptrs = [] (* TODO *) ;
413                   f_stacksize = $8 ;
414                   f_body = $10 }) }
415  | EXTERN STRINGLIT COLON signature { ($2, F_ext { ef_tag = $2 ;
416                                                    ef_sig = $4 }) }
417  | pos = position(error) { raise_error pos
418                            "Procedure or function declaration syntax error" }
419;
420
421parameters:
422    /* empty */    { [] }
423  | parameter_list { $1 }
424;
425
426parameter_list:
427    IDENT                      { $1 :: [] }
428  | parameter_list COMMA IDENT { $3 :: $1 }
429  | pos = position(error) { raise_error pos
430                            "Parameter declaration syntax error" }
431;
432
433signature:
434    type_  { { args = [] ; res = Type_ret $1 } }
435  | VOID
436      { { args = [] ; res = Type_void } }
437  | type_ MINUSGREATER signature
438          { let s = $3 in {s with args = $1 :: s.args } }
439  | pos = position(error) { raise_error pos "Signature syntax error" }
440;
441
442stack_declaration:
443    /* empty */            { 0 }
444  | STACK INTLIT SEMICOLON { $2 }
445  | pos = position(error)  { raise_error pos "Stack declaration syntax error" }
446;
447
448var_declarations:
449    /* empty */                      { [] }
450  | var_declarations var_declaration { $2 @ $1 }
451  | pos = position(error)            { raise_error pos
452                                         "Variable declaration syntax error" }
453;
454
455var_declaration:
456    VAR parameter_list SEMICOLON { $2 }
457;
458
459/* Statements */
460
461stmt:
462    expr SEMICOLON                         { mkeval $1 }
463  | IDENT EQUAL expr SEMICOLON             { mkassign $1 $3 }
464  | memory_q LBRACKET expr RBRACKET EQUAL expr SEMICOLON
465      { mkstore $1 $3 $6 }
466  | IF LPAREN expr RPAREN stmts ELSE stmts { mkifthenelse $3 $5 $7 }
467  | IF LPAREN expr RPAREN stmts            { mkifthenelse $3 $5 St_skip }
468  | LOOP stmts                             { St_loop $2 }
469  | BLOCK LBRACE stmt_list RBRACE          { St_block $3 }
470  | EXIT SEMICOLON                         { St_exit 0 }
471  | EXIT INTLIT SEMICOLON                  { St_exit $2 }
472  | RETURN SEMICOLON                       { St_return None }
473  | RETURN expr SEMICOLON                  { mkreturn_some $2 }
474  | GOTO IDENT SEMICOLON                   { St_goto $2 }
475  | IDENT COLON stmt                       { St_label ($1, $3) }
476  | SWITCH LPAREN expr RPAREN LBRACE switch_cases RBRACE
477        { mkswitch $3 $6 }
478  | MATCH LPAREN expr RPAREN LBRACE match_cases RBRACE
479          { mkmatch $3 $6 }
480  | TAILCALL expr LPAREN expr_list RPAREN COLON signature SEMICOLON
481              { mktailcall $2 $4 $7 }
482;
483
484stmt_list:
485    /* empty */    { St_skip }
486  | stmt stmt_list { St_seq ($1, $2) }
487  | pos = position(error) { raise_error pos "Statement syntax error" }
488;
489
490stmts:
491    LBRACE stmt_list RBRACE { $2 }
492  | stmt                    { $1 }
493;
494
495switch_cases:
496    DEFAULT COLON EXIT INTLIT SEMICOLON
497    { ([], $4) }
498  | CASE INTLIT COLON EXIT INTLIT SEMICOLON switch_cases
499        { let (cases, dfl) = $7 in (($2, $5) :: cases, dfl) }
500  | pos = position(error) { raise_error pos "Syntax error in switch construct" }
501;
502
503match_cases:
504    /* empty */                             { [] }
505  | CASE INTLIT COLON stmt_list match_cases { ($2, $4) :: $5 }
506  | pos = position(error) { raise_error pos "Syntax error in match construct" }
507;
508
509/* Expressions */
510
511expr:
512    LPAREN expr RPAREN                      { $2 }
513  | IDENT                               { RId $1 }
514  | INTLIT                              { RCst (Cst_int $1) }
515  | FLOATLIT                            { RCst (Cst_float $1) }
516  | STRINGLIT                           { RCst (Cst_addrsymbol $1) }
517  | AMPERSAND INTLIT                    { RCst (Cst_stackoffset $2) }
518  | MINUS expr    %prec p_uminus        { ROp1 (Op_negint, $2) }
519  | MINUSF expr   %prec p_uminus        { ROp1 (Op_negf, $2) }
520  | ABSF expr                           { ROp1 (Op_absf, $2) }
521  | INTOFFLOAT expr                     { ROp1 (Op_intoffloat, $2) }
522  | INTUOFFLOAT expr                    { ROp1 (Op_intuoffloat, $2) }
523  | FLOATOFINT expr                     { ROp1 (Op_floatofint, $2) }
524  | FLOATOFINTU expr                    { ROp1 (Op_floatofintu, $2) }
525  | TILDE expr                          { ROp1 (Op_notint, $2) }
526  | BANG expr                           { ROp1 (Op_notbool, $2) }
527  | INT8S expr                          { ROp1 (Op_cast8signed, $2) }
528  | INT8U expr                          { ROp1 (Op_cast8unsigned, $2) }
529  | INT16S expr                         { ROp1 (Op_cast16signed, $2) }
530  | INT16U expr                         { ROp1 (Op_cast16unsigned, $2) }
531  | FLOAT32 expr                        { ROp1 (Op_singleoffloat, $2) }
532  | expr PLUS expr                      { ROp2 (Op_add, $1, $3) }
533  | expr MINUS expr                     { ROp2 (Op_sub, $1, $3) }
534  | expr STAR expr                      { ROp2 (Op_mul, $1, $3) }
535  | expr SLASH expr                     { ROp2 (Op_div, $1, $3) }
536  | expr PERCENT expr                   { ROp2 (Op_mod, $1, $3) }
537  | expr SLASHU expr                    { ROp2 (Op_divu, $1, $3) }
538  | expr PERCENTU expr                  { ROp2 (Op_modu, $1, $3) }
539  | expr AMPERSAND expr                 { ROp2 (Op_and, $1, $3) }
540  | expr BAR expr                       { ROp2 (Op_or, $1, $3) }
541  | expr CARET expr                     { ROp2 (Op_xor, $1, $3) }
542  | expr LESSLESS expr                  { ROp2 (Op_shl, $1, $3) }
543  | expr GREATERGREATER expr            { ROp2 (Op_shr, $1, $3) }
544  | expr GREATERGREATERU expr           { ROp2 (Op_shru, $1, $3) }
545  | expr PLUSF expr                     { ROp2 (Op_addf, $1, $3) }
546  | expr MINUSF expr                    { ROp2 (Op_subf, $1, $3) }
547  | expr STARF expr                     { ROp2 (Op_mulf, $1, $3) }
548  | expr SLASHF expr                    { ROp2 (Op_divf, $1, $3) }
549  | expr EQUALEQUAL expr                { ROp2 (Op_cmp Cmp_eq, $1, $3) }
550  | expr BANGEQUAL expr                 { ROp2 (Op_cmp Cmp_ne, $1, $3) }
551  | expr LESS expr                      { ROp2 (Op_cmp Cmp_lt, $1, $3) }
552  | expr LESSEQUAL expr                 { ROp2 (Op_cmp Cmp_le, $1, $3) }
553  | expr GREATER expr                   { ROp2 (Op_cmp Cmp_gt, $1, $3) }
554  | expr GREATEREQUAL expr              { ROp2 (Op_cmp Cmp_ge, $1, $3) }
555  | expr EQUALEQUALU expr               { ROp2 (Op_cmpu Cmp_eq, $1, $3) }
556  | expr BANGEQUALU expr                { ROp2 (Op_cmpu Cmp_ne, $1, $3) }
557  | expr LESSU expr                     { ROp2 (Op_cmpu Cmp_lt, $1, $3) }
558  | expr LESSEQUALU expr                { ROp2 (Op_cmpu Cmp_le, $1, $3) }
559  | expr GREATERU expr                  { ROp2 (Op_cmpu Cmp_gt, $1, $3) }
560  | expr GREATEREQUALU expr             { ROp2 (Op_cmpu Cmp_ge, $1, $3) }
561  | expr EQUALEQUALF expr               { ROp2 (Op_cmpf Cmp_eq, $1, $3) }
562  | expr BANGEQUALF expr                { ROp2 (Op_cmpf Cmp_ne, $1, $3) }
563  | expr LESSF expr                     { ROp2 (Op_cmpf Cmp_lt, $1, $3) }
564  | expr LESSEQUALF expr                { ROp2 (Op_cmpf Cmp_le, $1, $3) }
565  | expr GREATERF expr                  { ROp2 (Op_cmpf Cmp_gt, $1, $3) }
566  | expr GREATEREQUALF expr             { ROp2 (Op_cmpf Cmp_ge, $1, $3) }
567  | memory_q LBRACKET expr RBRACKET     { RMem ($1, $3) }
568  | expr AMPERSANDAMPERSAND expr        { RCond ($1, $3, RCst (Cst_int 0)) }
569  | expr BARBAR expr                    { RCond ($1, RCst (Cst_int 1), $3) }
570  | expr QUESTION expr COLON expr       { RCond ($1, $3, $5) }
571  | expr LPAREN expr_list RPAREN COLON signature
572      { RCall ($1, $3, $6) }
573  | pos = position(error) { raise_error pos "Expression syntax error" }
574;
575
576expr_list:
577    /* empty */ { [] }
578  | expr_list_1 { $1 }
579;
580
581expr_list_1:
582    expr /* %prec COMMA */ { $1 :: [] }
583  | expr COMMA expr_list_1 { $1 :: $3 }
584;
585
586memory_q:
587    INT8S   { MQ_int8signed }
588  | INT8U   { MQ_int8unsigned }
589  | INT16S  { MQ_int16signed }
590  | INT16U  { MQ_int16unsigned }
591  | INT32   { MQ_int32 }
592  | INT     { MQ_int32 }
593  | FLOAT32 { MQ_float32 }
594  | FLOAT64 { MQ_float64 }
595  | FLOAT   { MQ_float64 }
596;
597
598type_:
599    INT   { Sig_int }
600  | FLOAT { Sig_float }
601;
602
Note: See TracBrowser for help on using the repository browser.