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 *array_expr = alloc_expression(token, EXPR_BINOP);
 105                         array_expr->op = '[';
 106                         array_expr->left = expr;
 107                         token = parse_expression(token->next, &array_expr->right);
 108                         token = expect(token, ']', "at end of array dereference");
 109                         expr = array_expr;
 110                         continue;
 111                 }
 112                 case SPECIAL_INCREMENT:         /* Post-increment */
 113                 case SPECIAL_DECREMENT: {       /* Post-decrement */
 114                         struct expression *post = alloc_expression(token, EXPR_POSTOP);
 115                         post->op = token->special;
 116                         post->unop = expr;
 117                         expr = post;
 118                         token = token->next;
 119                         continue;
 120                 }
 121                 case '.':                       /* Structure member dereference */
 122                 case SPECIAL_DEREFERENCE: {     /* Structure pointer member dereference */
 123                         struct expression *deref = alloc_expression(token, EXPR_DEREF);
 124                         deref->op = token->special;
 125                         deref->deref = expr;
 126                         token = token->next;
 127                         if (token->type != TOKEN_IDENT) {
 128                                 warn(token, "Expected member name");
 129                                 break;
 130                         }
 131                         deref->member = token;
 132                         token = token->next;
 133                         expr = deref;
 134                         continue;
 135                 }
 136
 137                 case '(': {                     /* Function call */
 138                         struct expression *call = alloc_expression(token, EXPR_BINOP);
 139                         call->op = '(';
 140                         call->left = expr;
 141                         token = comma_expression(token->next, &call->right);
 142                         token = expect(token, ')', "in function call");
 143                         expr = call;
 144                         continue;
 145                 }
 146
 147                 default:
 148                         break;
 149                 }
 150                 break;
 151         }
 152         *tree = expr;
 153         return token;
 154 }
 155
 156 static struct token *cast_expression(struct token *token, struct expression **tree);
 157 static struct token *unary_expression(struct token *token, struct expression **tree)
 158 {
 159         if (token->type == TOKEN_IDENT &&
 160             (token->ident == &sizeof_ident ||
 161              token->ident == &__alignof___ident)) {
 162                 struct expression *sizeof_ex = alloc_expression(token, EXPR_SIZEOF);
 163                 *tree = sizeof_ex;
 164                 tree = &sizeof_ex->unop;
 165                 token = token->next;
 166                 if (!match_op(token, '(') || !lookup_type(token->next))
 167                         return unary_expression(token, &sizeof_ex->cast_expression);
 168                 token = typename(token->next, &sizeof_ex->cast_type);
 169                 return expect(token, ')', "at end of sizeof type-name");
 170         }
 171
 172         if (token->type == TOKEN_SPECIAL) {
 173                 if (match_oplist(token->special,
 174                     SPECIAL_INCREMENT, SPECIAL_DECREMENT,
 175                     '&', '*', '+', '-', '~', '!', 0)) {
 176                         struct expression *unary = alloc_expression(token, EXPR_PREOP);
 177                         unary->op = token->special;
 178                         *tree = unary;
 179                         return cast_expression(token->next, &unary->unop);
 180                 }
 181         }
 182
 183         return postfix_expression(token, tree);
 184 }
 185
 186 /*
 187  * Ambiguity: a '(' can be either a cast-expression or
 188  * a primary-expression depending on whether it is followed
 189  * by a type or not.
 190  */
 191 static struct token *cast_expression(struct token *token, struct expression **tree)
 192 {
 193         if (match_op(token, '(')) {
 194                 struct token *next = token->next;
 195                 if (lookup_type(next)) {
 196                         struct expression *cast = alloc_expression(next, EXPR_CAST);
 197
 198                         token = typename(next, &cast->cast_type);
 199                         token = expect(token, ')', "at end of cast operator");
 200                         if (match_op(token, '{'))
 201                                 return initializer(token, &cast->cast_type->ctype);
 202                         token = cast_expression(token, &cast->cast_expression);
 203                         *tree = cast;
 204                         return token;
 205                 }
 206         }
 207         return unary_expression(token, tree);
 208 }
 209
 210 /* Generic left-to-right binop parsing */
 211 static struct token *lr_binop_expression(struct token *token, struct expression **tree,
 212         struct token *(*inner)(struct token *, struct expression **), ...)
 213 {
 214         struct expression *left = NULL;
 215         struct token * next = inner(token, &left);
 216
 217         if (left) {
 218                 while (next->type == TOKEN_SPECIAL) {
 219                         struct expression *top, *right = NULL;
 220                         int op = next->special;
 221                         va_list args;
 222
 223                         va_start(args, inner);
 224                         for (;;) {
 225                                 int nextop = va_arg(args, int);
 226                                 if (!nextop)
 227                                         goto out;
 228                                 if (op == nextop)
 229                                         break;
 230                         }
 231                         va_end(args);
 232                         top = alloc_expression(next, EXPR_BINOP);
 233                         next = inner(next->next, &right);
 234                         if (!right) {
 235                                 warn(next, "No right hand side of '%s'-expression", show_special(op));
 236                                 break;
 237                         }
 238                         top->op = op;
 239                         top->left = left;
 240                         top->right = right;
 241                         left = top;
 242                 }
 243         }
 244 out:
 245         *tree = left;
 246         return next;
 247 }
 248
 249 static struct token *multiplicative_expression(struct token *token, struct expression **tree)
 250 {
 251         return lr_binop_expression(token, tree, cast_expression, '*', '/', '%', 0);
 252 }
 253
 254 static struct token *additive_expression(struct token *token, struct expression **tree)
 255 {
 256         return lr_binop_expression(token, tree, multiplicative_expression, '+', '-', 0);
 257 }
 258
 259 static struct token *shift_expression(struct token *token, struct expression **tree)
 260 {
 261         return lr_binop_expression(token, tree, additive_expression, SPECIAL_LEFTSHIFT, SPECIAL_RIGHTSHIFT, 0);
 262 }
 263
 264 static struct token *relational_expression(struct token *token, struct expression **tree)
 265 {
 266         return lr_binop_expression(token, tree, shift_expression, '<', '>', SPECIAL_LTE, SPECIAL_GTE, 0);
 267 }
 268
 269 static struct token *equality_expression(struct token *token, struct expression **tree)
 270 {
 271         return lr_binop_expression(token, tree, relational_expression, SPECIAL_EQUAL, SPECIAL_NOTEQUAL, 0);
 272 }
 273
 274 static struct token *bitwise_and_expression(struct token *token, struct expression **tree)
 275 {
 276         return lr_binop_expression(token, tree, equality_expression, '&', 0);
 277 }
 278
 279 static struct token *bitwise_xor_expression(struct token *token, struct expression **tree)
 280 {
 281         return lr_binop_expression(token, tree, bitwise_and_expression, '^', 0);
 282 }
 283
 284 static struct token *bitwise_or_expression(struct token *token, struct expression **tree)
 285 {
 286         return lr_binop_expression(token, tree, bitwise_xor_expression, '|', 0);
 287 }
 288
 289 static struct token *logical_and_expression(struct token *token, struct expression **tree)
 290 {
 291         return lr_binop_expression(token, tree, bitwise_or_expression, SPECIAL_LOGICAL_AND, 0);
 292 }
 293
 294 static struct token *logical_or_expression(struct token *token, struct expression **tree)
 295 {
 296         return lr_binop_expression(token, tree, logical_and_expression, SPECIAL_LOGICAL_OR, 0);
 297 }
 298
 299 struct token *conditional_expression(struct token *token, struct expression **tree)
 300 {
 301         token = logical_or_expression(token, tree);
 302         if (match_op(token, '?')) {
 303                 struct expression *expr = alloc_expression(token, EXPR_CONDITIONAL);
 304                 expr->op = token->special;
 305                 expr->left = *tree;
 306                 *tree = expr;
 307                 token = parse_expression(token->next, &expr->cond_true);
 308                 token = expect(token, ':', "in conditional expression");
 309                 token = conditional_expression(token, &expr->cond_false);
 310         }
 311         return token;
 312 }
 313
 314 struct token *assignment_expression(struct token *token, struct expression **tree)
 315 {
 316         token = conditional_expression(token, tree);
 317         if (token->type == TOKEN_SPECIAL) {
 318                 static const int assignments[] = {
 319                         '=', SPECIAL_ADD_ASSIGN, SPECIAL_MINUS_ASSIGN,
 320                         SPECIAL_TIMES_ASSIGN, SPECIAL_DIV_ASSIGN,
 321                         SPECIAL_MOD_ASSIGN, SPECIAL_SHL_ASSIGN,
 322                         SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 323                         SPECIAL_OR_ASSIGN, SPECIAL_XOR_ASSIGN };
 324                 int i, op = token->special;
 325                 for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 326                         if (assignments[i] == op) {
 327                                 struct expression * expr = alloc_expression(token, EXPR_BINOP);
 328                                 expr->left = *tree;
 329                                 expr->op = op;
 330                                 *tree = expr;
 331                                 return assignment_expression(token->next, &expr->right);
 332                         }
 333         }
 334         return token;
 335 }
 336
 337 static struct token *comma_expression(struct token *token, struct expression **tree)
 338 {
 339         return lr_binop_expression(token, tree, assignment_expression, ',', 0);
 340 }
 341
 342 struct token *parse_expression(struct token *token, struct expression **tree)
 343 {
 344         return comma_expression(token,tree);
 345 }
 346
 347