elexscanner.cpp

用于词法分析的词法分析器

/* $Id: ElexScanner.cpp,v 1.15 1997/03/19 12:16:12 matt Exp $

   Elex scanner driver class.

   Implements a full backtracking scanner.  Backtracking is only
   limited by the amount of backtrack data maintained by the
   XInputStream class.

   (c) Matt Phillips 1996. */

#include "ElexScanner.h"

enum {ProdEOF = -1000}; // production number for the special eof state.

// the state the scanner is in when at eof.
const ElexState ElexScanner::eofState = {0, ProdEOF};

ElexScanner::ElexScanner (ElexScannerData &d, XInputStream &i, int lookahead) :
  ElexScannerBase (d), input (i), state (0)
{
  primeSymbols ();
  symbolLine = symbolColumn = 0;
  this->lookahead = lookahead + 1;
}

int ElexScanner::getNext ()
{
  reset ();

  symbol = SymNULL;

  do
  {
    // do an automatic freeze if there are enough symbols in the pipe
    // AND we are not in a backtrack state.
    if (symbolMarks.nItems () > lookahead &&
	(bestMatch.isEmpty () ||
	 *(symbolMarks.peekHead ()) > *(bestMatch.peekHead ())))
    {
      freeze (symbolMarks);
    }

    if (symbols.nItems () > 0)
    {
      makeCurrent (*(symbols.peekTail ()));
      symbols.popTail ();
    } else if (input.eof ())
    {
      if (state->isFinal ())
	match (state->prod);
      else if (state != data.start)
	handleNoAccept ();

      state = &eofState;
    } else
    {
      ElexState *toState = state->getTarget ((uchar)input.peek ());
     
      if (toState)
      {
	// check we're being greedy, mark for backtrack if necessary.
	if (state->isFinal ())
	  mark ();		

	state = toState;
	input.get ();
      } else if (state->isFinal ())
      {
	// char not accepted, but we can match a symbol.
	match (state->prod);
      } else
      {
	// char not accepted and not in final state.
	handleNoAccept ();
      }
    }
  } while (symbol == SymNULL);
}

void ElexScanner::mark ()
{
  // mark only if we haven't marked this position before.
  if (!input.isMarked (input.getIndex ()))
  {
    BacktrackMark *m = marks.pushHead ();
    m->mark (*this);
  }
}

// freezes one symbol (if possible) by moving it from symbolMarks and
// putting it in symbols.
void ElexScanner::freeze (SymbolMarkStack &symbolMarkStack)
{
  if (symbolMarkStack.nItems () > 1)
  {
    const SymbolMark *start = symbolMarkStack.peekTail ();
    symbolMarkStack.popTail ();
    const SymbolMark *end = symbolMarkStack.peekTail ();
    Symbol *sym = symbols.pushHead ();

    // remove all marks that occurred within the frozen symbol.
    marks.popTail (end->markCount - start->markCount);

    // setup symbols text and row, line.
    input.getText (sym->text, start->mark, end->mark);
    sym->line = start->mark.getLine ();
    sym->column = start->mark.getColumn ();
    sym->production = end->production;
  } 
}

void ElexScanner::makeCurrent (const ElexScanner::Symbol &sym)
{
  // setup basic symbol info
  symbolLine = sym.line;
  symbolColumn = sym.column;
  text = sym.text;

  // decide on symbol value.
  if (sym.production == ElexState::DefaultErrorProduction)
    symbol = SymERROR;
  else if (sym.production == ProdEOF)
    symbol = SymEOF;
  else
    symbol = invokeProduction (sym.production);

  // handle error symbol
  if (symbol == SymERROR)
  {
    error ("invalid symbol '" + sym.text + "'");
    text = "";
    symbol = SymNULL;
  }
}

int ElexScanner::backtrack ()
{
  if (marks.nItems () > 0)
  {
    // check whether the current match is the best
    if (symbolMarks.nItems () > 1 &&
	(bestMatch.isEmpty () ||
	 *(symbolMarks.peekHead ()) > *(bestMatch.peekHead ())))
    {
      bestMatch.assign (symbolMarks);
    }

    // execute backtrack operation
    const BacktrackMark *mark = marks.peekHead ();
    marks.popHead ();
    
    mark->jump (*this);
    match (state->prod);

    return 1;
  } else
    return 0;
}

// Handles a symbol match condition.
void ElexScanner::match (int production)
{
  SymbolMark *symbolMark;

  // merge contiguous error symbols
  if (production == data.errorProd &&
      symbolMarks.nItems () > 1 &&
      symbolMarks.peekHead ()->production == production)
    symbolMark = symbolMarks.peekHead ();
  else
  {
    symbolMark = symbolMarks.pushHead ();
    symbolMark->production = production;
  }

  symbolMark->mark.mark (input);
  symbolMark->markCount = marks.nItems ();

  reset ();
}

// Handles condition where character cannot be accepted: if the
// backtrack list is not empty, backtracks to the most recent mark and
// matches the symbol that would have been matched had we not been
// greedy.  If backtracking is not possible perform error recovery and
// report the error.
void ElexScanner::handleNoAccept ()
{
  if (!backtrack ())
  {
    // use previous best match if available
    if (bestMatch.nItems () > 0)
    {
       const SymbolMark *topMark = bestMatch.peekHead ();
       topMark->mark.jump (input);

      // symbol marks reinitialised to start at top of best match.
      // this sets up the start of the error symbol.
      symbolMarks.clear ();
      *(symbolMarks.pushTail ()) = *topMark;

      // freeze all symbols in the best match list
      while (bestMatch.nItems () > 1) 
      {
	freeze (bestMatch);
      }
      bestMatch.clear ();
    }

    if (symbolMarks.isEmpty ())
      primeSymbols ();

    // move input cursor beyond error symbol
    reset ();
    while (!input.eof () && !state->getTarget (input.peek ()))
    {
      input.get ();
    }

    match (data.errorProd);
  }
}

// resets current state to start state except where in special EOF
// state.
void ElexScanner::reset ()
{
  if (!state || state->prod != ProdEOF)
    state = data.start;
}

// initialise symbol marks to start at the current point in the input.
void ElexScanner::primeSymbols ()
{
  SymbolMark *sym = symbolMarks.pushHead ();
  sym->mark.mark (input);
  sym->production = ElexState::NoProduction;
  sym->markCount = 0;
}

void ElexScanner::error (const string &message)
{
  errors.error (message, input.filename, symbolLine, symbolColumn);
}

void ElexScanner::warning (const string &message)
{
  errors.warning (message, input.filename, symbolLine, symbolColumn);
}

void ElexScanner::BacktrackMark::mark (const ElexScanner &s)
{
  streamMark.mark (s.input);
  state = s.state;
  symbolCount = s.symbolMarks.nItems ();
}

void ElexScanner::BacktrackMark::jump (ElexScanner &s) const
{
  streamMark.jump (s.input);
  s.state = state;
  s.symbolMarks.popHead (s.symbolMarks.nItems () - symbolCount);
}

template class CircularQueue<ElexScanner::BacktrackMark>;
template class CircularQueue<ElexScanner::SymbolMark>;
template class CircularQueue<ElexScanner::Symbol>;