module/language/c/parser.mes

   1 ;;; -*-scheme-*-
   2
   3 ;;; Mes --- Maxwell Equations of Software
   4 ;;; Copyright © 2016 Jan Nieuwenhuizen <janneke@gnu.org>
   5 ;;;
   6 ;;; parser.mes: This file is part of Mes.
   7 ;;;
   8 ;;; Mes is free software; you can redistribute it and/or modify it
   9 ;;; under the terms of the GNU General Public License as published by
  10 ;;; the Free Software Foundation; either version 3 of the License, or (at
  11 ;;; your option) any later version.
  12 ;;;
  13 ;;; Mes is distributed in the hope that it will be useful, but
  14 ;;; WITHOUT ANY WARRANTY; without even the implied warranty of
  15 ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 ;;; GNU General Public License for more details.
  17 ;;;
  18 ;;; You should have received a copy of the GNU General Public License
  19 ;;; along with Mes.  If not, see <http://www.gnu.org/licenses/>.
  20
  21 ;;; Commentary:
  22
  23 ;;; parser.mes is a translation of cgram.y to Dominique Boucher's LALR.
  24 ;;; It parses a minimal int main () {}, see examples/main.c
  25
  26 ;;; Code:
  27
  28 (cond-expand
  29   (guile
  30    ;;(use-modules (srfi srfi-1))
  31    (use-modules (system base lalr))
  32    ;;(use-modules (ice-9 match))
  33    )
  34   (mes
  35    (mes-use-module (mes lalr))))
  36
  37 (gc)
  38 (define c-parser
  39   (lalr-parser
  40
  41    (lbrace rbrace lparen rparen lbracket rbracket semicolon colon dot comma
  42            =
  43            Identifier NumericLiteral StringLiteral
  44            break case continue goto label
  45            return switch
  46            for
  47            If else
  48            (left: or && ! * / + -)
  49            (left: bool double float enum void int struct)
  50            (left: < > <= >=)
  51            (left: ++ --)
  52            (nonassoc: == !=)
  53            )
  54
  55    (program
  56     (translation-unit *eoi*) : `(root ,@$1))
  57
  58    (translation-unit
  59     (external-declaration) : `(,$1)
  60     (translation-unit external-declaration) : `(,@$1 ,@$2))
  61
  62    (external-declaration
  63     (function-definition) : $1
  64     (declaration) : $1
  65     (error semicolon) : (begin (syntax-error "external declaration" @1 $1) '()))
  66
  67    (function-definition
  68     (declarator compound-statement) : `(function ,$1 (signature int (formals)) ,$2)
  69     (declaration-specifiers declarator compound-statement) : `(function ,$2 (signature ,$1 (formals)) ,$3)
  70     (declaration-specifiers declarator declaration-list compound-statement) : `(function ,$2 (signature ,$1 ,$3) ,$4))
  71
  72    (declaration
  73     (declaration-specifiers semicolon) : `(,$1)
  74     (declaration-specifiers init-declarator-list semicolon): `((,@$1 ,@$2))
  75     )
  76
  77    (declaration-list
  78     (declaration) : `(formals ,@$1)
  79     (declaration-list declaration) : `(,@$1 ,@(cdr $2)))
  80
  81    (declaration-specifiers
  82     ;;(storage-class-specifier) : `(,$1)
  83     (type-specifier) : `(,$1)
  84     ;;(type-qualifier) : `($1)
  85     ;;(storage-class-specifier declaration-specifiers) : (cons $1 $2)
  86     (type-specifier declaration-specifiers) : `(,$1 ,$2)
  87     ;;(type-qualifier declaration-specifiers) : (cons $1 $2)
  88     )
  89
  90    ;; (storage_class_specifier
  91    ;;  (auto)
  92    ;;  (extern)
  93    ;;  (register)
  94    ;;  (static)
  95    ;;  (typedef))
  96
  97    (type-specifier
  98     ;; (char) : $1
  99     ;; (double) : $1
 100     ;; (void) : $1
 101     ;; (float)
 102     (int) : 'int
 103     ;; (long)
 104     ;; (short)
 105     ;; (unsigned)
 106     ;; (struct-or-enum-specifier)
 107     ;; (enum-specifier)
 108     ;; (type-name)
 109     )
 110
 111    ;; (type-qualifier
 112    ;;  (const)
 113    ;;  (volatile))
 114
 115    ;; struct_or_union_specifier:
 116    ;;              struct_or_union_ident lbrace struct_declaration_list rbrace
 117    ;;           |  struct_or_union_ident
 118    ;;           ;
 119
 120    ;; struct_or_union_ident: struct_or_union
 121    ;;           | struct_or_union Identifier
 122    ;;           ;
 123
 124    ;; struct_or_union:   STRUCT                         { ; }
 125    ;;           |  UNION                                { ; }
 126    ;;           ;
 127
 128    ;; struct_declaration_list: struct_declaration
 129    ;;           |  struct_declaration_list struct_declaration
 130    ;;           ;
 131
 132    (init-declarator-list
 133     ;; (init-declarator %prec comma) : `(,$1) HUH?
 134     (init-declarator) : `(,$1)
 135     (init-declarator-list comma init-declarator) : `(,$1)
 136     )
 137    ;; init_declarator_list:     init_declarator %prec comma
 138    ;;           |  init_declarator_list comma init_declarator
 139    ;;           ;
 140
 141    (init-declarator
 142     (declarator) : $1
 143     (declarator = initializer) : `(= ,$1 ,$3)
 144     ;;          | error { yyerror("init declarator error"); }
 145     )
 146
 147    ;; struct_declaration: specifier_qualifier_list struct_declarator_list semicolon
 148    ;;           ;
 149
 150    ;; specifier_qualifier_list: type_specifier
 151    ;;           |  type_qualifier
 152    ;;           |  type_specifier specifier_qualifier_list
 153    ;;           | type_qualifier specifier_qualifier_list
 154    ;;           ;
 155
 156    ;; struct_declarator_list: struct_declarator
 157    ;;           |  struct_declarator_list comma struct_declarator
 158    ;;           ;
 159
 160    ;; struct_declarator: declarator
 161    ;;           |  COLON constant_expression            { ; }
 162    ;;           |  declarator COLON constant_expression
 163    ;;           ;
 164
 165    ;; enum_specifier:      ENUM Identifier lbrace enumerator_list rbrace        { ; }
 166    ;;           |  ENUM lbrace enumerator_list rbrace           { ; }
 167    ;;           |  ENUM Identifier                              { ; }
 168    ;;           ;
 169
 170    ;; enumerator_list:   enumerator
 171    ;;           |  enumerator_list comma enumerator
 172    ;;           ;
 173
 174    ;; enumerator:                  Identifier
 175    ;;           |  Identifier EQ constant_expression
 176    ;;           ;
 177
 178    (declarator
 179     (direct-declarator) : $1
 180     ;;(pointer direct-declarator)
 181     )
 182
 183    (direct-declarator
 184     (Identifier) : $1
 185     ;; (lparen declarator rparen)
 186     ;; (direct-declarator lbracket rbracket)
 187     ;; (direct-declarator lbracket constant-expression rbracket)
 188     ;; (lbracket constant-expression rbracket)
 189     ;; (direct-declarator lparen parameter-type-list rparen)
 190     (direct-declarator lparen rparen) : $1
 191     ;; (direct-declarator lparen identifier-list rparen)
 192     )
 193
 194    ;; pointer:     STAR                                 { ; }
 195    ;;           |  STAR pointer                         { ; }
 196    ;;           |  STAR type_qualifier_list             { ; }
 197    ;;           |  STAR type_qualifier_list pointer     { ; }
 198    ;;           ;
 199
 200    ;; type_qualifier_list: type_qualifier
 201    ;;           |  type_qualifier_list type_qualifier
 202    ;;           ;
 203
 204    ;; parameter_type_list: parameter_list
 205    ;;           | parameter_list comma ELLIPSIS
 206    ;;           ;
 207
 208    ;; parameter_list:      parameter_declaration
 209    ;;           |  parameter_list comma parameter_declaration
 210    ;;           ;
 211
 212    ;; parameter_declaration:
 213    ;;              declaration_specifiers declarator
 214    ;;           |  declaration_specifiers
 215    ;;           |  declaration_specifiers abstract_declarator
 216    ;;           ;
 217
 218    ;; identifier_list:        Identifier
 219    ;;           |  identifier_list comma Identifier
 220    ;;           |  error { yyerror("identifier list error"); }
 221    ;;           ;
 222
 223    (initializer
 224     ;;(assignment-expression %prec comma) HUH?
 225     (assignment-expression) : $1
 226     ;; initializer:       assignment_expression %prec comma
 227     ;;          |  lbrace initializer_list rbrace               { ; }
 228     ;;          |  lbrace initializer_list comma rbrace         { ; }
 229     ;;          ;
 230     )
 231
 232    ;; initializer_list:         initializer %prec comma
 233    ;;           |  initializer_list comma initializer
 234    ;;           ;
 235
 236    ;; type_name:           specifier_qualifier_list
 237    ;;           |  specifier_qualifier_list abstract_declarator
 238    ;;           ;
 239
 240    ;; abstract_declarator:      pointer
 241    ;;           |  direct_abstract_declarator
 242    ;;           |  pointer direct_abstract_declarator
 243    ;;           ;
 244
 245    ;; direct_abstract_declarator:
 246    ;;              lparen abstract_declarator rparen            { ; }
 247    ;;           |  lbrace rbrace                                { ; }
 248    ;;           |  direct_abstract_declarator lbrace rbrace
 249    ;;           |  lbrace constant_expression rbrace            { ; }
 250    ;;           |  direct_abstract_declarator lbrace constant_expression rbrace
 251    ;;           |  lparen rparen                                { ; }
 252    ;;           |  direct_abstract_declarator lparen rparen
 253    ;;           |  lparen parameter_list rparen                 { ; }
 254    ;;           |  direct_abstract_declarator lparen parameter_list rparen
 255    ;;           ;
 256
 257
 258    (statement
 259     ;;(labeled-statement)
 260     (expression-statement) : $1
 261     (compound-statement) : $1
 262     ;;(selection-statement)
 263     (iteration-statement) : $1
 264     (jump-statement) : $1
 265     (semicolon) : '()
 266     (error semicolon) : (begin (syntax-error "statement error" @1 $1) '())
 267     (error rbrace) : (begin (syntax-error "statement error" @1 $1) '()))
 268
 269
 270    ;; labeled_statement:
 271    ;;              Identifier COLON statement
 272    ;;           |  CASE x COLON statement               { ; }
 273    ;;           |  DEFAULT COLON statement              { ; }
 274    ;;           ;
 275
 276    (expression-statement
 277     (x semicolon) : $1)
 278
 279    (compound-statement
 280     (lbrace rbrace) : '(compound)
 281     (lbrace declaration-list rbrace) : `(compound ,$2)
 282     (lbrace statement-list rbrace) :  `(compound ,@$2)
 283     (lbrace declaration-list statement-list rbrace) : `(compound ,$2 ,@$3))
 284
 285    (statement-list
 286     (statement) : `(,$1)
 287     (statement-list statement) : `(,@$1 ,$2))
 288
 289    ;; selection_statement:
 290    ;;              IF lparen x rparen statement                 { ; }
 291    ;;           |  IF lparen x rparen statement ELSE statement  { ; }
 292    ;;           |  SWITCH lparen x rparen statement             { ; }
 293    ;;           ;
 294
 295    (iteration-statement
 296     ;; iteration_statement:
 297     ;;             WHILE lparen x rparen statement              { ; }
 298     ;;          |  DO statement WHILE lparen x rparen semicolon { ; }
 299     (for lparen forcntrl rparen statement) : `(for ,@$3 ,$5))
 300
 301    (forcntrl
 302     ;;          | semicolon semicolon x                         { ; }
 303     ;;          | semicolon x semicolon                         { ; }
 304     ;;          | semicolon x semicolon x                               { ; }
 305     ;;          | x semicolon semicolon
 306     ;;          | x semicolon semicolon x
 307     ;;          | x semicolon x semicolon
 308     (x semicolon x semicolon x) : `((start ,$1) (test ,$3) (step ,$5)))
 309
 310    (jump-statement
 311     (goto Identifier semicolon) : `(goto ,$2)
 312     (continue semicolon) : '(continue)
 313     (break semicolon) : '(break)
 314     (return semicolon) : '(return)
 315     (return x semicolon) : `(return ,$2))
 316
 317    (x
 318     (assignment-expression) : $1
 319     (x comma assignment-expression) : `(,$1 ,@$3))
 320
 321    (assignment-expression
 322     (equality-expression) : $1 ;; skip some
 323     ;;(conditional-expression) : $1
 324     (unary-expression assignment-operator assignment-expression) : `(,$2 ,$1 ,$3))
 325
 326    (assignment-operator
 327     (=) : '=)
 328    ;;           |  PLUSEQ                               { ; }
 329    ;;           |  MINUSEQ                              { ; }
 330    ;;           |  MUEQ                                 { ; }
 331    ;;           |  DIVEQ                                { ; }
 332    ;;           |  MODEQ                                { ; }
 333    ;;           |  SLEQ                         { ; }
 334    ;;           |  SREQ                         { ; }
 335    ;;           |  ANEQ                         { ; }
 336    ;;           |  OREQ                         { ; }
 337    ;;           |  XOREQ                                { ; }
 338    ;;           ;
 339
 340    ;; conditional_expression: logical_or_expression
 341    ;;           |  logical_or_expression IF_THEN x COLON conditional_expression
 342    ;;           ;
 343
 344    ;; constant_expression: conditional_expression
 345    ;;           ;
 346
 347    ;; logical_or_expression: logical_and_expression
 348    ;;           |  logical_or_expression OROR logical_and_expression
 349    ;;           ;
 350
 351    ;; logical_and_expression: inclusive_or_expression
 352    ;;           |  logical_and_expression ANDAND inclusive_or_expression
 353    ;;           ;
 354
 355    ;; inclusive_or_expression: exclusive_or_expression
 356    ;;           |  inclusive_or_expression OR exclusive_or_expression
 357    ;;           ;
 358
 359    ;; exclusive_or_expression: and_expression
 360    ;;           |  exclusive_or_expression XOR and_expression
 361    ;;           ;
 362
 363    ;; and_expression: equality_expression
 364    ;;           |  and_expression AND equality_expression
 365    ;;           ;
 366
 367    (equality-expression
 368     (relational-expression) : $1
 369     (equality-expression == relational-expression) : `(== ,$1 ,$3)
 370     (equality-expression != relational-expression) : `(!= ,$1 ,$3))
 371
 372    (relational-expression
 373     (shift-expression) : $1
 374     (relational-expression < shift-expression) : `(< ,$1 ,$3)
 375     (relational-expression <= shift-expression) : `(<= ,$1 ,$3)
 376     (relational-expression > shift-expression) : `(> ,$1 ,$3)
 377     (relational-expression >= shift-expression) : `(>= ,$1 ,$3))
 378
 379    (shift-expression
 380     (unary-expression) : $1 ;; skip some
 381     ;; shift_expression: additive_expression
 382     ;;          |  shift_expression LTLT additive_expression
 383     ;;          |  shift_expression GTGT additive_expression
 384     ;;          ;
 385     )
 386    ;; additive_expression: multiplicative_expression
 387    ;;           |  additive_expression PLUS multiplicative_expression
 388    ;;           |  additive_expression MINUS multiplicative_expression
 389    ;;           ;
 390
 391    ;; multiplicative_expression: cast_expression
 392    ;;           |  multiplicative_expression STAR cast_expression
 393    ;;           |  multiplicative_expression DIV cast_expression
 394    ;;           |  multiplicative_expression MOD cast_expression
 395    ;;           ;
 396
 397    ;; cast_expression:   unary_expression
 398    ;;           |  lparen type_name rparen cast_expression      { ; }
 399    ;;           ;
 400
 401    (unary-expression
 402     (postfix-expression) : $1
 403     (++ unary-expression) : `(++x ,$2)
 404     (-- unary-expression) : `(--x ,$2)
 405    ;;           |  SIZEOF unary_expression              { ; }
 406    ;;           |  SIZEOF lparen type_name rparen %prec SIZEOF  { ; }
 407    ;;           |  STAR cast_expression                 { ; }
 408    ;;           |  AND cast_expression                  { ; }
 409    ;;           |  MINUS cast_expression                { ; }
 410    ;;           |  PLUS cast_expression                 { ; }
 411    ;;           |  NEG cast_expression                  { ; }
 412    ;;           |  NOT cast_expression                  { ; }
 413    ;;           ;
 414     )
 415
 416    (postfix-expression
 417     (primary-expression) : $1
 418     ;;          |  postfix_expression lbracket x rbracket
 419     (postfix-expression lparen rparen) : `(call ,$1 (arguments))
 420     (postfix-expression lparen argument-expression-list rparen) : `(call ,$1 ,$3)
 421     ;;          |  postfix_expression FOLLOW Identifier
 422     ;;          |  postfix_expression DOT Identifier
 423     (postfix-expression ++) : `(x++ ,$1)
 424     (postfix-expression --) : `(x-- ,$1)
 425     )
 426
 427    (primary-expression
 428     (Identifier): $1
 429     (NumericLiteral) : $1
 430     ;; INT_LITERAL
 431     ;; CHAR_LITERAL
 432     ;; FLOAT_LITERAL
 433     ;; STRING_LITERAL
 434     (StringLiteral) : $1
 435     ;; lparen x rparen
 436     )
 437    ;;
 438
 439    (argument-expression-list
 440     (assignment-expression) : `(arguments ,$1)
 441     (argument-expression-list comma assignment-expression): `(,@$1 ,@(cdr $3)))))