langviz/Grammar.cc

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