如何获得 Rascal 上下文无关文法的强连接组件

Question

如问题所述，我希望能够将语法转换为一组强连接（仅限非终端）组件。我想通过从语法构建一个图然后调用连接组件函数来做到这一点。这让我想到了真正的问题：如何构建具有以下类型边的有向图：

For each A -> xBz where A,B in Non-terminals (N) and x and y in (sigma U N)*:
    construct an edge from A to B

是否有与此内置功能类似的东西，或者我必须自己完全实现吗？如果是这样，你能帮我开始吗，例如展示如何从语法中只获取终端、非终端和生产规则？而不是仅通过机器可解析的语法数据结构？

如果有更好的方法来查找组件而不是构建图表，那当然也是一个很好的答案。我希望这已经足够清楚了，如果还不清楚，请告诉我！

编辑： 我认为该算法相对简单，我只是不知道如何在 Rascal 中执行此操作。这是pseudo-code中算法的图片。这里 grammar.V 是它的非终端和 P 它的生产规则（不同的定义，所以不同的命名：s）

Answer 1

首先像这样为你的语法获取语法：

import Grammar;
gr = grammar(#YourTopNonterminal);

然后你可以使用这个库模块（带有关于如何提取依赖项的示例代码）：

import analysis::grammars::Dependency;
deps = symbolDependencies(gr);

你会得到依赖符号之间的二元关系，如下所示：

rascal>symbolDependencies(g)
Graph[Symbol]: {
  <sort("A"),sort("B")>,
  <sort("B"),sort("C")>
}

symbolDependencies的基本代码是这样的：

Graph[Symbol] symbolDependencies(Grammar g) =
  { <from,to> | /prod(Symbol from,[_*,Symbol elem,_*],_) := g, /Symbol to := elem}

推导遍历语法的所有规则，取头部from然后找到规则中的所有符号to（可能由于正则表达式而嵌套）和为每一对创建一个元组。

之后，您将开始分析和转换这种关系以获得强连通分量。库模块 analysis::graphs::Graph 有一个计算连通分量的示例函数（不是强连通分量，因此您必须对其进行调整）。

rascal>import analysis::graphs::Graph;
ok
rascal>connectedComponents(symbolDependencies(g))
set[set[Symbol]]: {{
    sort("A"),
    sort("C"),
    sort("B")
  }}

最后，将像 sort("A") 这样的符号打印回一个漂亮的名字会派上用场，尤其是当你在非终结符（如 * 和 +）上使用正则表达式时：

rascal>t = type(sort("A"),());
type[value]: type(
  sort("A"),
  ())
rascal>"<t>"
str: "A"

我还建议使用 viz::Figure

可视化图表

如何获得 Rascal 上下文无关文法的强连接组件

How to get the strongly connected components of a Rascal context-free grammar

graph

context-free-grammar

rascal

connected-components