begriffs open source - sa-parse/blob - src/lisp.y

   1 /* lisp.y  (requires Bison) */
   2
   3 /* a "pure" api means communication variables like yylval
   4    won't be global variables, and yylex is assumed to
   5    have a different signature */
   6
   7 %define api.pure true
   8
   9 /* change prefix of symbols from yy to "lisp" to avoid
  10    clashes with any other parsers we may want to link */
  11
  12 %define api.prefix {lisp}
  13
  14 /* generate much more meaningful errors rather than the
  15    uninformative string "syntax error" */
  16
  17 %define parse.error verbose
  18
  19 /* Bison offers different %code insertion locations in
  20    addition to yacc's %{ %} construct.
  21
  22    The "top" location is good for headers and feature
  23    flags like the _XOPEN_SOURCE we use here */
  24
  25 %code top {
  26         /* XOPEN for strdup */
  27         #define _XOPEN_SOURCE 600
  28         #include <stdio.h>
  29         #include <stdlib.h>
  30         #include <string.h>
  31
  32         /* Bison versions 3.7.5 and above provide the YYNOMEM
  33            macro to allow our actions to signal the unlikely
  34            event that they couldn't allocate memory. Thanks
  35            to the Bison team for adding this feature at my
  36            request. :) YYNOMEM causes yyparse() to return 2.
  37
  38            The following conditional define allows us to use
  39            the functionality in earlier versions too. */
  40
  41         #ifndef YYNOMEM
  42         #define YYNOMEM goto yyexhaustedlab
  43         #endif
  44 }
  45
  46 /* The "requires" code location is designed for defining
  47    data types that we can use as yylval's for tokens. Code
  48    in this section is also added to the .tab.h file for
  49    inclusion by calling code */
  50
  51 %code requires {
  52         enum sexpr_type {
  53                 SEXPR_ID, SEXPR_NUM, SEXPR_PAIR, SEXPR_NIL
  54         };
  55
  56         struct sexpr
  57         {
  58                 enum sexpr_type type;
  59                 union
  60                 {
  61                         int   num;
  62                         char *id;
  63                 } value;
  64                 struct sexpr *left, *right;
  65         };
  66 }
  67
  68 /* These are the semantic types available for tokens,
  69    which we name num, str, and node.
  70
  71    The %union construction is classic yacc as well. It
  72    generates a C union and sets its as the YYSTYPE, which
  73    will be the type of yylval */
  74
  75 %union
  76 {
  77         int num;
  78         char *str;
  79         struct sexpr *node;
  80 }
  81
  82 /* Add another argument in yyparse() so that we
  83    can communicate the parsed result to the caller.
  84    We can't return the result directly, since the
  85    return value is already reserved as an int, with
  86    0=success, 1=error, 2=nomem
  87
  88    NOTE
  89    In our case, the param is a data pointer. However,
  90    if it were a function pointer (such as a callback),
  91    then its type would have to be put behind a typedef,
  92    or else parse-param will mangle the declaration. */
  93
  94 %parse-param {struct sexpr **result}
  95
  96 /* param adds an extra param to yyparse (like parse-param)
  97    but also causes yyparse to send the value to yylex.
  98    In our case the caller will initialize their own scanner
  99    instance and pass it through */
 100
 101 %param {void *scanner}
 102
 103 /* the "provides" location adds the code to our generated
 104    parser, but also to the .tab.h file for use by callers */
 105
 106 %code provides {
 107         void sexpr_free(struct sexpr *s);
 108 }
 109
 110 /* unqualified %code is for internal use, things that
 111    our actions can see. These declarations prevent
 112    warnings.  Notice the final param in each that came
 113    from the %param directive above */
 114
 115 %code {
 116         int lisperror(void *foo, char const *msg, const void *s);
 117         int lisplex(void *lval, const void *s);
 118 }
 119
 120 /* Now when we declare tokens, we add their type
 121    in brackets. The type names come from our %union */
 122
 123 %token <str> ID
 124 %token <num> NUM
 125
 126 /* whereas tokens come from the lexer, these
 127    non-terminals are defined in the parser, and
 128    we set their types with %type */
 129
 130 %type <node> start sexpr pair list members atom
 131
 132 /* if there's an error partway through parsing, the
 133    caller wouldn't get a chance to free memory for
 134    the work in progress. Bison will clean up the memory
 135    if we provide destructors, though. */
 136
 137 %destructor { free($$); } <str>
 138 %destructor { sexpr_free($$); } <node>
 139
 140 %%
 141
 142  /* once again we use a dummy non-terminal to perform
 143     a side-effect, in this case setting *result */
 144
 145 start :
 146   sexpr   { *result = $$ = $1; return 0; }
 147 ;
 148
 149 sexpr :
 150   atom
 151 | list
 152 | pair
 153 ;
 154
 155 list :
 156
 157   /* This is a shortcut: we use the ascii value for
 158      parens '('=40, ')'=41 as their token codes.
 159      Thus we don't have to define a bunch of crap
 160      manually like LPAREN, RPAREN */
 161
 162   '(' members ')' { $$ = $2; }
 163
 164 | '('')' {
 165         struct sexpr *nil = malloc(sizeof *nil);
 166         if (!nil) YYNOMEM;
 167         *nil = (struct sexpr){.type = SEXPR_NIL};
 168         $$ = nil;
 169   }
 170 ;
 171
 172 members :
 173   sexpr {
 174         struct sexpr *s = malloc(sizeof *s),
 175                                  *nil = malloc(sizeof *nil);
 176         if (!s || !nil) {
 177                 free(s), free(nil);
 178                 YYNOMEM;
 179         }
 180         *nil = (struct sexpr){.type = SEXPR_NIL};
 181
 182         /* convention: we assume that a previous parser
 183            value like $1 is non-NULL, else it would have
 184            died already with YYNOMEM. We're responsible
 185            for checking only our own allocations */
 186
 187         *s = (struct sexpr){
 188                 .type = SEXPR_PAIR,
 189                 .left = $1,
 190                 .right = nil
 191         };
 192         $$ = s;
 193   }
 194 | sexpr members {
 195         struct sexpr *s = malloc(sizeof *s);
 196
 197         /* Another important memory convention: we
 198            can't trust that our lexer successfully
 199            allocated its yylvalue, because the signature
 200            of yylex doesn't communicate failure. We
 201            assume NULL in $1 means alloc failure and
 202            we report that. The only other way to signal
 203            from yylex would be to make a fake token to
 204            represent out-of-memory, but that's harder */
 205
 206         if (!s) YYNOMEM;
 207         *s = (struct sexpr){
 208                 .type = SEXPR_PAIR,
 209                 .left = $1,
 210                 .right = $2
 211         };
 212         $$ = s;
 213   }
 214 ;
 215
 216 pair :
 217   '(' sexpr '.' sexpr ')' {
 218         struct sexpr *s = malloc(sizeof *s);
 219         if (!s) YYNOMEM;
 220         *s = (struct sexpr){
 221                 .type = SEXPR_PAIR,
 222                 .left = $2,
 223                 .right = $4
 224         };
 225         $$ = s;
 226   }
 227 ;
 228
 229 atom :
 230   ID {
 231         if (!$1) YYNOMEM;
 232
 233         struct sexpr *s = malloc(sizeof *s);
 234         if (!s) YYNOMEM;
 235         *s = (struct sexpr){
 236                 .type = SEXPR_ID,
 237                 .value.id = strdup($1)
 238         };
 239         if (!s->value.id)
 240         {
 241                 free(s);
 242                 YYNOMEM;
 243         }
 244         $$ = s;
 245   }
 246 | NUM {
 247         struct sexpr *s = malloc(sizeof *s);
 248         if (!s) YYNOMEM;
 249         *s = (struct sexpr){
 250                 .type = SEXPR_NUM,
 251                 .value.num = $1
 252         };
 253         $$ = s;
 254   }
 255 ;
 256
 257 %%
 258
 259 /* notice the extra parameters required
 260    by %param and %parse-param */
 261
 262 int lisperror(void *yylval, char const *msg, const void *s)
 263 {
 264         (void)yylval;
 265         (void)s;
 266         return fprintf(stderr, "%s\n", msg);
 267 }
 268
 269 /* useful internally by us, and externally by callers */
 270
 271 void sexpr_free(struct sexpr *s)
 272 {
 273         if (!s)
 274                 return;
 275
 276         if (s->type == SEXPR_ID)
 277                 free(s->value.id);
 278         else if (s->type == SEXPR_PAIR)
 279         {
 280                 sexpr_free(s->left);
 281                 sexpr_free(s->right);
 282         }
 283         free(s);
 284 }