Пример разбора выражения в дерево
При парсинге исходный текст преобразуется в структуру данных, обычно - в дерево, которое отражает синтаксическую структуру входной последовательности и хорошо подходит для дальнейшей обработки.
Как правило, результатом синтаксического анализа является синтаксическая структура предложения, представленная либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторой комбинации первого и второго способов представления.
Всё что угодно, имеющее "синтаксис", поддается автоматическому анализу:
- языки программирования - разбор исходного кода языков программирования, в процессе трансляции (компиляции или интерпретации);
- структурированные данные - данные, языки их описания, оформления и т. д., например, XML, HTML, CSS, ini-файлы, специализированные конфигурационные файлы и т. п.
- SQL-запросы (DSL-язык)
- математические выражения
- регулярные выражения (которые, в свою очередь, могут использоваться для автоматизации лексического анализа)
- формальные грамматики
- лингвистика - человеческие языки, например, машинный перевод и другие генераторы текстов.
Типы алгоритмов
Восстановление после ошибок
Простейший способ реагирования на некорректную входную цепочку лексем - завершить синтаксический анализ и вывести сообщение об ошибке. Однако часто оказывается полезным найти за одну попытку синтаксического анализа как можно больше ошибок. Именно так ведут себя трансляторы большинства распространённых языков программирования.
Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:
- он должен ясно и точно сообщать о наличии ошибок;
- он должен обеспечивать быстрое восстановление после ошибки, чтобы продолжать поиск других ошибок;
- он не должен существенно замедлять обработку корректной входной цепочки.
Ниже описаны наиболее известные стратегии восстановления после ошибок.
Восстановление в режиме паники
При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определенного множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например, ;,) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.
Восстановление на уровне фразы
Иногда при обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию входного потока так, чтобы это позволило ему продолжать работу. Например, перед точкой с запятой, отделяющей различные операторы в языке программирования, синтаксический анализатор может закрыть все ещё не закрытые круглые скобки. Это более сложный в проектировании и реализации способ, однако, в некоторых ситуациях, он может работать значительно лучше восстановления в режиме паники. Естественно, данная стратегия бессильна, если настоящая ошибка произошла до точки обнаружения ошибки синтаксическим анализатором.
Продукции ошибок
Знание наиболее распространённых ошибок позволяет расширить грамматику языка продукциями, порождающими ошибочные конструкции. При срабатывании таких продукций регистрируется ошибка, но синтаксический анализатор продолжает работать в обычном режиме.
Разновидности трансляторов
Что такое компилятор? Что такое интерпретатор? Что такое исходный язык? Что такое целевой язык?
Интерпретаторы
- Форматтеры текста
- Статические анализаторы кода
- Препроцессоры
- макросы define
- включение файлов #include
- условная компиляция #ifdef
- расширения языка, которые препроцессор переводит в код на языке
Фазы трансляции
- Лексический анализ (сканирование)
- Синтаксический анализ (разбор, "парсинг")
- Семантический анализ
|
На примере выражения p := i + r * 60 id1 := id2 + id3 * 60
На примере трехадресного кода t1 := IntToReal(60) t2 := id3 * t1; t3 := id2 + t2; id1 := t3;
t1 := id3 * 60.0; id1 := id2 + t1;
MOVF id3, R2 MULF #60.0, R2 MOVF id2, R1 ADDF R2, R1 MOVF R1, id1 |
 |
Почти на каждой стадии могут выполняться дополнительные оптимизации, а также происходит анализ и обработка ошибок.
Математическим обеспечением фаз лексического и синтаксического анализа является теория формальных языков. Обычно лексические анализаторы генерируются с помощью регулярных выражений.
Синтаксический анализ основывается на теории контекстно-свободных (КС) грамматик. Общая форма КС-грамматики не позволяет разбирать язык достаточно простым (в частности, автоматически сгенерированным) парсером, потому языки программирования обычно принадлежат одному из нескольких специальных подклассов КС-языков (LL, LR, LALR), которые проще разбирать и некоторые из которых будут подробно изучены в курсе.
Упомянутые достижения теории формальных языков насчитывают уже несколько десятков лет, и в этой области не ожидается каких-либо новых разработок, тем более что имеющиеся теоретические результаты хорошо решают практические задачи. По другому обстоит дело с изучением других двух разделов компиляции: семантическим анализом и оптимизацией. Работы по формальному описанию семантики языков программирования интенсивно появлялись в 70-80-х годах. Однако ни одна из построенных теорий не вошла в широкое употребление при построении трансляторов, и сегодня дело обстоит таким образом, что семантика вначале описывается на естественном языке, а затем реализуется в компиляторе большим набором вручную закодированных условных операторов.
Напротив, в последние годы растёт актуальность теории оптимизирующих преобразований - это объясняется появлением всё более высокоуровневых языков и разнообразных аппаратных платформ. Оптимизация также требует привлечения развитого математического аппарата (в частности, для решения вопроса о корректности преобразований). Многие из достижений активно внедряются в промышленные трансляторы. Всё больше это касается преобразований, связанных с распараллеливанием.
На этапе построения семантического дерева строится таблица символов - в нее заносятся имена, присутствовавшие в исходном тексте, к ним добавляются такие атрибуты как тип, отведённая память, область видимости.
Группировка фаз
- Front-end и back-end Трансляторы.
Перечисленные выше фазы обычно группируются в два модуля - front-end и back-end, в зависимости от того, к какой стороне процесса компиляции они ближе, к исходному языку или к машинному коду для целевой платформы, соответственно. Возможность отдельно разрабатывать front-end и back-end повышает эффективность труда разработчиков трансляторов - насколько, зависит от эффективности используемого внутреннего представления, связывающего эти два модуля. В последнее время всё чаще выделяют middle-end - части компилятора, активно работающие с промежуточным представлением.
- Проходы. Группировка фаз компилятора в проходы (например, объединение фаз лексического, синтаксического, семантического анализа и генерации кода).
Разбиение процесса компиляции на фазы является логическим. Есть и другой, физический подход к такому разбиению - на проходы. Проходом обычно считается одно чтение исходного потока (и, возможно, одна законченная генерация выходного). Разные фазы могут группироваться в один проход.
- Уменьшение количества проходов (на примере предварительного описания подпрограмм). Технология обратных поправок.
Компиляция и многомодульность. Необходимость компилировать модуль в некоторый формат, содержащий правильную программу. Перемещаемые адреса. Редактор связей (линковщик).
Инструментарий для создания трансляторов
- Генераторы лексических анализаторов (сканеров)
- Генераторы синтаксических анализаторов (парсеров)
- Автоматические генераторы кода
Трансляторы трансляторов
- Lex + Yacc
- Flex + Bison
- CoCo
- Antlr
- Gold Parser Builder
- GPLex + GPPG
Генераторы лексических и синтаксических анализаторов
Обзор.
Yacc, Lex Byson, Flex CoCo ANTLR Gold Parser Builder GPPG
Создание лексического анализатора (сканера) с помощью gplex
Общая структура .l файла
Особенности .l файла gplex
Возвращение типов лексем
Лексемы идентификаторов, чисел.
Ключевые слова
Позиция лексемы
Начальные состояния сканера, их изменение, использование для вырезания комментариев:
%x COMMENT
%%
"/*" { BEGIN(COMMENT);}
<COMMENT> "*/" { BEGIN(INITIAL);}
<COMMENT> <<EOF>> { Console.WriteLine("Комментарий не закрыт");}
Создание синтаксического анализатора с помощью gppg
Общая структура .y файла
Задание типов лексем
Таблица приоритетов и ассоциативности
Особенности .y файла gppg
Примеры
- Простейший калькулятор
- Простейший калькулятор с приоритетом операций
- Создание дерева разбора программы
- Преобразование в XML
- Добавление переменных. Представление о таблице символов
- Добавление присваивания
- Добавление типов
- Добавление управляющих конструкций
ПО для разработки анализаторов
ANTLR - генератор парсеров
Bison - генератор парсеров
Coco/R - генератор сканера и парсера
GOLD - парсер
gppg - генератор парсеров для языка C#
JavaCC - генератор парсеров для языка Java
Lemon Parser - генератор парсеров
Lex - генератор сканеров
LRgen - генератор сканеров и парсеров
PEG.js - генератор парсеров для Javascript
Jison - генератор парсеров для Javascript
Ragel - генератор встраиваемых парсеров
Rats! - генератор парсеров для Java
Rebol
SableCC - генератор интерпретаторов
Spirit Parser Framework - генератор парсеров
Xerces - XML парсер
Yacc - генератор парсеров
SHProto - генератор FSM-парсеров
AGFL - генератор парсеров естественного языка
Литература
- Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. - М.: Вильямс, 2001.
- Карпов Ю. Г. Основы построения трансляторов. - М.: BHV, 2005.
- Свердлов С. З. Языки программирования и методы трансляции. - М.: Питер, 2007.
- Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. - М.: BHV, 2005.
- Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. - 2-е изд. - М.: Вильямс, 2008. - ISBN 978-5-8459-1349-4
- Робин Хантер Основные концепции компиляторов = The Essence of Compilers. - М.: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2