reach.c 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
  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. * reach.c
  14. * Determine which nonterminals are reachable, and also check that they
  15. * are all defined.
  16. */
  17. # include "types.h"
  18. # include "extern.h"
  19. # include "io.h"
  20. # include "assert.h"
  21. # ifndef NORCSID
  22. static string rcsid8 = "$Id$";
  23. # endif
  24. /* In this file the following routines are defined: */
  25. extern co_reach();
  26. STATIC reachable();
  27. STATIC reachwalk();
  28. co_reach() {
  29. /*
  30. * Check for undefined or unreachable nonterminals.
  31. */
  32. register p_nont p;
  33. register p_token t;
  34. register p_start st;
  35. register p_file x;
  36. register int s;
  37. /* Check for undefined nonterminals */
  38. for (p = nonterms; p < maxnt; p++) {
  39. if (! p->n_rule) { /* undefined */
  40. f_input = p->n_string;
  41. error(p->n_lineno,"Nonterminal %s not defined",
  42. p->n_name);
  43. }
  44. }
  45. /*
  46. * Walk the grammar rules, starting with the startsymbols
  47. * Mark the nonterminals that are encountered with the flag
  48. * REACHABLE, and walk their rules, if not done before
  49. */
  50. for (st = start; st; st = st->ff_next) {
  51. reachable(&nonterms[st->ff_nont]);
  52. }
  53. /*
  54. * Now check for unreachable nonterminals
  55. */
  56. for (x = files; x < maxfiles; x++) {
  57. f_input = x->f_name;
  58. for (s = x->f_nonterminals; s != -1; s = p->n_next) {
  59. p = &nonterms[s];
  60. if (! (p->n_flags & REACHABLE)) {
  61. warning(p->n_lineno,"nonterminal %s unreachable",
  62. p->n_name);
  63. }
  64. }
  65. for (s = x->f_terminals; s != -1; s = t->t_next) {
  66. t = &tokens[s];
  67. if (! (t->t_flags & REACHABLE)) {
  68. warning(t->t_lineno,"terminal %s not used",
  69. t->t_string);
  70. }
  71. }
  72. }
  73. }
  74. STATIC
  75. reachable(p) register p_nont p; {
  76. /*
  77. * Enter the fact that p is reachable, and look for implications
  78. */
  79. if (! (p->n_flags & REACHABLE)) {
  80. p->n_flags |= REACHABLE;
  81. /*
  82. * Now walk its grammar rule
  83. */
  84. if (p->n_rule) reachwalk(p->n_rule);
  85. }
  86. }
  87. STATIC
  88. reachwalk(p) register p_gram p; {
  89. /*
  90. * Walk through rule p, looking for nonterminals.
  91. * The nonterminals found are entered as reachable
  92. */
  93. for (;;) {
  94. switch(g_gettype(p)) {
  95. case ALTERNATION :
  96. reachwalk(g_getlink(p)->l_rule);
  97. break;
  98. case TERM :
  99. reachwalk(g_getterm(p)->t_rule);
  100. break;
  101. case NONTERM : {
  102. register p_nont n = &nonterms[g_getcont(p)];
  103. reachable(n);
  104. if (n->n_rule && g_gettype(n->n_rule) == EORULE &&
  105. ! g_getnpar(p) && (getntparams(n) == 0)) {
  106. register p_gram np = p;
  107. do {
  108. *np = *(np + 1);
  109. np++;
  110. } while (g_gettype(np) != EORULE);
  111. continue;
  112. }
  113. break;
  114. }
  115. case TERMINAL:
  116. tokens[g_getcont(p)].t_flags |= REACHABLE;
  117. break;
  118. case EORULE :
  119. return;
  120. }
  121. p++;
  122. }
  123. }