langviz/Grammar.cc

   1 ///////////////////////////////////////////////////////////////////////////////
   2 // Copyright (c) 2000-2015 Ericsson Telecom AB
   3 // All rights reserved. This program and the accompanying materials
   4 // are made available under the terms of the Eclipse Public License v1.0
   5 // which accompanies this distribution, and is available at
   6 // http://www.eclipse.org/legal/epl-v10.html
   7 ///////////////////////////////////////////////////////////////////////////////
   8 #include "Grammar.hh"
   9 #include "Rule.hh"
  10 #include "Iterator.hh"
  11 #include "Symbol.hh"
  12
  13 // =================================
  14 // ===== Grammar
  15 // =================================
  16
  17 Grammar::Grammar(const Grammar& p)
  18   : Node(p)
  19 {
  20   FATAL_ERROR("Grammar::Grammar()");
  21 }
  22
  23 Grammar::Grammar()
  24   : max_dist(-1)
  25 {
  26 }
  27
  28 Grammar::~Grammar()
  29 {
  30   for(size_t i=0; i<gs.size(); i++)
  31     delete gs.get_nth_elem(i);
  32   gs.clear();
  33   as.clear();
  34   ss.destruct_ss();
  35 }
  36
  37 Grammar* Grammar::clone() const
  38 {
  39   FATAL_ERROR("Grammar::clone()");
  40 }
  41
  42 Symbol* Grammar::get_symbol(const string& id)
  43 {
  44   if(ss.has_s_withId(id)) return ss.get_s_byId(id);
  45   Symbol *s=new Symbol(id);
  46   if(id[0]=='\'' || id[0]=='"' || id=="error") s->set_is_terminal();
  47   ss.add_s(s);
  48   return s;
  49 }
  50
  51 void Grammar::add_alias(const string& s1, const string& s2)
  52 {
  53   if(!as.has_key(s1))
  54     as.add(s1, get_symbol(s2));
  55   get_symbol(s1)->set_is_terminal();
  56 }
  57
  58 void Grammar::add_grouping(Grouping *p_grouping)
  59 {
  60   const string& id=p_grouping->get_id();
  61   if(gs.has_key(id)) {
  62     gs[id]->steal_rules(p_grouping);
  63     delete p_grouping;
  64   }
  65   else gs.add(id, p_grouping);
  66 }
  67
  68 Symbol* Grammar::get_alias(Symbol *p_symbol)
  69 {
  70   const string& id=p_symbol->get_id();
  71   return as.has_key(id)?as[id]:p_symbol;
  72 }
  73
  74 void Grammar::replace_aliases()
  75 {
  76   startsymbol=get_alias(startsymbol);
  77   for(size_t i=0; i<gs.size(); i++)
  78     gs.get_nth_elem(i)->replace_aliases(this);
  79   for(size_t i=0; i<as.size(); i++)
  80     ss.destruct_symbol(as.get_nth_key(i));
  81 }
  82
  83 Grouping* Grammar::get_grouping_bySymbol(Symbol *p_symbol)
  84 {
  85   const string& id=p_symbol->get_id();
  86   if(!gs.has_key(id)) FATAL_ERROR("Grammar::get_grouping()");
  87   return gs[id];
  88 }
  89
  90 void Grammar::compute_refs()
  91 {
  92   ItRefBuild it;
  93   it.visitGrammar(this);
  94 }
  95
  96 void Grammar::compute_can_be_empty()
  97 {
  98   bool changed;
  99   do {
 100     changed=false;
 101     size_t ng=get_nof_groupings();
 102     for(size_t ig=0; ig<ng; ig++) {
 103       Grouping *grp=get_grouping_byIndex(ig);
 104       Symbol *lhs=grp->get_lhs();
 105       if(lhs->get_can_be_empty()) continue;
 106       size_t nr=grp->get_nof_rules();
 107       for(size_t ir=0; ir<nr; ir++) {
 108         if(lhs->get_can_be_empty()) continue;
 109         Rule *rule=grp->get_rule_byIndex(ir);
 110         size_t ns=rule->get_nof_ss();
 111         bool b=true;
 112         for(size_t is=0; is<ns; is++)
 113           if(!rule->get_s_byIndex(is)->get_can_be_empty()) {b=false; break;}
 114         if(b) {lhs->set_can_be_empty(); changed=true;}
 115       } // for ir
 116     } // for ig
 117   } while(changed);
 118 }
 119
 120 void Grammar::compute_dists()
 121 {
 122   SymbolSet *prev_set, *next_set;
 123   prev_set=new SymbolSet();
 124   next_set=new SymbolSet();
 125   int dist=0;
 126   if(startsymbol) {
 127     prev_set->add_s(startsymbol);
 128     startsymbol->set_dist(dist);
 129   }
 130   size_t n=prev_set->get_nof_ss();
 131   while(n) {
 132     dist++;
 133     for(size_t i=0; i<n; i++)
 134       next_set->add_ss(prev_set->get_s_byIndex(i)->get_refs());
 135     n=next_set->get_nof_ss();
 136     SymbolSet *tmp_set=new SymbolSet();
 137     for(size_t i=0; i<n; i++) {
 138       Symbol *s=next_set->get_s_byIndex(i);
 139       if(s->get_dist()==-1) s->set_dist(dist);
 140       else tmp_set->add_s(s);
 141     }
 142     next_set->remove_ss(*tmp_set);
 143     delete prev_set;
 144     prev_set=next_set;
 145     next_set=tmp_set;
 146     next_set->remove_all();
 147     n=prev_set->get_nof_ss();
 148   } // while n
 149   delete prev_set;
 150   delete next_set;
 151   max_dist=dist;
 152 }
 153
 154 void Grammar::compute_all()
 155 {
 156   compute_refs();
 157   compute_can_be_empty();
 158   compute_dists();
 159 }