1cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Calculate which nonterminals can expand into the null string for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 1984, 1989, 2000-2006, 2009-2012 Free Software 405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 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 805436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program 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 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1105436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 12cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1305436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program 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 1905436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Set up NULLABLE, a vector saying which nonterminals can expand into 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project the null string. NULLABLE[I - NTOKENS] is nonzero if symbol I can 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project do so. */ 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <config.h> 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "getargs.h" 30cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "nullable.h" 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reduce.h" 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "symtab.h" 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/* Linked list of rules. */ 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projecttypedef struct rule_list 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct rule_list *next; 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *value; 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} rule_list; 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 42cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectbool *nullable = NULL; 43cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 44cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 45cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_print (FILE *out) 46cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 47cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 48cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fputs ("NULLABLE\n", out); 49cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = ntokens; i < nsyms; i++) 50cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fprintf (out, "\t%s: %s\n", symbols[i]->tag, 51cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[i - ntokens] ? "yes" : "no"); 52cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project fputs ("\n\n", out); 53cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 54cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 55cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 56cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_compute (void) 57cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 58cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_number ruleno; 59cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *s1; 60cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *s2; 61cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list *p; 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number *squeue = xnmalloc (nvars, sizeof *squeue); 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t *rcount = xcalloc (nrules, sizeof *rcount); 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* RITEM contains all the rules, including useless productions. 66cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Hence we must allocate room for useless nonterminals too. */ 67cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list **rsets = xcalloc (nvars, sizeof *rsets); 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This is said to be more elements than we actually use. 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project Supposedly NRITEMS - NRULES is enough. But why take the risk? */ 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_list *relts = xnmalloc (nritems + nvars + 1, sizeof *relts); 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable = xcalloc (nvars, sizeof *nullable); 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project s1 = s2 = squeue; 75cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p = relts; 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (ruleno = 0; ruleno < nrules; ++ruleno) 78cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules[ruleno].useful) 79cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *rules_ruleno = &rules[ruleno]; 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules_ruleno->rhs[0] >= 0) 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has a non empty RHS. */ 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *rp = NULL; 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project bool any_tokens = false; 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (ISTOKEN (*rp)) 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project any_tokens = true; 89cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has only nonterminals: schedule it for the second 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project pass. */ 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!any_tokens) 93cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (rp = rules_ruleno->rhs; *rp >= 0; ++rp) 94cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 95cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rcount[ruleno]++; 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p->next = rsets[*rp - ntokens]; 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p->value = rules_ruleno; 98cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rsets[*rp - ntokens] = p; 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project p++; 100cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project else 103cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 104cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* This rule has an empty RHS. */ 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang aver (item_number_as_rule_number (rules_ruleno->rhs[0]) 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang == ruleno); 107cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (rules_ruleno->useful 108cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project && ! nullable[rules_ruleno->lhs->number - ntokens]) 109cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 110cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[rules_ruleno->lhs->number - ntokens] = true; 111cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *s2++ = rules_ruleno->lhs->number; 112cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 113cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 114cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 115cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 116cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (s1 < s2) 117cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (p = rsets[*s1++ - ntokens]; p; p = p->next) 118cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 119cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule *r = p->value; 120cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (--rcount[r->number] == 0) 121cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (r->useful && ! nullable[r->lhs->number - ntokens]) 122cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 123cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable[r->lhs->number - ntokens] = true; 124cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project *s2++ = r->lhs->number; 125cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 126cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 127cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 128cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (squeue); 129cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (rcount); 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (rsets); 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (relts); 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (trace_flag & trace_sets) 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project nullable_print (stderr); 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectnullable_free (void) 140cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free (nullable); 142cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 143