{
  This module collects the various tables used by the Yacc program:
  - the symbol table
  - the rule table
  - the precedence table
  - the closure table
  - the LALR state, item, transition and reduction table
  Note: All tables are allocated dynamically (at initialization time)
  because of the 64KB static data limit. *)


  Copyright (c) 1990-92  Albert Graef <ag@muwiinfa.geschichte.uni-mainz.de>
  Copyright (C) 1996     Berend de Boer <berend@pobox.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., 675 Mass Ave, Cambridge, MA 02139, USA.


$Revision: 2 $
$Modtime: 96-07-31 21:15 $

$History: YACCTABL.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 YaccTabl;

interface

uses
  YaccBase;


{$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_nts            =  300;  (* maximum number of nonterminals              *)
max_lits           =  556;  (* number of literals (300+256)                *)
max_rules          =  301;  (* number of rules (300+1)                     *)
max_types          =  100;  (* number of type tags                         *)
max_prec           =   50;  (* maximum precedence level                    *)
max_states         =  600;  (* number of LR(0) states                      *)
max_items          = 2400;  (* number of items                             *)
max_trans          = 2400;  (* number of transitions                       *)
max_redns          = 1200;  (* number of reductions                        *)
{$ELSE}
max_nts            =  900;  (* maximum number of nonterminals              *)
max_lits           =  max_nts+256;  (* number of literals (300+256)                *)
max_rules          =  max_nts+1;  (* number of rules (300+1)                     *)
max_types          =  100;  (* number of type tags                         *)
max_prec           =   50;  (* maximum precedence level                    *)
{$IFDEF Windows}
max_states         =  800;  (* number of LR(0) states                      *)
{$ELSE}
max_states         = 1200;  (* number of LR(0) states                      *)
{$ENDIF}
max_items          = 9600;  (* number of items                             *)
max_trans          = 9600;  (* number of transitions                       *)
max_redns          = 1200;  (* number of reductions                        *)
{$ENDIF}

{$IFDEF MsDos}
max_rule_len       =   64;  (* maximum length of rules                     *)
max_set_items      =   64;  (* maximum number of items in an item set      *)
{$ELSE}
max_rule_len       =   64;  (* maximum length of rules                     *)
max_set_items      =   96;  (* maximum number of items in an item set      *)
{$ENDIF}

var

(* Actual table sizes: *)

n_nts            : Integer;
n_lits           : Integer;
n_rules          : Integer;
n_types          : Integer;
n_prec           : Integer;
n_states         : Integer;
n_items          : Integer;
n_trans          : Integer;
n_redns          : Integer;

type

(* Table data structures: *)

(* Symbol table: The symbol table consists of a hash table which stores
   print names and internal symbol numbers, and a key table which stores,
   for each internal symbol number, the corresponding hash key. *)

SymRec = record
           pname  : StrPtr;
             (* print name; empty entries are denoted by pname=nil *)
           deff   : Boolean;
             (* flag denoting whether symbol is already defined *)
           sym    : Integer;
             (* internal symbol number (0 or positive: literal symbols
                (literal characters have symbol numbers 1 thru 255);
                negative: nonterminal symbols; 0 denotes endmarker,
                -1 augmented start nonterminal, 256 is reserved for
                error token; note that the predefined symbols except
                the error literal are not actually stored in the symbol
                table; the error symbol is entered at initialization
                s.t. it always has number 256) *)
         end;

SymTable = array [1..max_keys] of SymRec;

SymKeyTable = array [-max_nts..max_lits-1] of Integer;
  (* hash keys for nonterminal and literal symbols *)

(* Rule table: the rule table consists of an array storing the rules
   sequentially in the order in which they appear in the source grammar;
   a rule no.s table which is used to sort rules w.r.t. left-hand side
   nonterminals (after the rule table has been constructed and sorted, all
   references to rules are done indirectly via the rule_no array s.t. the
   rules for each nonterminal can be accessed easily); and an offset table
   which stores, for each nonterminal, the corresponding first and last
   index in the rule no.s table. *)

RuleRec = record
            lhs_sym : Integer; (* lhs nonterminal *)
            rhs_len : Integer; (* length of rhs *)
            rhs_sym : array [1..max_rule_len] of Integer;
              (* rhs symbols *)
          end;

RuleRecPtr = ^RuleRec;

RuleTable = array [1..max_rules] of RuleRecPtr;

RuleNoTable = array [1..max_rules] of Integer;

RuleOffsRec = record
                rule_lo, rule_hi : Integer;
              end;

RuleOffsTable = array [1..max_nts] of RuleOffsRec;

(* Symbol type table: The symbol type table stores the types associated
   with the nonterminal and terminal grammar symbols (0 if none). *)

TypeTable    = array [1..max_types] of Integer;
  (* types declared in the definitions section *)

SymTypeTable = array [-max_nts..max_lits-1] of Integer;
  (* symbol types *)

(* Precedence table: The precedence table stores the type of each
   precedence level (left, right, nonassoc) and, for each literal
   symbol and grammar rule, the assigned precedence level (precedence
   level 0 if none). *)

PrecType = ( left, right, nonassoc );

PrecTable = array [1..max_prec] of PrecType;

SymPrecTable = array [0..max_lits-1] of Integer;

RulePrecTable = array [1..max_rules] of Integer;

(* Closure and first symbols table: The closure table stores, for each
   nonterminal X, the set of those nonterminals Y for which there is a
   rightmost derivation X =>+ Y ... . Similarly, the first set table
   stores, for each nonterminal X, the set of literals a for which there
   is a derivation X =>+ a ... . Both tables are of type SymSetTable.

   The nullable table stores, for each nonterminal, a flag denoting whether
   the nonterminal is nullable (i.e. may be derived to the empty string).

   These tables are constructed by the routines in the YaccClosure unit,
   and are used by the LALR parser construction algorithms in YaccLR0 and
   YaccLookaheads. *)

SymSetTable = array [1..max_nts] of IntSetPtr;

NullableTable = array [1..max_nts] of Boolean;

(* State table:

   Each state stores the first and last index of the kernel items,
   transitions and reductions belonging to it, and a hash key determined
   from the kernel items which is used to speed up searches for existing
   states.

   The items table stores the individual kernel items in the LR(0) set.
   Each entry consists of a rule number together with the item position,
   and a "next" field indicating the associated item in the successor state
   (0 if there is none). The ItemSet type is used to retrieve and manipulate
   individual item sets from the item table.

   The transition table stores the shift and goto transitions in each state
   (each transition is denoted by a (symbol, next_state) pair). Similarly,
   the reductions table stores the reductions in each state, where each
   action is denoted by a (symbolset, ruleno) pair. *)

StateRec = record
             item_lo, item_hi : Integer;
             trans_lo, trans_hi : Integer;
             redns_lo, redns_hi : Integer;
             key : Integer;
           end;

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

ItemRec = record
            rule_no, pos_no : Integer;
            next : Integer;
          end;

ItemSet = record
            n_items : Integer;
            item    : array [1..max_set_items] of ItemRec;
          end;

ItemTable = array [1..max_items] of ItemRec;

TransRec = record
             sym, next_state : Integer;
           end;

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

RednRec = record
            symset : IntSetPtr;
            rule_no : Integer;
          end;

RednTable = array [1..max_redns] of RednRec;

(* Lookaheads table: This table stores, for each kernel item, the
   corresponding LALR(1) lookahead symbol sets. *)

LookaheadTable = array [1..max_items] of IntSetPtr;

(* The propagation table is used to keep track of how lookaheads are
   propagated from kernel items to other lookahead sets. *)

PropList = ^PropEntry;

PropEntry = record
              symset : IntSetPtr;
              next : PropList;
            end;

PropTable = array [1..max_items] of PropList;


var

verbose           : Boolean;          (* status of the verbose option *)
debug             : Boolean;          (* status of the debug option *)
startnt           : Integer;          (* start nonterminal of grammar
                                         (0 if undefined) *)
sym_table         : ^SymTable;        (* symbol table *)
sym_key           : ^SymKeyTable;     (* symbol keys *)
rule_table        : ^RuleTable;       (* rule table *)
type_table        : ^TypeTable;       (* type table *)
sym_type          : ^SymTypeTable;    (* symbol types *)
prec_table        : ^PrecTable;       (* precedence table *)
sym_prec          : ^SymPrecTable;    (* literal symbols precedence *)
rule_prec         : ^RulePrecTable;   (* rules precedence *)
rule_no           : ^RuleNoTable;     (* rule no table *)
rule_offs         : ^RuleOffsTable;   (* rule offset table *)
closure_table     : ^SymSetTable;     (* closure table *)
first_set_table   : ^SymSetTable;     (* first set table *)
nullable          : ^NullableTable;   (* nullable flags table *)
state_table       : ^StateTable;      (* LR(0) state table *)
item_table        : ^ItemTable;       (* LR(0) kernel item table *)
trans_table       : ^TransTable;      (* transition table *)
redn_table        : ^RednTable;       (* reduction table *)
lookahead_table   : ^LookaheadTable;  (* LALR lookaheads table *)
prop_table        : ^PropTable;       (* lookahead propagation table *)


(* Operations: *)

(* Symbol table routines: *)

function new_nt : Integer;
  (* returns a new nonterminal number (<-1) *)

function new_lit : Integer;
  (* returns a new literal number above 256 *)

procedure add_lit ( sym : Integer );
  (* this routine allows to add a user-defined literal symbol;
     the current literal symbols count is adjusted accordingly *)

function get_key ( symbol : String ) : Integer;
  (* returns a hash key for symbol *)

procedure def_key ( k : Integer; sym : Integer );
  (* defines k to be a new symbol with internal symbol number sym *)

function is_def_key ( k : Integer; var sym : Integer ) : Boolean;
  (* checks whether symbol denoted by symbol table key k is already
     defined; if so, returns the corresponding symbol number *)

function pname ( sym : Integer ) : String;
  (* returns the print name of an internal symbol (`$end' for