reach.c 2.6 KB

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