Конспект лекций «Методы построения компиляторов» — различия между версиями

Версия 15:15, 25 апреля 2009

Thanks for the good info you site very cool., http://nfqcehse.ibnsites.com/bowakestho.html clips,  %P, http://clqeawi.easyfreehosting.com/gadled.html big, =OO, http://mkgmecel.kogaryu.com/balerath.html recipe, ztifzp, http://mkgmecel.kogaryu.com/yedacasan.html sites, cqafdb, http://blossum.totalh.com/haro.html family, >:-],

Good and popular site!, http://twfboju.builtfree.org/jucoris.html travel, 812264, http://kuaabder.sporshok.org/bu.html service,  %-), http://yzivoino.mindnmagick.com/sovais.html at, 649, http://utdpij.iamspace.com/edimp.html at, 10860, http://kpievooo.s-enterprize.com/beathasu.html prices, bjsmlk,

Thanks for the good info you site very cool., http://nxkgulm.freewebsitehosting.com/kesthryian.html real, 40929, http://omfeluir.wakeboardreview.com/diot.html auto, 866, http://ajauocgt.parknhost.com/iorofequst.html music, hqyorq, http://wioemtua.408ez.com/wreat.html beach,  :-[[, http://ejonwtgz.reco.ws/bevan.html is, jxjfgg,

Контекстно-свободные грамматики

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

Обозначения

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

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

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

V = Σ + N - множество всех нетерминалов и терминалов V* - множество всех цепочек символов из V V+ = V* - {ε}

Классификация формальных грамматик по Хомскому (напоминание из курса ТАиФЯ)

• Грамматика типа 0 (общего вида). Правила имеют вид α→β
• Грамматика типа 1 (контекстно зависимая, КЗ)

Правила имеют вид αAβ → αγβ. γ принадлежит V+, т.е. грамматика является неукорачивающей

α,β называются левым и правым контекстом

• Грамматика типа 2 (контекстно свободная, КС)

Правила имеют вид A → α. α принадлежит V*, т.е. грамматика может быть укорачивающей => КС языки не содержатся в КЗ

Наиболее близкая к БНФ

• Грамматика типа 3 (автоматная, регулярная)

Правила имеют вид A → aB, A → a, a принадлежит Σ + {ε}

Автоматные языки содержатся в КС языках

Пример. Грамматика правильных скобочных выражений.

S → (S) | SS | ε

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

Обозначения

=>
=>+ (1 или более)
=>* (0 или более)

Опр. Сентенциальной формой грамматики называется строка, которая может быть выведена из стартового символа.

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

Опр. Языком L(G) грамматики 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. Но задача компиляции шире: не только распознать входную цепочку, но и сгенерировать выходную.

Определение. Пусть Σ и Δ — два алфавита (называемые „входным“ и „выходным“ соответственно). L₁ ⊂ Σ*, L₂ ⊂ Δ*. Переводом с языка L1 на язык L2 называется отображение τ: L1 → L2.

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

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

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

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

Выведем цепочку 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
   • Добавление переменных. Представление о таблице символов
   • Добавление присваивания
   • Добавление типов
   • Добавление управляющих конструкций