types.h 7.4 KB

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