|
ИСТИНА |
Войти в систему Регистрация |
Интеллектуальная Система Тематического Исследования НАукометрических данных |
||
Алгоритмы преобразования бесконтекстных грамматик в L-графыстатья
- Автор: Ли Цзямянь
- Журнал: International Journal of Open Information Technologies
- Том: 13
- Номер: 11
- Год издания: 2025
- Издательство: Лаборатория Открытых Информационных Технологий факультета ВМК МГУ им. М.В. Ломоносова
- Местоположение издательства: Москва
- Первая страница: 6
- Последняя страница: 13
- Номер статьи: 2
- Аннотация: Теория формальных языков занимает важное место в компьютерной науке, где бесконтекстные (контекстно-свободные) грамматики благодаря своей мощной выразительности широко применяются в таких областях, как проектирование языков программирования, обработка естественного языка и построение компиляторов. Традиционно основным инструментом распознавания и обработки бесконтекстных языков были магазинные автоматы, однако разрозненность описаний переходов между состояниями и операций с магазином в виде отдельных команд усложняет анализ вычислений, затрудняя и практическое применение. L-графы задуманы как более совершенный и компактный инструмент представления и анализа формальных языков, благодаря наглядной графической структуре и чёткой семантике путей на графе, отражающих вычисления. В данной статье предлагается систематизированный алгоритм преобразования, способный трансформировать произвольную бесконтекстную грамматику в эквивалентный бесконтекстный L-граф. Данный метод выполняет наглядное взаимно-однозначное преобразование грамматических структур в графические. В отличие от магазинных автоматов, L-графы не содержат явных операций с магазином (стеком), используя скобочные пометки для реализации рекурсивной структуры, что делает их использование более интуитивно понятным. Кроме того, в работе показана возможность эффективного синтаксического анализа с помощью L-графов, что имеет практическую ценность. Lграфы, сохраняя выразительную мощность бесконтекстных грамматик, легче поддаются оптимизации (устранение избыточных вершин, дуг, уменьшение циклической сложности и др.), что повышает их эффективность как для теоретических исследований, так и для практических приложений.
- Добавил в систему: Ли Цзямянь