lextable.pas

Yacc例子代码

{
  This module collects the various tables used by the Lex program:
  - the symbol table
  - the position table
  - the DFA states and transition tables
  Note: All tables are allocated dynamically (at initialization time)
  because of the 64KB static data limit.


  Copyright (c) 1990-92  Albert Graef <[e-mail]>
  Copyright (C) 1996     Berend de Boer <[e-mail]>

  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., 675 Mass Ave, Cambridge, MA 02139, USA.


$Revision: 2 $
$Modtime: 96-08-01 10:23 $

$History: LEXTABLE.PAS $
 * 
 * *****************  Version 2  *****************
 * User: Berend       Date: 96-10-10   Time: 21:16
 * Updated in $/Lex and Yacc/tply
 * Updated for protected mode, windows and Delphi 1.X and 2.X.

}


unit LexTable;

interface

uses LexBase;


{$IFNDEF Win32}
var max_bytes : LongInt;
  (* available memory *)

function n_bytes : LongInt;
  (* memory actually used *)
{$ENDIF}

const

(* Maximum table sizes: *)

max_keys           =  997;  (* size of hash symbol table (prime number!)   *)
{$IFDEF MsDos}
max_pos            =  600;  (* maximum number of positions                 *)
max_states         =  300;  (* number of DFA states                        *)
max_trans          =  600;  (* number of transitions                       *)
max_start_states   =   50;  (* maximum number of user-defined start states *)
{$ELSE}
max_pos            = 1200;  (* maximum number of positions                 *)
max_states         =  600;  (* number of DFA states                        *)
max_trans          = 1200;  (* number of transitions                       *)
max_start_states   =  100;  (* maximum number of user-defined start states *)
{$ENDIF}

var

(* Actual table sizes: *)

n_pos            : Integer;
n_states         : Integer;
n_trans          : Integer;
n_start_states   : Integer;

type

(* Table data structures: *)

SymTable = array [1..max_keys] of record
             pname  : StrPtr;
               (* print name; empty entries are denoted by pname=nil *)
             case sym_type : ( none, macro_sym, start_state_sym ) of
             macro_sym : ( subst : StrPtr );
               (* macro substitution *)
             start_state_sym : ( start_state : Integer );
               (* start state *)
           end;

PosTableEntry = record
                  follow_pos    : IntSetPtr;
                    (* set of follow positions *)
                  case pos_type : ( char_pos, cclass_pos, mark_pos ) of
                  char_pos      : ( c   : Char );
                    (* character position *)
                  cclass_pos    : ( cc  : CClassPtr );
                    (* character class position *)
                  mark_pos      : ( rule, pos : Integer );
                    (* mark position *)
                end;

PosTable = array [1..max_pos] of PosTableEntry;

FirstPosTable  = array [0..2*max_start_states+1] of IntSetPtr;
                   (* first positions for start states (even states
                      are entered anywhere on the line, odd states only
                      at the beginning of the line; states 0 and 1 denote
                      default, states 2..2*n_start_states+1 user-defined
                      start states) *)

StateTableEntry = record
                    state_pos : IntSetPtr;
                      (* positions covered by state *)
                    final     : Boolean;
                      (* final state? *)
                    trans_lo,
                    trans_hi  : Integer;
                      (* transitions *)
                  end;

StateTable = array [0..max_states-1] of StateTableEntry;

TransTableEntry = record
                    cc              : CClassPtr;
                      (* characters of transition *)
                    follow_pos      : IntSetPtr;
                      (* follow positions (positions of next state) *)
                    next_state      : Integer;
                      (* next state *)
                  end;

TransTable = array [1..max_trans] of TransTableEntry;


var

verbose           : Boolean;          (* status of the verbose option *)
optimize          : Boolean;          (* status of the optimization option *)

sym_table         : ^SymTable;        (* symbol table *)
pos_table         : ^PosTable;        (* position table *)
first_pos_table   : ^FirstPosTable;   (* first positions table *)
state_table       : ^StateTable;      (* DFA state table *)
trans_table       : ^TransTable;      (* DFA transition table *)


(* Operations: *)

(* Hash symbol table:
   The following routines are supplied to be used with the generic hash table
   routines in LexBase. *)

function lookup(k : Integer) : String;
  (* print name of symbol no. k *)
procedure entry(k : Integer; symbol : String);
  (* enter symbol into table *)

(* Routines to build the position table: *)

procedure addCharPos(c : Char);
procedure addCClassPos(cc : CClassPtr);
procedure addMarkPos(rule, pos : Integer);
  (* Positions are allocated in the order of calls to addCharPos, addCClassPos
     and addMarkPos, starting at position 1. These routines also initialize
     the corresponding follow sets. *)

(* Routines to build the state table: *)

var act_state : Integer; (* state currently considered *)

function newState(POS : IntSetPtr) : Integer;
  (* Add a new state with the given position set; initialize the state's
     position set to POS (the offsets into the transition table are
     initialized when the state becomes active, see startStateTrans, below).
     Returns: the new state number *)

function addState(POS : IntSetPtr) : Integer;
  (* add a new state, but only if there is not already a state with the
     same position set *)

procedure startStateTrans;
procedure endStateTrans;
  (* initializes act_state's first and last offsets into the transition
     table *)

function n_state_trans(i : Integer) : Integer;
  (* return number of transitions in state i *)

procedure addTrans(cc : CClass; FOLLOW : IntSetPtr);
  (* adds a transition to the table *)

procedure mergeTrans;
  (* sorts transitions w.r.t. next states and merges transitions for the
     same next state in the active state *)

procedure sortTrans;
  (* sort transitions in act_state lexicographically *)

implementation

uses LexMsgs;

{$IFNDEF Win32}
function n_bytes : LongInt;
  begin
    n_bytes := max_bytes-memAvail
  end(*n_bytes*);
{$ENDIF}

(* Hash table routines: *)

function lookup(k : Integer) : String;
  begin
    with sym_table^[k] do
      if pname=nil then
        lookup := ''
      else
        lookup := copy(pname^, 1, length(pname^))
  end(*lookup*);
procedure entry(k : Integer; symbol : String);
  begin
    with sym_table^[k] do
      begin
        pname    := newStr(symbol);
        sym_type := none;
      end
  end(*entry*);

(* Routines to build the position table: *)

procedure addCharPos(c : Char);
  begin
    inc(n_pos);
    if n_pos>max_pos then fatal(pos_table_overflow);
    pos_table^[n_pos].follow_pos     := newIntSet;
    pos_table^[n_pos].pos_type       := char_pos;
    pos_table^[n_pos].c              := c;
  end(*addCharPos*);

procedure addCClassPos(cc : CClassPtr);