blob: 106bd0d161b4ed7bd96b47c9c248717d3df4cbe7 [file] [log] [blame]
/* $Id$ */
#define MAX_ARITY 2
#include <stdio.h>
typedef int ItemSetNum;
typedef int OperatorNum;
typedef int NonTerminalNum;
typedef int RuleNum;
typedef int ArityNum;
typedef int ERuleNum;
extern NonTerminalNum last_user_nonterminal;
extern NonTerminalNum max_nonterminal;
extern RuleNum max_rule;
extern ERuleNum max_erule_num;
extern int max_arity;
#ifdef __STDC__
#define ARGS(x) x
#define ARGS(x) ()
#ifndef NOLEX
#define DELTAWIDTH 4
typedef short DeltaCost[DELTAWIDTH];
typedef short *DeltaPtr;
extern void ASSIGNCOST ARGS((DeltaPtr, DeltaPtr));
extern void ADDCOST ARGS((DeltaPtr, DeltaPtr));
extern void MINUSCOST ARGS((DeltaPtr, DeltaPtr));
extern void ZEROCOST ARGS((DeltaPtr));
extern int LESSCOST ARGS((DeltaPtr, DeltaPtr));
extern int EQUALCOST ARGS((DeltaPtr, DeltaPtr));
#define PRINCIPLECOST(x) (x[0])
#define DELTAWIDTH 1
typedef int DeltaCost;
typedef int DeltaPtr;
#define ASSIGNCOST(l, r) ((l) = (r))
#define ADDCOST(l, r) ((l) += (r))
#define MINUSCOST(l, r) ((l) -= (r))
#define ZEROCOST(x) ((x) = 0)
#define LESSCOST(l, r) ((l) < (r))
#define EQUALCOST(l, r) ((l) == (r))
#define PRINCIPLECOST(x) (x)
#endif /* NOLEX */
#define NODIVERGE(c,state,nt,base) if (prevent_divergence > 0) CHECKDIVERGE(c,state,nt,base);
struct list {
void *x;
struct list *next;
typedef struct list *List;
struct intlist {
int x;
struct intlist *next;
typedef struct intlist *IntList;
struct operator {
char *name;
unsigned int ref:1;
OperatorNum num;
ItemSetNum baseNum;
ItemSetNum stateCount;
ArityNum arity;
struct table *table;
typedef struct operator *Operator;
struct nonterminal {
char *name;
NonTerminalNum num;
ItemSetNum baseNum;
ItemSetNum ruleCount;
struct plankMap *pmap;
struct rule *sampleRule; /* diagnostic---gives "a" rule that with this lhs */
typedef struct nonterminal *NonTerminal;
struct pattern {
NonTerminal normalizer;
Operator op; /* NULL if NonTerm -> NonTerm */
NonTerminal children[MAX_ARITY];
typedef struct pattern *Pattern;
struct rule {
DeltaCost delta;
ERuleNum erulenum;
RuleNum num;
RuleNum newNum;
NonTerminal lhs;
Pattern pat;
unsigned int used:1;
typedef struct rule *Rule;
struct item {
DeltaCost delta;
Rule rule;
typedef struct item Item;
typedef short *Relevant; /* relevant non-terminals */
typedef Item *ItemArray;
struct item_set { /* indexed by NonTerminal */
ItemSetNum num;
ItemSetNum newNum;
Operator op;
struct item_set *kids[2];
struct item_set *representative;
Relevant relevant;
ItemArray virgin;
ItemArray closed;
typedef struct item_set *Item_Set;
#define DIM_MAP_SIZE (1 << 8)
#define GLOBAL_MAP_SIZE (1 << 15)
struct mapping { /* should be a hash table for TS -> int */
List *hash;
int hash_size;
int max_size;
ItemSetNum count;
Item_Set *set; /* map: int <-> Item_Set */
typedef struct mapping *Mapping;
struct index_map {
ItemSetNum max_size;
Item_Set *class;
typedef struct index_map Index_Map;
struct dimension {
Relevant relevant;
Index_Map index_map;
Mapping map;
ItemSetNum max_size;
struct plankMap *pmap;
typedef struct dimension *Dimension;
struct table {
Operator op;
List rules;
Relevant relevant;
Dimension dimen[MAX_ARITY]; /* 1 for each dimension */
Item_Set *transition; /* maps local indices to global
itemsets */
typedef struct table *Table;
struct relation {
Rule rule;
DeltaCost chain;
NonTerminalNum nextchain;
DeltaCost sibling;
int sibFlag;
int sibComputed;
typedef struct relation *Relation;
struct queue {
List head;
List tail;
typedef struct queue *Queue;
struct plank {
char *name;
List fields;
int width;
typedef struct plank *Plank;
struct except {
short index;
short value;
typedef struct except *Exception;
struct plankMap {
List exceptions;
int offset;
struct stateMap *values;
typedef struct plankMap *PlankMap;
struct stateMap {
char *fieldname;
Plank plank;
int width;
short *value;
typedef struct stateMap *StateMap;
struct stateMapTable {
List maps;
extern void CHECKDIVERGE ARGS((DeltaPtr, Item_Set, int, int));
extern void zero ARGS((Item_Set));
extern ItemArray newItemArray ARGS((void));
extern ItemArray itemArrayCopy ARGS((ItemArray));
extern Item_Set newItem_Set ARGS((Relevant));
extern void freeItem_Set ARGS((Item_Set));
extern Mapping newMapping ARGS((int));
extern NonTerminal newNonTerminal ARGS((char *));
extern int nonTerminalName ARGS((char *, int));
extern Operator newOperator ARGS((char *, OperatorNum, ArityNum));
extern Pattern newPattern ARGS((Operator));
extern Rule newRule ARGS((DeltaPtr, ERuleNum, NonTerminal, Pattern));
extern List newList ARGS((void *, List));
extern IntList newIntList ARGS((int, IntList));
extern int length ARGS((List));
extern List appendList ARGS((void *, List));
extern Table newTable ARGS((Operator));
extern Queue newQ ARGS((void));
extern void addQ ARGS((Queue, Item_Set));
extern Item_Set popQ ARGS((Queue));
extern int equivSet ARGS((Item_Set, Item_Set));
extern Item_Set decode ARGS((Mapping, ItemSetNum));
extern Item_Set encode ARGS((Mapping, Item_Set, int *));
extern void build ARGS((void));
extern Item_Set *transLval ARGS((Table, int, int));
typedef void * (*ListFn) ARGS((void *));
extern void foreachList ARGS((ListFn, List));
extern void reveachList ARGS((ListFn, List));
extern void addToTable ARGS((Table, Item_Set));
extern void closure ARGS((Item_Set));
extern void trim ARGS((Item_Set));
extern void findChainRules ARGS((void));
extern void findAllPairs ARGS((void));
extern void addRelevant ARGS((Relevant, NonTerminalNum));
extern void *zalloc ARGS((unsigned int));
extern void zfree ARGS((void *));
extern NonTerminal start;
extern List rules;
extern List chainrules;
extern List operators;
extern List leaves;
extern List nonterminals;
extern List grammarNts;
extern Queue globalQ;
extern Mapping globalMap;
extern int exceptionTolerance;
extern int prevent_divergence;
extern int principleCost;
extern int lexical;
extern struct rule stub_rule;
extern Relation *allpairs;
extern Item_Set *sortedStates;
extern Item_Set errorState;
extern void dumpRelevant ARGS((Relevant));
extern void dumpOperator ARGS((Operator, int));
extern void dumpOperator_s ARGS((Operator));
extern void dumpOperator_l ARGS((Operator));
extern void dumpNonTerminal ARGS((NonTerminal));
extern void dumpRule ARGS((Rule));
extern void dumpRuleList ARGS((List));
extern void dumpItem ARGS((Item *));
extern void dumpItem_Set ARGS((Item_Set));
extern void dumpMapping ARGS((Mapping));
extern void dumpQ ARGS((Queue));
extern void dumpIndex_Map ARGS((Index_Map *));
extern void dumpDimension ARGS((Dimension));
extern void dumpPattern ARGS((Pattern));
extern void dumpTable ARGS((Table, int));
extern void dumpTransition ARGS((Table));
extern void dumpCost ARGS((DeltaCost));
extern void dumpAllPairs ARGS((void));
extern void dumpRelation ARGS((Relation));
extern void dumpSortedStates ARGS((void));
extern void dumpSortedRules ARGS((void));
extern int debugTrim;
#ifdef DEBUG
#define debug(a,b) if (a) b
#define debug(a,b)
extern int debugTables;
#define TABLE_INCR 8
#define STATES_INCR 64
#ifdef NDEBUG
#define assert(c) ((void) 0)
#define assert(c) ((void) ((c) || fatal(__FILE__,__LINE__)))
extern void doStart ARGS((char *));
extern void exit ARGS((int));
extern int fatal ARGS((char *, int));
extern void yyerror ARGS((char *));
extern void yyerror1 ARGS((char *));
extern void makeRuleDescArray();
extern void makeDeltaCostArray();
extern void makeStateStringArray();