Теория компиляции: черновики лекций
Формальная грамматика G задается:
1) алфавит обычных символов, или терминалов
Sigma = { a, b, c, d, e, ... }
2) алфавит метасимволов, или нетерминалов
(неформально они обозначают понятия языка -- подлежащее, сказуемое,
придаточное предложение, ...)
Обозначаются большими буквами латинского алфавита
N = {A, B, C, ..., Z}
3) среди метасимволов выделен начальный метасимвол
S in N
4) набор правил. Правила имеют вид:
u -> v,
слово u состоит из терминалов и нетерминалов
и содержит хотя бы 1 нетерминал;
слово v произвольное. Не исключаем случай пустого слова eps.
Вывод -- последовательность замен, начинаем с S, в конце получаем
цепочку из терминалов.
S -> a | b | aSa |bSb | eps
abba
S => bSb => baSab => baab
Язык, заданный грамматикой, состоит из всех терминальных
цепочек, выводимых из S.
Иерархия Хомского
0) грамматики общего вида -- таким образом получаются все
рекурсивно перечислимые языки;
aBTbR -> BabbbS
1) контекстно зависимые грамматики -- правила имеют вид
uAv -> uwv, w != eps
Прошлый раз показали, что язык L = { a^n b^n c^n, n = 1, 2, ... }
является контекстно зависимым.
abc, aabbcc, aaabbbccc, ...
S -> ABc | ABSc
Bc -> bc
Bb -> bb
??? BA -> AB ???
BA -> RA
RA -> RB
RB -> AB
Ab -> ab
Aa -> aa
S => ABSc => ABABcc => ABAbcc => AABbcc => AAbbcc =>
=> Aabbcc => aabbcc
Правило BA -> AB не имеет нужного вида, но это правило
можно заменить на 3 правила контекстно зависимого вида:
BA -> RA
RA -> RB
RB -> AB
BA => RA => RB => AB
2) Контекстно свободные грамматики
A -> u
Были рассмотрены примеры:
1) L = {a^n b^n, n = 1, 2, 3, ... }
ab, aabb, aaabbb, aaaabbbb, ...
2) язык арифметических формул -- плохая грамматика
S -> V | S + S | S - S | S * S | S / S | (S)
V -> a | b | ... | z
Примеры формул: a + a*b - (a*a + b)*(z - a)
3) хорошая грамматика языка арифметических формул
S -> T | S + T | S - T
T -> M | T * M | T / M
M -> V | ( S )
V -> a | b | ... | z
Дерево вывода цепочки языка (синтаксическое дерево)
a + b*c
В первой грамматике возможны 2 разных правых вывода:
S => S + S => S + S * S => S + S * V => S + S * c =>
S + V * c => S + b * c => V + b * c => a + b * c
Дерево вывода ( )
S
/ | \
S + S
| /|\
V S * S
| | |
a V V
| |
b c
Другой правый вывод
S => S * S => S * V => S * c => S + S * c => ... => a + b * c
Дерево этого вывода ( )
S
/ | \
S * S
/|\ |
S + S V
| | |
V V c
| |
a b
Первая грамматика неоднозначная, вторая однозначная,
т.е. каждая выводимая формула имеет только один правый вывод,
только один левый вывод и только одно дерево вывода.
Доказано, что существуют контекстно свободные языки, для которых нет
однозначной грамматики! (Пример есть в книге Ахо, Сети, Ульман).
Задача. Язык L = { u \in {a, b}*: deg_a(u) = deg_b(u) }
abbbaaba, ab, abab, abba
Придумать однозначную грамматику.
Задача. Язык Дика -- все правильные расстановки круглых скобок.
(), (()), (())((())), (()()), ... )(
Плохая (неоднозначная) грамматика:
S -> S | SS | (S)
Формула ()()() имеет 2 разных правых вывода / 2 разных дерева вывода.
S => SS => SSS => SS() => S()() => ()()()
S => SS => S() => SS() => S()() => ()()()
Хорошая (однозначная) грамматика:
S -> T | ST
T -> () | (S)
S => ST => S() => ST() => S()() => T()() => ()()()
S => T => (S) => (ST) => (S()) => (T()) => (()())
Лемма о разрастании (о накачке, pumping lemma).
Пусть L -- бесконечный контекстно свободный язык.
Тогда существует целое число K такое, что
если цепочка u языка L имеет длину >= K, то
она представляется в виде
u = h x g y t, причем
1) для любого n >= 1 цепочка
h x^n g y^n t также принадлежит языку
h xx g yy t, h xxx g yyy t, h xxxx g yyyy t, ...
2) |x| + |y| > 0 (хотя бы одна цепочка их x, y непустая)
3) | x g y | <= N.
fhgfhfkh fkdgkdtr djdg fdjgdjfdgdjgfjgf djgfdjgfdgfdj
x y
Применение: лемма позволяет доказать, что конкретный
язык не является контекстно свободным.
Пример: L = { a^n b^n c^n, n = 1, 2, 3, ... }
не является контекстно свободным.
Доказательство.
u = h x g y t
| x g y | <= K
Возьмем n > K. Тогда оба слова x, y не содержат
либо букву a, либо букву c =>
степень слова u xx g yy t по букве a будет строго меньше,
чем степень либо по b, либо по c.
aaaaaa bbbbbb cccccc
Пример 2: L = { uu, где u -- любое слово в алфавите {a, b} },
не является контекстно свободным.
Следствие: множество правильных программ на языке C
не является контекстно свободным языком.
int x, y;
x = x + y;
y = x->z;
3) автоматные языки == праволинейные языки == леволинейные языки
(== регулярные языки по теореме Клини).
Праволинейные языки
A -> uB, u -- слово из терминалов или пустое слово
A -> v, v -- слово из терминалов или пустое слово
Леволинейные языки
A -> Bu, u -- слово из терминалов или пустое слово
A -> v, v -- слово из терминалов или пустое слово
Автоматные языки
Конечный автомат -- ориентированный граф с пометками на ребрах:
пометки -- это буквы алфавита Sigma либо пустое слово.
Кроме того, в этом графе непустое множество вершин должно быть отмечено
как начальные вершины и непустое множество -- как конечные.
Язык, порождаемый КА -- это множество пометок всевозможных
путей из какой-то начальной в какую-то конечную вершину.
a*bc(ba*bc)*
aaabc
bc
aabc baaaaabc aaaaabc
Детерминированные и недетерминированные автоматы
Автомат детерминированный, если
1) у него только 1 начальная вершина,
2) нет ребер с отметкой пустого слова
(eps-переходов),
3) нет двух переходов по одной и той же
букве из одной и той же вершины.
Если автомат детерминированный, то с его помощью
для любого слова можно определить, принадлежит ли это
слово языку.
1. Устанавливаем автомат в начальное состояние.
2. Читаем первую букву слова. Если из состояния,
в котором находится автомат, нет перехода по этой букве,
то сразу говорим, что слово языку не принадлежит.
3. Переводим автомат в состояние, которое задается
переходом по данной букве.
4. Повторяем этот процесс до тех пор, пока не прочтем
слово до конца. Если мы остановились в конечной вершине,
то слово принадлежит языку, иначе нет.
Что делать, если автомат недетерминированный?
Будем использовать не 1 автомат, а несколько
однотипных автоматов (ансамбль автоматов) -- в любой
момент времени не больше, чем число состояний.
1. Создаем столько автоматов, сколько начальных
состояний.
2. Читаем очередную букву. Если какой-то автомат
не допускает перехода по этой букве, то удаляем его.
3. Если допускает несколько переходов по данной букве
(допустим, n переходов), то создаем дополнительно
n-1 автомат, переводим автоматы в соответствующие
состояния.
4. Если в нашем ансамбле есть 2 автомата в одном и
том же состоянии, то оставляем только 1 из них.
5. Цепочка принадлежит языку, если по окончанию ее
чтения хотя бы 1 из автоматов ансамбля находится
в конечном состоянии.
Мы рассмотрели алгоритм построения детерминированного
автомата, эквивалентного заданному недетерминированному.
A -- исходный недетерминированный автомат
B -- эквивалентный ему детерминированный.
Тогда число состояний автомата B <= 2^(число сост. A)
оценка экспоненциальная.
(a|b)* a (a|b) (a|b) ... (a|b)
aaabbabbba
aaabbbbbba переходит в состояние S
=
Подадим на вход любую цепочку длины 5, например, bbbbb
aaabbabbba bbbbb принадлежит языку
=
aaabbbbbba bbbbb не принадлежит языку
=
========================================================
Лемма о разрастании для автоматных языков (Pumping kemma --
лемма о накачке).
Пусть L -- автоматный язык. Тогда существует натуральное
число K такое, что если цепочка u принадлежит L и ее длина >= K,
то в любой подцепочке u длины >= K можно выделить фрагмент x
такой, что x можно повторить любое количество раз, и построенная
цепочка тоже будет принадлежать языку L.
u = s v h, где |v| >= K
Тогда v = pxq, |x| > 0 и для всякого m >= 1 цепочка
u = s p x^m q h тоже принадлежит языку L.
u = s v h, |v| > K
u = s pxq h
=> s pxxq h
s pxxxq h
s pxxxxq h
. . .
Пример применения этой леммы:
L = { a^n b^n, n >= 1 }
ab, aabb, aaabbb, ...
L не является автоматным.
Идея доказательства:
построим детерминированный КА для языка L. Возьмем
K = число состояний автомата + 1
Путь дважды проходит через некоторое состояние z.
a1 a2 a3 ... ai a_i+1 ... aj aj+1... an
s s
x = a_i+1...aj
Набор контрпримеров
L1 = { a^n b^n c^n } -- контекстно зависимый язык,
но не контекстно свободный
L2 = { a^n b^n } -- контекстно свободный язык, но не автоматный
S -> ab | aSb
aaaaaaaaaaaaaaaaaaabbbbbbbbbbbbbbbbbbbbbbb
Праволинейные языки: все правила грамматики имеют вид
A -> u, u -- слово из терминалов, может быть пустым
A -> uB, u -- слово из терминалов, B -- нетерминал
Леволинейная грамматика:
A -> u, u -- слово из терминалов, может быть пустым
A -> Bu, u -- слово из терминалов, B -- нетерминал
Теорема. Следующие 3 класса языков совпадают:
(1) автоматные языки;
(2) праволинейные языки;
(3) леволинейные языки.
(линейные языки A -> uBv)
Доказательство.
(1) => (2)
Рассмотрим ДКА, порождающий язык L. Построим праволинейную грамматику.
Нетерминалы грамматики соответствуют состояниям КА.
Начальному состоянию будет соответствовать начальный нетерминал S.
Если из состояния A есть переход в состояние B по букве a,
то в грамматику добавляем правило
A -> aB
Наконец, если состояние C является конечным, то добавляем правило
C -> eps
b*ab(ab*ab)*
Нетерминалы S1, S2, S3
Начальный нетерминал S1
Правила:
S1 -> a S2
S1 -> b S1
S2 -> b S3
S3 -> a S1
S3 -> eps
Обратно (2) => (1)
По праволинейной грамматике построим
КА, задающий тот же самый язык
1) могут быть правила вида
A -> a1 a2 ... ak B
Вводим дополнительные нетерминалы
A1, A2, A_k-1 и заменяем это правило на
на набор правил
A -> a1 A1
A1 -> a2 A2
. . .
A_k-3 -> a_k-2 A_k-2
A_k-2 -> a_k-1 A_k-1
A_k-1 -> ak B
Пример: правило
A ->abcB
заменяем на 3 правила
A -> a A1
A1 -> b A2
A2 -> c B
Если есть правило
A -> u, u -- слово из терминалов A -> a1 a2... ak
то заменяем его на набор правил
A -> a1 A1
A1 -> a2 A2
. . .
A_k-1 -> ak Ak
Ak -> eps
Пример:
A -> abc
заменяем на
A -> a A1
A1 -> b A2
A2 -> c A3
A3 -> eps
В результате правила будут иметь один из трех видов:
1) A -> B (цепное правило),
2) A -> aB,
3) A -> eps
Теперь построим граф НКА:
вершины -- это нетерминалы грамматики,
начальная вершина соответствует начальному нетерминалу,
если есть правило
A -> B
то из вершины A есть eps-переход в вершину B,
если есть правило
A -> aB
a
то есть переход A --> B,
если есть правило
A -> eps,
то вершина A -- конечная.
Докажем (1) => (3)
Автоматный язык можно задать леволинейной грамматикой
A -> Bu
S => Aa => Bba => Cdba => ... цепочка при выводе в леволинейной
грамматике наращивается справа налево. Соответственно,
будем строить конечный автомат, в котором выводам в леволинейной грамматике
будут сообветствовать пути от конечной к начальной вершине.
Пусть S -- начальный метасимвол грамматики.
Тогда для всех конечных вершин автомата B1, B2, ..., Bk
добавим правила
S -> B1
S -> B2
...
S -> Bk
Путь в автомате есть переход
a
A ---> B
Тогда добавим правило
B -> Aa
Для начальной вершины С автомата добавим правило
С -> eps
Пример: автомат, соотв. регулярному выражению
b*ab(ab*ab)*
S -> S3
S3 -> S2 b
S2 -> S1 a
S1 -> S1 b
S1 -> S3 a
S1 -> eps
Пример: выведем цепочку bbabaab
S => S3 => S2 b => S1 ab =>S3 aab =>
S2 baab => S1 abaab => S1 babaab =>
S1 bbabaab => bbabaab
Импликация (3) => (1)
Теорема Клини.
Классы автоматных и регулярных языков совпадают.
Определение регулярного языка и регулярного выражения.
1. Язык, состоящий из пустой цепочки, регулярен.
Рег. выражение: ()
2. Для всякой буквы a алфавита язык, состоящий из одноэлементной
цепочки из одной этой буквы, регулярен.
Рег. выражение: a
3. L1, L2 -- регулярные языки. Тогда
L1 L2 = { u v, u \in L1, v \in L2 } регулярен.
Рег. выражение: e1 e2
4. Объединение двух регулярных языков регулярно
Рег. выражение: (e1 | e2)
5. Итерация Клини реулярного языка регулярна.
L* = { u1 u2 ... uk, u_i \in L, k >= 0 }
Отметим, что eps \in L*
Рег. выражение: (e)*
Д-во теоремы Клини.
L -- регулярный язык => автоматный.
Индукция по построению языка (по рег. выражению).
Строим недетерминированный автомат с ровно одним начальным
и ровно одним конечным состоянием.
1) пустая цепочка
eps
(S) ---> (F)
2) одноэлементная цепочка
a
(S) ---> (F)
3) произведение языков
eps
(S1) --> ... -->(F1) ---> (S2) --> ... -->(F2)
(последовательное соединение)
4) объединение -- параллельное соединение
/ (S1) --> ... -->(F1)\
/ \
(S) (F)
\ /
\ (S2) --> ... -->(F2)/
5) итерация Клини
eps
+----------+
/ \
/ V
(S) --> ... -->(F)
^ /
\ /
+----------+
======================================================
Следующие классы языков совпадают.
1. Автоматные языки.
2. Праволинейные языки
A -> uB
A -> u
u -- терминальная цепочка
3. Леволинейные языки
A -> Bu
A -> u
u -- терминальная цепочка
4. Регулярные языки -- определяются с помощью построения,
1) L = { eps } -- регулярный () \( '(' "("
2) L = { a } -- регулярный a
3) объединение L1 и L2 регулярно (e1|e2)
4) произведение L1 и L2 регулярно e1 e2
5) итерация Клини L* регулярна (e)*
L* = { u1 u2... uk, ui \in L, k >= 0 }
eps \in L*
Теорема Клини
Классы автоматных и регулярных языков совпадают
Было доказано
Если L регулярный, то L автоматный
Нетривиальная часть теоремы Клини состоит в доказательстве обратного
включения: если язык L автоматный, то L регулярный.
Доказательство.
Перенумеруем вершины конечного автомата числами 1, 2, ..., n
Язык L(i, j, k) состоим из меток путей, начинающихся в
вершине i, заканчивающихся в вершине j,
а промежуточные вершины принадлежат
множеству {1, 2, ..., k}
L(7, 100, 3):
7, 2, 1, 3, 1, 2, 2, 100
Докажем, что языки L(i, j, k) регулярны.
Тогда L = объединение L(i, j, n) по всем парам (i, j),
где i -- начальная, j -- конечная вершина.
Докажем, что языки L(i, j, k) регулярны индукцией по k
Базис индукции k = 0
Объединение одноэлем. цепочек, соответствующих всем
ребрам из i в j
L(i, i, 0) содержит пустую цепочку
Шаг индукции
Пусть утверждение доказано для k < n
Докажем для k+1
Случай i != k+1, j != k+1
L(i, j, k+1) =
L(i, j, k) +
L(i, k+1, k) L(k+1, k+1, k)* L(k+1, j, k)
Случай i = k+1, j != k+1
L(k+1, j, k+1) =
L(k+1, j, k) +
L(k+1, k+1, k)* L(k+1, j, k)
Случай i != k+1, j = k+1
L(i, k+1, k+1) =
L(i, k+1, k) +
L(i, k+1, k) L(k+1, k+1, k)*
Случай i = k+1, j = k+1
L(k+1, k+1, k+1) = L(k+1, k+1, k)*
Теорема доказана
Теорема дает алгоритм построения регулярного выражения
по конечному автомату. Пример
a a ___
_ --> _ --> ---
-->|1| |2| ||3|| a(ba)*a (b(ba)*a)*
- <-- - <-- ___
b b ---
L = L(1, 3, 3)
L(1, 3, 3) = L(1,3,2) + L(1,3,2) L(3,3,2)* = L(1,3,2) L(3,3,2)*
L(1,3,2) = L(1,3,1) + L(1,2,1) L(2,2,1)* L(2,3,1)
L(1,3,1) -- пустое множество
L(1,3,2) = L(1,2,1) L(2,2,1)* L(2,3,1)
L(1,2,1) = a
L(2,2,1) = ba
L(2,3,1) = a
L(1,3,2) = a(ba)*a
L(3,3,2) = L(3,3,1) + L(3,2,1)L(2,2,1)*L(2,3,1) =
= L(3,2,1) L(2,2,1)* L(2,3,1)
L(3,2,1) = b
L(2,2,1) = ba
L(2,3,1) = a
L(3,3,2) = b(ba)*a
Ответ: L = L(1,3,2) L(3,3,2)* = a(ba)*a (b(ba)*a)*
Проблема звёздной высоты:
для данного языка минимум из звёздных высот всех регулярных
выражений.
(a|b)c -- высота 0
(ab|ba)* -- высота 1
(abc(ab|ba)*)*bc -- высота 2
Указать алгоритм вычисления звёздной высоты регулярного выражения
(автоматного языка).
==========================================================
Алгоритм 1: НКА => ДКА
Алгоритм 2: Рег. выражение => НКА
Алгоритм 3: НКА => рег. выражение
---------------------------------
Алгоритм 4: ДКА => Минимальный ДКА
Алгоритм 5: По двум ДКА можно проверить, изоморфны ли они
Минимальный конечный автомат -- автомат, задающий данный
автоматный язык с минимальным числом состояний.
Теорема. Для данного автоматного языка все минимальные
детерминированные конечные автоматы, задающие его, изоморфны.
Отсюда получаем алгорит проверки, задают ли два регулярных
выражения один и тот же язык. Применяем алгоритмы
2, 1, 4, 5
Рег. выражение => НКА => ДКА => Мин. ДКА => проверяем изоморфизм.
Алгоритмически разрешима проблема равенства языков или
эквивалентности рег. выражений.
Заметим, что проблема равенства контекстно свободных языков
алгоритмически неразрешима.
Построение минимального ДКА
1. Убираем все вершины, недостижимые из начальной.
2. Убираем все бесполезные вершины, из которых нет пути
ни в какую конечную вершину.
3. Две вершины эквивалентны, если множество меток путей из первой
вершины в конечные вершины совпадает с
множество меток путей из второй вершины в конечные вершины.
вершины i, j эквивалентны, если L_init(i) = L_init(j)
Это отношение эквивалентности. Фактор граф по этому
отношению эквивалентности будет минимальным детерминированным
автоматом, задающим данный язык.
Минимальный ДКА можно построить следующим образом.
Дан автоматный язык L, возьмем G -- ДКА без недостижимых
и бесполезных вершин.
Рассмотрим множество цепочек U, состоящее из всевозможных
начал слов из L
U = { u: существует v такое, что uv \in L }
Введем на множестве U отношение эквивалентности:
u1 эквивалентно u2, если множества продолжений
слов u1 и u2 совпадают.
V(u) = { v: uv \in L }
u1 эквивалентно u2, если V(u1) = V(u2)
|U/эквив| <= |G|
_ a __
u -> ua, если ua \in U
Определение корректно. Мы построили конечный автомат,
задающий данный язык.
Алгоритм построения минимального ДКА (он часто называется
каноническим автоматом, задающим автоматный язык).
Минимальный ДКА получается из любого ДКА без недостижимых
и бесполезных вершин склеиванием эквивалентных вершин.
Определяем разбиение вершин ДКА на классы вершин.
На шаге n в одном классе будут содержаться вершины, не различимые
путями длины <= n.
Шаг 0. Разбиваем все вершины вершины на 2 класса:
конечные вершины, не конечные вершины
. . .
Шаг n+1. На предыдущем шаге вершины разбиты на k классов,
в каждом из классов содержатся вершины, которые не
различаются путями длины n.
Делаем более мелкое разбиение:
две вершины u1, u2 из одного класса в смысле отношения
эквивалентности En не эквивалентны в смысле
E_n+1, если по какой-то букве a
a a
u1-->v1, u2-->v2, v1 не эквивалентно v2 в смысле En.
Окончание алгоритма -- когда наступает стабилизация,
En = E_n+1.
Пример:
a a ___
1 --> 2 --> ||3||
\ b\ ^
b\ / a
\> 4 --> ||5||
Шаг 0: {3, 5}, {1, 2, 4 }
Шаг 1: {1}, {2, 4}, {3, 5}
Шаг 2: {1}, {2, 4}, {3, 5}
======================================
Операции над языками
Практически любые опрерации с регулярными языками
не выводят нас за этот класс
1. Объединение +
2. Пересечение +
Можно построить автомат, задающий пересечение
автоматных языков:
G1 задает язык L1 G2 задает L1
G1 x G2 (Si, Tj) -- состояния
a a
Si --> Sk Tj --> Tl
a
(Si, Tj) --> (Sk, Tl)
3. Дополнение
1) достроим автомат до полного
(для каждой буквы и каждой вершиня есть переход из этой вершины
по этой букве);
2) объявим все конечные вершины не конечными, а все не конечные --
конечными.
4. Произведение L1 L2 -- последовательному соединению автоматов. +
5. Итерация Клини +
============================================================
В классе контекстно свободных языков
1. Объединение + S1
S2 => S -> S1 | S2
2. Пересечение -
Было доказано, что язык L = { a^n b^c c^n, n >= 1 }
не является КС-языком
L1 = { a^n b^n c^k, n, k >= 1 } aaaabbbbcc
L2 = { a^n b^k c^k, n, k >= 1 } aabbbbcccc
L = L1 пересечение L2
L1, L2 -- КС-языки
Грамматика для L1
S -> A C
A -> ab | aAb
C -> c | Cc
3. Дополнение -
Иначе, используя теорию множеств
L1 ^ L2 = дополнение (доп(L1) U доп(L2))
=======================================================
Удаление eps-правил
A -> eps
Можно удалить все такие правила, кроме, возможно, правила
S -> eps, S -- начальный нетерминал
Идея: как удалить правило A -> eps
B -> uAvAw
Удаляем правило A -> eps и при этом добавляем 3 правила
B -> uAvAw | uvAw | uAvw | uvw
Цепные правила:
A -> B
Это правило удаляем,
во всех правилах, где есть A в правой части, добавляем правила,
где какие-то буквы A заменены на B
C -> uAvAw
C -> uAvAw | uBvAw | uAvBw | uBvBw
Нормальная форма Хомского
A -> BC
A -> b
S -> eps
A -> aBcDe
A1 -> a
C1 -> c
E1 -> e
A -> A1 B C1 D E1
A -> BCDE
----------
A -> B A2
A2 -> C A3
A3 -> D E
============================================================
Задача разбора -- противоположна задаче вывода
S -> F $
F -> T | F + T | F - T
T -> M | T * M | T / M
M -> a | (F)
a + a*a/a - (a+a)*a
Выведем цепочку a + a * a $
Построим левый вывод
S => F $ => F + T $ => T + T $ => M + T $ => a + T $ => a + T * M $ =>
=> a + M * M $ => a + a * M $ => a + a * a $
В задаче разбора мы идем в другую сторону:
в начале нам дана терминальная цепочка, и мы хотим ее свернуть к начальному
нетерминалу, по пути восстановив весь вывод.
Есть 2 класса алгоритмов разбора:
1) нисходящий, или рекурсивный разбор, или LL(1)-разбор.
L (Left) -- просматриваем входную цепочку слева направо,
L (Left) -- строим левый вывод,
1 -- просматриваем входную цепочку на 1 символ вперед
a1 a2 a3 | a4 a5 ... an $
обработанная необработанная часть
часть
2) восходящий разбор (с помощью конечного автомата со стеком),
или LR(1)-разбор
L (Left) -- просматриваем входную цепочку слева направо,
R (Right) -- строим правый вывод,
1 -- просматриваем входную цепочку на 1 символ вперед
Оказывается, что класс LR(1)-языков шире, чем класс LL(1)-языков.
Грамматика допускает LL(1)-разбор => допускает LR(1)-разбор.
Грамматика
S -> F $
F -> T | F + T | F - T
T -> M | T * M | T / M
M -> a | (F)
допускает LR(1)-разбор, но не LL(1)-разбор.
В случае данного языка грамматику можно преобразовать так,
чтобы она допускала рекурсивный разбор, но при этом она
потеряет свою простоту и естественность.
Идея рекурсивного разбора
S -> F $
void processS() {
processF();
skip('$');
}
void processF() {
processF();
skip('+');
processT();
}
Грамматика обладает свойством LL(1) <=>
если есть несколько правил для одного нетерминала { r1, r2, ..., r_k },
то множества Director(r_i) != Director(r_j)
Что такое Director(r)?
Правило r имеет вид
A -> u
1) из u не выводится eps, тогда Director(r) = First(u) --
множество терминалов, с которых могут начинаться
цепочки, выводимые из u;
2) если из u выводится пустая цепочка, то
Director(r) = First(u) + Next(A)
B ->uAw
Next(A) = + Director(w)
Как преобразовать грамматику в рекурсивную?
A -> Aw1 | Aw2 | ... | Awk | u1 | u2 | ... | ul
слова u_i не начинаются с A
Что можно вывести?
A => Aw1 | A w3 w1 | A w2 w3 w1 | u1 w2 w3 w1
uwwwwwwwwwwwwww
A -> u1 T | u2 T | ... ul T T -- Tail
T -> eps | w1 T | w2 T... | wk T
Преобразуем грамматику
S -> F $
F -> T | F + T | F - T
T -> M | T * M | T / M
M -> a | (F)
к лево-рекурсивному виду
S -> F $
F -> T E E -- хвост формулы F
E -> eps | + T E | - T E
T -> M H H -- хвост терма
H -> eps | * M H | / M H
M -> a | (F)
<automaton>
<state name="1">
<initial value="true"/>
<final value="false">
<transfer>
<signal="a"/>
<destination="nameOfState"/>
</transfer>
<transfer>
<signal="b"/>
<destination="nameOfState2"/>
</transfer>
</state>
</automaton>
=================================
11 Dec 2020
Разбор (Parsing) -- задача, противоположная выводу.
В выводе мы начинаем с начального нетерминала грамматики,
заканчиваем терминальной цепочкой.
При разборе мы начинаем с терминальной цепочки и восстанавливаем
вывод в обратном порядке, заканчиваем начальным нетерминалом.
Мы рассмотрели рекурсивный разбор (LL(1)-разбор, строим
левые выводы). F -> F + T | T
F -> T E
E -> eps | + T E
Восходящий разбор, или разбор с помощью детерминированного
конечного автомата со стеком (с магазинной памятью), или
LR(1)-разбор (строим правые выводы). Языки, которые
допускают подобный разбор, называются детерминированными.
Детерминированные != однозначные, детерминированные языки --
это собственный подкласс однозначных языков.
Пример: язык палиндромов является однозначным,
но не является детерминированным.
S -> a | b | aa | bb | aSa | bSb
LL(1) < LR(1) < Однозначные языки < КС языки
Определим LR-процесс.
Состояние LR-процесса в любой момент определяется
1) стеком LR-процесса
2) аванцепочкой.
Стек LR-процесса -- это слово из терминалов и нетерминалов,
которое наращивается или сокращается с правого конца.
Аванцепочка состоит из терминалов
+------------
| AbcdFGeH <-- abcdabaacc
+------------
Состояние LR-процесса: стек и аванцепочка
+------------
| AbcdFGeH <-- abcdabaacc
+------------
Возможны 2 действия:
1) сдвиг (shift) -- символ из аванцепочки переносится в стек
+------------
| AbcdFGeH <-- abcdabaacc, сдвиг =>
+------------
+------------
| AbcdFGeHa <-- bcdabaacc
+------------
2) свертка по некоторому правилу (reduce). Пример
есть правило T -> GeHa
+------------
| AbcdFGeHa <-- bcdabaacc, свертку по правилу T -> GeHa =>
+------------
+------------
| AbcdFT <-- bcdabaacc
+------------
Начальное состояние LR-процесса: стек пуст, аванцепочка совпадает
с исходной цепочкой
LR-процесс успешный, если по окончанию аванцепочка пуста,
а в стеке лежит начальный метасимвол грамматики.
Предложение. Существует взаимно однозначное соответствие между
правыми выводами в грамматике и успешными LR-процессами.
S -> F $ a*a + (a+a)*a
F -> T | F + T
T -> M | T * M
M -> a | ( F )
Выведем a + a*a $
S => F $ => F + T $ => F + T*M $ => F + T*a $ => F + M*a $ => F + a*a $ =>
=> T + a*a $ => M + a*a $ => a + a*a $
LR-процесс
+--- +--- +---
| a + a*a $,сдвиг => |a + a*a $,свертка => |M + a*a $ свертка,
+--- +--- M ->a +--- T -> M
+--- +--- +---
|T + a*a $, свертка => |F + a*a $ сдвиг, сдвиг => |F+a *a $ свертка
+--- F -> T +--- +--- M -> a
+--- +--- +-----
|F+M *a $ свертка => |F+T *a $ сдвиг, сдвиг => |F+T*a $ свертка =>
+--- T -> M +--- +----- M -> a
+----- +--- +-- +---
|F+T*M $ свертка => |F+T $ свертка => |F $ сдвиг |F $ eps, свертка =>
+----- T -> T*M +--- F -> F+T +-- +--- S -> F $
+--
|S eps успешное завершение LR-процесса
+--
Проблема
В некоторых ситациях возможны несколько разных действий:
сдвиг либо свертка, или две свертки по разным правилам.
Если сделать неправильное действие, то можно потом не довести
LR-процесс до успешного завершения.
Для разрешения неоднозначностей строится конечный автомат.
В процессе восходящего разбора стек парсера параллелен стеку
LR-процесса. Стек парсера содержит номера состояний разбора
(их конечное число). Действие на каждом шаге определяется
по номеру состояния на вершине стека и по первому
символу аванцепочки. При сдвиге вычисляется номер состояния,
которое добавляется в стек разбора, по таблице разбора.
Строки таблицы занумерованы номерами состояний, а столбцы --
терминалами и нетерминалами грамматики.
| a | ( | ) | + | * | $ | S | F | T
---+---+---+---+---+---+---+---+---+------------------
5 |сдв|сдв| |св | | |сдв сдв сдв
| 7 | 11| |F->T | 10 3 5
Построение множества состояний LR(0)-разбора
(действие -- сдвиг или свертка, по какому правилу свертка,
определяется только но основе вершины стека разбора).
Определение 1
Ситуацией LR(0)-разбора называется правило грамматики
с отмеченной позицией в правой части.
F -> F + T
Этому правилу соответствуют 4 ситуации:
F -> _ F + T, F -> F _ + T, F -> F + _ T, F -> F + T_
Определение 2
Состоянием LR(0)-разбора называется конечное множество LR(0)-ситуаций.
Алгоритм построения множества состояний LR(0)-разбора.
Рассмотрим на примере грамматики арифметических формул
S -> F $ Не LR(0)-грамматика
F -> T | F + T
T -> M | T * M
M -> a | ( F )
0) S->_F$, 1) сдвиг F в 0 2) сдвиг T в 0 3) сдвиг M в 0 4) сдвиг a в 0
F->_T, F->_F+T, S->F_$, F->F_+T F->T_, T->T_*M T->M_ M->a_
T->_M, T->_T*M, конфликт сдв-св
M->_a, M->_(F)
5) сдвиг ( в 0 6) сдвиг $ в 1 7) сдвиг + в 1 8) сдвиг * в 2
M->(_F), S->F$_ F->F+_T, T->T*_M,
F->_T, F->_F+T, T->_M, T->_T*M M->_a, M->_(F)
T->_M, T->_T*M, M->_a, M->_(F)
M->_a, M->_(F)
9) сдвиг F в 5
M->(F_), F->F_+T
10) сдвиг T в 7 11) сдвиг ) в 9 12) сдвиг + в 9
F->F+T_, M->(F)_ F->F+_T
T->T_*M T->_M, T->_T*M,
конфликт M->_a, M->_(F)
сдвиг-свертка
Состояние допускает сдвиг, если есть ситуация с терминалом после символа подчеркивания.
Состояние допускает свертку по правилу A->u, если есть ситуация A->u_ сданным правилом
и позицией после конца правой части.
Есть конфликт сдвиг-свертка, если состояние допускает как сдвиг, так и свертку.
Есть конфликт свертка-свертка, если состояние допускает свертку по двум разным правилам.
Грамматика допускает LR(0)-разбор, если в построенном множестве LR(0)-состояний
нет конфликтов.
Таблица разбора | s = shift = сдвиг
| a | + | * | ( | ) | $ | S | F | T | M r = reduce = свертка
-----|----|---|---|---|---|---|---|---|---|--
0 |s 4 |err|err|s 5|err|err|ok |s1 |s2 |s3
1 | | | | | | | | | |
2 | | | | | | | | | |
3 | | | | | | | | | |
4 | | | | | | | | | |
5 | | | | | | | | | |
6 | | | | | | | | | |
7 | | | | | | | | | |
8 | | | | | | | | | |
9 | | | | | | | | | |
10 | | | | | | | | | |
11 | | | | | | | | | |
12 | | | | | | | | | |
+-- +--- +-- +---
|0 a + a |0 4 + a свертка по M->a |0 M+a, |0 3 +a,
+-- +--- +-- +---
+-- +--- +--- +---
| | a | | M
+-- +--- +--- +---
===============================================
18 Dec 2020
3
S -> F $ 2 8 3
F -> a | a F 2^2^3 2 = 2 != 4
Выводимы цепочки вида aaa...a$
Построим множество LR(0)-состояний разбор
Состояние -- множество LR(0)-ситуаций
LR(0)-ситуация -- правило грамматики с отмеченной позицией
в правой части. Примеры ситуаций:
S -> F_$, F -> _a, F -> a_F, F -> a F_
(всего 8 ситуаций в этой грамматике)
Построим множество возможных LR(0)-ситуаций для этой грамматики
0) S -> _F$, 1) S -> F_$ 2) F -> a_, F -> a_F,
F -> _a, F -> _aF F -> _a, F -> _aF
конфликт сдвиг-свертка
Грамматика не является LR(0)-грамматикой.
На самом деле, эта грамматика является LR(1)-грамматикой, т.е.
множество LR(1)-состояний конфликтов не содержит.
LR(1)-ситуация разбора -- это правило грамматики с отмеченной позицией
в правой части правила + указание множества
терминалов, которые могут идти за концом правой
части правила.
Пример:
F -> _a|{$, a}
LR(1)-состояние разбора -- это конечное множество LR(1)-ситуаций.
Алгоритм построения множества LR(1)-состояний проиллюстрируем на примере.
Грамматика:
S -> F $
F -> a
F -> a F
0) S -> _F$|{eps} 1) S -> F_$|{eps}
F -> _a|{$}, F -> _aF|{$}
2) F -> a_|{$}, F -> a_F|{$},
F -> _a|{$}, F -> _aF|{$}
Первая ситуация предписывает свертку, если первый символ аванцепочки -- $
третья и четвертая ситуации предписывают сдвиг, когда первый символ
аванцепочки -- a. Конфликт, таким образом, разрешается.
3) S -> F$_|{eps} 4) F -> aF_|{$}
================================================================
5) F -> a_|{$}, F -> a_F|{$}, это совпадает с состоянием 2
F -> _a|{$}, F -> _aF|{$} (не нужно)
================================================================
Вернемся к грамматике арифметических формул
S -> F $
F -> T | F + T
T -> M | T * M
M -> a | ( F )
Начнем выписывать LR(1)-состояния разбора
0) S -> _F$|{eps}
F -> _T|{$}, F -> _F+T|{$}
T -> _M|{$}, T -> _T*M|{$},
F -> _T|{+}, F -> _F+T|{+},
M -> _a|{$}, M -> _(F)|{$},
T -> _M|{*}, T -> _T*M|{*},
T -> _M|{+}, T -> _T*M|{+},
M -> _a|{*}, M -> _(F)|{*},
M -> _a|{+}, M -> _(F)|{+},
Объединяем множества терминалов в фигурных скобках:
0) S -> _F$|{eps}
F -> _T|{$, +}, F -> _F+T|{$, +},
T -> _M|{$, *, +} T -> _T*M|{$, *, +},
M -> _a|{$, *, +}, M -> _(F)|{$, *, +}
Делая сдвиг T, получаем состояние 2
2) F -> T_|{$, +} свертка при первом символе аванцепочки $ или +
T -> T_*M|{$, *, +} сдвиг при первом символе аванцепочки *
т.к. эти множества не пересекаются, то
конфликта нет.
Определение:
если в построенном множестве LR(1)-состояний нет конфликтов,
то грамматика обладает свойством LR(1) (допускает LR(1)-разбор).
Грамматики, которые допускают восходящий разбор на конечном детерминированном
автомате со стеком, называются детерминированными (не путать с
однозначными грамматиками!).
Предложение.
Если грамматика детерминированная, то она однозначная.
Обратное неверно: есть однозначные языки, не являющиеся детерминированными.
Пример: грамматика палиндромов в 2-буквенном алфавите.
abba я иду с мечем судия
race car
а роза упала на лапу азора
шалаш
я с вами дима вся
S -> F$
F -> eps | aFa | bFb
0) S -> _F$|{eps},
F -> _|{eps}, F -> _aFa|{eps}, F -> _bFb|{eps}
1) S -> F_$|{eps}
2) F -> a_Fa|{eps},
F -> _|{a}, F -> _aFa|{a}, F -> _bFb|{a}
Конфликт сдвиг-свертка:
ситуация F -> _|{a} предписывает свертку, если аванцепочка начинается
с a;
ситуация F -> _aFa|{a} предписывает сдвиг, если аванцепочка начинается
с a.
========================================================
a + a * a
(a + a) * a
a + (a * a)
double *a[10]; // == *(a[10]) массив указателей
double (*a)[10]; // == указатель на массив
int *f(double); // ф-ция от double, возвращающая указатель на int
int (*f)(double); // указатель на ф-цию от double, возвращающю int
declaration ->
base_type declarator_list ;
declarator_list ->
declarator | declarator_list , declarator
declarator ->
array | * declarator
array ->
variable | array [ dimension ] | ( declarator )
В С операция * имеет более низкий приоритет, чем
квадратная или круглая скобка.
Предложение
Класс LL(1) языков содержится в классе LR(1)-языков
Точнее, любая LL(1)-грамматика является LR(1)-грамматикой,
обратное неверно.