Skip to content

Latest commit

 

History

History
525 lines (391 loc) · 39.6 KB

tasks.md

File metadata and controls

525 lines (391 loc) · 39.6 KB
Raw

Задачи по курсу «Формальные языки»

Задача 1. Инициализация рабочего окружения

Полный балл: 5

  • Сделать fork данного репозитория.
  • Добавить ссылку на ваш fork в таблицу.
  • Добавить в совладельцы форка одного из ассистентов (чтобы узнать, кого именно, нужно посмотреть в таблицу)
  • Реализовать модуль, предоставляющий перечисленные ниже возможности. Для работы с графами использовать cfpq-data. Данный модуль в дальнейшем будет расширяться. Функции, которые необходимо реализовать:
    • По имени графа вернуть количество вершин, рёбер и перечислить различные метки, встречающиеся на рёбрах. Для получения графа по имени использовать эту функцию.
    • По количеству вершин в циклах и именам меток строить граф из двух циклов и сохранять его в указанный файл в формате DOT (использовать pydot).
  • Добавить необходимые тесты.

Задача 2. Построение детерминированного конечного автомата по регулярному выражению и недетерминированного конечного автомата по графу

Полный балл: 5

  • Используя возможности pyformlang реализовать функцию построения минимального ДКА по заданному регулярному выражению. Формат регулярного выражения.
    • Требуемая функция:
    def regex_to_dfa(regex: str) -> DeterministicFiniteAutomaton:
    pass
  • Используя возможности pyformlang реализовать функцию построения недетерминированного конечного автомата по графу, в том числе по любому из графов, которые можно получить, пользуясь функциональностью, реализованной в Задаче 1 (загруженный из набора данных по имени граф, сгенерированный синтетический граф). Предусмотреть возможность указывать стартовые и финальные вершины. Если они не указаны, то считать все вершины стартовыми и финальными.
    • Требуемая функция:
    def graph_to_nfa(
  graph: MultiDiGraph, start_states: Set[int], final_states: Set[int]
) -> NondeterministicFiniteAutomaton:
    pass
  • Добавить собственные тесты при необходимости.

Задача 3. Регулярные запросы для всех пар вершин

Полный балл: 5

  • Реализовать тип (AdjacencyMatrixFA), представляющий конечный автомат в виде разреженной матрицы смежности из sciPy (или сразу её булевой декомпозиции) и информации о стартовых и финальных вершинах. У типа должны быть конструктор от DeterministicFiniteAutomaton и NondeterministicFiniteAutomaton (первый является подклассом второго, так что можно не различать их явно) из Задачи 2.
  • Реализовать функцию-интерпретатор для типа AdjacencyMatrixFA, выясняющую, принимает ли автомат заданную строку и является ли язык, задающийся автоматом, пустым. Для реализации последней функции рекомендуется использовать транзитивное замыкание матрицы смежности.
    • Требуемые функции: 
      def accepts(self, word: Iterable[Symbol]) -> bool:
 pass
def is_empty(self) -> bool:
 pass
  • Используя разреженные матрицы из sciPy реализовать функцию пересечения двух конечных автоматов через тензорное произведение.
    • Требуемая функция: 
      def intersect_automata(automaton1: AdjacencyMatrixFA,
        automaton2: AdjacencyMatrixFA) -> AdjacencyMatrixFA:
   pass
  • На основе предыдущей функции реализовать функцию выполнения регулярных запросов к графам: по графу с заданными стартовыми и финальными вершинами и регулярному выражению вернуть те пары вершин из заданных стартовых и финальных, которые связанны путём, формирующем слово из языка, задаваемого регулярным выражением.

    • Требуемая функция:

      def tensor_based_rpq(regex: str, graph: MultiDiGraph, start_nodes: set[int],
      final_nodes: set[int]) -> set[tuple[int, int]]:
   pass

    • Для конструирования регулярного запроса и преобразований графа использовать результаты Задачи 2.

  • Добавить собственные тесты при необходимости.

Задача 4. Регулярные запросы для нескольких стартовых вершин

Полный балл: 8

  • Используя разреженные матрицы из sciPy реализовать функцию достижимости с регулярными ограничениями с несколькими стартовыми вершинами (алгоритм на основе multiple source BFS через линейную алгебру).
    • Для конструирования регулярного запроса и графа использовать Задачи 2.
    • Требуемая функция:
    def ms_bfs_based_rpq(regex: str, graph: MultiDiGraph, start_nodes: set[int],
         final_nodes: set[int]) -> set[tuple[int, int]]:
  pass
  • Добавить собственные тесты при необходимости.

Задача 5. Экспериментальное исследование алгоритмов для регулярных запросов

Полный балл: 15

Задача посвящена анализу производительности алгоритма решения задачи достижимости между всеми парами вершин и с заданным множеством стартовых вершин с регулярными ограничениями через.

Исследуются следующие задачи достижимости, решаемые в предыдущих работах.

  • Достижимость между всеми парами вершин.
  • Достижимость для каждой из заданного множества стартовых вершин.

Вопросы, на которые необходимо ответить в ходе исследования.

  • Какое представление разреженных матриц и векторов лучше подходит для каждой из решаемых задач?
  • Начиная с какого размера стартового множества выгоднее решать задачу для всех пар и выбирать нужные?

Решение данной задачи оформляется как Python notebook. Для того, чтобы обеспечить возможность проверки, необходимо сделать notebook самодостаточным: в него должны быть включены все действия, необходимые для воспроизведения эксперимента. Также в notebook размещается отчет и анализ результатов ваших экспериментов в текстовом виде. Отчет сопровождается диаграммами, таблицами, картинками, если это необходимо для объяснения результатов.

Решением является не просто код, но отчёт об экспериментальном исследовании, который должен являться связанным текстом и содержать (как минимум) следующие разделы:

  • Постановка задачи
  • Описание исследуемых решений
  • Описание набора данных для экспериментов
    • Графы
    • Запросы
  • Описание эксперимента
    • Оборудование
    • Что и как замерялось, как эти измерения должны помочь ответить на поставленные вопросы
  • Результаты экспериментов
    • Графики, таблицы
  • Анализ результатов экспериментов
    • Ответы на поставленные вопросы, аргументация ответов

При постановке экспериментов и базовом анализе результатов не лишним будет воспользоваться советами отсюда. При написании отчёта можно попробовать вдохновиться рекомендациями отсюда.

  • Создать Python notebook, подключить необходимые зависимости.
  • Подключить решения из предыдущих работ.
  • Сформировать набор данных.
    • Выбрать некоторые графы из набора. Не забудьте обосновать, почему выбрали именно эти графы.
    • Используя функцию из первой домашней работы узнать метки рёбер графов и на основе этой информации сформулировать не менее четырёх различных запросов к каждому графу. Лучше использовать наиболее часто встречающиеся метки. Требования к запросам:
      • Запросы ко всем графам должны следовать некоторому общему шаблону. Например, если есть графы g1 и g2 с различными наборами меток, то ожидается, что запросы к ним будут выглядеть, например, так:
        • g1:
          • (l1 | l2)* l3
          • (l3 | l4)+ l1*
          • l1 l2 l3 (l4|l1)*
        • g2:
          • (m1 | m3)* m2
          • (m1 | m3)+ m2*
          • m1 m2 m3 (m3|m1)*
      • В запросах должны использоваться все общепринятые конструкции регулярных выражений (замыкание, конкатенация, альтернатива). То есть хотя бы в одном запросе к каждому графу должна быть каждая из этих конструкций.
    • Для генерации множеств стартовых вершин воспользоваться этой функцией. Не забывайте, что от того, как именно устроено стартовое множество, сильно зависит время вычисления запроса.
  • Сформулировать этапы эксперимента. Что нужно сделать, чтобы ответить на поставленные вопросы? Почему?
  • Провести необходимые эксперименты, замеры
  • Оформить результаты экспериментов
  • Провести анализ результатов
    • Ответить на поставленные вопросы
    • Аргументировать ответы (пользуясь полученными результатами экспериментов)
  • Не забыть опубликовать notebook в репозитории

Задача 6. Преобразование грамматики в ОНФХ, алгоритм Хеллингса

Полный балл: 10

  • Используя возможности pyformlang для работы с контекстно-свободными грамматиками реализовать функцию преобразования контекстно-свободной грамматики в ослабленную нормальную форму Хомского (ОНФХ). 
    def cfg_to_weak_normal_form(cfg: pyformlang.cfg.CFG) -> pyformlang.cfg.CFG:
    pass
  • Реализовать функцию, основанную на алгоритме Хеллингса, решающую задачу достижимости между всеми парами вершин для заданного графа и заданной КС грамматики (не обязательно в ОНФХ).
    • Для работы с графом использовать функции из предыдущих задач.
    def hellings_based_cfpq(
  cfg: pyformlang.cfg.CFG,
  graph: nx.DiGraph,
  start_nodes: set[int] = None,
  final_nodes: set[int] = None,
) -> set[tuple[int, int]]:
   pass
  • Добавить собственные тесты при необходимости.

Задача 7. Матричный алгоритм решения задачи достижимости с КС ограничениями

Полный балл: 10

  • Реализовать функцию, основанную на матричном алгоритме, решающую задачу достижимости между всеми парами вершин для заданного графа и заданной КС грамматики.
    • Для преобразования грамматики в ОНФХ использовать результаты предыдущих работ.
    • Для реализации матричных операций использовать sciPy. 
      def matrix_based_cfpq(
    cfg: pyformlang.cfg.CFG,
    graph: nx.DiGraph,
    start_nodes: Set[int] = None,
    final_nodes: Set[int] = None,
) -> set[tuple[int, int]]:
  pass
  • Добавить собственные тесты при необходимости.

Задача 8. Тензорный алгоритм решения задачи достижимости с КС ограничениями

Полный балл: 10

  • Реализовать функцию, основанную на тензорном алгоритме, решающую задачу достижимости между всеми парами вершин для заданного графа и заданной КС грамматики.
    • Для преобразования грамматики в RSM использовать результаты предыдущих работ. Явно опишите функции преобразования CFG -> RSM и EBNF -> RSM
    • Для реализации матричных операций использовать sciPy.
    • Необходимые функции:
    def tensor_based_cfpq(
  rsm: pyformlang.rsa.RecursiveAutomaton,
  graph: nx.DiGraph,
  final_nodes: set[int] = None,
  start_nodes: set[int] = None,
) -> set[tuple[int, int]]:
  pass


def cfg_to_rsm(cfg: pyformlang.cfg.CFG) -> pyformlang.rsa.RecursiveAutomaton:
  pass


def ebnf_to_rsm(ebnf: str) -> pyformlang.rsa.RecursiveAutomaton:
  pass
  • Добавить собственные тесты при необходимости.

Задача 9. Алгоритм решения задачи достижимости с КС ограничениями, основанный на GLL

Полный балл: 15

  • Реализовать функцию, основанную на алгоритме Generalized LL (работающего с RSM), решающую задачу достижимости между всеми парами вершин для заданного графа и заданной КС грамматики.
    • Для работы с графами и RSM использовать функции из предыдущих задач.
    • Требуемая функция:
    def gll_based_cfpq(
      rsm: pyformlang.rsa.RecursiveAutomaton,
      graph: nx.DiGraph,
      start_nodes: set[int] = None,
      final_nodes: set[int] = None,
  ) -> set[tuple[int, int]]:
  pass
  • Добавить собственные тесты при необходимости.

Задача 10. Экспериментальное исследование алгоритмов решения задачи достижимости с КС ограничениями

Полный балл: 20

Задача посвящена анализу производительности различных алгоритмов решения задачи достижимости между всеми парами вершин с контекстно-свободными ограничениями: алгоритма Хеллингса, матричного алгоритма, тензорного алгоритма, алгоритма на основе GLL. В ходе анализа необходимо ответить на следующие вопросы.

  • Какой из трёх указанных алгоритмов обладает лучшей производительностью?
  • Имеет ли смысл для решения задачи достижимости с регулярными ограничениями использовать алгоритмы для КС ограничений (ведь регулярные --- частный случай КС) или всё же лучше использовать специализированные алгоритмы для регулярных ограничений?
  • Как влияет грамматика на производительность тензорного алгоритма и алгоритма на основе GLL? Если зафиксировать язык, то как свойства грамматики (размер, (не)однозначность) влияют на производительность.

Решение данной задачи оформляется как Python notebook. Для того, чтобы обеспечить возможность проверки, необходимо сделать notebook самодостаточным: в него должны быть включены все действия, необходимые для воспроизведения эксперимента. Также в notebook размещается отчет и анализ результатов ваших экспериментов в текстовом виде. Отчет сопровождается диаграммами, таблицами, картинками, если это необходимо для объяснения результатов.

Решением является не просто код, но отчёт об экспериментальном исследовании, который должен являться связанным текстом и содержать (как минимум) следующие разделы:

  • Постановка задачи

  • Описание исследуемых решений

  • Описание набора данных для экспериментов

    • Графы
    • Запросы

  • Описание эксперимента

    • Оборудование
    • Что и как замерялось, как эти измерения должны помочь ответить на поставленные вопросы

  • Результаты экспериментов

    • Графики, таблицы

  • Анализ результатов экспериментов

    • Ответы на поставленные вопросы, аргументация ответов

  • Создать Python notebook, подключить необходимые зависимости.

  • Подключить необходимые решения из предыдущих работ.

  • Сформировать набор данных.

    • Выбрать некоторые графы из набора. Не забудьте обосновать, почему выбрали именно эти графы. Обратите внимание, что в наборе есть графы и грамматики для различных прикладных задач (анализ RDF, анализ указателей в С, анализ Java-программ). Рекомендуется выбирать графы, относящиеся к различным областям.
    • В качестве запросов предлагается использовать грамматики из раздела "Canonical grammars" в описании соответствующего графа (пример). При необходимости (например, при ответе на третий вопрос), можно "оптимизировать" грамматику, вручную создав оптимальную RSM. Или же наоборот, преобразовать её в ОНФХ, или сделать её (не)однозначной.

  • Сформулировать этапы эксперимента. Что нужно сделать, чтобы ответить на поставленные вопросы? Почему?

  • Провести необходимые эксперименты, замеры

  • Оформить результаты экспериментов

  • Провести анализ результатов

    • Ответить на поставленные вопросы
    • Аргументировать ответы (пользуясь полученными результатами экспериментов)

  • Не забыть опубликовать notebook в репозитории

Задача 11. Язык запросов к графам

Полный балл: 15

Конкретный синтаксис

prog = stmt*

stmt = bind | add | remove | declare

declare = 'let' VAR 'is' 'graph'

bind = 'let' VAR '=' expr

remove = 'remove' ('vertex' | 'edge' | 'vertices') expr 'from' VAR

add = 'add' ('vertex' | 'edge') expr 'to' VAR

expr = NUM | CHAR | VAR | edge_expr | set_expr | regexp | select

set_expr = '[' expr (',' expr)* ']'

edge_expr = '(' expr ',' expr ',' expr ')'

regexp = CHAR | VAR | '(' regexp ')' | (regexp '|' regexp) | (regexp '^' range) | (regexp '.' regexp) | (regexp '&' regexp)

range = '[' NUM '..' NUM? ']'

select = v_filter? v_filter? 'return' VAR (',' VAR)? 'where' VAR 'reachable' 'from' VAR 'in' VAR 'by' expr

v_filter = 'for' VAR 'in' expr

VAR = [a..z] [a..z 0..9]*
NUM = 0 | ([1..9] [0..9]*)
CHAR = '"' [a..z] '"'

Пример запроса.

let g is graph

add edge (1, "a", 2) to g
add edge (2, "a", 3) to g
add edge (3, "a", 1) to g
add edge (1, "c", 5) to g
add edge (5, "b", 4) to g
add edge (4, "b", 5) to g

let q = "a"^[1..3] . q . "b"^[2..3] | "c"

let r1 = for v in [2] return u where u reachable from v in g by q

add edge (5, "d", 6) to g

let r2 = for v in [2,3] return u,v where u reachable from v in g by (q . "d")

Правила вывода типов

Константы типизируются очевидным образом.

Тип переменной определяется типом выражения, с которым она связана.

[b(v)] => t
_________________
[Var (v)](b) => t

Пересечение для двух КС не определено.

[e1](b) => FA ;  [e2](b) => FA
______________________________________
[Intersect (e1, e2)](b) => FA


[e1](b) => FA ;  [e2](b) => RSM
_______________________________________
[Intersect (e1, e2)](b) => RSM


[e1](b) => RSM ;  [e2](b) => FA
_______________________________________
[Intersect (e1, e2)](b) => RSM

Остальные операции над автоматами типизируются согласно формальных свойств классов языков.

[e1](b) => FA ;  [e2](b) => FA
_____________________________________
[Concat (e1, e2)](b) => FA


[e1](b) => FA ;  [e2](b) => RSM
______________________________________
[Concat (e1, e2)](b) => RSM


[e1](b) => RSM ;  [e2](b) => FA
______________________________________
[Concat (e1, e2)](b) => RSM


[e1](b) => RSM ;  [e2](b) => RSM
______________________________________
[Concat (e1, e2)](b) => RSM


[e1](b) => FA ;  [e2](b) => FA
______________________________________
[Union (e1, e2)](b) => FA


[e1](b) => FA ;  [e2](b) => RSM
_______________________________________
[Union (e1, e2)](b) => RSM


[e1](b) => RSM ;  [e2](b) => FA
_______________________________________
[Union (e1, e2)](b) => RSM


[e1](b) => RSM ;  [e2](b) => RSM
_______________________________________
[Union (e1, e2)](b) => RSM


[e](b) => FA
______________________
[Repeat (e)](b) => FA


[e](b) => RSM
______________________
[Repeat (e)](b) => RSM


[e](b) => char
________________________
[Symbol (e)](b) => FA

Запрос возвращает множество (вершин или пар вершин)

[e](b) => Set<int>
_______________________________
[VFilter (v, e)](b) => Set<int>


[q](b) => RSM, [ret](b) => int
_____________________________________________________
[Select (vf1, vf2, ret, v1, v2, g, q)](b) => Set<int>


[q](b) => FA, [ret](b) => int
_____________________________________________________
[Select (vf1, vf2, ret, v1, v2, g, q)](b) => Set<int>


[q](b) => FA, [ret](b) => int * int
____________________________________________________________
[Select (vf1, vf2, ret, v1, v2, g, q)](b) => Set<int * int>


[q](b) => RSM, [ret](b) => int * int
____________________________________________________________
[Select (vf1, vf2, ret, v1, v2, g, q)](b) => Set<int * int>

Динамическая семантика языка запросов

Связывание переопределяет имя.

[e](b1) => x,b2
_____________________________________
[Bind (v, e)](b1) => (), (b1(v) <= x)

Результатом исполнения программы является словарь, где ключ --- имя переменной в связывании, у которого в правой части select, а значение --- результат вычисления соответствующего запроса.

Задача

  • С использованием ANTLR реализовать синтаксический анализатор предложенного выше языка. А именно, реализовать функцию, которая принимает строку и возвращает дерево разбора.
  • Реализовать функцию, которая по дереву разбора возвращает количество узлов в нём.
  • Реализовать функцию, которая по дереву разбора строит ранее разобранную строку.
  • Расширить CI шагом генерации парсера по спецификации. Обратите внимание, что генерируемые по спецификации файлы не выкладываются в репозиторий.
    • Grammarinator, используемый нами для генерации тестов, подтягивает вместе с собой ANTLeRinator, который можно использовать для получения исполняемого файла ANTLR
    • Либо можно использовать более стандартные antlr4-tools

Требуемые функции:

# Второе поле показывает корректна ли строка (True, если корректна)
def program_to_tree(program: str) -> tuple[ParserRuleContext, bool]:
    pass

def nodes_count(tree: ParserRuleContext) -> int:
    pass

def tree_to_program(tree: ParserRuleContext) -> str:
    pass

Задача 12. Интерпретатор языка запросов к графам

Полный балл: 22

В данной задаче необходимо разработать интерпретатор языка запросов, разработанного в предыдущей работе. Для исполнения запросов использовать алгоритмы, реализованные в предыдущих работах. Кроме реализации необходимо предоставить минимальную документацию, поясняющую принятые в процессе реализации решения (например, в readme).

Обратите внимание, что кроме непосредственно интерпретатора необходимо реализовать вывод типов. Тестирование данной функциональности должно быть возможно в изоляции. Фактически, должна быть реализована отдельная функция, которая по дереву разбора выводит типы и кидает исключение, если программа не можете быть типизирована корректно.

  • Реализовать механизм вывода типов, гарантирующий корректность построения запросов (в частности, что не строится пересечение двух контекстно-свободных языков, или что множества вершин задаются значениями допустимых типов).
    • Работа системы типов должна соответствовать правилам, указанным предыдущей задаче.
    • Постарайтесь сделать сообщения об ошибках максимально дружественными к пользователю.
  • Из множества реализованных в предыдущих работах алгоритмов выполнения запросов к графам выбрать те, которые будут использоваться в интерпретаторе. Обосновать свой выбор (зафиксировать в документации).
  • Используя парсер из предыдущей работы, разработанную систему вывода типов, выбранные алгоритмы, реализовать интерпретатор языка, описанного в предыдущей задаче.
    • Требуется реализовать функцию, которая по дереву разбора, предоставленному ANTLR, вернёт словарь, содержащий для всех связываний, где в правой части select, имя (левую часть связывания) в качестве ключа, а в качестве значения --- результат выполнения соответствующего запроса.
    • Проследите за адекватностью сообщений об ошибках. Вам же проще отлаживаться будет.
    • Постарайтесь максимально использовать возможности ANTLR по работе с деревом разбора.
  • Добавить необходимые тесты.

Требуемые функции:

def typing_program(program: str) -> bool:
  pass

def exec_program(program: str) -> dict[str, set[tuple]]:
  pass