types.h 8.1 KB

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