TonitaN
commented
1 month ago А вы тестировали, точно? Или сразу поверили тому коду, который написал ChatGPT?
regex = "a|ba|bc*a" приводит к падению программы.
Open TonitaN opened 2 months ago
TonitaN
commented
1 month ago А вы тестировали, точно? Или сразу поверили тому коду, который написал ChatGPT?
regex = "a|ba|bc*a" приводит к падению программы.
viachistiakov
commented
1 month ago Задача реализовать разбор регулярных выражений оказалось не таким простым заданием и заняло у меня около двух недель. Разбор работы кода и затраченного времени.
from z3 import Solver, Bool, Or, And, sat
from graphviz import Digraph
import os
import subprocessСначала подключаем нужные библиотеки. z3 используется для логических операций и проверки ассоциативности, graphviz помогает нам визуализировать дерево, а os и subprocess нужны для работы с файловой системой и открытия созданных графиков.
Класс TreeNode:
class TreeNode:
def __init__(self, label, left=None, right=None):
self.label = label
self.left = left
self.right = right
def __repr__(self):
if self.left is None and self.right is None:
return f"Leaf({self.label})"
return f"Node({self.label}, {self.left}, {self.right})"Этот класс представляет узел дерева. Каждый узел имеет метку и два дочерних узла (левый и правый). Если узел не имеет дочерних узлов, он считается листом.
Функции для разбора выражений:
def build_parse_tree(expression):
expression = expression.replace('?', '|') # Опцию заменяем на альтернативу
return parse_alternatives(expression)Эта функция заменяет символ ? на |, так как в нашем случае мы обрабатываем альтернативы, и вызывает функцию parse_alternatives.
def parse_alternatives(expression):
segments = []
segment = ""
balance = 0
for char in expression:
if char == '(':
balance += 1
elif char == ')':
balance -= 1
if char == '|' and balance == 0:
segments.append(segment)
segment = ""
else:
segment += char
if segment:
segments.append(segment)
if len(segments) > 1:
node = TreeNode('|')
node.left = parse_alternatives(segments[0])
node.right = parse_alternatives("|".join(segments[1:]))
return node
return parse_concatenations(expression)Эта функция разбивает выражение на части по символу |, учитывая баланс скобок. Если частей больше одной, создается узел для альтернативы.
def parse_concatenations(expression):
segments = []
segment = ""
balance = 0
for i, char in enumerate(expression):
if char == '(':
balance += 1
elif char == ')':
balance -= 1
if balance == 0 and (i == len(expression) - 1 or expression[i + 1] not in ('|', '*', '(', ')')):
segment += char
segments.append(segment)
segment = ""
else:
segment += char
if segment:
segments.append(segment)
if len(segments) > 1:
node = TreeNode('.')
node.left = parse_concatenations(segments[0])
node.right = parse_concatenations("".join(segments[1:]))
return node
return parse_iterations(expression)Здесь выражение разбивается по символам конкатенации (.). Опять же, учитывается баланс скобок, чтобы не ломать структуру выражения.
def parse_iterations(expression):
if expression.endswith('*'):
node = TreeNode('*')
node.left = parse_primary(expression[:-1])
return node
return parse_primary(expression)Эта функция обрабатывает итерации, то есть символ * в конце выражения.
def parse_primary(expression):
if expression.startswith('(') and expression.endswith(')'):
return parse_alternatives(expression[1:-1])
return TreeNode(expression)Здесь мы обрабатываем базовые элементы выражения. Если выражение окружено скобками, оно обрабатывается как альтернативы.
Вывод дерева в консоль:
def display_tree(node, depth=0):
"""Функция для вывода дерева в консоль."""
indent = " " * depth
print(indent + node.label)
if node.left:
display_tree(node.left, depth + 1)
if node.right:
display_tree(node.right, depth + 1)Эта функция выводит дерево разбора с отступами, чтобы было видно его структуру.
Создание и сохранение графа:
def add_nodes_edges(node, graph, node_id=0, parent_id=None):
"""Функция для добавления узлов и рёбер в граф Graphviz."""
if node is not None:
# Узел
current_id = node_id
node_id += 1
# Выбор цвета узла в зависимости от метки
if node.label == '|':
node_color = 'lightblue' # Цвет для альтернативы
elif node.label == '.':
node_color = 'lightgreen' # Цвет для конкатенации
elif node.label == '*':
node_color = 'lightyellow' # Цвет для итерации
else:
node_color = 'lightgrey' # Цвет для букв или пустых меток
# Узлы
graph.node(f'{current_id}', label=node.label, shape='ellipse', style='filled', color=node_color,
fontcolor='black', fontsize='14', width='1.2', height='0.8')
# Связи
if parent_id is not None:
graph.edge(f'{parent_id}', f'{current_id}', color='black', arrowsize='0.7', penwidth='2')
if node.left:
node_id = add_nodes_edges(node.left, graph, node_id, current_id)
if node.right:
node_id = add_nodes_edges(node.right, graph, node_id, current_id)
return node_idФункция добавляет узлы и связи в граф, учитывая тип узла и соответствующий цвет.
def create_graph(node):
"""Функция для создания графа с помощью Graphviz."""
graph = Digraph(comment='Parse Tree')
graph.attr(size='10,10', rankdir='TB', fontsize='16', fontname='Arial', dpi='300') # Настройки графа
add_nodes_edges(node, graph)
return graph
Эта функция создает граф с настройками и добавляет в него узлы и рёбра.def save_and_open_graph(graph, filename='parse_tree'):
"""Функция для сохранения и открытия графа."""
graph.render(filename, format='png', cleanup=True)
image_path = f'{filename}.png'
if os.path.exists(image_path):
subprocess.run(['start', image_path], shell=True) # Открывает изображение в WindowsФункция сохраняет граф в файл и открывает его.
Проверка ассоциативности:
def verify_associativity(node):
"""Функция для проверки ассоциативности регулярных выражений."""
solver = Solver()
def add_constraints(node, level=0):
if node.label == '|':
if node.left:
add_constraints(node.left, level + 1)
if node.right:
add_constraints(node.right, level + 1)
left_expr = Bool(f'left_{level}')
right_expr = Bool(f'right_{level}')
solver.add(Or(left_expr, right_expr))
elif node.label == '.':
if node.left:
add_constraints(node.left, level + 1)
if node.right:
add_constraints(node.right, level + 1)
left_expr = Bool(f'left_{level}')
right_expr = Bool(f'right_{level}')
solver.add(And(left_expr, right_expr))
elif node.label == '*':
if node.left:
add_constraints(node.left, level + 1)
expr = Bool(f'expr_{level}')
solver.add(expr)
else:
expr = Bool(f'expr_{level}')
solver.add(expr)
add_constraints(node)
if solver.check() == sat:
print(f"Ассоциативность соблюдается для узла: {node.label}")
else:
print(f"Ассоциативность не соблюдается для узла: {node.label}")Эта функция проверяет ассоциативность регулярного выражения с помощью решателя z3.
Основной блок кода:
if __name__ == "__main__":
regex_input = "a|ba|bc*a"
parse_tree = build_parse_tree(regex_input)
print("Дерево разбора регулярного выражения:")
display_tree(parse_tree) # Вывод в консоль
graph = create_graph(parse_tree) # Создание графа
save_and_open_graph(graph) # Сохранение и открытие графа
verify_associativity(parse_tree)Здесь задается регулярное выражение, строится дерево разбора, выводится его структура в консоль, создается и сохраняется граф, а также проверяется ассоциативность.
Почему это заняло две недели:
Пример визуализации для выражения: (a)|(ba)|(b(c*)a)
TonitaN
commented
3 weeks ago Не всегда разбирает до конца: a** порождает некорректные узлы, равно как и (()a())*
TonitaN
commented
3 weeks ago Параллельно можно переходить к следующей задаче - переписывание дерева регулярного выражения в инициализацию регулярного выражения в языке SMT2 (через методы построения класса re и str.to_re для константных строк). При этом, если в регулярном выражении есть конкатенация нескольких литер, то представление этой конкатенации должно быть именно через путь: строка целиком => str.to_re, а не через использование последовательных методов re.++
viachistiakov
commented
2 weeks ago Исправил разбор, теперь правильно порождает
viachistiakov
commented
2 weeks ago Задача переписывание дерева в инициализацию регулярного выражения представляет собой инструмент для разбора регулярных выражений и визуализации их в виде деревьев разбора с последующим преобразованием в формат SMT2 для логических проверок.
class SMT2Converter:
def __init__(self, root):
self.root = rootКонструктор класса принимает корень дерева разбора (root) и сохраняет его в атрибуте экземпляра. Корень дерева разбора представляет собой дерево, которое вы хотите преобразовать в формат SMT2.
def convert(self):
return self._convert_node(self.root)Метод convert запускает процесс конвертации дерева разбора в формат SMT2. Он вызывает внутренний метод _convert_node, передавая ему корень дерева. Результатом является строка, представляющая регулярное выражение в формате SMT2.
def _convert_node(self, node):
if node.label == '|':
return f"(re.union {self._convert_node(node.left)} {self._convert_node(node.right)})"
elif node.label == '.':
# Обрабатываем конкатенацию
left = self._convert_node(node.left)
right = self._convert_node(node.right)
return f"(re.++ {left} {right})"
elif node.label == '*':
return f"(re.* {self._convert_node(node.left)})"
else:
# Экранирование литералов
escaped_label = node.label.replace('"', '\\"')
return f"(str.to_re \"{escaped_label}\")"Этот метод рекурсивно обходит узлы дерева разбора и преобразует их в соответствующие SMT2 конструкции.
if node.label == '|':
return f"(re.union {self._convert_node(node.left)}Если узел представляет альтернативу (или), то вызываются рекурсивно _convert_node для левого и правого подузлов, которые преобразуются в SMT2 представление. Затем создается SMT2 выражение для объединения (или) двух регулярных выражений.
elif node.label == '.':
# Обрабатываем конкатенацию
left = self._convert_node(node.left)
right = self._convert_node(node.right)
return f"(re.++ {left} {right})"Если узел представляет конкатенацию (или последовательность), то также рекурсивно преобразуются левые и правые поддеревья. Затем создается SMT2 выражение для конкатенации двух регулярных выражений.
elif node.label == '*':
return f"(re.* {self._convert_node(node.left)})"Если узел представляет итерацию (звездочку), то рекурсивно преобразуется поддерево для выражения, которое повторяется. Затем создается SMT2 выражение для итерации.
else:
# Экранирование литералов
escaped_label = node.label.replace('"', '\\"')
return f"(str.to_re \"{escaped_label}\")"Если узел представляет собой литерал (например, символ или пустое слово), то оно преобразуется в SMT2 выражение для строки. Литералы экранируются для правильного форматирования в SMT2.
class TreeNode:
def __init__(self, label, left=None, right=None):
self.label = label
self.left = left
self.right = right
def __repr__(self):
if self.left is None and self.right is None:
return f"Leaf({self.label})"
return f"Node({self.label}, {self.left}, {self.right})"Объяснение: • TreeNode представляет узел дерева разбора регулярного выражения. • label — это метка узла (например, символ или оператор). • left и right — это дочерние узлы для бинарных операторов. • Метод repr возвращает строковое представление узла, что полезно для отладки и визуализации. Функции для проверки и разбиения регулярных выражений:
def is_valid_regex(expression):
"""Проверяет корректность регулярного выражения."""
try:
re.compile(expression)
return True
except re.error:
return FalseОбъяснение: Проверяет, является ли строка корректным регулярным выражением, используя re.compile. Если регулярное выражение некорректно, оно вызывает исключение re.error.
def validate_empty_groups(expression):
"""Проверяет наличие пустых групп в регулярном выражении."""
pattern = re.compile(r'\(\s*\)')
if pattern.search(expression):
raise ValueError("Ошибка: Пустая группа '()' в регулярном выражении.")Объяснение: Проверяет, содержит ли регулярное выражение пустые группы вида (). Если такие группы найдены, выбрасывается исключение.
def tokenize(regex):
tokens = []
i = 0
while i < len(regex):
if regex[i] in {'(', ')', '*', '|'}:
tokens.append(regex[i])
i += 1
else:
if regex[i] == 'ε':
tokens.append('ε')
i += 1
else:
tokens.append(regex[i])
i += 1
return tokensОбъяснение: Преобразует регулярное выражение в список токенов. Специальные символы и операторы добавляются как есть, а остальные символы добавляются как они есть.
def to_rpn(tokens):
precedence = {'*': 3, '.': 2, '|': 1}
output = []
stack = []
# Добавление явных операторов конкатенации
i = 0
result = []
while i < len(tokens):
token = tokens[i]
result.append(token)
if token not in {'(', '|'} and i + 1 < len(tokens):
next_token = tokens[i + 1]
if next_token not in {')', '*', '|'}:
result.append('.')
i += 1
tokens = result
for token in tokens:
if token.isalnum() or token == 'ε':
output.append(token)
elif token == '(':
stack.append(token)
elif token == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # Удаляем '('
else: # Операторы
while stack and stack[-1] != '(' and precedence.get(stack[-1], 0) >= precedence.get(token, 0):
output.append(stack.pop())
stack.append(token)
while stack:
output.append(stack.pop())
return outputОбъяснение: Преобразует список токенов в обратную польскую запись (RPN). Операторы с различными уровнями приоритета обрабатываются с помощью стека.
def build_parse_tree_from_rpn(rpn):
stack = []
for token in rpn:
if token == '*':
if not stack:
raise ValueError("Недостаточно операндов для '*'.")
node = TreeNode('*', left=stack.pop())
stack.append(node)
elif token == '.':
if len(stack) < 2:
raise ValueError("Недостаточно операндов для '.'.")
right = stack.pop()
left = stack.pop()
node = TreeNode('.', left=left, right=right)
stack.append(node)
elif token == '|':
if len(stack) < 2:
raise ValueError("Недостаточно операндов для '|'.")
right = stack.pop()
left = stack.pop()
node = TreeNode('|', left=left, right=right)
stack.append(node)
else: # Это буква или пустое слово (ε)
stack.append(TreeNode(token))
if len(stack) != 1:
raise ValueError("Некорректное выражение, стек не пуст после обработки RPN.")
return stack[0] if stack else NoneОбъяснение: Построение дерева разбора из списка RPN. Стек используется для создания узлов дерева на основе операндов и операторов.
def display_tree(node, depth=0):
"""Функция для вывода дерева в консоль."""
indent = " " * depth
print(indent + node.label)
if node.left:
display_tree(node.left, depth + 1)
if node.right:
display_tree(node.right, depth + 1)Объяснение: Рекурсивно выводит дерево разбора на консоль. Узлы и их глубина выводятся с соответствующими отступами.
def add_nodes_edges(node, graph, node_id=0, parent_id=None):
"""Функция для добавления узлов и рёбер в граф Graphviz."""
if node is not None:
current_id = node_id
node_id += 1
# Выбор цвета узла в зависимости от метки
if node.label == '|':
node_color = 'lightblue' # Цвет для альтернативы
elif node.label == '.':
node_color = 'lightgreen' # Цвет для конкатенации
elif node.label == '*':
node_color = 'lightyellow' # Цвет для итерации
else:
node_color = 'lightgrey' # Цвет для букв или пустых меток
# Узлы
graph.node(f'{current_id}', label=node.label, shape='ellipse', style='filled', color=node_color,
fontcolor='black', fontsize='14', width='1.2', height='0.8')
# Связи
if parent_id is not None:
graph.edge(f'{parent_id}', f'{current_id}', color='black', arrowsize='0.7', penwidth='2')
if node.left:
node_id = add_nodes_edges(node.left, graph, node_id, current_id)
if node.right:
node_id = add_nodes_edges(node.right, graph, node_id, current_id)
return node_idОбъяснение: Создает граф с узлами и связями, используя библиотеку Graphviz. Узлы окрашиваются в зависимости от их типа (например, альтернативные узлы).
def create_graph(node):
"""Функция для создания графа с помощью Graphviz."""
graph = Digraph(comment='Parse Tree')
graph.attr(size='10,10', rankdir='TB', fontsize='16', fontname='Arial', dpi='300') # Настройки графа
add_nodes_edges(node, graph)
return graphОбъяснение: Создает объект графа, добавляет в него узлы и связи, и возвращает получившийся граф.
def save_and_open_graph(graph, filename='parse_tree'):
"""Функция для сохранения и открытия графа."""
graph.render(filename, format='png', cleanup=True)
image_path = f'{filename}.png'
if os.path.exists(image_path):
subprocess.run(['start', image_path], shell=True) # Открывает изображение в WindowsОбъяснение: Сохраняет граф в файл PNG и открывает его с помощью стандартного просмотрщика изображений в Windows. Проверка ассоциативности
def verify_associativity(node):
"""Функция для проверки ассоциативности регулярных выражений."""
solver = Solver()
def add_constraints(node, level=0):
if node.label == '|':
if node.left:
add_constraints(node.left, level + 1)
if node.right:
add_constraints(node.right, level + 1)
left_expr = Bool(f'left_{level}')
right_expr = Bool(f'right_{level}')
solver.add(Or(left_expr, right_expr))
elif node.label == '.':
if node.left:
add_constraints(node.left, level + 1)
if node.right:
add_constraints(node.right, level + 1)
left_expr = Bool(f'left_{level}')
right_expr = Bool(f'right_{level}')
solver.add(And(left_expr, right_expr))
elif node.label == '*':
if node.left:
add_constraints(node.left, level + 1)
expr = Bool(f'expr_{level}')
solver.add(expr)
else:
expr = Bool(f'expr_{level}')
solver.add(expr)
add_constraints(node)
if solver.check() == sat:
print(f"Associativity is satisfied for node: {node.label}")
else:
print(f"Associativity is not satisfied for node: {node.label}")Объяснение: Использует Z3 Solver для проверки ассоциативности регулярного выражения. Задаются логические ограничения для различных операторов регулярных выражений.
class SMT2Converter:
def __init__(self, root):
self.root = root
def convert(self):
return self._convert_node(self.root)
def _convert_node(self, node):
if node.label == '|':
return f"(re.union {self._convert_node(node.left)} {self._convert_node(node.right)})"
elif node.label == '.':
# Обрабатываем конкатенацию
left = self._convert_node(node.left)
right = self._convert_node(node.right)
return f"(re.++ {left} {right})"
elif node.label == '*':
return f"(re.* {self._convert_node(node.left)})"
else:
# Экранирование литералов
escaped_label = node.label.replace('"', '\\"')
return f"(str.to_re \"{escaped_label}\")"Объяснение: • Конвертирует дерево разбора в формат SMT2 для использования с инструментами формальной верификации. Каждый узел дерева преобразуется в соответствующую SMT2 конструкцию.
def main():
while True:
regex = input("Введите регулярное выражение для разбора (или 'quit' для выхода): ").strip()
if regex.lower() == 'quit':
break
if not is_valid_regex(regex):
print("Некорректное регулярное выражение. Попробуйте еще раз.")
continue
try:
validate_empty_groups(regex)
tokens = tokenize(regex)
rpn = to_rpn(tokens)
parse_tree = build_parse_tree_from_rpn(rpn)
print("Дерево разбора регулярного выражения:")
display_tree(parse_tree)
verify_associativity(parse_tree)
converter = SMT2Converter(parse_tree)
smt2_repr = converter.convert()
print("SMT2 представление для выражения:")
print(smt2_repr)
graph = create_graph(parse_tree)
save_and_open_graph(graph)
except ValueError as e:
print(f"Ошибка: {e}")
if __name__ == "__main__":
main()Основная функция запускает цикл, в котором пользователь вводит регулярные выражения. Если выражение корректно, оно разбирается, проверяется, и преобразуется в SMT2. Также создается и открывается граф с деревом разбора.
TonitaN
commented
2 weeks ago Не видно работы со смежными конкатенациями символов, которые должны преобразовываться в строку, как я писала выше.
viachistiakov
commented
2 weeks ago Исправил, теперь корректно объединяет смежные символы в одну строку.
viachistiakov
commented
2 weeks ago Антонина Николаевна, в старом коде генерировал SMT2-представления для отдельных строк через str.to_re, а затем объединял их с помощью re.++. Это делало ненужные промежуточные шаги.
В новом коде добавил логику для непосредственного объединения строк на этапе их генерации. В частности, добавил проверку:
if left.startswith('(str.to_re "') and right.startswith('(str.to_re "'):
left_str = left[len('(str.to_re "'): -2]
right_str = right[len('(str.to_re "'): -2]
return f'(str.to_re "{left_str + right_str}")Этот блок кода заменяет комбинацию двух отдельных вызовов str.to_re на один, если оба поддерева содержат строки. То есть, теперь строки сливаются сразу, и лишь потом вызывается str.to_re
viachistiakov
commented
2 weeks ago Прошу назначьте мне следующее задание пожалуйста
viachistiakov
commented
6 days ago Загрузил предварительный вариант, re и z3 немного разные библиотеки, а точнее z3 не имеет ограниченный функцинал, тут и возникают сложности
Задача до 11.07: на вход программе подаётся регулярное выражение, содержащее буквы латинского алфавита, круглые скобки, альтернативу, итерацию и опцию (вопросительный знак). Ассоциативность учитывается, т.е. выражения вида
abc(a|b|)корректны. Тут же демонстрируется, что у альтернативы могут быть и пустые аргументы. Приоритеты тоже учитываются: итерация имеет максимальный приоритет, на втором месте конкатенация, слабее всех - альтернатива. Т.е.a|ba|bc*aчитаем как(a)|(ba)|(b(c*)a).Необходимо построить (бинарное) дерево разбора регулярного выражения, сохраняющее его семантику. Метки узлов - конкатенация, альтернатива (опцию рассахариваем до альтернативы), итерация (у итерации только один потомок), пустая метка или буква (листовые метки).