给定 Rascal 中的具体语法，如何生成语言的任意实例？

Question

鉴于一种语言的具体语法，我想定义一个函数“实例”，其签名为 str (type[&T]) 可以用具体化类型调用语法和 return 语言的有效实例。

例如，使用此语法：

lexical IntegerLiteral = [0-9]+;           

start syntax Exp            
  = IntegerLiteral          
  | bracket "(" Exp ")"     
  > left Exp "*" Exp        
  > left Exp "+" Exp        
  ;

实例(#Exp)的有效return可以是“1+(2*3)”。

具体语法定义的具体化类型确实包含有关产生式的信息，但我不确定这种方法是否比专用数据结构更好。关于如何实现它的任何指示？

Answer 1

最自然的做法是使用标准库中 ParseTree 模块中的 Tree 数据类型。它是解析器生成的格式，但您也可以自己使用。要从树中获取字符串，只需将其打印成如下字符串：

str s = "<我的树>";

一个比较完整的随机树生成器可以在这里找到：https://github.com/cwi-swat/drambiguity/blob/master/src/GenerateTrees.rsc

实现的核心是这样的：

Tree randomChar(range(int min, int max)) = char(arbInt(max + 1 - min) + min);

Tree randomTree(type[Tree] gr) 
  = randomTree(gr.symbol, 0, toMap({ <s, p> | s <- gr.definitions, /Production p:prod(_,_,_) <- gr.definitions[s]}));

Tree randomTree(\char-class(list[CharRange] ranges), int rec, map[Symbol, set[Production]] _)
  = randomChar(ranges[arbInt(size(ranges))]);

default Tree randomTree(Symbol sort, int rec, map[Symbol, set[Production]] gr) {
   p = randomAlt(sort, gr[sort], rec);  
   return appl(p, [randomTree(delabel(s), rec + 1, gr) | s <- p.symbols]);
}

default Production randomAlt(Symbol sort, set[Production] alts, int rec) {
  int w(Production p) = rec > 100 ?  p.weight * p.weight : p.weight;
  int total(set[Production] ps) = (1 | it + w(p) | Production p <- ps);
  
  r = arbInt(total(alts));
  
  count = 0;
  for (Production p <- alts) {
    count += w(p);
    if (count >= r) {
      return p;
    }
  } 
  
  throw "could not select a production for <sort> from <alts>";
}

Tree randomChar(range(int min, int max)) = char(arbInt(max + 1 - min) + min);

这是一个简单的递归函数，它从具体化的文法中随机选择产生式。

终止的诀窍在于每个规则的 weight。这是先验计算的，因此每个规则在随机选择中都有自己的权重。我们注意使导致终止的规则集至少有 50% 的机会被选中（与递归规则相反）（此处代码：https://github.com/cwi-swat/drambiguity/blob/master/src/Termination.rsc）

Grammar terminationWeights(Grammar g) { 
   deps = dependencies(g.rules);
   weights = ();
   recProds = {p | /p:prod(s,[*_,t,*_],_) := g, <delabel(t), delabel(s)> in deps};
   
   for (nt <- g.rules) {
      prods       = {p | /p:prod(_,_,_) := g.rules[nt]};
      count       = size(prods);
      recCount    = size(prods & recProds);
      notRecCount = size(prods - recProds);
      
      // at least 50% of the weight should go to non-recursive rules if they exist
      notRecWeight = notRecCount != 0 ? (count * 10) / (2 * notRecCount) : 0;
      recWeight = recCount != 0 ? (count * 10) / (2 * recCount) : 0;
      
      weights += (p : p in recProds ? recWeight : notRecWeight | p <- prods); 
   }
       
   return visit (g) { 
       case p:prod(_, _, _) => p[weight=weights[p]]
   }
}

@memo 
rel[Symbol,Symbol] dependencies(map[Symbol, Production] gr) 
  = {<delabel(from),delabel(to)> | /prod(Symbol from,[_*,Symbol to,_*],_) := gr}+;

请注意，此 randomTree 算法不会终止于非“生产性”语法（即它们只有像 syntax E = E;

这样的规则）

它还可以生成由消歧规则过滤的树。因此，您可以通过运行解析器对生成的字符串进行检查并检查解析错误。它还可以生成不明确的字符串。

顺便说一下，这段代码的灵感来自伦敦国王学院的 Naveneetha Vasudevan 的博士论文。

给定 Rascal 中的具体语法，如何生成语言的任意实例？

How to generate arbitrary instances of a language given its concrete syntax in Rascal?

code-generation

rascal