9 Mar 2022
Теория и практика разработки компиляторов
-----------------------------------------
В прошлом семестре была теория:
1) формальные языки и грамматики
определение грамматики и языка;
2) классы грамматик (иерархия Хомского)
u --> v u, v <- (Sigma & N)*
u содержит хотя бы 1 нетерминал
S <- N
язык L -- это множество цепочек, выводимых из S
-- грамматики без ограничений определяют слишком большой класс
языков: рекурсивно перечислимые языки. Нет алгоритма, который
позволяет определить принаждежность цепочки языку.
-- контекстно зависимые языки:
uAv --> uwv, A <- N, |w| > 0 (неукорачивающая грамматика)
Допускается также правило
S --> eps
L = { a^n b^n c^n, a, b, c <- Sigma, n > 0 }
abc, aabbcc, aaabbbccc, ...
Грамматика этого языка:
S --> ABc | ABSc ABABABABcccc
Bc --> bc
BA --> AB
Bb --> bb
Ab --> ab
Aa --> aa
Вывод aabbcc
S => ABSc => ABABcc => ABAbcc => AABbcc => AAbbcc => Aabbcc => aabbcc
К сожалению, в нашей грамматике есть правило
BA --> AB
которое не имеет требуемого вида: uAv --> uwv
Но можно место этого правила использовать 3 правила:
BA --> FA
FA --> FB
FB --> AB
Любая неукоращивающая грамматика может быть преобразована
до контекстно зависимой, эквивалениной ей в смысле порожденного ей языка.
-- контекстно-свободные грамматики
Правила имеют вид
A --> w A <- N, w <- (Sigma U N)*
в том числе w может быть пустым словом.
Теорема
Класс контекстно-свободных языков является подклассом
контекстно зависимых языков.
Доказательство предоставляется алгоритмом избавления от eps-правил
A --> eps такие правила исключаем, если A != S
B --> uAvAw для таких правил добавляем еще правила
B --> uvAw | uAvw | uvw
Обратное неверно: язык L = { a^n b^n c^n } не контекстно свободный.
Доказательство получается путем применения леммы о разрастании
(pumping lemma, лемма о накачке).
Пусть L -- КС-язык. Тогда существует число K:
если цепочка u <- L, |u| >= K, то цепочку u можно разбить на 5 частей
u = v x w y t
так, что при синхронном повторении подслов x, y мы будем получать
цепочки из L:
для всякого i > 0 цепочка
v x^i w y^i t
также принадлежит языку L
v xx w yy t
v xxx w yyy t
v xxxx w yyyy t
. . .
Причем | x w y | <= K
Дерево вывода (синтаксическое дерево)
Пример: грамматика языка арифм. формул
S -> S + S | S * S | a | ( S )
L состоит из правильный арифметических формул с буквой a в качестве операнда
a, a*a, (a), a+a*a, a+(a*a), (a+a)*a, ...
Рассмотрим вывод цепочки a+a*a
S => S + S => S + S * S => S + S * a => S + a * a => a + a * a
S
/ | \
S + S
| /|\
a S * S
| |
a a
Для той же цепочки можно построить другой правый вывод:
S => S * S => S * a => S + S * a => S + a * a => a + a * a
S
/ | \
S * S
/|\ |
S + S a
| |
a a
Такая грамматика называется неоднозначной.
Идея доказательства леммы о разрастании.
Возьмем достаточно длинную цепочку и ее дерево вывода...
В нем повторится какой-нибудь нетерминал на пути от корня к
терминальной вершине...
Все естественный языки неоднозначны (есть фразы, которые можно
понять по разному).
Пусть x -- элемент идеала I кольца R, который был опеределен
при доказательстве теоремы 1.
Струи Арагвы и Куры узрели русские шатры.
Грамматику языка арифм. формул
S -> S + S | S * S | a | ( S )
можно преобразовать в однозначную:
S -> T | S + T
T -> M | T * M
M -> a | (S)
Формула a + a*a имеет только одно дерево вывода
(только 1 левый вывод и только 1 правый вывод)
S
/ + \
S T
| /|\
T T * M
| | |
M M a
| |
a a
Формальные языки должны быть однозначными.
Нужно уметь придумывать однозначные грамматики.
КС язык называется существенно неоднозначным, если
для него не существует однозначной грамматики.
Такие языки есть (пример в книге Axo, Ульман "Форм. языки").
Пример: язык правильной расстановки скобок (язык Дика).
(()())()
Плохая грамматика этого языка:
S -> () | S S | (S)
Неоднозначна, поскольку цепочка ()()()
имеет два правых вывода: S1 S2, S1 = ()(), S2 = ()
S1 S2, S1 = (), S2 = ()()
Как изменить грамматику?
S -> T | S T
T -> () | (S)
Задача:
L = { цепочки в алфавите Sigma={a, b}, в которых число букв a
равно числу букв b }
Придумать однозначную грамматику.
-- автоматные, или праволинейные, или леволинейные, или регулярные языки.
Языки, задаваемые конечными автоматами.
Задача разбора противоположна задаче вывода.
Вывод -- начинаем с начального нетерминала S, применяем правила вывода,
заканчиваем терминальной цепочкой.
Разбор (parsing) -- начинаем с терминальной цепочки, постепенно восстанавливам
вывод цепочки (справа налево), в конце-концов сворачиваем ее
к начальному нетерниналу (это при восходящем разборе; бувает еще
рекурсивный, или нисходящий разбор).
===============================================================
16 Mar 2022
Прошлый раз я напомнил определение формальной грамматики Хомского и
языка, порожденного грамматикой.
Sigma -- алфавит терминалов
N -- алфавит метасимволов (нетерминалов)
L -- подмножество Sigma* (Sigma* -- множество конечных цепочек из элементов
Sigma, включая пустую цепочку eps)
Правила грамматики имеют вид
u --> v u, v <- (Sigma U N)*
u должна содержать хотя бы один нетерминал.
S <- N -- начальный нетерминал.
Вывод -- последовательность замен:
tur => tvr
Язык, заданный грамматикой -- этo множество цепочек,
выводимых из S
В общем случае мы получаем класс рекурсивно перечислимых языков,
для которых алгоритмически неразрешима проблема принадлежности цепочки языку.
1. Контекстно-зависимые языки
Правила имеют вид
uAv --> uwv A <- N, u,v,w <- (Sigma U N)*, |w| > 0
также допускается одно правило
S --> eps
Прошлый раз было показано, что язык L = { a^n b^n c^n } контекстно зависимый
abc, aabbcc, aaabbbccc, ...
2. Контекстно-свободные языки
Правила имеют вид
A --> u A <- N, u <- (Sigma U N)*
Язык L = { a^n b^n c^n } не является контекстно свободным.
Доказывается с помощью леммы о разрастании:
Если L -- бесконечный КС язык, то существует число K:
ecли u <- L, |u| >= K ==>
u представима в виде
u = v x w y t |x| + |y| > 0, |x w y| <= K
причем цепочки
v xx w yy t
v xxx w yyy t
v xxxx w yyyy t
. . .
v x^i w y^i t
тоже принадлежат языку
Еще один пример не КС языка:
L = { u u, u <- {a, b}* }
3. Право-линейные языки
A --> uB, u -- терминальная цепочка
A --> u
Лево-линейные языки
A --> Bu, u -- терминальная цепочка
A --> u
Автоматные языки
Регулярные языки
Теорема Клини утверждает, что классы автоматных и регулярных языков
совпадают.
Вернемся к контекстно свободным языкам.
Мы можем рассмотреть задачу вывода цепочки и обратную задачу
разбора: дана терминальная цепочка, надо восстановить ее вывод.
Утверждение: для КС языков проблема принадлежности цепочки языку
алгоритмически разрешима. Существует алгоритм, основанный на идеях
динамического программирования, работающий за время O(n^3).
Однако этот алгоритм не применяется на практике.
На практике применяются 2 алгоритма разбора:
1) рекурсивный, или нисходящий, или LL(1)-разбор;
(класс грамматик, допускающих рекурсивный разбор, достаточно узкий).
S -> S + S | S * S | a | ( S )
плохая (неоднозначная грамматика a+a*a)
хорошая (однозначная) грамматика:
S -> T | S + T
T -> M | T * M
M -> a | (S)
Правый вывод формулы a+a*a
S => S + T => S + T => S + T * M => S + T * a => S + M * a =>
S + a * a => T + a * a => M + a * a => a + a * a
Но! Эта грамматика не допускает рекурсивный разбор.
Эту грамматику можно преобразовать так, чтобы она допускала рекурсивный
разбор:
вместо правил S -> T | S + T
S => S + T => S + T + T => S + T + T + ... + T => T + T + T + ... + T
используем правила
S -> T H
H -> eps | + T H
H -- это хвост формулы
2) восходящий, или LR(1)-разбор
L -- цепочку чистается слева (Left) направо;
R -- строятся правые (Right) выводы
1 -- мы заглядываем на 1 символ вперед.
Восходящий разбор выполняется с помощью конечного автомата со
стековой памятью (с "магазинной" памятью).
Рассмотрим понятие LR-процесса.
Состояние LR-процесса задается
1) стеком LR-процесса -- цепочка из терминалов и нетерминалов,
которая наращивается с правого конца;
2) аванцепочкой из терминалов (это непрочитанная часть исходной цепочки).
Рассматриваем задачу восстановления вывода данной терминальной цепочки.
LR-процесс как бы противоположен процессу вывода цепочки.
Рассмотрим на примере цепочки a+a*a
Ее правый вывод формулы a+a*a
S => S + T => S + T => S + T * M => S + T * a => S + M * a =>
=> S + a * a => T + a * a => M + a * a => a + a * a
В LR-процессе имеются 2 типа действий:
1) сдвиг (shift) -- перенос первого символа аванцепочки в стек
+------
|aBDaeW abcab
+------
==>
+-------
|aBDaeWa bcab
+-------
2) свертка по правилу F -> eWa (reduce)
если слово в вершине стека есть правая часть некоторого правила,
то оно заменяется на нетерминал в левой части правила
+-------
|aBDaeWa bcab
+-------
==>
+-----
|aBDaF bcab
+-----
аванцепочка остается без изменений.
LR-процесс называется успешным, если по окончанию аванцепочка пустая,
а в стеке начальный метасимвол.
Предложение
Существует взаимно однозначное соотвествие между LR-процессами
и правыми выводами в грамматике.
На примере a+a*a
Правый вывод:
S => S + T => S + T * M => S + T * a => S + M * a =>
=> S + a * a => T + a * a => M + a * a => a + a * a
LR-процесс
+--
| a+a*a сдвиг
+--
+--
|a +a*a свертка по правилу M -> a
+--
+--
|M +a*a свертка по правилу T -> M
+--
+--
|T +a*a свертка по правилу S -> T
+--
+--
|S +a*a два раза сдвиг
+--
+---
|S+a *a свертка по правилу M -> a
+---
+---
|S+M *a свертка по правилу T -> M
+---
+---
|S+T *a два раза сдвиг
+---
+-----
|S+T*a свертка по правилу M -> a
+-----
+-----
|S+T*M свертка по правилу T -> T*M
+-----
+---
|S+T свертка по правилу S -> S+T
+---
+--
|S успешное завершение LR-процесса
+--
LR-процесс неоднозначен, если мы сделаем неверное действие,
то можем не довести LR-процесс до успешного завершения.
Для правильного определения действия, которое нужно делать на
каждом шаге LR-процесса, мы строим конечный детерминированный автомат.
Определим множество LR(0)-состояний разбора.
Определение:
ситуацией LR(0)-разбора называется правило грамматики
с отмеченной позицией в правой части. (Позиция отмечается
либо точкой, либо символом подчеркивания).
Пример: для правила
S -> S + T
имеется 4 ситуации
S -> _S + T, S -> S_+ T, S -> S+_T, S -> S+T_
Состоянием LR(0)-разбора называется конечное множество ситуаций.
Алгоритм построения множества состояний LR(0)-разбора на примере
несложной грамматики:
int a, d, c;
double e, f;
Рассмотрим язык, состоящий из цепочек
t n;
t n, n;
t n, n, n;
Грамматика:
S -> t L;
L -> n | L, n
1) S -> _t L;
делая в состоянии 1 сдвиг t, получаем состояние 2:
2) S -> t_L;
L -> _n
L -> _L, n
делая в состоянии 2 сдвиг L, получаем состояние 3:
3) S -> t L_;
L -> L_, n
делая в состоянии 2 сдвиг n, получаем состояние 4:
4) L -> n_
делая в состоянии 3 сдвиг ;, получим состояние 5:
5) S -> t L;_
делая в состоянии 3 сдвиг "," получим состояние 6:
6) L -> L,_n
делая в состоянии 6 сдвиг n, получим состояние 7:
7) L -> L,n_
Состояние допускает сдвиг терминала x, если есть ситуация, где после
подчеркивания стоит x;
Состояние допускает свертку по правилу A -> w,
если есть ситуация A -> w_ (подчеркивание после конца правой части).
В состоянии есть конфликт сдвиг-свертка, если оно допускает и сдвиг,
и свертку.
В состоянии есть конфликт свертка-свертка, если оно допускает
свертку по двум разным правилам.
Грамматика допускает LR(0)-разбор (или это LR(0)-грамматика),
если конфликтов нет.
Разобранная грамматика является LR(0)-грамматикой.
============================================================
23 Mar 2022
Любую КС-грамматику можно преобразовать так,
чтобы было только одно правило с левой частью S
и S не встречался бы в правых частях правил.
Иначе берем новый нетерминал S'
и правило
S' -> S
S -> w
. . .
В прошлый раз для грамматики
S -> t L;
L -> n | L, n
(язык
t n;
t n, n;
t n, n, n;
)
было построено множество состояний LR(0)-разбора
(7 состояний):
1) S -> _t L;
2) S -> t_L;
L -> _n
L -> _L, n
3) S -> t L_;
L -> L_, n
4) L -> n_
5) S -> t L;_
6) L -> L,_n
7) L -> L,n_
Как работает LR-парсер?
У него также есть стек и аванцепочка, только в стеке
хранятся не символы (терминалы и нетерминалы), а номера
состяний LR(0)-разбора. Но стек парсера как бы параллелен
стеку LR-процесса, хотя его глубина на единицу больше.
Выпишем таблицу состояний и переходов LR-парсера
Строки таблицы нумеруются номерами состояний, а столбцы -- терминалами и
нетерминалами грамматики.
t n , ; L S
--------------------------------------------------------
1 сдв->2 err err err err допуск
2 err сдв->4 err err сдв->3 err
3 err err сдв->6 сдв->5 err err
4 свертка по правилу L -> n
5 свертка по правилу S -> t L;
6 err сдв->7 err err err err
7 свертка по правилу L -> L,n
--------------------------------------------------------
Разберем работу LR-парсера для цепочки
t n, n;
1) начало
+----
|1 t n, n;
|
+----
В соответствии с таблицей, в состоянии 1 делаем сдвиг t и переходим в
состояние 2
2) на вершине стека -- состояние 2, делаем сдвиг n и переходим в состояние 4
+----
|1 2 n, n;
| t
+----
3) в состоянии 4 действие -- свертка по правилу по правилу L -> n
+-----
|1 2 4 , n;
| t n
+-----
Парсер выполняет свертку в 2 этапа:
-- сначала из стека удаляется правая часть правила (если правая часть
имеет размер k символов, то из стека удаляются верхние k элементов).
А в начало аванцепочки мысленно добавляем левую часть правила
+----
|1 2 L , n;
| t
+----
И затем в состоянии на вершине стека (в нашем случае 2) делаем сдвиг L
и в соответствии с таблицей парсера переходим в состояние 3
4) в состоянии 3, делая сдвиг ",", переходим в состояние 6
+-----
|1 2 3 , n;
| t L
+-----
5) в состоянии 6 делаем сдвиг n и переходм в состояние 7
+-------
|1 2 3 6 n;
| t L ,
+-------
6) в состоянии 7 выполняем свертку по правилу L -> L , n
+---------
|1 2 3 6 7 ;
| t L , n
+---------
Парсер выполняет свертку в 2 этапа:
сначала выкидываем из стека правую часть правила и
в аванцепочку добавляем левую часть правила:
+---
|1 2 L ;
| t
+---
И затем в состоянии 2 делаем сдвиг L и переходим в состояние 3
7) в состоянии 3 делаем сдвиг ";" и переходим в состояние 5
+-----
|1 2 3 ;
| t L
+-----
8) в состоянии 5 выполняем свертку по правилу S -> t L ;
+-------
|1 2 3 5
| t L ;
+-------
Сначала удаляем правую часть правила из стека и добавляем
в аванцепочку левую часть правила:
+--
|1 S
|
+--
Делаем в начальном состоянии 1 сдвиг S и переходим в состояние
"успешное завершение разбора"
9)
+--------
|1 Допуск
| S
+--------
Помимо стека разбора (в котором содержатся номера состояний),
LR-парсер поддерживает также семантический стек, который может
содержать данные любого типа, которые соответствуют
узлам синтаксического дерева. Например, если мы строим дерево
вывода, то каждому нетерминалу в стеке LR-процесса будет соответствовать
поддерево с корнем, помеченным этим нетерминалом
+----------
|......AbCd
| t h t -- дерево, соответствующее A, h -- дерево для C
+----------
свертка по правилу F -> AbCd
+----------
|......F
| s s -- дерево, соответствующее F
+----------
Дерево s: F
/ / \ \
t b h d
Для арифметических формул семантический стек может хранить,
например, вычисленное значение, соответствующее данному нетерминалу.
Вычисление промежуточных значений происходит во время сверток:
+-------------
| . . .F + F свертка F -> F + F
| . . .7 12
+------------
+----------
| . . . F
| . . . 19
+----------
===========================================================
Отметим, что большинство грамматик не являются LR(0)-грамматиками,
т.е. множество LR(0)-состояний, построенное по описанному выше алгоритму,
содержит конфликты:
1) сдвиг-свертка, когда состояние допускает и сдвиг, и свертку;
2) свертка-свертка, когда состояние допускает свертку по двум
разным правилам.
Рассмотрим простой пример грамматика, не являющейся LR(0)-грамматикой.
Вызов функции в языке C имеет вид
f()
f(e) e от слова expression
f(e, e)
f(e, e, e)
. . .
Грамматика этого языка:
S -> f(L)
L -> eps | A L -- список, который может быть и пустым
A -> e | A, e A -- непустой список
Построим множество LR(0)-состояний для этой грамматики
1) S ->_f(L)
Делая сдвиг f в состоянии 1, получаем
2) S -> f_(L)
Делая сдвиг ( в состоянии 2, получаем
3) S -> f(_L) конфликт сдвиг-свертка
L -> _ свертка по правилу L -> eps
L -> _A
A -> _e сдвиг e
A -> _A, e
Делая сдвиг L в состоянии 3, получаем
4) S -> f(L_)
Делая сдвиг A в состоянии 3, получаем
5) L -> A_ конфлика сдвиг-свертка
A -> A_, e
Делая сдвиг e в состоянии 3, получаем
6) A -> e_
Делая сдвиг ) в состоянии 4, получаем
7) S -> f(L)_
Делая сдвиг "," в состоянии 5, получаем
8) A -> A,_e
Делая сдвиг e в состоянии 8, получаем
9) A -> A,e_
В построенном множестве в двух состояниях 3 и 5 имеется
конфликт сдвиг-свертка. Таким образом, данная грамматика
не является LR(0)-грамматикой. Как мы увидим, в данном
случае конфликты разрешаются с помощью учета первого символа
аванцепочки. Например, в состоянии 3 свертка выполняется,
когда первый символ аванцепочки равен ")", а сдвиг --
когда он равен "e". Для учета возможных первых символов
аванцепочки и определения соответствующих действий строится
система состояний LR(1)-разбора; здесь единица означает
учет одного (т.е. первого) символа аванцепочки при принятии
решения об очередном действии.
===========================================================