parse.c 14.3 KB
Newer Older
1 2 3
/* $Id$ $Revision$ */
/* vim:set shiftwidth=4 ts=8: */

ellson's avatar
ellson committed
4 5 6 7 8 9 10 11 12
/*************************************************************************
 * Copyright (c) 2011 AT&T Intellectual Property 
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors: See CVS logs. Details at http://www.graphviz.org/
 *************************************************************************/
13

14
/* Lefteris Koutsofios - AT&T Labs Research */
15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42

#include "common.h"
#include "mem.h"
#include "code.h"
#include "tbl.h"
#include "lex.h"
#include "parse.h"
#include "internal.h"

static jmp_buf eljbuf;

#define GTOKIFEQ(t) { \
    if (Ltok == (t)) \
        Lgtok (); \
    else \
        err ("expected token: '%s', found: '%s'", Lnames[t], Lnames[Ltok]); \
}

typedef struct lv_t {
    int si, vi;
} lv_t;
static lv_t *lvp;
static int lvn, flvi, llvi;
#define GETLVSTR(i) (char *) Cgetstring (lvp[i].si)
#define GETLVNUM(i) lvp[i].vi
#define LVINCR 1000
#define LVSIZE sizeof (lv_t)

43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67
static int pexpr (void);
static int getop (int, int);
static int pexpi (int);
static int pexp5 (void);
static int pexp6 (void);
static int pexp7 (void);
static int pargs (void);
static int pcons (void);
static int pvar (void);
static int pfunc (void);
static int pdecl (int *);
static int ptcons (void);
static int pstmt (void);
static int pifst (void);
static int pwhilest (void);
static int pforst (void);
static int pbreakst (void);
static int pcontinuest (void);
static int preturnst (void);

static void addlv (int, int);
static void err (char *, ...);

void Pinit (void) {
    lvp = Marrayalloc ((long) LVINCR * LVSIZE);
68 69 70 71
    lvn = LVINCR;
    flvi = llvi = 0;
}

72 73
void Pterm (void) {
    Marrayfree (lvp);
74 75 76 77
    lvp = NULL;
    lvn = flvi = llvi = 0;
}

78
Tobj Punit (Psrc_t *sp) {
79 80
    int ui, ei;

81 82
    Lsetsrc (sp->flag, sp->s, sp->fp, sp->tok, sp->lnum);
    Creset ();
83 84
    flvi = llvi = 0;

85 86
    if (setjmp (eljbuf) != 0)
        return NULL;
87 88

    while (Ltok == L_SEMI)
89
        Lgtok ();
90
    if (Ltok == L_EOF)
91
        return NULL;
92

93 94 95 96 97
    ui = Cnew (C_CODE);
    ei = pexpr ();
    Csetfp (ui, ei);
    Lgetsrc (&sp->flag, &sp->s, &sp->fp, &sp->tok, &sp->lnum);
    return Tcode (cbufp, 0, cbufi);
98 99
}

100 101
/*  shortcut: this function creates a piece of code that corresponds to
    <internal func name> = function () internal "<internal func name>";
102
*/
103
Tobj Pfunction (char *ifnam, int ifnum) {
104 105
    int ui, ai, vi, si, fi, li1, li2, di, ifi, ifn;

106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129
    Creset ();
    ui = Cnew (C_CODE);
    ai = Cnew (C_ASSIGN);
    Csetfp (ui, ai);
    vi = Cnew (C_GVAR);
    si = Cstring (ifnam);
    Csetfp (vi, si);
    Csetfp (ai, vi);
    fi = Cnew (C_FUNCTION);
    Csetnext (vi, fi);
    li1 = Cinteger (0);
    Csetfp (fi, li1);
    li2 = Cinteger (0);
    Csetnext (li1, li2);
    di = Cnew (C_DECL);
    Csetfp (di, C_NULL);
    Csetnext (li2, di);
    ifi = Cnew (C_INTERNAL);
    ifn = Cinteger ((long) ifnum);
    Csetfp (ifi, ifn);
    Csetnext (di, ifi);
    Csetinteger (li1, (long) (Cgetindex () - fi));
    Csetinteger (li2, 0);
    return Tcode (cbufp, 0, cbufi);
130 131
}

132 133
/*  shortcut: this function creates a piece of code that corresponds to
    <func name> (<args>); where <args> is the second argument (ao)
134
*/
135
Tobj Pfcall (Tobj fo, Tobj ao) {
136 137
    int ui, fi, ffi, ai, aai;

138 139 140 141 142 143 144 145 146
    Creset ();
    ui = Cnew (C_CODE);
    fi = Cnew (C_FCALL);
    Csetfp (ui, fi);
    ffi = Cnew (C_PVAR);
    Csetobject (ffi, fo);
    Csetfp (fi, ffi);
    ai = Cnew (C_ARGS);
    Csetnext (ffi, ai);
147
    if (ao) {
148 149 150
        aai = Cnew (C_PVAR);
        Csetobject (aai, ao);
        Csetfp (ai, aai);
151
    } else
152 153
        Csetfp (ai, C_NULL);
    return Tcode (cbufp, 0, cbufi);
154 155
}

156
static int pexpr (void) {
157 158
    int ai, ei0, ei1;

159
    ei0 = pexpi (0);
160
    if (Ltok != C_ASSIGN)
161
        return ei0;
162

163 164 165 166 167
    ai = Cnew (C_ASSIGN);
    Csetfp (ai, ei0);
    Lgtok ();
    ei1 = pexpr ();
    Csetnext (ei0, ei1);
168 169 170 171
    return ai;
}

static int lextab[][7] = {
172 173 174 175 176 177
    {   L_OR,       0,     0,    0,    0,    0, 0 },
    {  L_AND,       0,     0,    0,    0,    0, 0 },
    {   L_EQ,    L_NE,  L_LT, L_LE, L_GT, L_GE, 0 },
    { L_PLUS, L_MINUS,     0,    0,    0,    0, 0 },
    {  L_MUL,   L_DIV, L_MOD,    0,    0,    0, 0 },
    {      0,       0,     0,    0,    0,    0, 0 }
178 179 180
};

static int parsetab[][7] = {
181 182 183 184 185 186
    {   C_OR,       0,     0,    0,    0,    0, 0 },
    {  C_AND,       0,     0,    0,    0,    0, 0 },
    {   C_EQ,    C_NE,  C_LT, C_LE, C_GT, C_GE, 0 },
    { C_PLUS, C_MINUS,     0,    0,    0,    0, 0 },
    {  C_MUL,   C_DIV, C_MOD,    0,    0,    0, 0 },
    {      0,       0,     0,    0,    0,    0, 0 }
187 188
};

189
static int getop (int t, int i) {
190 191 192
    int j;

    for (j = 0; lextab[i][j] != 0; j++)
193 194
        if (t == lextab[i][j])
            return parsetab[i][j];
195 196 197
    return -1;
}

198
static int pexpi (int k) {
199 200 201
    int ei0, ei1, ei2, ptok;

    if (lextab[k][0] == 0)
202 203 204 205 206 207 208 209 210 211
        return pexp5 ();

    ei0 = pexpi (k + 1);
    while ((ptok = getop (Ltok, k)) != -1) {
        ei1 = Cnew (ptok);
        Csetfp (ei1, ei0);
        Lgtok ();
        ei2 = pexpi (k + 1);
        Csetnext (ei0, ei2);
        ei0 = ei1;
212 213 214 215
    }
    return ei0;
}

216
static int pexp5 (void) {
217 218 219
    int ei0, ei1;

    if (Ltok == L_MINUS) {
220 221 222 223 224
        ei0 = Cnew (C_UMINUS);
        Lgtok ();
        ei1 = pexp5 ();
        Csetfp (ei0, ei1);
        return ei0;
225
    }
226
    return pexp6 ();
227 228
}

229
static int pexp6 (void) {
230 231 232
    int ei0, ei1;

    if (Ltok == L_NOT) {
233 234 235 236 237
        ei0 = Cnew (C_NOT);
        Lgtok ();
        ei1 = pexp6 ();
        Csetfp (ei0, ei1);
        return ei0;
238
    }
239
    return pexp7 ();
240 241
}

242 243
static int pexp7 (void) {
    int ei0, ei1, ei2;
244

245
    ei0 = 0;
246 247
    switch (Ltok) {
    case L_FUNCTION:
248 249 250
        Lgtok ();
        ei0 =  pfunc ();
        break;
251
    case L_LP:
252 253 254 255 256 257
        ei0 = Cnew (C_PEXPR);
        Lgtok ();
        ei1 = pexpr ();
        GTOKIFEQ (L_RP);
        Csetfp (ei0, ei1);
        break;
258
    case L_LB:
259 260
        ei0 = ptcons ();
        break;
261 262
    case L_STRING:
    case L_NUMBER:
263 264
        ei0 = pcons ();
        break;
265
    case L_ID:
266 267 268 269 270 271 272 273 274 275 276
        ei0 = pvar ();
        if (Ltok == L_LP) { /* ie: it's really a function call */
            ei1 = ei0;
            ei0 = Cnew (C_FCALL);
            Csetfp (ei0, ei1);
            Lgtok ();
            ei2 = pargs ();
            Csetnext (ei1, ei2);
            GTOKIFEQ (L_RP);
        }
        break;
277
    default:
278
        err ("expected EXP7 type token, found: %s", Lnames[Ltok]);
279 280 281 282
    }
    return ei0;
}

283
static int pargs (void) {
284 285
    int ai, ei0, ei1;

286
    ai = Cnew (C_ARGS);
287
    if (Ltok == L_RP) {
288 289
        Csetfp (ai, C_NULL);
        return ai;
290
    }
291 292
    ei0 = pexpr ();
    Csetfp (ai, ei0);
293
    while (Ltok != L_RP) {
294 295 296
        GTOKIFEQ (L_COMMA);
        if (Ltok == L_RP)
            err ("expected expression, found: %s", Lnames[Ltok]);
297

298 299 300
        ei1 = pexpr ();
        Csetnext (ei0, ei1);
        ei0 = ei1;
301 302 303 304
    }
    return ai;
}

305 306
static int pcons (void) {
    int ci;
307 308
    double d;

309
    ci = 0;
310 311
    switch (Ltok) {
    case L_NUMBER:
312 313 314
        d = atof (Lstrtok);
        ci = (d == (double) (long) d) ? Cinteger ((long) d) : Creal (d);
        break;
315
    case L_STRING:
316 317
        ci = Cstring (Lstrtok);
        break;
318
    default:
319
        err ("expected scalar constant, found: %s", Lnames[Ltok]);
320
    }
321
    Lgtok ();
322 323 324
    return ci;
}

325
static int pvar (void) {
326 327
    int vi, ci0, ci1, i;

328 329 330
    vi = Cnew (C_GVAR);
    ci0 = Cstring (Lstrtok);
    Csetfp (vi, ci0);
331
    for (i = flvi; i < llvi; i++) {
332 333 334 335 336 337 338
        if (strcmp (GETLVSTR (i), Lstrtok) == 0) {
            Csettype (vi, C_LVAR);
            ci1 = Cinteger ((long) GETLVNUM (i));
            Csetnext (ci0, ci1);
            ci0 = ci1;
            break;
        }
339
    }
340
    Lgtok ();
341
    if (Ltok != L_DOT && Ltok != L_LB)
342
        return vi;
343 344

    while (Ltok == L_DOT || Ltok == L_LB) {
345 346 347 348 349 350 351 352 353 354 355 356 357 358
        if (Ltok == L_DOT) {
            Lgtok ();
            if (Ltok != L_ID)
                err ("expected identifier, found: %s", Lnames[Ltok]);
            ci1 = Cstring (Lstrtok);
            Csetnext (ci0, ci1);
            Lgtok ();
        } else {
            Lgtok ();
            ci1 = pexpr ();
            Csetnext (ci0, ci1);
            GTOKIFEQ (L_RB);
        }
        ci0 = ci1;
359 360 361 362
    }
    return vi;
}

363
static int pfunc (void) {
364 365 366
    int fi, di, si, ifi, ifn, ldi, i, li1, li2;
    int owncbufi, ownflvi, ownllvi, flvn, ifnum;

367
    owncbufi = Cgetindex ();
368 369 370 371
    ownflvi = flvi, ownllvi = llvi;
    flvi = llvi;
    flvn = 0;

372 373 374 375 376 377 378 379
    fi = Cnew (C_FUNCTION);
    GTOKIFEQ (L_LP);
    li1 = Cinteger (0);
    Csetfp (fi, li1);
    li2 = Cinteger (0);
    Csetnext (li1, li2);
    di = pdecl (&flvn);
    Csetnext (li2, di);
380
    i = di;
381
    GTOKIFEQ (L_RP);
382
    if (Ltok == L_INTERNAL) {
383 384 385 386 387 388 389 390 391 392 393
        Lgtok ();
        if (Ltok == L_STRING) {
            if ((ifnum = Igetfunc (Lstrtok)) == -1)
                err ("no such internal function: %s", Lstrtok);
            ifi = Cnew (C_INTERNAL);
            ifn = Cinteger ((long) ifnum);
            Csetfp (ifi, ifn);
            Csetnext (i, ifi);
            Lgtok ();
        } else
            err ("expected token: STRING, found: '%s'", Lnames[Ltok]);
394
    } else {
395 396 397 398 399 400 401 402 403 404 405 406 407 408
        GTOKIFEQ (L_LCB);
        while (Ltok == L_LOCAL) {
            Lgtok ();
            ldi = pdecl (&flvn);
            Csetnext (i, ldi);
            i = ldi;
            GTOKIFEQ (L_SEMI);
        }
        while (Ltok != L_RCB) {
            si = pstmt ();
            Csetnext (i, si);
            i = si;
        }
        GTOKIFEQ (L_RCB);
409
    }
410 411
    Csetinteger (li1, (long) (Cgetindex () - owncbufi));
    Csetinteger (li2, (long) flvn);
412 413 414 415
    flvi = ownflvi, llvi = ownllvi;
    return fi;
}

416
static int pdecl (int *lvnp) {
417 418
    int di, si, i;

419
    di = Cnew (C_DECL);
420
    if (Ltok != L_ID) {
421 422
        Csetfp (di, C_NULL);
        return di;
423
    }
424 425 426
    si = Cstring (Lstrtok);
    addlv (si, (*lvnp)++);
    Csetfp (di, si);
427
    i = si;
428
    Lgtok ();
429
    if (Ltok != L_COMMA)
430 431
        return di;
    Lgtok ();
432
    while (Ltok == L_ID) {
433 434 435 436 437 438 439 440 441 442
        si = Cstring (Lstrtok);
        addlv (si, (*lvnp)++);
        Lgtok ();
        Csetnext (i, si);
        i = si;
        if (Ltok == L_COMMA) {
            Lgtok ();
            if (Ltok != L_ID)
                err ("expected identifier, found %s", Lnames[Ltok]);
        }
443 444 445 446
    }
    return di;
}

447
static int ptcons (void) {
448 449
    int ti, ei0, ei1;

450 451
    ti = Cnew (C_TCONS);
    Lgtok ();
452
    if (Ltok == L_RB) {
453 454 455
        Csetfp (ti, C_NULL);
        Lgtok ();
        return ti;
456
    }
457 458
    ei1 = pexpi (0);
    Csetfp (ti, ei1);
459
    ei0 = ei1;
460 461 462
    GTOKIFEQ (L_ASSIGN);
    ei1 = pexpr ();
    Csetnext (ei0, ei1);
463
    ei0 = ei1;
464
    GTOKIFEQ (L_SEMI);
465
    while (Ltok != L_RB) {
466 467 468 469 470 471 472 473
        ei1 = pexpi (0);
        Csetnext (ei0, ei1);
        ei0 = ei1;
        GTOKIFEQ (L_ASSIGN);
        ei1 = pexpr ();
        Csetnext (ei0, ei1);
        ei0 = ei1;
        GTOKIFEQ (L_SEMI);
474
    }
475
    Lgtok ();
476 477 478
    return ti;
}

479
static int pstmt (void) {
480 481
    int si, i0, i1;

482
    si = Cnew (C_STMT);
483 484
    switch (Ltok) {
    case L_SEMI:
485 486 487
        Csetfp (si, C_NULL);
        Lgtok ();
        break;
488
    case L_LCB:
489 490 491 492 493 494 495 496 497 498 499 500 501 502 503
        Lgtok ();
        if (Ltok == L_RCB) {
            Csetfp (si, C_NULL);
        } else {
            i1 = pstmt ();
            Csetfp (si, i1);
            i0 = i1;
            while (Ltok != L_RCB) {
                i1 = pstmt ();
                Csetnext (i0, i1);
                i0 = i1;
            }
        }
        Lgtok ();
        break;
504
    case L_IF:
505 506 507
        i0 = pifst ();
        Csetfp (si, i0);
        break;
508
    case L_WHILE:
509 510 511
        i0 = pwhilest ();
        Csetfp (si, i0);
        break;
512
    case L_FOR:
513 514 515
        i0 = pforst ();
        Csetfp (si, i0);
        break;
516
    case L_BREAK:
517 518 519
        i0 = pbreakst ();
        Csetfp (si, i0);
        break;
520
    case L_CONTINUE:
521 522 523
        i0 = pcontinuest ();
        Csetfp (si, i0);
        break;
524
    case L_RETURN:
525 526 527
        i0 = preturnst ();
        Csetfp (si, i0);
        break;
528
    default:
529 530 531
        i0 = pexpr ();
        Csetfp (si, i0);
        GTOKIFEQ (L_SEMI);
532 533 534 535
    }
    return si;
}

536
static int pifst (void) {
537 538
    int isi, ii, ti, ei;

539 540 541 542 543 544 545 546
    isi = Cnew (C_IF);
    Lgtok ();
    GTOKIFEQ (L_LP);
    ii = pexpr ();
    Csetfp (isi, ii);
    GTOKIFEQ (L_RP);
    ti = pstmt ();
    Csetnext (ii, ti);
547
    if (Ltok == L_ELSE) {
548 549 550
        Lgtok ();
        ei = pstmt ();
        Csetnext (ti, ei);
551 552 553 554
    }
    return isi;
}

555
static int pwhilest (void) {
556 557
    int wi, ei, si;

558 559 560 561 562 563 564 565
    wi = Cnew (C_WHILE);
    Lgtok ();
    GTOKIFEQ (L_LP);
    ei = pexpr ();
    Csetfp (wi, ei);
    GTOKIFEQ (L_RP);
    si = pstmt ();
    Csetnext (ei, si);
566 567 568
    return wi;
}

569
static int pforst (void) {
570 571
    int fi, i0, i1, si;

572 573 574 575 576
    fi = Cnew (C_FOR);
    Lgtok ();
    GTOKIFEQ (L_LP);
    i0 = (Ltok == L_SEMI) ? Cnew (C_NOP): pexpr ();
    Csetfp (fi, i0);
577
    if (Ltok == L_IN) {
578 579 580 581 582
        Csettype (fi, C_FORIN);
        Lgtok ();
        i1 = pexpr ();
        Csetnext (i0, i1);
        i0 = i1;
583
    } else {
584 585 586 587 588 589 590 591
        GTOKIFEQ (L_SEMI);
        i1 = (Ltok == L_SEMI) ? Cnew (C_NOP): pexpr ();
        Csetnext (i0, i1);
        i0 = i1;
        GTOKIFEQ (L_SEMI);
        i1 = (Ltok == L_SEMI) ? Cnew (C_NOP): pexpr ();
        Csetnext (i0, i1);
        i0 = i1;
592
    }
593 594 595
    GTOKIFEQ (L_RP);
    si = pstmt ();
    Csetnext (i0, si);
596 597 598
    return fi;
}

599
static int pbreakst (void) {
600 601
    int bi;

602 603 604 605
    bi = Cnew (C_BREAK);
    Csetfp (bi, C_NULL);
    Lgtok ();
    GTOKIFEQ (L_SEMI);
606 607 608
    return bi;
}

609
static int pcontinuest (void) {
610 611
    int ci;

612 613 614 615
    ci = Cnew (C_CONTINUE);
    Csetfp (ci, C_NULL);
    Lgtok ();
    GTOKIFEQ (L_SEMI);
616 617 618
    return ci;
}

619
static int preturnst (void) {
620 621
    int ri, ei;

622 623
    ri = Cnew (C_RETURN);
    Lgtok ();
624
    if (Ltok == L_SEMI) {
625 626 627
        Csetfp (ri, C_NULL);
        GTOKIFEQ (L_SEMI);
        return ri;
628
    }
629 630 631
    ei = pexpr ();
    Csetfp (ri, ei);
    GTOKIFEQ (L_SEMI);
632 633 634
    return ri;
}

635
static void addlv (int si, int vi) {
636 637 638
    int i;

    if (llvi >= lvn) {
639 640
        lvp = Marraygrow (lvp, (long) (lvn + LVINCR) + LVSIZE);
        lvn += LVINCR;
641 642 643
    }
    lvp[llvi].si = si, lvp[llvi].vi = vi, llvi++;
    for (i = llvi - 2; i >= flvi; i--)
644 645
        if (strcmp (GETLVSTR (i), GETLVSTR (llvi - 1)) == 0)
            err ("local variable %s multiply defined", GETLVSTR (i));
646 647
}

648
static void err (char *fmt, ...) {
649 650 651
    va_list args;

    va_start(args, fmt);
652 653 654 655 656
    Lprintpos ();
    vfprintf (stderr, fmt, args);
    fprintf (stderr, "\n");
    fflush (stdout);
    longjmp (eljbuf, 1);
657
}