时间戳

首页 > 解决方案 > 给定 Rascal 中的具体语法，如何生成语言的任意实例？

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

问题描述

给定一种语言的具体语法，我想定义一个带有签名str (type[&T])的函数“实例”，它可以用语法的具体类型调用并返回该语言的有效实例。

例如，使用以下语法：

lexical IntegerLiteral = [0-9]+;           

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

instance(#Exp)的有效返回可能是“1+(2*3)”。

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

标签： code-generationrascal

解决方案

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

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 的博士论文。

推荐阅读