к библиотеке   к ТПОИ   Устройства ввода информации   к экономической информатике   к дискретной математике

Введение в теорию трансляторов

  1. Типы алгоритмов
  2. Восстановление после ошибок
  3. Восстановление в режиме паники
  4. Восстановление на уровне фразы
  5. Продукции ошибок
  6. Разновидности компиляторов
  7. Фазы компиляции
  8. Группировка фаз
  9. Инструментарий для создания компиляторов
  10. Компиляторы компиляторов
  11. Порождающие грамматики
  12. Классификация формальных грамматик
  13. Порождение (вывод)
  14. Перевод (трансляция)
  15. Схема синтаксически управляемого перевода
  16. Транслирующие грамматики
  17. Атрибутные грамматики и трансляция
  18. Синтаксический анализ
  19. Нисходящий синтаксический анализ
  20. Нерекурсивный предиктивный анализ
  21. Множества FIRST и FOLLOW
  22. Восходящий синтаксический анализ
  23. Генераторы анализаторов
  24. ПО для разработки анализаторов
  25. Литература

Одним из центральных понятий в информатике является формализующая обработка информации, называемая парсингом. На ее входе имеется неподходящий для дальнейшей обработки информации текст. Это может быть текст либо на другом языке (на другом уровне языка), либо недостаточно или совсем не формализованный текст, непригодный для простой автоматической обработки.

Синтаксический анализ, парсинг - это процесс сопоставления линейной последовательности лексем (слов, фраз) языка с его формальной грамматикой. Результатом обычно является дерево разбора (синтаксическое дерево). Обычно применяется совместно с лексическим анализом. Синтаксический анализатор (парсер) - это программа или часть программы, выполняющая синтаксический анализ, то есть распознавание входной информации. При этом входные данные преобразуются к виду, пригодному для дальнейшей обработки. Этот вид обычно представляет собой формальную модель входной информации на языке последующего процесса обработки информации.


Пример разбора выражения в дерево

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

Как правило, результатом синтаксического анализа является синтаксическая структура предложения, представленная либо в виде дерева зависимостей, либо в виде дерева составляющих, либо в виде некоторой комбинации первого и второго способов представления.

Всё что угодно, имеющее "синтаксис", поддается автоматическому анализу:

Типы алгоритмов

Нисходящий парсер (англ. top-down parser) - такой парсер, в котором продукции грамматики раскрываются, начиная со стартового символа, до получения требуемой последовательности лексем.
Восходящий парсер (англ. bottom-up parser) - такой парсер, в котором продукции восстанавливаются из правых частей, начиная с токенов-лексем и кончая стартовым символом.

Восстановление после ошибок

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

Таким образом перед обработчиком ошибок синтаксического анализатора стоят следующие задачи:

Ниже описаны наиболее известные стратегии восстановления после ошибок.

Восстановление в режиме паники

При обнаружении ошибки синтаксический анализатор пропускает входные лексемы по одной, пока не будет найдена одна из специально определенного множества синхронизирующих лексем. Обычно такими лексемами являются разделители, например, ;,) или }. Набор синхронизирующих лексем должен определять разработчик анализируемого языка. При такой стратегии восстановления может оказаться, что значительное количество символов будут пропущены без проверки на наличие дополнительных ошибок. Данная стратегия восстановления наиболее проста в реализации.

Восстановление на уровне фразы

Иногда при обнаружении ошибки синтаксический анализатор может выполнить локальную коррекцию входного потока так, чтобы это позволило ему продолжать работу. Например, перед точкой с запятой, отделяющей различные операторы в языке программирования, синтаксический анализатор может закрыть все ещё не закрытые круглые скобки. Это более сложный в проектировании и реализации способ, однако, в некоторых ситуациях, он может работать значительно лучше восстановления в режиме паники. Естественно, данная стратегия бессильна, если настоящая ошибка произошла до точки обнаружения ошибки синтаксическим анализатором.

Продукции ошибок

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

Разновидности компиляторов

Что такое компилятор. Исходный и целевой язык.

Фазы компиляции

  • Лексический анализ (сканирование)
  • Синтаксический анализ (разбор, "парсинг")
  • Семантический анализ

На примере выражения 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 повышает эффективность труда разработчиков компиляторов - насколько, зависит от эффективности используемого внутреннего представления, связывающего эти два модуля. В последнее время всё чаще выделяют middle-end - части компилятора, активно работающие с промежуточным представлением.

Разбиение процесса компиляции на фазы является логическим. Есть и другой, физический подход к такому разбиению - на проходы. Проходом обычно считается одно чтение исходного потока (и, возможно, одна законченная генерация выходного). Разные фазы могут группироваться в один проход.

Компиляция и многомодульность. Необходимость компилировать модуль в некоторый формат, содержащий правильную программу. Перемещаемые адреса. Редактор связей (линковщик).

Инструментарий для создания компиляторов

Компиляторы компиляторов

Порождающие грамматики

Определение. Терминалы, нетерминалы, символы. Продукции. Стартовый символ.

Обозначения:

a,b,c, ... - терминалы
u,v,w,x,y,z - строки (цепочки) терминалов
A,B,C, ... - нетерминалы
α,β,γ, ... - строки (цепочки) нетерминалов и терминалов
ε - пустая цепочка

Опр. формальной грамматики (порождающей грамматики Хомского)

G = (N,Σ,P,S)
N - нетерминалы
Σ - терминалы
P - правила вывода (продукции) вида α→β, α - непустая 

V = Σ + N - множество всех нетерминалов и терминалов

V* - множество всех цепочек символов из V

V+ = V* - {ε}

Классификация формальных грамматик по Хомскому

Правила имеют вид αAβ → αγβ. γ принадлежит V+, т.е. грамматика является неукорачивающей
α,β называются левым и правым контекстом
Правила имеют вид A → α. α принадлежит V*, т.е. грамматика может быть укорачивающей => КС языки не содержатся в КЗ
Наиболее близкая к БНФ
Правила имеют вид A → aB, A → a, A → ε
Автоматные языки содержатся в КС языках

Пример. Грамматика, порождающая язык правильных скобочных выражений.

S → (S) | SS | ε

Порождение (вывод)

Обозначения

=>
=>+ (1 или более)
=>* (0 или более)
Сентенциальная форма грамматики - это строка, которая может быть выведена из стартового символа.
Предложение (сентенция) грамматики - это сентенциальная форма, состоящая из одних терминалов.
Язык L(G) грамматики - это множество всех ее предложений.

Обозначения:

=>(lm)
=>(lm)*
=>(rm)+

Левый, правый вывод (порождение).

Пример

E → E + T
  | T
T → T * P
  | P
P → i
  | ( E )

Левый и правый вывод для предложения i + i * i

Дерево вывода (синтаксическое дерево, дерево разбора) строки предложения. В отличие от порождения, из него исключена информация о порядке вывода.

Крона дерева разбора - цепочка меток листьев слева направо

Грамматика, которая дает более одного дерева разбора для некоторого предложения, называется неоднозначной.

Пример неоднозначной грамматики. Грамматика арифметических выражений.

E → E+E | E*E | i

Два дерева разбора для цепочки i + i * i

Преобразование в эквивалентную однозначную грамматику:

E → E + T
  | T
T → T * P
  | P
P → i

Пример неоднозначной грамматики. Грамматика условного оператора

S → if b then S
  | if b then S else S
  | a  

Два дерева разбора для цепочки if b then if b then a

Преобразование в эквивалентную однозначную грамматику:

S → if b then S
  | if b then S2 else S
  | a  
S2 → if b then S2 else S2
  | a  

Утверждение. Проблема неоднозначности произвольной КС-грамматики алгоритмически не разрешима

Леворекурсивные грамматики, их проблемы. Алгоритм устранения левой рекурсии.

Перевод (трансляция)

Ранее мы решали вопрос о принадлежности некоторой цепочки α интересующему нас языку L, задаваемому грамматикой G. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение.

Перевод с языка L1 на язык L2 - Пусть Σ и Δ - два алфавита (называемые "входным" и "выходным" соответственно). L1 ⊂ Σ*, L2 ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

Чтобы решить указанную задачу (т.е. конструктивно определить перевод), можно встроить в процесс проверки принадлежности некоторые действия, формирующие на выходе желаемый результат.

Схема синтаксически управляемого перевода (СУ-схема)

СУ-схема - это грамматика, в которую с каждым синтаксическим правилом встроен элемент перевода.

Пример. Перевод алгебраического выражения в ПОЛИЗ (польская инверсная запись). Запишем правила грамматика вместе с элементами перевода.

Правило Элемент перевода
E → E + T E = E T +
E → T E = T
T → T * P T = T P *
T → P T = P
P → (E) P = E
P → <id> P = <id>

Выведем цепочку a * (b + c) и одновременно переведём её в ПОЛИЗ: a b c + * (как обычно, используем левый вывод):

(E, E) ⇒ (T, T) ⇒ (T * P, T P *) ⇒ (P * P, P P *) ⇒ (a * P, a P *) ⇒ (a * (E), a E *) ⇒
       ⇒ (a * (E + T), a E T + *) ⇒* (a * (b + c), a b c + *)

Определение.

Схема синтаксически управляемого перевода - это пятёрка

T = (N, Σ, Δ, R, S),

где:

N - множество нетерминалов ("переменных"),
Σ - входной алфавит,
Δ - выходной алфавит,
S - стартовый символ (S ∊ N),
R = {A → (α, β) | A ∊ N, α ∊ (N ∪ Σ)*, β ∊ (N ∪ Δ)*}.

Причём α и β в каждом конкретном правиле содержат одни и те же нетерминалы с точностью до перестановки.

Далее считаем, что задана некоторая СУ-схема T = (N, Σ, Δ, R, S).

Определение.

Входная грамматика, соответствующая СУ-схеме T - это четвёрка

Gin = (N, Σ, R, S),

где

P = {A → α | ∃β A → (α, β) ∊ R}.

Определение.

Выходная грамматика, соответствующая СУ-схеме T - это четвёрка

Go = (N, Δ, R, S),

где

P = {A → β | ∃α A → (α, β) ∊ R}.

Определение.

СУ-перевод, СУ-трансляция - это множество

{(x, y) | (S, S) ⇒* (x, y), x ∊ Σ*, y ∊ Δ*},

обозначаемое обычно τ(T).

СУ-перевод можно понимать как трансформацию синтаксических деревьев (соответствующих выводу входной и выходной цепочек).

Транслирующие грамматики

Позволяют решать задачу перевода в более сложных случаях, чем СУ-схемы. ТГ это разновидность КС-грамматик, где символы (терминалы) разделены на два множества, Σi и Σa (a от action), называемые "входными" и "операционными" соответственно. При использовании ТГ, чтобы различать элементы Σi и Σa, будем заключать последние в фигурные скобки, '{', '}', считая получившиеся на письме три символа одним символом алфавита.

Пример. Перевод простого алгебраического выражения в ПОЛИЗ ...

Определение.

активная цепочка - Пусть α ∊ (Σi ∪ Σa)*. Тогда α называется активной цепочкой. Входные (операционные) символы активной цепочки, записанные отдельно в том же порядке, как они встречались в ней, образуют входную (операционную) цепочку.

Операционные символы можно трактовать как имена процедур, выполняющих определённые действия. Пока - процедур без параметров. Операционные символы также могут использоваться для интерпретации кода. Операционные символы могут находиться в любой части результата продукции, не только в суффиксе, но это может сильно усложнить парсер (иногда придётся откатываться).

Атрибутные грамматики и трансляция

В АГ с каждым символом грамматики может быть связан один или несколько атрибутов. Для каждого синтаксического правила вводятся семантические правила, устанавливающие функциональные зависимости между атрибутами.

Дерево, содержащее атрибуты, называется аннотированным. Атрибуты придают смысл синтаксической структуре, описываемой деревом, и потому аннотированное дерево называется также семантическим деревом.

Пример. Вычисление простого арифметического выражения ...

Типы атрибутов.

  1. Синтезированные - значения таких атрибутов зависят только от значений атрибутов потомков в дереве разбора.
  2. Унаследованные - значения таких атрибутов зависят от значений атрибутов родительского узла, узлов-братьев и сестёр (дочерних для родительского), а также других атрибутов самого узла.

Синтаксический анализ

Понятие синтаксического анализатора.

Нисходящие (top-down) и восходящие (bottom-up) синтаксические анализаторы

Нисходящий синтаксический анализ

Предиктивный синтаксический анализатор - это синтаксический анализатор, работающий методом рекурсивного спуска и не требующий откатов.

Нерекурсивный предиктивный анализ

Схема работы со стеком, таблицей разбора, входным буфером

Алгоритм нерекурсивного предиктивного анализа

Пример

Множества FIRST и FOLLOW

Определение.

Пример.

Алгоритм построения таблиц предиктивного анализа.

Определение LL(1) грамматики. Пояснение названия.

Утв. LL(1) грамматика не может быть леворекурсивной или неоднозначной.

Эквивалентное определение LL(1) грамматики.

Восстановление после ошибок в предиктивном анализе.

Восходящий синтаксический анализ

Наиболее распространенная разновидность - ПС-анализ (перенос-свертка - shift-reduce)

Понятие основы. Примеры.

Обращенное правое порождение и обрезка основ.

Стековая реализация ПС-анализа. Основные операции:

Перенос (shift)
Свертка (reduce)
Допуск  (accept)
Ошибка  (error)

Утв. Основа всегда находится на вершине стека и никогда - внутри него. Доказательство.

Понятие активного префикса.

LR-анализаторы. SLR, канонический LR и LALR анализаторы.

Общая схема и алгоритм LR-анализа. Пример.

LR-грамматики.

Неоднозначности вида shift-reduce и их разрешение.

Генераторы лексических и синтаксических анализаторов

Обзор.

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

Примеры

  1. Простейший калькулятор
    • Простейший калькулятор с приоритетом операций
    • Создание дерева разбора программы
    • Преобразование в 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 - генератор парсеров естественного языка

Литература

  1. Ахо А., Сети Р., Ульман Д. Компиляторы. Принципы, технологии, инструменты. - М.: Вильямс, 2001.
  2. Карпов Ю. Г. Основы построения трансляторов. - М.: BHV, 2005.
  3. Свердлов С. З. Языки программирования и методы трансляции. - М.: Питер, 2007.
  4. Опалева Э. А., Самойленко В.П. Языки программирования и методы трансляции. - М.: BHV, 2005.
  5. Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. Компиляторы: принципы, технологии и инструментарий = Compilers: Principles, Techniques, and Tools. - 2-е изд. - М.: Вильямс, 2008. - ISBN 978-5-8459-1349-4
  6. Робин Хантер Основные концепции компиляторов = The Essence of Compilers. - М.: "Вильямс", 2002. - С. 256. - ISBN 5-8459-0360-2
к библиотеке   к ТПОИ   Устройства ввода информации   к экономической информатике   к дискретной математике
Знаете ли Вы, что "гравитационное линзирование" якобы наблюдаемое вблизи далеких галактик (но не в масштабе звезд, где оно должно быть по формулам ОТО!), на самом деле является термическим линзированием, связанным с изменениями плотности эфира от нагрева мириадами звезд. Подробнее читайте в FAQ по эфирной физике.

НОВОСТИ ФОРУМАФорум Рыцари теории эфира
Рыцари теории эфира
 24.05.2017 - 20:22: СОВЕСТЬ - Conscience -> ПРОБЛЕМА КРИМИНАЛИЗАЦИИ ЭКОНОМИКИ - Карим_Хайдаров.
24.05.2017 - 19:39: СОВЕСТЬ - Conscience -> Просвещение от О.Н. Четвериковой - Карим_Хайдаров.
24.05.2017 - 16:55: СОВЕСТЬ - Conscience -> Декларация Академической Свободы - Карим_Хайдаров.
24.05.2017 - 14:52: СОВЕСТЬ - Conscience -> КОЛЛАПС МИРОВОЙ ФИНАНСОВОЙ СИСТЕМЫ - Карим_Хайдаров.
24.05.2017 - 06:20: Беседка - Chatter -> ЭПИСТОЛЯРНАЯ ФИЗИКА - Карим_Хайдаров.
24.05.2017 - 06:19: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Гипотеза о причине смещения линии апсид эллиптических орбит - Карим_Хайдаров.
23.05.2017 - 16:17: СОВЕСТЬ - Conscience -> Проблема народного образования - Карим_Хайдаров.
23.05.2017 - 13:07: СОВЕСТЬ - Conscience -> Просвещение от Сергея Салля - Карим_Хайдаров.
15.05.2017 - 05:53: ЦИТАТЫ ЧУЖИХ ФОРУМОВ - Outside Quotings -> Украинский сайт ЭкоТехника - Карим_Хайдаров.
13.05.2017 - 07:01: ЭКСПЕРИМЕНТАЛЬНАЯ ФИЗИКА - Experimental Physics -> Опыты Майкельсона-Морли,Маринова и увлечение эфира - Сергей_Юдин.
11.05.2017 - 16:32: ЭКОЛОГИЯ - Ecology -> Биологическая безопасность населения - Карим_Хайдаров.
11.05.2017 - 11:36: СОВЕСТЬ - Conscience -> Просвещение от Ю.Ю. Болдырева - Карим_Хайдаров.
Bourabai Research Institution home page

Bourabai Research - Технологии XXI века Bourabai Research Institution