lexer.C

/*
 * This file is part of the "Archon" framework.
 * (http://files3d.sourceforge.net)
 *
 * Copyright © 2002 by Kristian Spangsege and Brian Kristiansen.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation under the terms of the GNU General Public License is
 * hereby granted. No representations are made about the suitability of
 * this software for any purpose. It is provided "as is" without express
 * or implied warranty. See the GNU General Public License
 * (http://www.gnu.org/copyleft/gpl.html) for more details.
 *
 * The characters in this file are ISO8859-1 encoded.
 *
 * The documentation in this file is in "Doxygen" style
 * (http://www.doxygen.org).
 */

#include <archon/util/text.H>
#include <archon/util/nfa.H>
#include <archon/util/dfa.H>

#include <archon/util/lexer.H>

using namespace std;

namespace Archon
{
  namespace Utilities
  {
    namespace
    {
      const unsigned bol_bit = 1;
      const unsigned eol_bit = 2;
      const unsigned bow_bit = 4;
      const unsigned eow_bit = 8;
    }

    string LexerBase::InputException::getMessage() const throw()
    {
      return Text::toString(lineNumber)+ ": Unexpected character " +
        Text::toString(Text::escapeNonprintable(text));
    }

    Lexer::Engine::Engine(const RuleSet &ruleSet, const ActorBase *a):
      actor(a)
    {
      rules.resize(ruleSet.rules.size());
      NFA nfa;
      for(unsigned i=0; i<ruleSet.rules.size(); ++i)
      {
        const RuleSet::Rule &r = ruleSet.rules[i];
        const int priority = ruleSet.rules.size()-i-1;
        nfa.altern(NFA(r.regex, priority));
        rules[priority] = Rule(r.method, r.lexeme);
      }

      DFA::AnchorInfo anchorInfo(0xE000, 4);
      //cerr << nfa.print() << "\n";
      DFA dfa1(nfa, 0, &anchorInfo);
      //cerr << a.print() << "\n";
      dfa = auto_ptr<DFA>(new DFA(DFA::Minimize(dfa1)));
      //cerr << dfa->print() << "\n";

      // Precalculate anchor masks for each state
      anchorMasks.resize(dfa->getNumberOfStates(), 0);
      for(unsigned i=0; i<static_cast<unsigned>(dfa->getNumberOfStates()); ++i)
      {
        const DFA::State &s = dfa->getState(i);
        unsigned &mask = anchorMasks[i];
        for(unsigned j=0; j<4; ++j)
          if(s.step(0xE000+j) != -1) mask |= 1u<<j;
      }
    }

    void Lexer::getNext(Lexeme &lexeme)
    {
      for(;;)
      {
        // Discard previous lexeme from buffer
        if(charCount > 0)
        {
          copy(buffer.begin()+charCount, buffer.begin()+bufferSize, buffer.begin());
          bufferSize -= charCount;
          charCount = 0;
        }

        int stateIndex = 0;

        int finalRuleIndex   = -1;
        int finalCharCount   = -1;
        int finalAnchorState = -1;
        int finalLineNumber  = -1;

        // Support for discartion of characters
        int secondAnchorState = -1;
        int secondLineNumber = -1;

        do
        {
          // Fetch the current DFA state
          const DFA::State *state = &engine.dfa->getState(stateIndex);
          const int ruleIndex = state->getFinalValue();
          if(ruleIndex >= 0)
          {
            finalRuleIndex   = ruleIndex;
            finalCharCount   = charCount;
            finalAnchorState = anchorState;
            finalLineNumber  = lineNumber;
          }

          const int charCountBeforeRead   = charCount;
          const int anchorStateBeforeRead = anchorState;
          const int lineNumberBeforeRead  = lineNumber;

          // Read another character
          uchar ch;
          bool eoi = false;
          if(charCount<bufferSize) ch = buffer[charCount++];
          else
          {
            if(reader->read(&ch, 1)<1) eoi = true;
            else
            {
              if(bufferSize<static_cast<int>(buffer.size()))
                buffer[bufferSize] = ch;
              else buffer += ch;
              ++bufferSize;
              ++charCount;
            }
          }

          unsigned anchorMask = 0; // A function of anchor state and input symbol
          switch(anchorState)
          {
            // At the beginning of a line
          case 0:
            if(eoi)
            {
              anchorMask = bol_bit|eol_bit;
              break;        
            }
            switch(ch)
            {
            case '\r':
              anchorMask = bol_bit|eol_bit;
              ++lineNumber;
              anchorState = 2;
              break;
            case '\n':
            case '\v':
            case '\f':
            case 0x85:
            case 0x2028:
            case 0x2029:
              anchorMask = bol_bit|eol_bit;
              ++lineNumber;
              break;
            default:
              anchorMask = bol_bit;
              anchorState = 1;
            }
            break;

            // After the beginning of a line
          case 1:
            if(eoi)
            {
              anchorMask = eol_bit;
              break;        
            }
            switch(ch)
            {
            case '\r':
              anchorMask = eol_bit;
              anchorState = 2;
              break;
            case '\n':
            case '\v':
            case '\f':
            case 0x85:
            case 0x2028:
            case 0x2029:
              anchorMask = eol_bit;
              ++lineNumber;
              anchorState = 0;
              break;
            default:
              anchorMask = 0;
            }
            break;

            // After a '\r'
          case 2:
            if(eoi)
            {
              anchorMask = bol_bit|eol_bit;
              break;        
            }
            switch(ch)
            {
            case '\n':
              anchorMask = 0;
              anchorState = 0;
              break;
            case '\r':
              anchorMask = bol_bit|eol_bit;
              ++lineNumber;
              break;
            case '\v':
            case '\f':
            case 0x85:
            case 0x2028:
            case 0x2029:
              anchorMask |= bol_bit|eol_bit;
              ++lineNumber;
              anchorState = 0;
              break;
            default:
              anchorMask = bol_bit;
              anchorState = 1;
            }
            break;
          }

          if(secondAnchorState == -1)
          {
            secondAnchorState = anchorState;
            secondLineNumber  = lineNumber;
          }

          // Step along anchor edges first
          while(unsigned mask = engine.anchorMasks[stateIndex] & anchorMask)
          {
            unsigned bitPos = 0;
            while(!(mask&1u))
            {
              mask >>= 1;
              ++bitPos;
            }
            anchorMask &= ~(1u<<bitPos);
            stateIndex = state->step(0xE000+bitPos);
            state = &engine.dfa->getState(stateIndex);
            const int ruleIndex = state->getFinalValue();
            if(ruleIndex >= 0)
            {
              finalRuleIndex   = ruleIndex;
              finalCharCount   = charCountBeforeRead;
              finalAnchorState = anchorStateBeforeRead;
              finalLineNumber  = lineNumberBeforeRead;
            }
          }

          if(eoi) break;

          // Step to the next DFA state
          stateIndex = state->step(ch);
        }
        while(stateIndex != -1);

        if(finalRuleIndex < 0)
        {
          if(charCount == 0)
          {
            lexeme.type = type = -1;
            return;
          }

          charCount   = 1;
          anchorState = secondAnchorState;
          lineNumber  = secondLineNumber;
          if(context)
          {
            context->lexerError();
            continue;
          }
          throw InputException(lineNumber, getText());
        }

        charCount   = finalCharCount;
        anchorState = finalAnchorState;
        lineNumber  = finalLineNumber;

        const Engine::Rule &rule = engine.rules[finalRuleIndex];
        lexeme = rule.lexeme;
        if(rule.method > -1)
          engine.actor->call(rule.method, context, lexeme);

        if(lexeme.type < 0) continue;
        type = lexeme.type;
        return;
      }
    }
  }
}

---