Computer Science 301 - 2002

Tutorials for week 14 - (b) Practice in recursive descent parsing and error recovery

1. Is the following grammar LL(1)?

     COMPILER Goal $TF

     IGNORE CHR(1) .. CHR(31)

     PRODUCTIONS
       Goal =  A { B } "." .
       A    =  C  |  "(" [ B ] ")"  |  "[" C "]" .
       B    =  "x"  |  "y" { C } "z" .
       C    =  "p"  |  "q" .
     END Goal.

2. The following gives the outline of a parser and scanner for the language defined by the above grammar.

    #include "misc.h"
    #include "set.h"

    // +++++++++++++++++++++++++ Character Handler +++++++++++++++++++++++++

    FILE *inFile;
    char ch;                        // Lookahead character for scanner

    void GetChar (void) {
    // Obtains next character ch from inFile, or CHR(0) if EOF reached
      ch = fgetc(inFile);
      putchar(ch);
      if (ch == EOF) ch = '\0';
    }

    // +++++++++++++++++++++++++ Scanner +++++++++++++++++++++++++++++++++++

    enum SYMBOLS { EOFSym, unknownSym, lParenSym, rParenSym, lBrackSym,
                   rBrackSym, periodSym, pSym, qSym, xSym, ySym, zSym };

    SYMBOLS sym;                    // Lookahead token for parser

    void GetSym (void) {
    // Scans for next sym from inFile
      while (ch > 0 && ch <= ' ') GetChar(); // skip whitespace
      switch (tolower(ch)) {
        case '\0' : sym = EOFSym; break;
        case 'p'  : sym = pSym; GetChar(); break;
        case 'q'  : sym = qSym; GetChar(); break;
        case 'x'  : sym = xSym; GetChar(); break;
        case 'y'  : sym = ySym; GetChar(); break;
        case 'z'  : sym = zSym; GetChar(); break;
        case '('  : sym = lParenSym; GetChar(); break;
        case ')'  : sym = rParenSym; GetChar(); break;
        case '['  : sym = lBrackSym; GetChar(); break;
        case ']'  : sym = rBrackSym; GetChar(); break;
        case '.'  : sym = periodSym; GetChar(); break;
        default   : sym = unknownSym; GetChar(); break;
      }
    }

    // +++++++++++++++++++++++++ Parser ++++++++++++++++++++++++++++++++++++

    void abort (char *S) {
    // Abandon parsing with error message S
      fprintf(stderr, "%s", S); exit(1);
    }

    void accept (SYMBOLS WantedSym, char *S) {
    // Check that lookahead token is WantedSym
      if (sym == WantedSym) GetSym(); else abort(S);
    }

    void main (int argc, char *argv[])  {
      if ((inFile = fopen(argv[1], "r")) == NULL) {
        fprintf(stderr, "Could not open %s", argv[1]); exit(1);
      }
      GetChar();               // Initialise character handler
      GetSym();                // Initialise scanner
      Goal();                  // Initialise parser
      fprintf(stderr, "Parsed correctly");
    }

Complete the parser by developing the routine Goal and those it needs to call, using brute force error detection (ie kill the parsing process when an error is discovered with a suitable error message

3. Improve your parsing routines to incorporate error recovery and synchronization using the techniques discussed in section 10.3, using the routines below:

     void accept (SYMBOLS WantedSym, char *S) {
     // Check that lookahead token is WantedSym
       if (sym == WantedSym) GetSym();
       else {
         fprintf(stderr, "%s\n", S);
         errors = true;
       }
     }

     void test (SymSet allowed, SymSet beacons, char *S) {
     // Test whether current Sym is in Allowed, and recover if not
       if (allowed.memb(sym)) return;
       fprintf(stderr, "%s\n", S);
       errors = true;
       SymSet stopset = allowed + beacons;
       while (!stopset.memb(sym)) GetSym();
     }

Errors in Prac Kit for Prac 13

I apologise - there were a few small errors in the kit for Prac 13

In the PARVA.ATG file, the section:

Assignment
=                           (. TABLE_types vartype, exptype;
                               TABLE_entries entry; .)
   Designator<classset(TABLE_vars), entry, vartype>
   AssignOp
   (   Expression<exptype>  (. if (compatible ...

has AssignOP is in the wrong place. It should read:

Assignment
=                           (. TABLE_types vartype, exptype;
                               TABLE_entries entry; .)
   Designator<classset(TABLE_vars), entry, vartype>
   (   AssignOp                                            // ------ here
       Expression<exptype>  (. if (compatible ...

In the TABLE.CPP file the code reading

void TABLE::printtable(FILE *lst)
  putc('\n', lst);
      ...

      case TABLE_procs:
        fprintf(lst, " Function %6d %6d %6d\n",
                     symtable[i].p.entrypoint); break;

has an error in the fprintf control string. It should read

void TABLE::printtable(FILE *lst)
{ putc('\n', lst);
      ...

      case TABLE_procs:
        fprintf(lst, " Function %6d\n",                    // ------ here
                     symtable[i].p.entrypoint); break;