util/LLgen/src/types.h

   1 /* Copyright (c) 1991 by the Vrije Universiteit, Amsterdam, the Netherlands.
   2  * For full copyright and restrictions on use see the file COPYING in the top
   3  * level of the LLgen tree.
   4  */
   5
   6 /*
   7  *  L L G E N
   8  *
   9  *  An Extended LL(1) Parser Generator
  10  *
  11  *  Author : Ceriel J.H. Jacobs
  12  */
  13
  14 /*
  15  * $Id: types.h,v 2.13 1997/02/21 11:27:57 ceriel Exp $
  16  * Type and structure definitions
  17  */
  18
  19 typedef int     *p_set;         /* pointer to bitset */
  20 typedef char    *p_mem;         /* pointer to some core */
  21 typedef char    *string;
  22
  23 /*
  24  * structure for a token
  25  */
  26 typedef struct token {
  27         int     t_tokno;        /* Lexical token number */
  28         union {
  29                 string  t_s;    /* Attribute is either a string or */
  30                 int     t_v;    /* an integer */
  31         } t_x;
  32 # define t_string t_x.t_s
  33 # define t_num t_x.t_v
  34         int     t_flags;
  35         int     t_next;
  36         int     t_lineno;
  37 } t_token, *p_token;
  38
  39 /*
  40  * structure for the grammar elements
  41  */
  42 typedef struct gram {
  43         int     x;              /* for lay-out see comment below */
  44         int     g_lineno;       /* element found on this line number */
  45 #ifdef NON_CORRECTING
  46         int     g_erroneous;    /* 1 if element declared erroneous */
  47 #endif
  48         union {
  49                 int     g_index;
  50                 struct term *   g_term;
  51                 struct link *   g_link;
  52 #ifdef NON_CORRECTING
  53                 /* If this is an action with a %substart g_subparse
  54                    points to the list of startsymbols of the subparser */
  55                 struct ff_firsts *g_subparse;
  56 #endif
  57         } g_i;
  58 } t_gram,*p_gram;
  59
  60 /*
  61  * Layout of the field x:
  62  *
  63  * 15  ....... 7 6 ........ 3 2 .... 0
  64  * -----------------------------------
  65  * | unused    | | nparams  | | type |
  66  * -----------------------------------
  67  */
  68 # define EORULE         00      /* End of (sub)rule */
  69 # define ACTION         01      /* Imbedded action */
  70 # define NONTERM        02      /* A nonterminal */
  71 # define TERMINAL       03      /* A terminal */
  72 # define TERM           04      /* Something between square brackets */
  73 # define ALTERNATION    05      /* Alternation (|) */
  74 # define LITERAL        06      /* Also a terminal */
  75
  76 /*
  77  * Access macros for the x-field of a grammar element
  78  */
  79 # define g_gettype(p)   ((p)->x&07)
  80 # define g_getcont(p)   ((p)->g_i.g_index)
  81 # define g_getterm(p)   ((p)->g_i.g_term)
  82 # define g_getlink(p)   ((p)->g_i.g_link)
  83 # define g_getnpar(p)   (((p)->x>>3)&017)
  84 # define g_settype(p,s) { assert(((unsigned)(s))<=07);(p)->x=((p)->x&~07)|(s);}
  85 # define g_setcont(p,s) ((p)->g_i.g_index=(s))
  86 # define g_setterm(p,s) ((p)->g_i.g_term = (s))
  87 # define g_setlink(p,s) ((p)->g_i.g_link = (s))
  88 # define g_setnpar(p,s) { assert(((unsigned)(s))<=017);(p)->x=((p)->x&~0170)|((s)<<3);}
  89 #ifdef NON_CORRECTING
  90 # define g_getsubparse(p)       ((p)->g_i.g_subparse)
  91 # define g_setsubparse(p,s)     ((p)->g_i.g_subparse = (s))
  92 #endif
  93 /*
  94  * Some constants to communicate with the symbol table search routine
  95  */
  96 # define UNKNOWN        00      /* Not equal to NONTERM, TERMINAL or LITERAL */
  97
  98 /*
  99  * Some constants for safety
 100  */
 101 # define SAFE           0       /* Indicates that a scan is done, and that the
 102                                  * token is correct
 103                                  */
 104 # define SAFESCANDONE   1       /* Indicates that a scan is done, and that the
 105                                  * token will not be skipped
 106                                  */
 107 # define SCANDONE       2       /* Indicates that a scan is done */
 108 # define NOSCANDONE     3       /* Indicates that no scan is done */
 109 # define NOSAFETY       4       /* Safety not yet computed */
 110
 111 /*
 112  * nonterminal structure
 113  */
 114 typedef struct {
 115         int     n_flags;        /* low order four bits are reserved
 116                                  * the parameter count
 117                                  */
 118 # define getntparams(p) ((p)->n_flags&017)
 119 # define setntparams(p,i)       {assert(((unsigned)(i))<=017);(p)->n_flags&=~017;(p)->n_flags|=(i);}
 120 # define GENSTATIC      01000   /* set if routine can be made static */
 121 # define RECURSIVE      02000   /* Set if the default rule is recursive */
 122 # define PARAMS         04000   /* tells if a nonterminal has parameters */
 123 # define EMPTY          010000  /* tells if a nonterminal produces empty */
 124 # define LOCALS         020000  /* local declarations ? */
 125 # define REACHABLE      040000  /* can this nonterminal be reached ? */
 126 # define VERBOSE        0100000 /* Set if in LL.output file */
 127         char    n_insafety;
 128         char    n_outsafety;
 129 # define getntsafe(p)   ((p)->n_insafety)
 130 # define setntsafe(p,i) {assert(((unsigned)(i))<=NOSAFETY);(p)->n_insafety=(i);}
 131 # define getntout(p)    ((p)->n_outsafety)
 132 # define setntout(p,i)  {assert(((unsigned)(i))<=NOSAFETY);(p)->n_outsafety=(i);}
 133         int     n_count;        /* pieces of code before this rule */
 134         int     n_lineno;       /* declared on line ... */
 135         p_gram  n_rule;         /* pointer to right hand side of rule */
 136         union {
 137                 p_set   n_f;    /* ptr to "first" set */
 138                 string  n_s;    /* If this nonterminal is not declared,
 139                                  * This field indicates the filename in
 140                                  * which it occurred
 141                                  */
 142         } n_x;
 143 # define n_first  n_x.n_f
 144 # define n_string n_x.n_s
 145 #ifdef NON_CORRECTING
 146         p_set   n_nc_first;     /* Pointer to non-corr first set */
 147         p_set   n_nc_follow;    /* Pointer to non-corr follow set */
 148 #endif
 149         p_set   n_follow;       /* pointer to the "follow" set  */
 150         p_set   n_contains;     /* pointer to symbols that can be produced */
 151         string  n_name;         /* name of nonterminal */
 152         int     n_next;         /* index of next nonterminal */
 153         long    n_off;          /* index of parameters in action file */
 154 } t_nont, *p_nont;
 155
 156 /*
 157  * hash table structure
 158  */
 159 typedef struct h_entry {
 160         string          h_name;         /* pointer to name */
 161         t_gram          h_type;         /* Type and index */
 162         struct h_entry  *h_next;        /* next in hash chain */
 163 } t_entry, *p_entry;
 164
 165 /*
 166  * link structure to link alternations
 167  */
 168 typedef struct link {
 169         unsigned int    l_flag;
 170 # define COND           01              /* Set if this alternative has a %if */
 171 # define DEF            02              /* This alternative is default */
 172 # define PREFERING      010             /* %prefer */
 173 # define AVOIDING       020             /* %avoid */
 174 # define NOCONF         01000           /* Set if there is a resolver without
 175                                          * conflict
 176                                          */
 177         p_gram          l_rule;         /* pointer to this rule */
 178         p_set           l_symbs;        /* set, when to take this rule */
 179 #ifdef NON_CORRECTING
 180         p_set           l_nc_symbs;
 181 #endif
 182         p_set           l_others;       /* set, when to take another rule */
 183 } t_link, *p_link;
 184
 185 /*
 186  * Structure for a repitition specification
 187  */
 188 typedef int t_reps,*p_reps;
 189
 190 # define FIXED          00      /* a fixed number */
 191 # define STAR           01      /* 0 or more times */
 192 # define PLUS           02      /* 1 or more times */
 193 # define OPT            03      /* 0 or 1 times */
 194
 195 /*
 196  * Access macros for repitition in term
 197  */
 198 # define r_getkind(q)   ((q)->t_repeats&03)
 199 # define r_getnum(q)    (((q)->t_repeats>>2)&037777)
 200 # define r_setkind(q,s) { assert(((unsigned)(s))<=03);(q)->t_repeats=((q)->t_repeats&0177774)|(s);}
 201 # define r_setnum(q,s)  { assert(((unsigned)(s))<=037777);(q)->t_repeats=((q)->t_repeats&03)|((s)<<2);}
 202
 203 /*
 204  * header structure for a term
 205  */
 206 typedef struct term {
 207         t_reps  t_repeats;
 208         int     t_flags;        /* Low order three bits for safety */
 209 # define gettout(q)     ((q)->t_flags&07)
 210 # define settout(q,i)   {assert(((unsigned)(i))<=NOSAFETY);(q)->t_flags&=~07;(q)->t_flags|=i;}
 211 # define PERSISTENT     010     /* Set if this term has %persistent */
 212 # define RESOLVER       020     /* Set if this term has %while */
 213 # define EMPTYFIRST     0100    /* Error, empty first */
 214 # define EMPTYTERM      0200    /* Error, term can produce empty */
 215 /* # define NOCONF      01000   see link structure */
 216
 217         p_gram  t_rule;         /* pointer to this term */
 218         p_set   t_follow;       /* set of followers */
 219         p_set   t_first;        /* set of firsts */
 220 #ifdef NON_CORRECTING
 221         p_set   t_nc_first;     /* set of non corr firsts */
 222         p_set   t_nc_follow;    /* set of non corr followers */
 223 #endif
 224         p_set   t_contains;     /* contains set */
 225 } t_term, *p_term;
 226
 227 /*
 228  * structure for firstmacros list
 229  */
 230 typedef struct ff_firsts {
 231         string  ff_name;        /* Name of the macro */
 232         int     ff_nont;        /* for this nonterminal */
 233         struct ff_firsts *ff_next;
 234 } t_first, *p_first;
 235
 236 /*
 237  * structure for start symbol list
 238  */
 239 typedef t_first t_start;
 240 typedef p_first p_start;
 241
 242 /*
 243  * structure for file names and info
 244  */
 245 typedef struct f_file {
 246         string  f_name;         /* File name */
 247         p_first f_firsts;       /* ptr to list of firstmacros that must be
 248                                  * generated in the target file for this
 249                                  * grammar file
 250                                  */
 251         int f_nonterminals;     /* list of nonterminals in this file  */
 252         int f_terminals;        /* list of terminals in this file  */
 253         p_set f_used;           /* set of nonterminals used in this file */
 254 } t_file, *p_file;
 255
 256 typedef struct info_alloc {
 257         /*
 258          * Structure used for dynamically growing arrays
 259          */
 260         unsigned i_size;        /* Size of the array */
 261         unsigned i_esize;       /* Size of an element */
 262         unsigned i_incr;        /* When filled, add room for i_incr elements */
 263         p_mem   i_ptr;          /* ptr to base of array */
 264         p_mem   i_max;          /* ptr to first free */
 265         p_mem   i_top;          /* ptr to top of array */
 266 } t_info, *p_info;
 267
 268 # ifdef NDEBUG
 269 # define STATIC static
 270 # else /* not NDEBUG */
 271 # define STATIC extern
 272 # endif /* not NDEBUG */