zabika.ru 1

Промежуточный отчёт по курсовой работе.

Тема : "Разработка GLR-анализатора для среды .NET".

Научный руководитель: Лукичёв Александр Сергеевич.

Исполнитель: Григорьев Семён.



  1. Введение

Задачи автоматизированного реинжиниринга программ выдвигают особые

требования к генераторам синтаксических анализаторов .

Для устаревшего языка сложно (а зачастую и невозможно) задать однозначную

контекстно-свободную грамматику. Необходимо существенно преобразовать его

спецификацию, которая приводится в документации, чтобы получить такую

грамматику, но при этом она перестает быть сопровождаемой [1]. Поэтому

устаревший язык обычно задается с помощью неоднозначной контекстно-свободной

грамматики.

При поддержке нескольких диалектов языка необходима возможность лёгкой трансформации грамматики. Однако,зачастую, изменение одного правила приводит к появлению десятков конфликтов в грамматике[1], которые необходимо разрешать вручную.

Это требует большого количества времени.

Как вариант решения этих задач в статье [1] предлагается использовать GLR грамматики и соответствующие инструменты построения анализаторов. Действительно, GLR-алгоритм разрешает неоднозначности в грамматике на уровне концепции. По этому задание спецификации трансляции становится проще, требует меньше времени. Получившийся код компактнее и сопровождаемее.



  1. Цель

Целью работы является разработка GLR-анализатора для среды .NET.



  1. Ожидаемые результаты.

    Результатом работы будет являться представление спецификации трансляции на основе атрибутной GLR-грамматики в среде .NET и алгоритм построения GLR-анализаторов на основе подобного представления.

  2. Реализация.

    Платформой для создания инструмента выбран .NET . Основным языком реализации является F#[2]. Так же предлагается использовать C#.


    1. Внутреннее представление.

      За основу внутреннего представления грамматики взято представление инструмента YARD. Такой выбор сделан по тому, что... Планируется расширить представление конструкциями для расширенных регулярных выражений и перестановок.

  3. Литература.

[1]Mark G.J. van den Brand, Alex Sellink, Chris Verhoef Current Parsing Techniques in Software Renovation Considered Harmful.// IWPC ’98: Proceedings of the 6th International Workshop on Program Comprehension. — IEEE Computer Society, Washington,1998.

[2] http://www.research.microsoft.com/fsharp (дистрибутивы и документация по языку F#)

[2] Ахо А., Сети Р., Ульман Дж. Компиляторы: принципы, технологии, инструменты.

М:. Издательский дом «Вильямс»2003. 768 с.

[3] Чемоданов И.С. Генератор синтаксических анализаторов для решения задач автоматизированного реинжиниринга программ.

[4] Dick Grune, Ceriel Jacobs PARSING TECHNIQUES A Practical Guide.

research.microsoft.com/fsharp/

Планы на редактирование.

Уже сейчас предложено делать LALR(1) таблицу на основе цитаты: «We have explained Tomita’s parser using an LR(0) table; in his book Tomita uses an SLR(1) table. In fact the method will work with any bottom-up table or even with no table at all. The weaker the table, the more non-determinism will have to be resolved by breadth-first search, and for the weakest of all tables, the absent table, the method degenerates into full breadth-first search. Since the latter is involved in principle in all variants of the method, the time requirements are in theory exponential; in practice they are very modest, generally linear or slightly more than linear and almost always less than those of Earley’s parser or of the CYK parser, except for very ambiguous grammars. »

Посмотреть на recursive ascent


Просто функциональное выполнение LR-анализаторов дано, вместе с простым доказательством правильности. Это представлено как обобщение рекурсивного анализатора спуска. Для грамматик non-LR сложность времени нашего анализатора является кубической, если функции, которые составляют анализатор, осуществлены как функции записки, то есть функции, которые запоминают результаты предыдущих просьб. Функции записки также облегчают простой способ построить очень компактное представление леса разбора. Для LR (0) грамматики, наш алгоритм близко связан с рекурсивными анализаторами подъема, недавно обнаруженными Kruseman Aretz [1] и Roberts [2]. Расширенный CF грамматики (грамматики с регулярными выражениями в стороне правой руки) могут быть разобраны с простой модификацией LR-анализатора для нормального CF грамматики.

ВВЕДЕНИЕ

В этой газете мы даем просто функциональное выполнение LR-анализаторов, применимых к общему CF грамматики. Это будет получено как обобщение известной рекурсивной техники парсинга спуска. Для LR (0) грамматики, наш результат подразумевает детерминированный анализатор, который близко связан с рекурсивными анализаторами подъема, обнаруженными Kruseman Aretz [1] и Roberts [2]. В общем недетерминированном случае у анализатора есть кубическая сложность времени, если функции разбора осуществлены как функции записки [3], которые являются функциями, которые запоминают и снова используют результаты предыдущих просьб. Memofunctions легко осуществлены на большинстве программных языков. Понятие функций записки также используется, чтобы определить алгоритм, который строит кубическое представление для леса разбора, то есть коллекцию деревьев разбора. Это требовалось Tomita, что недетерминированные LR-анализаторы полезны для обработки естественного языка. В [4] он представил обсуждение о том, как сделать недетерминированный LR-парсинг, с устройством, названным стеком graphstructured. С нашим анализатором мы показываем, что никакие явные манипуляции стека не необходимы; они могут быть выражены неявно с использованием соответствующих программных языковых понятий. Большинство учебников по парсингу не включает надлежащие доказательства правильности для LR-анализаторов, главным образом потому что такие доказательства имеют тенденцию быть скорее вовлеченными. Теорию LRparsing нужно все еще считать слаборазвитой, по этой причине. Наше представление, однако, содержит удивительно простое доказательство правильности. Фактически, это доказательство - крупный вклад этой бумаги в парсинг теории. Один из его уроков - то, что CF класс грамматики часто - естественный, чтобы проверить анализаторы для, даже если эти анализаторы посвящены некоторому специальному классу грамматик. Если grammarlis ограничил в некотором роде, анализатор для общего CF, у грамматик могут быть свойства, которые позволяют умным уловкам выполнения увеличить эффективность. Поскольку мы показываем ниже, отношение между LR-анализаторами и LR-грамматиками - этот вид. Особенно в обработке естественного языка, стандарт CF грамматики часто слишком ограничиваются в их сильной порождающей власти. Расширенным CF формализм грамматики, позволяя правила иметь регулярные выражения в правильной ручной стороне, является полезное расширение, по этой причине. Не трудно обобщить наш анализатор, чтобы справиться с расширенными грамматиками, хотя заявление LR-парсинга к расширенному CF грамматики известно, чтобы быть проблематично [5]. Мы сначала представляем рекурсивное устройство распознавания спуска в пути, который позволяет желательное обобщение. Тогда мы получаем рекурсивное устройство распознавания подъема и его доказательство. Если грамматика - LR (0) несколько лидерства уловок выполнения на рекурсивное устройство распознавания подъема касательно [1]. Впоследствии, сложности времени и пространства устройства распознавания проанализированы, и алгоритм для того, чтобы построить кубическое представление для лесов разбора дан. Бумага заканчивается обсуждением расширенных CF грамматики.

Рассмотрите CF грамматики G , с терминалами VT и нетерминалы V/v. Позвольте V = VN U VT. Известная нисходящая техника парсинга - рекурсивный анализатор спуска. Рекурсивные анализаторы спуска состоят из многих процедур, обычно один для каждого нетерминального. Здесь мы представляем вариант, который состоит из функций, один для каждого пункта (усеянное правило). Мы используем неортодоксальный оператор [.] охвата, чтобы нанести на карту каждый пункт к его функции: (мы используем греческие буквы для произвольных элементов V *) [-