1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Calculate which nonterminals can expand into the null string for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 3cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Copyright (C) 1984, 1989, 2000, 2001, 2002, 2003, 2004, 2005, 2006 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Free Software Foundation, Inc. 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This file is part of Bison, the GNU Compiler Compiler. 7cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Bison is free software; you can redistribute it and/or modify 9cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 10cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation; either version 2, or (at your option) 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Bison is distributed in the hope that it will be useful, 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project along with Bison; see the file COPYING. If not, write to 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Boston, MA 02110-1301, USA. */ 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set up NULLABLE, a vector saying which nonterminals can expand into 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project do so. */ 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <config.h> 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "getargs.h" 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "nullable.h" 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reduce.h" 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "symtab.h" 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Linked list of rules. */ 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct rule_list 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct rule_list *next; 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *value; 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} rule_list; 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbool *nullable = NULL; 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_print (FILE *out) 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fputs ("NULLABLE\n", out); 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = ntokens; i < nsyms; i++) 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, "\t%s: %s\n", symbols[i]->tag, 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[i - ntokens] ? "yes" : "no"); 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fputs ("\n\n", out); 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_compute (void) 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_number ruleno; 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *s1; 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *s2; 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list *p; 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *squeue = xnmalloc (nvars, sizeof *squeue); 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t *rcount = xcalloc (nrules, sizeof *rcount); 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* RITEM contains all the rules, including useless productions. 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hence we must allocate room for useless nonterminals too. */ 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list **rsets = xcalloc (nvars, sizeof *rsets); 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This is said to be more elements than we actually use. 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Supposedly NRITEMS - NRULES is enough. But why take the risk? */ 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts); 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable = xcalloc (nvars, sizeof *nullable); 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s1 = s2 = squeue; 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p = relts; 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (ruleno = 0; ruleno < nrules; ++ruleno) 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules[ruleno].useful) 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *rules_ruleno = &rules[ruleno]; 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules_ruleno->rhs[0] >= 0) 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has a non empty RHS. */ 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *rp = NULL; 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool any_tokens = false; 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ISTOKEN (*rp)) 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project any_tokens = true; 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has only nonterminals: schedule it for the second 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pass. */ 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!any_tokens) 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rcount[ruleno]++; 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p->next = rsets[*rp - ntokens]; 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p->value = rules_ruleno; 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rsets[*rp - ntokens] = p; 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p++; 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 105cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 106cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has an empty RHS. */ 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project assert (item_number_as_rule_number (rules_ruleno->rhs[0]) 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project == ruleno); 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules_ruleno->useful 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && ! nullable[rules_ruleno->lhs->number - ntokens]) 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[rules_ruleno->lhs->number - ntokens] = true; 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *s2++ = rules_ruleno->lhs->number; 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (s1 < s2) 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (p = rsets[*s1++ - ntokens]; p; p = p->next) 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *r = p->value; 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (--rcount[r->number] == 0) 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (r->useful && ! nullable[r->lhs->number - ntokens]) 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[r->lhs->number - ntokens] = true; 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *s2++ = r->lhs->number; 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (squeue); 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (rcount); 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (rsets); 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (relts); 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_sets) 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable_print (stderr); 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_free (void) 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (nullable); 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 145