105436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Output a graph of the generated parser, for Bison. 2cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 305436638acc7c010349a69c3395f1a57c642dc62Ying Wang Copyright (C) 2001-2007, 2009-2012 Free Software Foundation, Inc. 4cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 5cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project This file is part of Bison, the GNU Compiler Compiler. 6cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 705436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is free software: you can redistribute it and/or modify 8cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project it under the terms of the GNU General Public License as published by 905436638acc7c010349a69c3395f1a57c642dc62Ying Wang the Free Software Foundation, either version 3 of the License, or 1005436638acc7c010349a69c3395f1a57c642dc62Ying Wang (at your option) any later version. 11cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 1205436638acc7c010349a69c3395f1a57c642dc62Ying Wang This program is distributed in the hope that it will be useful, 13cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project but WITHOUT ANY WARRANTY; without even the implied warranty of 14cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project GNU General Public License for more details. 16cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 17cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project You should have received a copy of the GNU General Public License 1805436638acc7c010349a69c3395f1a57c642dc62Ying Wang along with this program. If not, see <http://www.gnu.org/licenses/>. */ 19cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 20cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include <config.h> 21cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "system.h" 22cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 23cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "LR0.h" 24cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "closure.h" 25cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "complain.h" 26cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "conflicts.h" 27cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "files.h" 28cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "getargs.h" 29cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "gram.h" 3005436638acc7c010349a69c3395f1a57c642dc62Ying Wang#include "graphviz.h" 31cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "lalr.h" 32cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "print_graph.h" 33cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "reader.h" 34cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "state.h" 35cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project#include "symtab.h" 36cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 37cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 38cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*----------------------------. 39cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Construct the node labels. | 40cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`----------------------------*/ 41cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 4205436638acc7c010349a69c3395f1a57c642dc62Ying Wang/* Print the lhs of a rule in such a manner that there is no vertical 4305436638acc7c010349a69c3395f1a57c642dc62Ying Wang repetition, like in *.output files. */ 4405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 4505436638acc7c010349a69c3395f1a57c642dc62Ying Wangstatic void 4605436638acc7c010349a69c3395f1a57c642dc62Ying Wangprint_lhs (struct obstack *oout, rule *previous_rule, rule *r) 4705436638acc7c010349a69c3395f1a57c642dc62Ying Wang{ 4805436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (previous_rule && STREQ (previous_rule->lhs->tag, r->lhs->tag)) 4905436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 5005436638acc7c010349a69c3395f1a57c642dc62Ying Wang int i; 5105436638acc7c010349a69c3395f1a57c642dc62Ying Wang for (i = 0; i < strlen (r->lhs->tag); ++i) 5205436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_1grow (oout, ' '); 5305436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_1grow (oout, '|'); 5405436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 5505436638acc7c010349a69c3395f1a57c642dc62Ying Wang else 5605436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 5705436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, escape (r->lhs->tag)); 5805436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_1grow (oout, ':'); 5905436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 6005436638acc7c010349a69c3395f1a57c642dc62Ying Wang} 6105436638acc7c010349a69c3395f1a57c642dc62Ying Wang 62cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 63cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectprint_core (struct obstack *oout, state *s) 64cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 65cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *sitems = s->items; 6605436638acc7c010349a69c3395f1a57c642dc62Ying Wang rule *previous_rule = NULL; 6705436638acc7c010349a69c3395f1a57c642dc62Ying Wang size_t i; 68cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project size_t snritems = s->nitems; 69cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 70cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Output all the items of a state, not only its kernel. */ 71cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (report_flag & report_itemsets) 72cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 73cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project closure (sitems, snritems); 74cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sitems = itemset; 7505436638acc7c010349a69c3395f1a57c642dc62Ying Wang snritems = nitemset; 76cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 77cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 7805436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_printf (oout, _("State %d"), s->number); 7905436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, "\\n\\l"); 80cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < snritems; i++) 81cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 82cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *sp; 83cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project item_number *sp1; 84cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project rule_number r; 85cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 86cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project sp1 = sp = ritem + sitems[i]; 87cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 88cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project while (*sp >= 0) 8905436638acc7c010349a69c3395f1a57c642dc62Ying Wang sp++; 90cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 91cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project r = item_number_as_rule_number (*sp); 92cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 9305436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_printf (oout, "%3d ", r); 9405436638acc7c010349a69c3395f1a57c642dc62Ying Wang print_lhs (oout, previous_rule, &rules[r]); 9505436638acc7c010349a69c3395f1a57c642dc62Ying Wang previous_rule = &rules[r]; 96cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 97cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (sp = rules[r].rhs; sp < sp1; sp++) 9805436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_printf (oout, " %s", escape (symbols[*sp]->tag)); 99cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 10005436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, " ."); 101cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 102cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (/* Nothing */; *sp >= 0; ++sp) 10305436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_printf (oout, " %s", escape (symbols[*sp]->tag)); 10405436638acc7c010349a69c3395f1a57c642dc62Ying Wang 10505436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Experimental feature: display the lookahead tokens. */ 10605436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (report_flag & report_lookahead_tokens 10705436638acc7c010349a69c3395f1a57c642dc62Ying Wang && item_number_is_rule_number (*sp1)) 10805436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 10905436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Find the reduction we are handling. */ 11005436638acc7c010349a69c3395f1a57c642dc62Ying Wang reductions *reds = s->reductions; 11105436638acc7c010349a69c3395f1a57c642dc62Ying Wang int redno = state_reduction_find (s, &rules[r]); 11205436638acc7c010349a69c3395f1a57c642dc62Ying Wang 11305436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Print them if there are. */ 11405436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (reds->lookahead_tokens && redno != -1) 11505436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 11605436638acc7c010349a69c3395f1a57c642dc62Ying Wang bitset_iterator biter; 11705436638acc7c010349a69c3395f1a57c642dc62Ying Wang int k; 11805436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *sep = ""; 11905436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, " ["); 12005436638acc7c010349a69c3395f1a57c642dc62Ying Wang BITSET_FOR_EACH (biter, reds->lookahead_tokens[redno], k, 0) 12105436638acc7c010349a69c3395f1a57c642dc62Ying Wang { 12205436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, sep); 12305436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, escape (symbols[k]->tag)); 12405436638acc7c010349a69c3395f1a57c642dc62Ying Wang sep = ", "; 12505436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 12605436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_1grow (oout, ']'); 12705436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 12805436638acc7c010349a69c3395f1a57c642dc62Ying Wang } 12905436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_sgrow (oout, "\\l"); 130cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 131cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 132cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 133cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 134cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*---------------------------------------------------------------. 135cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Output in graph_obstack edges specifications in incidence with | 136cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| current node. | 137cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`---------------------------------------------------------------*/ 138cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 139cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 14005436638acc7c010349a69c3395f1a57c642dc62Ying Wangprint_actions (state const *s, FILE *fgraph) 141cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 14205436638acc7c010349a69c3395f1a57c642dc62Ying Wang transitions const *trans = s->transitions; 143cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project int i; 144cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 14505436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (!trans->num && !s->reductions) 146cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project return; 147cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 148cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < trans->num; i++) 149cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project if (!TRANSITION_IS_DISABLED (trans, i)) 150cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project { 151cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state *s1 = trans->states[i]; 152cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project symbol_number sym = s1->accessing_symbol; 153cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 15405436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Shifts are solid, gotos are dashed, and error is dotted. */ 15505436638acc7c010349a69c3395f1a57c642dc62Ying Wang char const *style = 15605436638acc7c010349a69c3395f1a57c642dc62Ying Wang (TRANSITION_IS_ERROR (trans, i) ? "dotted" 15705436638acc7c010349a69c3395f1a57c642dc62Ying Wang : TRANSITION_IS_SHIFT (trans, i) ? "solid" 15805436638acc7c010349a69c3395f1a57c642dc62Ying Wang : "dashed"); 15905436638acc7c010349a69c3395f1a57c642dc62Ying Wang 16005436638acc7c010349a69c3395f1a57c642dc62Ying Wang if (TRANSITION_IS_ERROR (trans, i) 16105436638acc7c010349a69c3395f1a57c642dc62Ying Wang && strcmp (symbols[sym]->tag, "error") != 0) 16205436638acc7c010349a69c3395f1a57c642dc62Ying Wang abort (); 16305436638acc7c010349a69c3395f1a57c642dc62Ying Wang output_edge (s->number, s1->number, 16405436638acc7c010349a69c3395f1a57c642dc62Ying Wang TRANSITION_IS_ERROR (trans, i) ? NULL : symbols[sym]->tag, 16505436638acc7c010349a69c3395f1a57c642dc62Ying Wang style, fgraph); 166cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project } 16705436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* Display reductions. */ 16805436638acc7c010349a69c3395f1a57c642dc62Ying Wang output_red (s, s->reductions, fgraph); 169cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 170cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 171cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 172cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project/*-------------------------------------------------------------. 173cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| Output in FGRAPH the current node specifications and exiting | 174cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project| edges. | 175cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project`-------------------------------------------------------------*/ 176cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 177cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectstatic void 17805436638acc7c010349a69c3395f1a57c642dc62Ying Wangprint_state (state *s, FILE *fgraph) 179cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 180cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project struct obstack node_obstack; 181cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 18205436638acc7c010349a69c3395f1a57c642dc62Ying Wang /* A node's label contains its items. */ 183cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_init (&node_obstack); 184cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project print_core (&node_obstack, s); 185cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project obstack_1grow (&node_obstack, '\0'); 18605436638acc7c010349a69c3395f1a57c642dc62Ying Wang output_node (s->number, obstack_finish (&node_obstack), fgraph); 18705436638acc7c010349a69c3395f1a57c642dc62Ying Wang obstack_free (&node_obstack, 0); 188cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 189cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Output the edges. */ 19005436638acc7c010349a69c3395f1a57c642dc62Ying Wang print_actions (s, fgraph); 191cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 192cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 193cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 194cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectvoid 195cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Projectprint_graph (void) 196cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project{ 197cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project state_number i; 19805436638acc7c010349a69c3395f1a57c642dc62Ying Wang FILE *fgraph = xfopen (spec_graph_file, "w"); 19905436638acc7c010349a69c3395f1a57c642dc62Ying Wang start_graph (fgraph); 200cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 201cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project /* Output nodes and edges. */ 202cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project new_closure (nritems); 203cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project for (i = 0; i < nstates; i++) 20405436638acc7c010349a69c3395f1a57c642dc62Ying Wang print_state (states[i], fgraph); 205cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project free_closure (); 206cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project 20705436638acc7c010349a69c3395f1a57c642dc62Ying Wang finish_graph (fgraph); 208cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project xfclose (fgraph); 209cea198a11f15a2eb071d98491ca9a8bc8cebfbc4The Android Open Source Project} 210