parse.c

   1 /*
   2  * Stupid C parser, version 1e-6.
   3  *
   4  * Let's see how hard this is to do.
   5  */
   6 #include <stdarg.h>
   7 #include <stdlib.h>
   8 #include <stdio.h>
   9 #include <string.h>
  10 #include <ctype.h>
  11 #include <unistd.h>
  12 #include <fcntl.h>
  13
  14 #include "token.h"
  15 #include "parse.h"
  16
  17 void show_expression(struct expression *expr)
  18 {
  19         if (!expr)
  20                 return;
  21
  22         switch (expr->type) {
  23         case EXPR_BINOP:
  24                 printf("< ");
  25                 show_expression(expr->left);
  26                 printf(" %s ", show_special(expr->op));
  27                 show_expression(expr->right);
  28                 printf(" >");
  29                 break;
  30         case EXPR_PREOP:
  31                 printf("( ");
  32                 printf(" %s ", show_special(expr->op));
  33                 show_expression(expr->unop);
  34                 printf(" )");
  35                 break;
  36         case EXPR_POSTOP:
  37                 printf("( ");
  38                 show_expression(expr->unop);
  39                 printf(" %s ", show_special(expr->op));
  40                 printf(" )");
  41                 break;
  42         case EXPR_PRIMARY:
  43                 printf("%s", show_token(expr->token));
  44                 break;
  45         case EXPR_DEREF:
  46                 printf("< ");
  47                 show_expression(expr->deref);
  48                 printf("%s", show_special(expr->op));
  49                 printf("%s", show_token(expr->member));
  50                 printf(" >");
  51                 break;
  52         default:
  53                 printf("WTF");
  54         }
  55 }
  56
  57 static struct expression *alloc_expression(struct token *token, int type)
  58 {
  59         struct expression *expr = malloc(sizeof(struct expression));
  60
  61         if (!expr)
  62                 die("Unable to allocate expression");
  63         memset(expr, 0, sizeof(*expr));
  64         expr->type = type;
  65         expr->token = token;
  66         return expr;
  67 }
  68
  69 static struct token *expect(struct token *token, int op)
  70 {
  71         if (!token ||
  72              token->value.type != TOKEN_SPECIAL ||
  73              token->value.special != op) {
  74                 warn(token, "Expected %s", show_special(op));
  75                 return token;
  76         }
  77         return token->next;
  78 }
  79
  80 static struct token *comma_expression(struct token *, struct expression **);
  81
  82 static struct token *primary_expression(struct token *token, struct expression **tree)
  83 {
  84         struct expression *expr = NULL;
  85
  86         switch (token->value.type) {
  87         case TOKEN_IDENT:
  88         case TOKEN_INTEGER:
  89         case TOKEN_FP:
  90         case TOKEN_STRING:
  91                 expr = alloc_expression(token, EXPR_PRIMARY);
  92                 token = token->next;
  93                 break;
  94
  95         case TOKEN_SPECIAL:
  96                 if (token->value.special == '(') {
  97                         expr = alloc_expression(token, EXPR_PREOP);
  98                         expr->op = '(';
  99                         token = parse_expression(token->next, &expr->unop);
 100                         token = expect(token, ')');
 101                         break;
 102                 }
 103         /* Fallthrough */
 104         default:
 105                 warn(token, "Expected primary expression");
 106         }
 107         *tree = expr;
 108         return token;
 109 }
 110
 111 static struct token *postfix_expression(struct token *token, struct expression **tree)
 112 {
 113         struct expression *expr = NULL;
 114
 115         token = primary_expression(token, &expr);
 116         while (expr && token && token->value.type == TOKEN_SPECIAL) {
 117                 switch (token->value.special) {
 118                 case '[': {                     /* Array dereference */
 119                         struct expression *array_expr = alloc_expression(token, EXPR_BINOP);
 120                         array_expr->op = '[';
 121                         array_expr->left = expr;
 122                         token = parse_expression(token->next, &array_expr->right);
 123                         token = expect(token, ']');
 124                         expr = array_expr;
 125                         continue;
 126                 }
 127                 case SPECIAL_INCREMENT:         /* Post-increment */
 128                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 129                         struct expression *post = alloc_expression(token, EXPR_POSTOP);
 130                         post->op = token->value.special;
 131                         post->unop = expr;
 132                         expr = post;
 133                         token = token->next;
 134                         continue;
 135                 }
 136                 case '.':                       /* Structure member dereference */
 137                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 138                         struct expression *deref = alloc_expression(token, EXPR_DEREF);
 139                         deref->op = token->value.special;
 140                         deref->deref = expr;
 141                         token = token->next;
 142                         if (!token || token->value.type != TOKEN_IDENT) {
 143                                 warn(token, "Expected member name");
 144                                 break;
 145                         }
 146                         deref->member = token;
 147                         token = token->next;
 148                         expr = deref;
 149                         continue;
 150                 }
 151
 152                 case '(': {                     /* Function call */
 153                         struct expression *call = alloc_expression(token, EXPR_BINOP);
 154                         call->op = '(';
 155                         call->left = expr;
 156                         token = comma_expression(token->next, &call->right);
 157                         token = expect(token, ')');
 158                         expr = call;
 159                         continue;
 160                 }
 161
 162                 default:
 163                         break;
 164                 }
 165                 break;
 166         }
 167         *tree = expr;
 168         return token;
 169 }
 170
 171 static struct token *unary_expression(struct token *token, struct expression **tree)
 172 {
 173         return postfix_expression(token, tree);
 174 }
 175
 176 static struct token *cast_expression(struct token *token, struct expression **tree)
 177 {
 178         return unary_expression(token, tree);
 179 }
 180
 181 /* Generic left-to-right binop parsing */
 182 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 183         struct token *(*inner)(struct token *, struct expression **), ...)
 184 {
 185         struct expression *left = NULL;
 186         struct token * next = inner(token, &left);
 187
 188         if (left) {
 189                 while (next && next->value.type == TOKEN_SPECIAL) {
 190                         struct expression *top, *right = NULL;
 191                         int op = next->value.special;
 192                         va_list args;
 193
 194                         va_start(args, inner);
 195                         for (;;) {
 196                                 int nextop = va_arg(args, int);
 197                                 if (!nextop)
 198                                         goto out;
 199                                 if (op == nextop)
 200                                         break;
 201                         }
 202                         va_end(args);
 203                         top = alloc_expression(next, EXPR_BINOP);
 204                         next = inner(next->next, &right);
 205                         if (!right) {
 206                                 warn(token, "Syntax error");
 207                                 break;
 208                         }
 209                         top->op = op;
 210                         top->left = left;
 211                         top->right = right;
 212                         left = top;
 213                 }
 214         }
 215 out:
 216         *tree = left;
 217         return next;
 218 }
 219
 220 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 221 {
 222         return lr_binop_expression(token, tree, cast_expression, '*', '/', '%', 0);
 223 }
 224
 225 static struct token *additive_expression(struct token *token, struct expression **tree)
 226 {
 227         return lr_binop_expression(token, tree, multiplicative_expression, '+', '-', 0);
 228 }
 229
 230 static struct token *shift_expression(struct token *token, struct expression **tree)
 231 {
 232         return lr_binop_expression(token, tree, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 233 }
 234
 235 static struct token *relational_expression(struct token *token, struct expression **tree)
 236 {
 237         return lr_binop_expression(token, tree, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 238 }
 239
 240 static struct token *equality_expression(struct token *token, struct expression **tree)
 241 {
 242         return lr_binop_expression(token, tree, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 243 }
 244
 245 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 246 {
 247         return lr_binop_expression(token, tree, equality_expression, '&', 0);
 248 }
 249
 250 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 251 {
 252         return lr_binop_expression(token, tree, bitwise_and_expression, '^', 0);
 253 }
 254
 255 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 256 {
 257         return lr_binop_expression(token, tree, bitwise_xor_expression, '|', 0);
 258 }
 259
 260 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 261 {
 262         return lr_binop_expression(token, tree, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 263 }
 264
 265 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 266 {
 267         return lr_binop_expression(token, tree, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 268 }
 269
 270 struct token *comma_expression(struct token *token, struct expression **tree)
 271 {
 272         return lr_binop_expression(token, tree, logical_or_expression, ',', 0);
 273 }
 274
 275 struct token *parse_expression(struct token *token, struct expression **tree)
 276 {
 277         return comma_expression(token,tree);
 278 }