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