---

scanner_dfa_writer.cc

Go to the documentation of this file.

/*
 *  File:       scanner_dfa_writer.cc
 *              $Id: scanner_dfa_writer.cc,v 1.13 2002/07/09 08:54:51 alec Exp $
 *
 *  Author:     Alec Panoviciu (alecu@email.com)
 * 
 *  Comments:
 *
 *  Revision history:
 *
 *  $Log: scanner_dfa_writer.cc,v $
 *  Revision 1.13  2002/07/09 08:54:51  alec
 *  0.0.3 stuff
 *
 *  Revision 1.12  2002/07/09 03:04:58  alec
 *  OWN_STRINGS bu*beep*it finally vanished
 *  gcc 3.1&mingw - related cleanups
 *
 *  Revision 1.11  2002/06/26 20:50:22  alec
 *  g++ 3.x happy
 *
 *  Revision 1.10  2002/06/23 23:29:55  alec
 *  profile-based optimization stuff
 *
 *  Revision 1.9  2002/06/13 11:41:46  alec
 *  added #line stuff
 *
 *  Revision 1.8  2002/05/31 12:11:09  alec
 *  *** empty log message ***
 *
 *  Revision 1.7  2002/05/27 03:03:36  alec
 *  doc update
 *
 *  Revision 1.6  2002/05/22 01:42:24  alec
 *  stream(buffer) switching, getChar, unGetChar implemented
 *  some bug fixes
 *
 *  Revision 1.5  2002/05/16 21:46:06  alec
 *  8x generated code speed improvement (almost 2x flex) weeepeeee!!!
 *
 *  Revision 1.4  2002/05/08 10:36:18  alec
 *  added keyword tokens support
 *
 *  Revision 1.3  2002/05/07 10:02:18  alec
 *  fixed some bugs & mem leaks; added MORE tokens support
 *
 *  Revision 1.2  2002/05/04 17:39:22  alec
 *  the scanner works (slightly tested)
 *
 *  Revision 1.1  2002/05/01 16:34:01  alec
 *  *** empty log message ***
 *
 */

/*
  Copyright (C) 2002 Alexandru Panoviciu (alecu@email.com)

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 */

#include "../config.h"

#ifdef HAVE_STAT
#include <sys/types.h>
#include <sys/stat.h>
#include <unistd.h>
#endif

#include <fstream>
#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <cctype>
#include <sstream>
#include <list>
#include <functional>
using namespace std;


#include "scanner_dfa_writer.hh"
#include "prop_registry.hh"
#include "scanner_spec.hh"
#include "scanner_dfa_spec.hh"
#include "basic_dfa_spec.hh"
#include "token_spec.hh"
#include "dfa_profile.hh"


ScannerDfaWriter::ScannerDfaWriter (TokenSpec &tSpec_,
                                    PropRegistry &registry_) :
  Writer(registry_),
  tSpec(tSpec_)
{}

void ScannerDfaWriter::writeScanner (ScannerDfaSpec &dfa)
{
  string throwClause;
  string includeMacro = className2macro(dfa.className);
  if (registry["USE_EXCEPTIONS"]) throwClause = " throw (ScanException)";

  // check whether a profiling file was given and see whether we should use it
  // now or cause it to be generated.
  registry["DUMP_PROFILE"] = false;
  ScannerDfaProfile sdp(dfa);
  if ((string) registry["PROFILING_FILE"] != "")
  {
#ifdef HAVE_STAT
    struct stat st1, st2;
    stat(((string) registry["PROFILING_FILE"]).c_str(), &st1);
    stat(((string) registry["input_file"]).c_str(), &st2);
    if (st1.st_mtime < st2.st_mtime) {
#else
    bool useExisting = false;
    if (ifstream(((string) registry["PROFILING_FILE"]).c_str())) {
      cout << "Profiling data file " << registry["PROFILING_FILE"]
           << " found. Use it ? (y/n):";
      cin >> useExisting;
    }
    if (!useExisting) {
#endif
      // the profile data appears to be older than the grammar file. we assume
      // we should generate it again
      registry["DUMP_PROFILE"] = true;
      if (registry["be_verbose"])
        cerr << formatWarning(Position(), string("Profile data file ") +
                              (string) registry["PROFILING_FILE"] + " is older"
                              " than the grammar file. Run the generated "
                              "scanner once on the sample input to re-generate"
                              " the profile data then re-run cppcc (see the "
                              "user's guide for more information on profile "
                              "based optimization).") << endl;
    } else {
      // the profile data seems to match our grammar, we try and use it when
      // generating the scanner
      if (registry["be_verbose"])
        cerr << formatWarning(string("Will use profile data from ") +
                              registry["PROFILING_FILE"] + " when generating"
                              " this scanner.") << endl;
      ifstream ifs(((string) registry["PROFILING_FILE"]).c_str());
      if (!ifs) {
        cerr << formatWarning(string("Could not open profile data file ") +
                              registry["PROFILING_FILE"] + ". It will be "
                              "generated on the "
                              "next run of the generated scanner.") << endl;
        registry["DUMP_PROFILE"] = true;
      } else if (!sdp.read(ifs))
      {
        cerr << formatWarning(string("Profile data from file ") +
                              registry["PROFILING_FILE"] + " does not match "
                              "this grammar. It will be re-generated on the "
                              "next run of the generated scanner.") << endl;
        registry["DUMP_PROFILE"] = true;
        sdp.reset();
      }
    }
  }

  // scanner's .hh

  openStream(fullPath(className2hh(dfa.className)));

  line() << "#ifndef " << includeMacro;
  line() << "#define " << includeMacro;
  line();
  line() << "#include <string>";
  line() << "#include <fstream>";
  line() << "#include <iostream>";
  line() << "#include <exception>";
  line() << "#include <deque>";
  line() << "#include <stack>";
  line() << "using namespace std;";
  //  line() << "#include <ios>";
  line();
  line() << "#include \"" << className2hh(tSpec.className) << "\"";
  line();
  if (!dfa.preambleCode.empty())
    writeChunk(dfa.preambleCode);
  line() << "namespace cppcc";
  line() << "{";
  line();
  
  line() << "class ScanException : public exception";
  line() << "{";
  indent();
  line() << "public:";
  indent();
  line();
  line() << "ScanException (const string &message_ = \"Scan exception\") :";
  line() << "  message(message_)";
  line() << "{}";
  line();
  line() << "ScanException (const Position &pos_,";
  line() << "               const string &message_ = \"Scan exception\") :";
  line() << "  message(message_), pos(pos_)";
  line() << "{}";
  line();
  line() << "~ScanException () throw ()";
  line() << "{}";
  line();
  line() << "virtual operator string () const";
  line() << "{";
  indent();
  line() << "return string(pos) + \": \" + message;";
  unindent();
  line() << "}";
  line();
  line() << "virtual const char* what () throw ()";
  line() << "{";
  indent();
  line() << "return message.c_str();";
  unindent();
  line() << "}";
  line();
  unindent();
  line() << "private:";
  line();
  indent();
  line() << "Position pos;";
  line() << "string message;";
  unindent();
  unindent();
  line() << "};";
  line();

  line() << "class " << dfa.className << "_base";
  line() << "{";
  indent();
  line() << "protected:";
  indent();
  line() << "bool onScanError (ScanException &ex) { return false; }";
  line() << "bool onIOError (ScanException &ex) { return false; }";
  line() << "bool wrap () { return false; }";
  line() << "void commonTokenAction (" << tSpec.className << " &tok) {}";
  unindent();
  unindent();
  line() << "};";
  line();
  
  line() << "class " << dfa.className << ": public "
         << dfa.className << "_base";
  if (!dfa.inheritance.empty()) {
    ofs << ", ";
    writeChunk(dfa.inheritance);
  }
  line() << "{";
  line() << "public:";
  indent();
  line();

  line() << "struct t_laCell";
  line() << "{";
  indent();
  line() << tSpec.className << " *token;";
  line() << "struct t_laCell *next;";
  line() << "t_laCell(" << tSpec.className
        << " *token_, struct t_laCell *next_) : token(token_), next(next_) {}";
  line() << "~t_laCell() { delete token; }";
  unindent();
  line() << "};";
  line();
  
  line() << dfa.className << " (istream *in_ = NULL)" << throwClause;
  line() << "    : _buffer(NULL), _reject(false), _more(false),";
  if (registry["DEBUG_SCANNER"])
    line() << "_bsz(5), _pbsz(5)";
  else
    line() << "_bsz(8 * 1024), _pbsz(100)";
  line() << "{";
  indent();
  line() << "switchToStream(in_);";
  line() << "lookahead = false;";
  line() << "la0 = _laBegin = _laEnd = new struct t_laCell(new " << tSpec.className << ", NULL);";
  line() << "la0->next = la0;";
  line() << "switchToState(START);";
  if (registry["DUMP_PROFILE"])
    line() << "_freqs_init();";
  unindent();
  line() << "}";
  line();
  if (registry["DUMP_PROFILE"]) {
    line();
    line() << "~" << dfa.className << "() { _freqs_dump(); }";
    line();
  }
  line() << "void rejectToken() {_reject = true; }";
  line();
  line() << "void switchToStream (istream *in)";
  line() << "{";
  indent();
  line() << "resetPos();";
  line() << "inputStream = in;";
  line() << "_binit();";
  unindent();
  line() << "}";
  line();

  line() << "class StreamState";
  line() << "{";
  indent();
  line() << "friend class " << dfa.className << ";";
  line() << "istream *inputStream;";
  line() << "char *_buffer, *_ch, *_start, *_eob;";
  if (registry["COUNT_COLUMNS"])
    line() << "char * _bol;";
  line() << "int _bsz, _pbsz;";
  line() << "bool _lta, _eof;";
  line() << "Position bPos, ePos;";
  line();
  line() << "StreamState (istream *inputStream_, char *_buffer_, int _bsz_,";
  if (registry["COUNT_COLUMNS"]) 
    line() << "            int _pbsz_, char *_start_, char *_bol_, char *_ch_,";
  else
    line() << "            int _pbsz_, char *_start_, char *_ch_,";
  line() << "             char *_eob_, bool _lta_, bool _eof_,";
  line() << "             Position &bPos_, Position &ePos_) :";
  line() << "  inputStream(inputStream_), _buffer(_buffer_), _bsz(_bsz_),";
  if (registry["COUNT_COLUMNS"]) 
    line() << "    _pbsz(_pbsz_), _start(_start_), _bol(_bol_), _ch(_ch_),";
  else
    line() << "   _pbsz(_pbsz_), _start(_start_), _ch(_ch_),";
  line() << "   _eob(_eob_), _lta(_lta_), _eof(_eof_),";
  line() << "   bPos(bPos_), ePos(ePos_)";
  line() << "{}";
  line();
  line() << "~StreamState () { if (_buffer != NULL) delete[] _buffer; }";
  unindent();
  line() << "};";
  line();
  
  line() << "StreamState* pushStream (istream *in)";
  line() << "{";
  indent();
  line() << "StreamState *res = new StreamState(inputStream, _buffer, _bsz,";
  if (registry["COUNT_COLUMNS"]) 
    line() << "                    _pbsz, _more ? _start : _ch, _bol, _ch,";
  else
    line() << "                          _pbsz, _more ? _start : _ch, _ch,";
  line() << "                                   _eob, _lta, _eof,";
  line() << "                                 _more ? bPos : ePos, ePos);";
  line() << "_buffer = NULL;";
  line() << "switchToStream(in);";
  line() << "return res;";
  unindent();
  line() << "}";
  line();
  
  line() << "void popStream (StreamState *s)";
  line() << "{";
  indent();
  line() << "if (_buffer != NULL) delete[] _buffer;";
  line() << "inputStream = s->inputStream;";
  line() << "_buffer = s->_buffer;";
  line() << "_bsz = s->_bsz;";
  line() << "_pbsz = s->_pbsz;";
  line() << "_start = s->_start;";
  if (registry["COUNT_COLUMNS"])
    line() << "_bol = s->_bol;";
  line() << "_ch = s->_ch;";
  line() << "_eob = s->_eob;";
  line() << "_lta = s->_lta;";
  line() << "_eof = s->_eof;";
  line() << "bPos = s->bPos;";
  line() << "ePos = s->ePos;";
  line() << "s->_buffer = NULL;";
  line() << "delete s;";
  unindent();
  line() << "}";
  line();
    

  line() << "istream& getInputStream ()";
  line() << "{";
  indent();
  line() << "return *inputStream;";
  unindent();
  line() << "}";
  line();
  
  line() << "int switchToState (int newState)";
  line() << "{";
  indent();
  line() << "int prevState = _state;";
  line() << "_state = newState;";
  line() << "return prevState;";
  unindent();
  line() << "}";
  line();

  line() << "int getState ()";
  line() << "{";
  indent();
  line() << "return _state;";
  unindent();
  line() << "}";
  line();

  line() << "int pushState (int newState)";
  line() << "{";
  indent();
  line() << "_stateStack.push(_state);";
  line() << "return switchToState(newState);";
  unindent();
  line() << "}";
  line();

  line() << "int popState ()";
  line() << "{";
  indent();
  line() << "int prevState = switchToState(_stateStack.top());";
  line() << "_stateStack.pop();";
  line() << "return prevState;";
  unindent();
  line() << "}";
  line();
  
  line() << "const Position& getCurrentPos ()";
  line() << "{";
  indent();
  line() << "return bPos;";
  unindent();
  line() << "}";
  line();

  line() << "void resetPos ()";
  line() << "{";
  indent();
  line() << "ePos.ln = bPos.ln = 1;";
  if (registry["COUNT_COLUMNS"]) {
    line() << "bPos.col = ePos.col = 1;";
    line() << "_bol = _ch;";
  }
  unindent();
  line() << "}";
  line();
  
  line() << "int newLine ()";
  line() << "{";
  indent();
  if (registry["COUNT_COLUMNS"]) {
    line() << "_bol = _ch;";
    line() << "ePos.col = 1;";
  }
  line() << "return ePos.ln++;";
  unindent();
  line() << "}";
  line();

  line() << "bool lookingAhead ()";
  line() << "{";
  indent();
  line() << "return lookahead;";
  unindent();
  line() << "}";
  line();
  
  
  line() << "int getChar ()" << throwClause;
  line() << "{";
  indent();
  line() << "for(;;) {";
  indent();
  line() << "unsigned int c = *_ch++;";
  line() << "if (_ch == _eob) {";
  indent();
  line() << "_ch--;";
  line() << "if (_eof && !wrap()) return EOF;";
  line() << "else _brefill();";
  unindent();
  line() << "} else {";
  indent();
  line() << "if (_start == _ch - 1) _start = _ch;";
  line() << "return c;";
  unindent();
  line() << "}";
  unindent();
  line() << "}";
  unindent();
  line() << "}";
  line();

  line() << "void unGetChars (const char *c, int n);";
  
  line() << "void unGetChar (char c)";
  line() << "{";
  indent();
  line() << "unGetChars(&c, 1);";
  unindent();
  line() << "}";
  line();

  line() << "void unGetChars (const string &s)";
  line() << "{";
  indent();
  line() << "unGetChars(s.data(), s.length());";
  unindent();
  line() << "}";
  line();

  line() << "void unGetChars (const char *s)";
  line() << "{";
  indent();
  line() << "unGetChars(s, strlen(s));";
  unindent();
  line() << "}";
  line();
  
  line() << tSpec.className << "* la (int k)" << throwClause;
  line() << "{";
  indent();
  line() << "struct t_laCell *p, *q;";
  line() << "for (p = la0; k >= 0; k--, q = p, p = p->next) {";
  indent();
  line() << "if (p == _laEnd) {";
  indent();
  line() << "if (_laEnd->next == _laBegin)";
  indent();
  line() << "_laEnd->next = new struct t_laCell(new " << tSpec.className
         << "(), _laBegin);";
  unindent();
  line() << "_scan(_laEnd->token);";
  line() << "_laEnd = _laEnd->next;";
  unindent();
  line() << "}";
  unindent();
  line() << "}";
  line() << "return q->token;";
  unindent();
  line() << "}";
  line();

  line() << tSpec.className << "* la ()" << throwClause;
  line() << "{";
  indent();
  line() << "if (la0 == _laEnd) {";
  indent();
  line() << "if (_laEnd->next == _laBegin)";
  indent();
  line() << "_laEnd->next = new struct t_laCell(new " << tSpec.className
         << "(), _laBegin);";
  unindent();
  line() << "struct t_laCell *x = _laEnd;";
  line() << "_laEnd = _laEnd->next;";
  line() << "_scan(x->token);";
  unindent();
  line() << "}";
  line() << "return la0->token;";
  unindent();
  line() << "}";
  line();
  
  
  line() << "void consume ()" << throwClause;
  line() << "{";
  indent();
  line() << "la();"; // make sure we have a token there
  line() << "la0 = la0->next;";
  line() << "if (!lookahead)";
  indent();
  line() << "_laBegin = _laBegin->next;";
  unindent();
  unindent();
  line() << "}";
  line();

  // this one is actually used by the parser. It relies on the parser's code
  // to ensure that the queue contains a token and also to delete the returned
  // token. 
  line() << "void unchecked_consume ()";
  line() << "{";
  indent();
  line() << "la0 = la0->next;";
  line() << "if (!lookahead)";
  indent();
  line() << "_laBegin = _laBegin->next;";
  unindent();
  unindent();
  line() << "}";
  line();

  line() << "void setMarker ()";
  line() << "{";
  indent();
  line() << "lookahead = true;";
  line() << "laMarkers.push(la0);";
  unindent();
  line() << "}";
  line();

  line() << "void rewindToMarker ()";
  line() << "{";
  indent();
  line() << "la0 = laMarkers.top();";
  line() << "laMarkers.pop();";
  line() << "if (laMarkers.empty()) {";
  indent();
  line() << "lookahead = false;";
  line() << "_laBegin = la0;";
  unindent();
  line() << "}";
  unindent();
  line() << "}";
  line();
  
  //  line() << "

  line();
  for (int i = 0; i < dfa.states.size(); i++)
    line() << "static const int " << dfa.states[i]->name << ";";
  line();
  
  unindent();
  
  line() << "protected: // the ugly stuff";
  line();
  indent();
  line() << "void _scan(" << tSpec.className
         << " *token)" << throwClause <<";";

  line() << "Position bPos, ePos;";
  line() << "istream *inputStream;";
  line();
  
  line() << "bool lookahead;";
  line() << "struct t_laCell *la0, *_laBegin, *_laEnd;";
  line() << "stack<struct t_laCell*> laMarkers;";
  line() << "int _state;";
  line() << "stack<int> _stateStack;";
  line() << "bool _reject;";
  line();
  
  line() << "void _brefill ()" << throwClause << ";";
  line() << "void _binit()" << throwClause << ";";   
  line() << "int _bsz; //buffer size";
  line() << "int _pbsz; //extra bytes for pushback";
  // out internal buffer. _bsz are "normal characters", and we need an extra
  // byte to store the '\0' character that tells us we reached the buffer's
  // end.
  line() << "char *_buffer;";
  // _start points to the first char of the current token
  // _ch is the current char
  // _eob points one past the last character in the buffer (i.e to the '\0' we
  // appended. 
  line() << "char *_ch; // current char";
  line() << "char *_eob; // one past the last char in the buffer";
  line() << "char *_start; // points ot the token's start";
  line() << "bool _eof; // eof seen during _brefill";
  line() << "bool _lta; // last token in the stream was accepted";
  line() << "bool _more; // true in token actions of MORE tokens";
  if (registry["COUNT_COLUMNS"])
    line() << "char * _bol; // _ch - _bol = col increment.";
  line();
  unindent();
  if (registry["DUMP_PROFILE"])
  {
    line() << "private: // DFA profiling stuff";
    line();
    indent();
    line() << "unsigned int **_freqs[" << sdp.size() << "];";
    line() << "unsigned int *_freqs_sz[" << sdp.size() << "];";
    line();
    line() << "void _freqs_init ();";
    line();
    line() << "void _freqs_dump ();";
    line();
    line() << "void _bump_counter (int lState, int state, int transition);";
    unindent();
    line();
  }
  if (!dfa.userCode.empty()) {
    line() << "private: // user code";
    line();
    for (int i = 0; i < dfa.userCode.size(); i++)
      writeChunk(dfa.userCode[i]);
    line();
  }
  line() << "}; // end class " << dfa.className;
  line();
  line();
  line() << "} //end namespace cppcc" << endl;
  line() << "#endif // ifndef " << includeMacro;
  
  closeStream();

  // scanner's .cc

  openStream(fullPath(className2cc(dfa.className)));
  line();
  line() << "#include \"" << className2hh(dfa.className) << "\"";
  line();
  for (int i = 0; i < dfa.states.size(); i++)
    line() << "const int cppcc::" << dfa.className << "::" <<
      dfa.states[i]->name << " = " << i << ";";
  line();

  line() << "void cppcc::" << dfa.className << "::_brefill ()" << throwClause;
  line() << "{";
  indent();
  if (registry["DEBUG_SCANNER"])
      line() << "cerr << \"refilling buffer.\" << endl;";
  line() << "if (!*inputStream) {";
  indent();
  writeExceptionCode("Input error.", "onIOError", false);
  unindent();
  line() << "}";
  line() << "for (struct t_laCell *p = _laBegin; p != _laEnd; p = p->next)";
  indent();
  line() << "p->token->_cacheImg();";
  unindent();
  line() << "if (_start != _ch) {";
  indent();
  line() << "if (_start <= _buffer + _pbsz) {";
  indent();
  line() << "int nbsz = _pbsz;";
  line() << "do { nbsz *= 2; } while (nbsz <= _bsz + _pbsz);";
  if (registry["DEBUG_SCANNER"])
    line() << "cerr << \"growing buffer from \" << _bsz << \" to \" << nbsz"
      "<< endl;";
  line() << "_bsz = nbsz;";
  line() << "char *newBuf = new char[_bsz + _pbsz + 1];";
  line() << "memcpy(newBuf + _pbsz, _start, _ch - _start);";
  if (registry["COUNT_COLUMNS"])
    line() << "_bol += newBuf - _buffer;";
  line() << "_ch += newBuf - _buffer;";
  line() << "_start = newBuf + _pbsz;";
  line() << "delete[] _buffer;";
  line() << "_buffer = newBuf;";
  unindent();
  line() << "} else {";
  indent();
  line() << "memmove(_buffer + _pbsz, _start, _ch - _start);";
  if (registry["COUNT_COLUMNS"]) line() << "_bol -= _start - (_buffer + _pbsz);";
  line() << "_ch = _buffer + _pbsz + (_ch - _start);";
  line() << "_start = _buffer + _pbsz;";
  unindent();
  line() << "}";
  unindent();
  line() << "} else {";
  indent();
  line() << "_start = _ch = _buffer + _pbsz;";
  if (registry["COUNT_COLUMNS"])
    line() << "_bol = _start;";
  unindent();
  line() << "}";
  line() << "inputStream->read(_ch, _bsz - (_ch - (_buffer + _pbsz)));";
  line() << "_eob = _ch + inputStream->gcount();";
  line() << "*_eob++  = \'\\0\';";
  line() << "_eof = inputStream->eof();";
  line() << "_lta = false;";
  unindent();
  line() << "}";
  line();
  line() << "void cppcc::" << dfa.className << "::_binit ()" << throwClause;
  line() << "{";
  indent();
  line() << "if (_buffer == NULL) _buffer = new char[_bsz + _pbsz + 1];";
  line() << "_start = _ch = _eob = _buffer + _pbsz;";
  line() << "*_eob++  = \'\\0\';";
  line() << "_eof = inputStream == NULL;";
  unindent();
  line() << "}";
    

  line() << "void cppcc::" << dfa.className
         << "::unGetChars (const char *c, int n)";
  line() << "{";
  /* ok, since we cache the token images anyway this stuff can be greatly
  simplified. Once i'm convinced the OWN_SRINGS is dead and gone i can get rid
         of most of this tuff (cause i no longer need to preserve the text
         before _ch).
  */
  indent();
  line () << "if (_start < _buffer + n) { //grow the buffer";
  indent();
  line() << "int npbsz = _pbsz, delta = 0;";
  line() << "for (struct t_laCell *p = _laBegin; p != _laEnd; p = p->next)";
  indent();
  line() << "p->token->_cacheImg();";
  unindent();
  line() << "do { npbsz *= 2; delta = npbsz - _pbsz; } while (delta < n);";
  if (registry["DEBUG_SCANNER"])
    line() << "cerr << \"growing pushback area from \" << _pbsz"
      " << \" to \" << npbsz << endl;";
  line() << "char *newBuf = new char[_bsz + npbsz + 1];";
  line() << "memcpy(newBuf + delta, _start, _eob - _start + 1);";
  if (registry["COUNT_COLUMNS"])
    line() << "_bol += newBuf + delta - _start;";
  line() << "_ch += newBuf + delta - _start;";
  line() << "_eob += newBuf + delta - _start;";
  line() << "_start = newBuf + delta;";
  line() << "_pbsz = npbsz;";
  line() << "delete[] _buffer;";
  line() << "_buffer = newBuf;";
  unindent();
  line() << "}";
  line() << "memmove(_start - n, _start, n);";
  line() << "_ch -= n;";
  line() << "_start -= n;";
  if (registry["COUNT_COLUMNS"])
    line() << "_bol -= n;";
  line() << "memcpy(_ch, c, n);";
  unindent();
  line() << "}";
  line();
  
  if (registry["DUMP_PROFILE"])
  {
    line();
    line() << "void cppcc::" << dfa.className << "::_freqs_init ()";
    line() << "{";
    indent();
    for (int i = 0; i < sdp.size() ; i++) {
      line() << "_freqs[" << i << "] = new (unsigned int *)[" << sdp[i].size()
             << "];";
      line() << "_freqs_sz[" << i << "] = new unsigned int [" << sdp[i].size()
             << "];";
      for (int j = 0; j < sdp[i].size(); j++) {
        line() << "_freqs[" << i << "][" << j << "] = new unsigned int["
               << sdp[i][j].size() << "];";
        line() << "_freqs_sz[" << i << "][" << j << "] = " << sdp[i][j].size()
               << ";";
        line() << "for (int i = 0; i < " << sdp[i][j].size() << "; i++)";
        line() << "  _freqs[" << i << "][" << j << "][i] = 0;";
      }
          
    }
    unindent();
    line() << "}";
    line();
    line() << "void cppcc::" << dfa.className << "::_freqs_dump ()";
    line() << "{";
    indent();
    line() << "ofstream ofs(\"" << registry["PROFILING_FILE"] << "\");";
    for (int i = 0; i < sdp.size(); i++) {
      for (int j = 0; j < sdp[i].size(); j++) {
        line() << "for (unsigned int i = 0; i < _freqs_sz["
               << i << "][" << j << "]; i++)";
        line() << "  ofs << _freqs[" << i << "][" << j << "][i] << \" \";";
        line() << "ofs << endl;";
      }
      line() << "ofs << endl; ";
    }
    unindent();
    line() << "}";
    line();
    line() << "void cppcc::" << dfa.className
           << "::_bump_counter (int lState, int state, int transition)";
    line() << "{";
    indent();
    line() << "if (_freqs[lState][state][transition] ==  UINT_MAX) {";
    line() << "for (unsigned int i = 0; i < _freqs_sz[lState][state]; i++)";
    line() << "  _freqs[lState][state][i] >>= 1;";
    line() << "}";
    line() << "_freqs[lState][state][transition]++;";
    unindent();
    line() << "}";
    line();
  }
  
  line() << "void cppcc::" << dfa.className << "::_scan (" << tSpec.className
         << " *token)" << throwClause;
  line() << "{";
  indent();
  line() << "register unsigned char c;";
  line();
  
  line() << "for(;;)";
  line() << "{";
  indent();

  // the DFAs:
  
  line() << "switch (getState())";
  line() << "{";
  for (int i = 0; i < dfa.states.size(); i++)
  {
    line() << "case " << dfa.states[i]->name << ":";
    indent();
    writeDfa(*dfa.states[i], sdp[i]);
    unindent();
  }

  // default handler if lexical state went to nowhere
  line() << "default:";
  indent();
  line() << "{";
  indent();
  writeExceptionCode("Illegal lexical state", "onScanError");
  unindent();
  line() << "}";
  unindent();
  
  line() << "}"; // switch (getCurState())

  // code for accepting states/error:
  line();
  for (int t = 0; t < tSpec.count(); t++)
  {
    if (tSpec[t].kind() == ITokenSpec::special) continue;
    
    line() << "__accept_token_" << tSpec[t].name() << "_:";
    indent();

    if (registry["DEBUG_SCANNER"]) {
      line() << "{";
      indent();
      line() << "char x = *_ch;";
      line() << "*_ch = \'\\0\';";
      line() << "cerr << \"Accepted a " << tSpec[t].name()
             << "(\" << " << t << " << \") token at position \" << bPos.ln"
             << (registry["COUNT_COLUMNS"] ? " << \",\" << bPos.col" : "")
             << " << \" up to \" << ePos.ln"
             << (registry["COUNT_COLUMNS"] ? " << \",\" << ePos.col + (_ch - _bol)" : "")
             << " << \" image: \\\"\" << _start << \"\\\".\" << endl;";
      line() << "*_ch = x;";
      unindent();
      line() << "}";
    }

    switch (tSpec[t].kind())
    {
    case ITokenSpec::skip:
      if (registry["COUNT_COLUMNS"]) {
        line() << "ePos.col += _ch - _bol;";
        line() << "_bol = _ch;";
      }
      if (!tSpec[t].tokAction().empty()) {
        line() << "token->_set(" << tSpec.className << "::" << tSpec[t].name()
               << ", bPos, ePos, _start, _ch - _start);";
        line() << "{";
        writeChunk(tSpec[t].tokAction());
        line() << "}";
      }
      line() << "_start = _ch;";
      line() << "bPos = ePos;";
      line() << "continue;";
      break;
    case ITokenSpec::keyword:
      line() << "{";
      indent();
      line() << "token->id = " << tSpec.className << "::" << tSpec[t].name()
             << ";";
      if (registry["COUNT_COLUMNS"]) {
        line() << "ePos.col += _ch - _bol;";
        line() << "_bol = _ch;";
      }
      line() << "token->bPos = bPos;";
      line() << "token->ePos = ePos;";
      if (!tSpec[t].tokAction().empty()) {
        line() << "token->_set(_start, _ch - _start);";
        line() << "{";
        writeChunk(tSpec[t].tokAction());
        line() << "}";
      }
      line() << "commonTokenAction (*token);";
      line() << "bPos = ePos;";
      line() << "_start = _ch;";
      line() << "if (_reject) { _reject = false; continue; }";
      line() << "else return;";
      unindent();
      line() << "}";
      break;
    case ITokenSpec::regular:
      line() << "{";
      indent();
      if (registry["COUNT_COLUMNS"]) {
        line() << "ePos.col += _ch - _bol;";
        line() << "_bol = _ch;";
      }
      line() << "token->_set(" << tSpec.className << "::" << tSpec[t].name()
             << ", bPos, ePos, _start, _ch - _start);";
      if (!tSpec[t].tokAction().empty()) {
        line() << "{";
        writeChunk(tSpec[t].tokAction());
        line() << "}";
      }
      line() << "commonTokenAction (*token);";
      line() << "bPos = ePos;";
      line() << "_start = _ch;";
      line() << "if (_reject) { _reject = false; continue; }";
      line() << "else return;";
      unindent();
      line() << "}";
      break;
    case ITokenSpec::more:
      if (!tSpec[t].tokAction().empty()) {
        if (registry["COUNT_COLUMNS"]) {
          line() << "ePos.col += _ch - _bol;";
          line() << "_bol = _ch;";
        }
        line() << "token->_set(" << tSpec.className << "::" << tSpec[t].name()
               << ", bPos, ePos, _start, _ch - _start);";
        line() << "_more = true;";
        line() << "{";
        writeChunk(tSpec[t].tokAction());
        line() << "}";
        line() << "_more = false;";
      }
      line() << "continue;";
    }
    unindent();
  }
  line() << "__scan_error_:";
  indent();
  line() << "{";
  indent();
#ifdef DEBUG
  line() << "cerr << \" unexpected: 0x\" << hex << (int) c << endl;";
#endif
  line() << "string msg = string(\"Unexpected character \\\'\") + (char) c + \"\\\'.\";";
  writeExceptionCode("msg", "onScanError", true);
  unindent();
  line() << "}";
  unindent();

  line() << "__unexpected_eof_:";
  indent();
  line() << "{";
  indent();
  line() << "string msg(\"Unexpected EOF.\");";
  writeExceptionCode("msg", "onScanError", true);
  unindent();
  line() << "}";

  line() << "__eof_seen_:";
  indent();
  line() << "token->id = " << tSpec.className << "::eof;";
  line() << "token->bPos = bPos;";
  line() << "token->ePos = ePos;";
  line() << "return;";
  unindent();

  unindent();  
  unindent();
  line() << "}"; // for (;;)
  unindent();
  line() << "}"; // _scan()
  line();
  closeStream();
}

typedef map<int, vector<unsigned char> > GoToMap;
typedef pair<unsigned long int, GoToMap::iterator> Wtrans;
struct t_Wgtr : public binary_function<Wtrans, Wtrans, bool>
{
  bool operator () (const Wtrans &a, const Wtrans &b)
  {
    return a.first > b.first;
  }
};
      
void ScannerDfaWriter::writeDfa (BasicDfaSpec &dfa, BasicDfaProfile &sdp)
{
  for (int s = 0; s < dfa.states.size(); s++)
  {
    line() << "__" << dfa.name << "_" << s << "_:";
    indent();
    // regroup the transitions table by next state
    
    GoToMap goTo;
    for (int t = 0; t < dfa.states[s].transitions.size(); t++)
    {
      goTo[dfa.states[s].transitions[t].to].
                        push_back(dfa.states[s].transitions[t].on);
    }  

    // WeightedTrans will contain pairs consisting of an interator into the
    // goTo map (aka pointer to a transition from the current state) and its
    // weight or frequency as read from the profiling file. We then order this
    // list by the frequencies and generate code such that the most frequent
    // transitions are placed at the beginning.
    vector<Wtrans> weightedTrans;

    {
      int k = 0;
      for (GoToMap::iterator i = goTo.begin(); i != goTo.end(); i++, k++)
        weightedTrans.push_back(Wtrans(sdp[s][k], i));

      stable_sort<vector<Wtrans>::iterator, t_Wgtr>(weightedTrans.begin(),
                                                    weightedTrans.end(),
                                                    struct t_Wgtr());
    }
        
    // dump transitions:
    int transNo = 0;
    for (vector<Wtrans>::iterator i = weightedTrans.begin();
         i != weightedTrans.end(); i++, transNo++)
    {
      if (i != weightedTrans.begin()) line() << "else ";
      else {
        line() << "c = *_ch++;";
        line();
      }
      Wtrans &wtr = *i;
      unsigned long int weight = wtr.first;
      ofs << " /*" << weight << "*/ if (";
      int nextState = (*wtr.second).first;
      vector<unsigned char> &on = (*wtr.second).second;
      sort(on.begin(), on.end());
      int j = 0;
      j = writeCharCompare(on, j);
      while (j < on.size())
      {
        ofs << " || ";
        j = writeCharCompare(on, j);
      }
      ofs << ")";
      indent();
      line();
      if (registry["DUMP_PROFILE"])
        ofs << "{ _bump_counter(" << dfa.name << ", " << s << ", "
            << transNo << "); ";
      ofs << "goto __" << dfa.name << "_" << nextState << "_;";
      if (registry["DUMP_PROFILE"])
        ofs << " }";
      unindent();
    }
    if (!goTo.empty())
    {
      line() << "if ((_ch-- == _eob) && (c == \'\\0\')) {";
      indent();
      line() << "if (_eof) {";
      indent();
      if (!registry["TOKENS_SPAN_EOF"]) {
        line() << "if ((_ch != _start) && !_lta)";
        if (dfa.states[s].isFinal)
          ofs << "{ _lta = true; goto __accept_token_"
              << tSpec[dfa.states[s].tokId].name() << "_; }";
        else ofs << "goto __unexpected_eof_;";
      }
      line() << "if (!wrap()) goto __eof_seen_;";
      unindent();
      line() << "}";
      line() << "if (_ch + 1 == _eob) _brefill();";
      line() << "goto __" << dfa.name << "_" << s << "_;";
      unindent();
      line() << "}";
    }
    // dump what do we do if no transition was taken:
    if (dfa.states[s].isFinal) {
      // weppeeeee just found a token !
      line() << "goto __accept_token_"
             << tSpec[dfa.states[s].tokId].name() << "_;";
    } else {
      // uh oh...
      line() << "goto __scan_error_;";
    }
    unindent();
  }
}

string formatChar (unsigned int c)
{
  ostringstream oss;
  oss << "'";
  if (isgraph(c)) {
    switch (c) {
    case '\'': oss << "\\\'"; break;
    case '\\': oss << "\\\\"; break;
    default: oss << (unsigned char) c;
    }
  }
  else 
    switch (c)
    {
    case ' ': oss << " "; break;
    case '\n': oss << "\\n"; break;
    case '\t': oss << "\\t"; break;
    case '\v': oss << "\\v"; break;
    case '\b': oss << "\\b"; break;
    case '\r': oss << "\\r"; break;
    case '\f': oss << "\\f"; break;
    case '\\': oss << "\\\\"; break;
    case '\"': oss << "\\\""; break;
    case '\'': oss << "\\\'"; break;
    default:
      oss << oct << "\\" << c;
    }
  oss << "\' /*" << dec << c<< "*/";
  return oss.str();
}

int ScannerDfaWriter::writeCharCompare (vector<unsigned char> v, int i)
{
  int j = i + 1;
  unsigned char first = v[i];
  unsigned char last = v[i];
  while ((j < v.size()) && (v[j] == last + 1)) last = v[j++];

  if (first == last) {
    if (first == 0)
      ofs << "((c == \'\\0\') && (_ch != _eob))";
    else
      ofs << "(c == " << formatChar(first) << ")";
    
  } else {
    if (first == 0) {
      ofs << "((c == \'\\0\') && (_ch != _eob)) || ";
      first++;
    }
    if (last == 255)
      ofs << "("<< formatChar(first) << " <= c)";
    else 
      ofs << "((" << formatChar(first) << " <= c) && (c <= "
          << formatChar(last) << "))";
  }
  
  return j;
}


void ScannerDfaWriter::writeExceptionCode (const string &what,
                                           const string &handlerName,
                                           bool isName)
{
  if (isName) {
    line() << "ScanException __ex(ePos, " << what << ");";
  } else {
    line() << "ScanException __ex(ePos, \"" << what << "\");";
  }
  if (registry["DEBUG_SCANNER"])
    line() << "cerr << \"Scanner exception: \" << __ex.what() << endl;";
  line() << "if (!" << handlerName << "(__ex))";
  indent();
  if (registry["USE_EXCEPTIONS"]) line() << "throw __ex;";
  else line() << "abort();";
  unindent();
}

---