/*  Parsing.  (Table driven top-down recursive-descent parser) */

/*   The parser used here is based on a design by Tony Brooker which was
    originally used in Atlas Autocode and the "Compiler Compiler".
    It generates a concrete syntax tree rather than the abstract
    syntax tree more popular in modern compilers.  A later phase
    converts from concrete to abstract.

    (The concrete syntax tree is a reasonable tool to use for source
     to source manipulations, prettyprinting, etc etc; you *can*
     use it to generate code from directly, but it's far more awkward.)

    Note that the parsing procedure here is just a piece of code
    to walk a pre-built table.  There is nothing in this section
    which reflects the grammar, if that is what you are looking for.
    You'll find the grammar embedded in the 'compile()' procedure
    in the following section.
 */

// It might be possible to have the parser transparently skip any whitespace c[] tokens
// while parsing.  Then with cooperation from the lexer we can actually store the white space
// on a line-by-line basis, thus allowing full source reconstruction for error reporting,
// code listings etc.  Maybe just:  while (c[cp].t == TYPE_WHITESPACE) cp += 1;

int cp = 0;  // code pointer.  Has to be global state.
int ap = 0;  // Analysis record pointer.

int parse(int pp, int depth) // depth is only for indentation in diags
{
  /*  Main parsing procedure.  This is a table-driven parser, with the tables
      being generated from the grammar rules embedded in the 'compile' procedure
      below.  The result of the parse is a tree structure, and the values of the
      nodes in the tree structure are used to drive a large 'case' statement
      which selects the actions to be performed after a successful parse.

      There is no grammatical structure embedded in this procedure.  If you're
      looking for the grammar definition, see the procedure called 'compile' instead.
   */
  int saved_cp;
  int saved_ap;
  int i;
  int gp;
  int alts;
  int match;
  // char saved_desc[256];

  /*  Initialisation */
  gp = phrase_start[pp-512-MAX_BIP];
  alts = gram[gp];
  gp++; // gp now points to first element (length) of first alt

  saved_cp = cp;
  saved_ap = ap;
  

  for (i = 0; i < alts; i++) {
    /*  Starting with the root phrase, recursively examine each alternative */
    int each;
    int phrases = gram[gp++];
    int phrase_count;
    int gap = 0;

    cp = saved_cp;
    ap = saved_ap;

    if (ap+3 > next_free_a) next_free_a = ap+3;

    A[ap++] = pp;   // record which phrase (could be done outside loop)
    A[ap++] = i;    // and which alt.


    // Count slots needed.  *Could* be precalculated and stored
    // in the grammar, either embedded (after the ALT) or as a
    // separate table

    for (each = 0; each < phrases; each++) if (gram[gp+each] >= 512) gap++;

    A[ap++] = gap;    // Count of alts (gap)
    // ap+gap now points to the slot after the space required, which
    // is where the first subphrase will be stored.
    ap = ap+gap; // recursive subphrases are stored after this phrase.
                 // ap is left updated if successful.


    // successfully parsed phrases are stored in A[saved_ap+3+n]

    if (saved_ap+3+gap > next_free_a) next_free_a = saved_ap+3+gap;

    match = TRUE; // stays true if all subphrases match
    phrase_count = 0; // only phrases which make it into the A record,
                      // i.e. excluding literals and keywords
    for (each = 0; each < phrases; each++) {
      /*  Within a single grammar rule (alternative), ensure that each subphrase is present */
      int phrase = gram[gp+each] & DROP_SPECIAL_BITS;
      int optional_phrase = gram[gp+each] & OPTIONAL_PHRASE;
      int negated_phrase = gram[gp+each] & NEGATED_PHRASE;

      while (c[cp].t == TYPE_WHITESPACE) cp += 1; // skip whitespace before each alt

      if (cp > bestparse) {
        static char s[128]; // off heap instead?  - binary size

        // this is used in reporting syntax errors.
        // we get better diags if DEBUG_PARSER is true
        if (phrase < 256) {
          sprintf(s, "'%c'", phrase);
        } else if (phrase < 512) {
          sprintf(s, "\"%s\"", keyword[phrase-256]);
        } else if (phrase < 512+MAX_BIP) {
	  //#ifdef EXTENDED_ERROR_REPORTING
          sprintf(s, "{%s}", phrasename[phrase-512]);
	  //#else
          //sprintf(s, "{BIP %d}", phrase-512);
	  //#endif
        } else {
	  //#ifdef EXTENDED_ERROR_REPORTING
          sprintf(s, "<%s>", phrasename[phrase-512]);
	  //#else
          //sprintf(s, "<Phrase %d>", phrase-512);
	  //#endif
        }

        looking_for = s;
        bestparse = cp;
      }

      if (phrase < 256) {
	/*  Literal */
        if ((c[cp].t != TYPE_CHAR) || (c[cp].s[0] != phrase)) match = FALSE; else cp++;
        // Don't record literals        
      } else if (phrase < 512) {
	/*  Keyword */
        if ((c[cp].t != TYPE_KEYWORD) || (strcmp(keyword[phrase-256], c[cp].s) != 0)) match = FALSE; else cp++;
        // Don't record keywords
      } else if (phrase < 512+MAX_BIP) {
	/*  Built-in phrase */
        int where = ap; // next phrase to be parsed will be stored at current 'ap'.
	// BUG: BIPS should also allow <?...> and <!...> as users won't distinguish BIPs from phrases
        if (c[cp].t != BIP[phrase-512]) {
          match = FALSE;
	} else {
          A[ap++] = phrase;
          A[ap++] = 1;
          A[ap++] = 1;
          A[ap++] = cp++;
          A[saved_ap+3+phrase_count++] = where; // Record BIP
        }
      } else {
	/*  Recursive call to parser for a subphrase */
        int where = ap; // next phrase to be parsed will be stored at current 'ap'.
        if (negated_phrase) {
          int here = cp;
          if (!parse(phrase, depth+1)) {
            A[saved_ap+3+phrase_count++] = -1; // was 'where'
          } else {
            match = FALSE;
	  }
          cp = here; // negated phrase never consumes any input
	} else if (optional_phrase) {	
          int input_stream_pos = cp;
          if (parse(phrase, depth+1)) {
            A[saved_ap+3+phrase_count++] = where;
            cp = input_stream_pos; // now re-parse the input stream with the following alts
          } else {
            match = FALSE;
	  }
        } else {
          if (parse(phrase, depth+1)) {
            A[saved_ap+3+phrase_count++] = where;
          } else {
            match = FALSE;
	  }
        }
      }
      
      if (!match) break;
      
    }
    gp += phrases; // move over all phrases, to next alt

    if (match) break;

    // gp now points to first element (length) of next alt, or start of next phrase
    
  }

  return(match);
  
}