Как получить сильносвязанные компоненты грамматики без контекста Rascal - PullRequest
Новая
       13

Как получить сильносвязанные компоненты грамматики без контекста Rascal

0 голосов
/ 25 апреля 2018

как говорится в вопросе, я хотел бы иметь возможность преобразовать грамматику в набор сильно связанных (не терминальных) компонентов. Я хочу сделать это путем построения графа из грамматики, а затем вызвать функцию связанных компонентов. Это подводит меня к реальной проблеме: как построить этот ориентированный граф, имеющий ребра типа: 

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. Вот изображение алгоритма в псевдокоде . Здесь грамматика. V - нетерминалы, а P - правила производства (другое определение, поэтому разные имена: s)

1 Ответ

0 голосов
/ 25 апреля 2018

Сначала получите грамматику для вашего синтаксиса следующим образом: 

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

...