Недавно отправил тезисы на конференцию, думаю стоит опубликовать их и здесь.
УДК 004.9, 004.02
ФУНКЦИОНАЛЬНЫЙ ПОДХОД К РАЗРАБОТКЕ ПАРСЕРА НА ЯЗЫКЕ C#
Автор: Д.А. Пелевин, Тюменский Государственный Нефтегазовый Университет
Научный руководитель: к.ф-м.н А.О. Ярославов, группа ИТ-Компаний Арсенал+
По иерархии Хомского, грамматики делятся на 4 типа, каждый последующий является более ограниченным подмножеством предыдущего (но в тоже время легче поддающегося анализу, таблица 1).
Таблица 1 – Иерархия грамматик по Хомскому.
| |
Грамматика
|
Язык
|
Необходимый и достаточный автомат
|
|
Тип-0
|
Неограниченная
|
Рекурсивно перечислимый
Рекурсивный
|
Машина Тьюринга
Решатель
|
|
Тип-1
|
Контекстная
Индексированная
|
Контекстные
Индексированные
|
Линейно-ограниченные
Встроенная магазинная
|
|
Тип-2
|
Контекстно-свободная
Детерминированная КС
Наблюдаемая магазинная
|
Контекстно-свободные
Детерминированные КС
Наблюдаемо магазинные
|
Не/детерминировано магазинный
Наблюдаемо магазинный
|
|
Тип-3
|
Регулярная
|
Регулярные
|
Конечный автомат
|
Исторически сложилось, что фактически все существующие грамматики были разработаны с учетом отсутствия больших вычислительных мощностей и сводятся к автоматам. Создание таких автоматов сложно и требует высокой квалификации, тщательного тестирования. Модернизация таких алгоритмов требует повторного полного тестирования всего автомата. Кроме того с ростом и развитием технологий требуется портирование старых алгоритмов на новые платформы.
Проблема написания конечных автоматов была решена посредством создания специализированных программ генераторов синтаксических анализаторов (Yacc, Bizon, ANTLR и др.). В некоторых случаях требуется также наличие лексического анализатора, поэтому используются совместно с генераторами лексических анализаторов. Данные генераторы на входе получают грамматику, а на выходе выдают программный код-парсер, который потом компилируется.
Преимуществами описанных генераторов является использование языков описания грамматик (Lada, PEG, ppeg, Frisby и др.), использование быстрых автоматов. Недостатками же данных генераторов являются:
— сложность внесения изменений в генерируемый код;
— сложность управления оптимальной кодогенерацией;
— неприменимость при создании динамических парсеров.
Целью исследования является поиск удобных подходов к решению практических задач синтаксического анализа.
При написании программ на языках типа C++, Java и др., чаще всего используется императивный подход, который, главным образом, заключается в том, что оперирует переменными, структурами, массивами, состоянием памяти компьютера, посредством алгоритма, т.е. посредством последовательности конкретных команд.
Многие алгоритмы могут быть более эффективно реализованы при помощи чистых функций. В первую очередь это относится к сортировке и поиску. Некоторые задачи, как например задача перевода одного формализованного языка на другой или задача разбора синтаксических конструкций, могут быть решены только при использовании методов функционального программирования.
Поэтому на принципах функционального программирования могут решаться такие задачи, как символьные вычисления, вывод на знаниях, обработка формализованных и естественных языков, выявление знаний в базах данных, создание общающихся между собой программных систем (агентов), и другие. Все эти задачи традиционны для искусственного интеллекта.
Особенностями функционального подхода является:
— отсутствие явно выраженной последовательности действий;
— отсутствие глобальных переменных, которые вы можете свободно менять в любой функции;
— отсутствие аргументов, передаваемых по ссылке;
— функция это не адрес на некий блок кода, а полноценный объект;
— функция может оперировать только своими аргументами и только в режиме чтения;
— функции не разрешается вызывать внутри себя какие-либо функции, которые могут изменить внешние объекты (массивы, классы, структуры, глобальные переменные, объекты ядра ОС);
— нет возможности напрямую использовать указатели и адресную арифметику.
И так, функциональный подход преимущественно оперирует функциями, как объектами, и их аргументами, посредством описания структуры отношений и выражений одних функций через другие. Примерно так же, как это выглядит в математике.
В итоге, очевидно, что имеется ряд серьезных ограничений, однако в этом есть огромные преимущества. Главное преимущество в том, что функции при таких ограничениях превращаются в самодостаточные детерминированные сущности, которые не зависят от состояния внешней среды. Другими словами, нет такой вероятности и/или внешних и внутренних обстоятельств, чтобы для некоторой функции F, когда-либо изменилось истинность выражения F(A) == B, где A – некоторое конкретное значение аргумента; B – конкретное значение результата. Такое качество называют отсутствием побочных эффектов.
А это значит, можно свободно оперировать функциями:
— вызывать в любой последовательности (распараллеливание);
— кэшировать результаты вычислений (меморизация);
— как угодно комбинировать функции, т.е. динамически порождать из одних функций другие.
В функциональном программировании один из основных подходов к синтаксическому анализу базируется на, так называемых, комбинаторах.
Комбинатор — это функция, принимающая в качестве аргументов другие функции и возвращающая функцию, которая является комбинацией аргументов по какому-то определённому правилу.
Комбинаторы — должны быть без побочных эффектов. Всё, что им разрешается, так это комбинировать аргументы и возвращать результат.
Если представить любой парсер как функцию, которая принимает на вход текст, а на выходе возвращает результаты анализа в некоторой унифицированной форме, то можно будет, с помощью комбинаторов, делать из простых парсеров более сложные (комплексные).
Следует так же понимать, что при программировании парсера порядком вызова комбинаторов мы определяем ещё и грамматику парсера.
Комбинаторный подход позволяет пользоваться ранее написанными парсерами любой природы. Внутри лямбда функций можно использовать, в том числе, и императивные функции – это отступление от ФП, но при определенных условиях допустимое. К примеру, можно использовать регулярные выражения. Таким образом, можно использовать наиболее подходящий парсер в каждом конкретном случае, повторно использовать ранее разработанный код.
На данный момент, очевидно, что данный подход к разработке парсеров позволяет реализовать парсер осуществляющий анализ языка большой сложности. Такой парсер по скорости разбора сопоставим с регулярные выражения, но более прост в написании, может иметь больше возможностей, кроме того параллельно может выстраивать дерево разбора, помечая тип каждого элемента дерева.
Большие перспективы у такой методики анализа текста в динамическом программирование (т.к. возможны интерпретация и компиляция на лету). Как следствие, в генетических адаптивных алгоритмах; в адаптивных алгоритмах обучения нейронных сетей.
Возможность описания сложных нерегулярных, меняющихся во времени грамматик позволяет использовать данный подход для анализа естественных языков.
Если Вы нашли ошибку, пожалуйcта выделите ее и нажмите Shift + E или нажмите здесь чтобы информировать меня. Спасибо.
