some functions for analyzing a grammar

Recursion.rsc

module lang::rascal::grammar::analyze::Recursion

import Grammar;
import ParseTree;
import analysis::grammars::Dependency;
import Relation;

set[Symbol] reachable(type[&T] g, Symbol s) {
  res = {s};
  
  solve (res) { 
    res += {e | s <- res, /prod(/s, es, _) := g.definitions, e <- es};
  }
  
  return res;
}

@memo
set[Symbol] nullable(type[&T] g) {
  res = {};
  
  solve (res) {
    res += {s | /prod(s, es, _) := g.definitions, {*es} <= res};
  } 
 
  return res;
}

@memo
set[Production] recursive(type[&T] g) {
   deps = symbolDependencies(grammar({}, g.definitions))+;
   return {p | /p:prod(s,_,_) := g.definitions, <s,s> in deps};    
}

@memo
rel[Production, int] rightRecursive(type[&T] g) {
   deps = symbolDependencies(grammar({}, g.definitions))+;
   nulls = nullable(g);
   return { <p, size(l)> | /p:prod(_,[*l,s,*r],_) := g.definitions, <s,s> in deps, {*r} <= nulls};   
}

@memo
rel[Production, int] leftRecursive(type[&T] g) {
   deps = symbolDependencies(grammar({}, g.definitions))+;
   nulls = nullable(g);
   return {<p,size(l)> | /p:prod(_,[*l,s,*r],_) := g.definitions, <s,s> in deps, {*l} <= nulls};