expression.c

   1 /*
   2  * sparse/expression.c
   3  *
   4  * Copyright (C) 2003 Linus Torvalds, all rights reserved.
   5  *
   6  * This is the expression parsing part of parsing C.
   7  */
   8 #include <stdarg.h>
   9 #include <stdlib.h>
  10 #include <stdio.h>
  11 #include <string.h>
  12 #include <ctype.h>
  13 #include <unistd.h>
  14 #include <fcntl.h>
  15
  16 #include "lib.h"
  17 #include "token.h"
  18 #include "parse.h"
  19 #include "symbol.h"
  20 #include "scope.h"
  21 #include "expression.h"
  22
  23 static int match_oplist(int op, ...)
  24 {
  25         va_list args;
  26
  27         va_start(args, op);
  28         for (;;) {
  29                 int nextop = va_arg(args, int);
  30                 if (!nextop)
  31                         return 0;
  32                 if (op == nextop)
  33                         return 1;
  34         }
  35 }
  36
  37 static struct token *comma_expression(struct token *, struct expression **);
  38
  39 struct token *parens_expression(struct token *token, struct expression **expr, const char *where)
  40 {
  41         token = expect(token, '(', where);
  42         if (match_op(token, '{')) {
  43                 struct expression *e = alloc_expression(token, EXPR_STATEMENT);
  44                 struct statement *stmt = alloc_statement(token, STMT_COMPOUND);
  45                 *expr = e;
  46                 e->statement = stmt;
  47                 start_symbol_scope();
  48                 token = compound_statement(token->next, stmt);
  49                 end_symbol_scope();
  50                 token = expect(token, '}', "at end of statement expression");
  51         } else
  52                 token = parse_expression(token, expr);
  53         return expect(token, ')', where);
  54 }
  55
  56 struct token *primary_expression(struct token *token, struct expression **tree)
  57 {
  58         struct expression *expr = NULL;
  59
  60         switch (token->type) {
  61         case TOKEN_INTEGER:
  62         case TOKEN_FP:
  63         case TOKEN_CHAR:
  64                 expr = alloc_expression(token, EXPR_CONSTANT);
  65                 token = token->next;
  66                 break;
  67
  68         case TOKEN_IDENT: {
  69                 expr = alloc_expression(token, EXPR_SYMBOL);
  70                 expr->symbol = lookup_symbol(token->ident, NS_SYMBOL);
  71                 token = token->next;
  72                 break;
  73         }
  74
  75         case TOKEN_STRING:
  76                 expr = alloc_expression(token, EXPR_CONSTANT);
  77                 do {
  78                         token = token->next;
  79                 } while (token->type == TOKEN_STRING);
  80                 break;
  81
  82         case TOKEN_SPECIAL:
  83                 if (token->special == '(') {
  84                         expr = alloc_expression(token, EXPR_PREOP);
  85                         expr->op = '(';
  86                         token = parens_expression(token, &expr->unop, "in expression");
  87                         break;
  88                 }
  89         default:
  90                 ;
  91         }
  92         *tree = expr;
  93         return token;
  94 }
  95
  96 static struct token *postfix_expression(struct token *token, struct expression **tree)
  97 {
  98         struct expression *expr = NULL;
  99
 100         token = primary_expression(token, &expr);
 101         while (expr && token->type == TOKEN_SPECIAL) {
 102                 switch (token->special) {
 103                 case '[': {                     /* Array dereference */
 104                         struct expression *deref = alloc_expression(token, EXPR_PREOP);
 105                         struct expression *add = alloc_expression(token, EXPR_BINOP);
 106
 107                         deref->op = '*';
 108                         deref->unop = add;
 109
 110                         add->op = '+';
 111                         add->left = expr;
 112                         token = parse_expression(token->next, &add->right);
 113                         token = expect(token, ']', "at end of array dereference");
 114                         expr = deref;
 115                         continue;
 116                 }
 117                 case SPECIAL_INCREMENT:         /* Post-increment */
 118                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 119                         struct expression *post = alloc_expression(token, EXPR_POSTOP);
 120                         post->op = token->special;
 121                         post->unop = expr;
 122                         expr = post;
 123                         token = token->next;
 124                         continue;
 125                 }
 126                 case '.':                       /* Structure member dereference */
 127                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 128                         struct expression *deref = alloc_expression(token, EXPR_DEREF);
 129                         deref->op = token->special;
 130                         deref->deref = expr;
 131                         token = token->next;
 132                         if (token->type != TOKEN_IDENT) {
 133                                 warn(token, "Expected member name");
 134                                 break;
 135                         }
 136                         deref->member = token;
 137                         token = token->next;
 138                         expr = deref;
 139                         continue;
 140                 }
 141
 142                 case '(': {                     /* Function call */
 143                         struct expression *call = alloc_expression(token, EXPR_CALL);
 144                         call->op = '(';
 145                         call->left = expr;
 146                         token = comma_expression(token->next, &call->right);
 147                         token = expect(token, ')', "in function call");
 148                         expr = call;
 149                         continue;
 150                 }
 151
 152                 default:
 153                         break;
 154                 }
 155                 break;
 156         }
 157         *tree = expr;
 158         return token;
 159 }
 160
 161 static struct token *cast_expression(struct token *token, struct expression **tree);
 162 static struct token *unary_expression(struct token *token, struct expression **tree)
 163 {
 164         if (token->type == TOKEN_IDENT &&
 165             (token->ident == &sizeof_ident ||
 166              token->ident == &__alignof___ident)) {
 167                 struct expression *sizeof_ex = alloc_expression(token, EXPR_SIZEOF);
 168                 *tree = sizeof_ex;
 169                 tree = &sizeof_ex->unop;
 170                 token = token->next;
 171                 if (!match_op(token, '(') || !lookup_type(token->next))
 172                         return unary_expression(token, &sizeof_ex->cast_expression);
 173                 token = typename(token->next, &sizeof_ex->cast_type);
 174                 return expect(token, ')', "at end of sizeof type-name");
 175         }
 176
 177         if (token->type == TOKEN_SPECIAL) {
 178                 if (match_oplist(token->special,
 179                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 180                     '&', '*', '+', '-', '~', '!', 0)) {
 181                         struct expression *unary = alloc_expression(token, EXPR_PREOP);
 182                         unary->op = token->special;
 183                         *tree = unary;
 184                         return cast_expression(token->next, &unary->unop);
 185                 }
 186         }
 187
 188         return postfix_expression(token, tree);
 189 }
 190
 191 /*
 192  * Ambiguity: a '(' can be either a cast-expression or
 193  * a primary-expression depending on whether it is followed
 194  * by a type or not.
 195  */
 196 static struct token *cast_expression(struct token *token, struct expression **tree)
 197 {
 198         if (match_op(token, '(')) {
 199                 struct token *next = token->next;
 200                 if (lookup_type(next)) {
 201                         struct expression *cast = alloc_expression(next, EXPR_CAST);
 202
 203                         token = typename(next, &cast->cast_type);
 204                         token = expect(token, ')', "at end of cast operator");
 205                         if (match_op(token, '{'))
 206                                 return initializer(token, &cast->cast_type->ctype);
 207                         token = cast_expression(token, &cast->cast_expression);
 208                         *tree = cast;
 209                         return token;
 210                 }
 211         }
 212         return unary_expression(token, tree);
 213 }
 214
 215 /* Generic left-to-right binop parsing */
 216 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 217         struct token *(*inner)(struct token *, struct expression **), ...)
 218 {
 219         struct expression *left = NULL;
 220         struct token * next = inner(token, &left);
 221
 222         if (left) {
 223                 while (next->type == TOKEN_SPECIAL) {
 224                         struct expression *top, *right = NULL;
 225                         int op = next->special;
 226                         va_list args;
 227
 228                         va_start(args, inner);
 229                         for (;;) {
 230                                 int nextop = va_arg(args, int);
 231                                 if (!nextop)
 232                                         goto out;
 233                                 if (op == nextop)
 234                                         break;
 235                         }
 236                         va_end(args);
 237                         top = alloc_expression(next, EXPR_BINOP);
 238                         next = inner(next->next, &right);
 239                         if (!right) {
 240                                 warn(next, "No right hand side of '%s'-expression", show_special(op));
 241                                 break;
 242                         }
 243                         top->op = op;
 244                         top->left = left;
 245                         top->right = right;
 246                         left = top;
 247                 }
 248         }
 249 out:
 250         *tree = left;
 251         return next;
 252 }
 253
 254 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 255 {
 256         return lr_binop_expression(token, tree, cast_expression, '*', '/', '%', 0);
 257 }
 258
 259 static struct token *additive_expression(struct token *token, struct expression **tree)
 260 {
 261         return lr_binop_expression(token, tree, multiplicative_expression, '+', '-', 0);
 262 }
 263
 264 static struct token *shift_expression(struct token *token, struct expression **tree)
 265 {
 266         return lr_binop_expression(token, tree, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 267 }
 268
 269 static struct token *relational_expression(struct token *token, struct expression **tree)
 270 {
 271         return lr_binop_expression(token, tree, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 272 }
 273
 274 static struct token *equality_expression(struct token *token, struct expression **tree)
 275 {
 276         return lr_binop_expression(token, tree, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 277 }
 278
 279 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 280 {
 281         return lr_binop_expression(token, tree, equality_expression, '&', 0);
 282 }
 283
 284 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 285 {
 286         return lr_binop_expression(token, tree, bitwise_and_expression, '^', 0);
 287 }
 288
 289 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 290 {
 291         return lr_binop_expression(token, tree, bitwise_xor_expression, '|', 0);
 292 }
 293
 294 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 295 {
 296         return lr_binop_expression(token, tree, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 297 }
 298
 299 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 300 {
 301         return lr_binop_expression(token, tree, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 302 }
 303
 304 struct token *conditional_expression(struct token *token, struct expression **tree)
 305 {
 306         token = logical_or_expression(token, tree);
 307         if (match_op(token, '?')) {
 308                 struct expression *expr = alloc_expression(token, EXPR_CONDITIONAL);
 309                 expr->op = token->special;
 310                 expr->left = *tree;
 311                 *tree = expr;
 312                 token = parse_expression(token->next, &expr->cond_true);
 313                 token = expect(token, ':', "in conditional expression");
 314                 token = conditional_expression(token, &expr->cond_false);
 315         }
 316         return token;
 317 }
 318
 319 struct token *assignment_expression(struct token *token, struct expression **tree)
 320 {
 321         token = conditional_expression(token, tree);
 322         if (token->type == TOKEN_SPECIAL) {
 323                 static const int assignments[] = {
 324                         '=', SPECIAL_ADD_ASSIGN, SPECIAL_MINUS_ASSIGN,
 325                         SPECIAL_TIMES_ASSIGN, SPECIAL_DIV_ASSIGN,
 326                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 327                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 328                         SPECIAL_OR_ASSIGN, SPECIAL_XOR_ASSIGN };
 329                 int i, op = token->special;
 330                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 331                         if (assignments[i] == op) {
 332                                 struct expression * expr = alloc_expression(token, EXPR_BINOP);
 333                                 expr->left = *tree;
 334                                 expr->op = op;
 335                                 *tree = expr;
 336                                 return assignment_expression(token->next, &expr->right);
 337                         }
 338         }
 339         return token;
 340 }
 341
 342 static struct token *comma_expression(struct token *token, struct expression **tree)
 343 {
 344         return lr_binop_expression(token, tree, assignment_expression, ',', 0);
 345 }
 346
 347 struct token *parse_expression(struct token *token, struct expression **tree)
 348 {
 349         return comma_expression(token,tree);
 350 }
 351
 352