Формальные языки и грамматики, элементы теории компиляции
=========================================================
А.Пентус, М.Пентус
Математическая теория формальных языков
Это обзор, не отягощенный излишними подробностями доказательств.
LL(k) == LL(1)
А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции
Д.Грис. Классическая теория компиляторов
По сравнению с курсом М.Пентус, этот курс имеет более практическую
направленность. Мы рассматриваем в основном те части теории
формальных языков, которые применяются на практике
при написании компиляторов. Во второй половине курса мы
рассмотрим модельный компилятор языка, похожего на Python,
с динамической типизацией, но с синтаксисом, больше похожим на
C/C++.
===============================================================
Мы будем рассматривать формальные языки, заданные с помощью порождающих
грамматик (Хомский).
Язык развивается по пути упрощения.
Задание языка с помощью формальной грамматики.
Алфавит -- конечное множество символов, обзначается буквой Sigma.
Элементы Sigma обычно обозначают маленькими латинскими буквами
из начала латинского алфавита: a, b, c, d, e, ...
Элементы Sigma называют терминалами, или обычными символами.
Для задания грамматики мы дополнительно определяем конечное множество
N нетерминалов, или метасимволов. Метасимволы неформально
обозначают некоторые составные элементы цепочек языка.
|Sigma| < inf -- терминалы, или обычные символы { a, b, c, d, ... }
N -- нетерминалы, или метасимволы { A, B, C, ..., Z }
{ <группа подлежащего>,
<группа сказуемого>,
<обстоятельство>, ... }
N не пересекается с Sigma
В N есть начальный нетерминал, обычно обозначается через S ("Start" ?)
Любые цепочки из терминалов и нетерминалов обозначаются латинскими буквами
из конца алфавита: u, v, w, x, y, z, ...
Грамматика задается набором правил вывода.
Правила имеют вид
u --> v,
где u, v <- (Sigma U N)* M -- множество M* -- множество конечных
цепочек элементов из M,
включая пустую цепочку eps
При этом слово u должно содержать хотя бы один нетерминал.
Правило означает, что в процессе вывода фразы языка мы можем заменить
левую часть u правила на его его правую часть v.
В грамматике должно быть хотя бы одно правило с левой частью S
(начальный нетерминал).
Шаг вывода:
пусть есть цепочка вида xuy
применяем правило u --> v и преобразуем эту цепочку к
xvy
Цепочка t выводима из цепочки r, если t можно преобразовать в r
несколькими заменами по правилам грамматики.
Язык, заданный грамматикой -- это множество терминальных цепочек,
выводимых из начального метасимвола S грамматики.
Пример: плохая грамматик арифметических формул.
Sigma: { a, b, c, d, ..., z, +, -, *, /, (, ) }
N = { S }
Правила:
S -> a
S -> b
...
S -> z
S -> S+S
S -> S-S
S -> S*S
S -> S/S
S -> (S)
Несколько правил с одинаковой левой частью можно записать в одну строку,
используя знак перечисления |
S -> a | b | c | ... z
S -> S + S | S - S
S -> S*S | S/S
S -> (S)
Выведем цепочку (a + b)*c
S => S*S => (S)*S => (S+S)*S => (a+S)*S => (a+b)*S => (a+b)*c
Иерархия Хомского
Грамматики развиватся на классы
0) грамматики без ограничений. Класс языков получается очень большой, это все
рекурсивно перечислимые языки. Для этого класса алгоримически неразрешима
проблема принадлежности цепочки языку.
Пример грамматики класса 0.
L = { aaaa...a 100101 }
a^n запись n в двоичной системе
Грамматика для этого языка.
S -> BAa0E
B -> BAa | eps
Aa -> aA
A0 -> 0A
A1 -> 1A
AE -> CE
0C -> 1
1C -> C0
aC -> a1
E -> eps
Вывести цепочку
aaaaa101
S => BAa0E => BAaAa0E => BAaAaAa0E => BAaAaAaAa0E => BAaAaAaAaAa0E =>
=> AaAaAaAaAa0E =>... => AaAaAaAaa0AE => AaAaAaAaa0CE => AaAaAaAaa1E => ...
=> AaAaAaaa1AE => AaAaAaaa1CE => AaAaAaaaC0E => AaAaAaaa10E => ...
=> aaaaa101E => aaaaa101
1) Контекстно-зависимые грамматики, или просто контекстные грамматики.
Правила имеют вид
xAy --> xuy, где A <- N, |u| > 0 (неукорачивающие правила)
Слова x, y могут быть пустыми.
Пример контекстно зависимого языка:
L = { a^n b^n c^n, n > 0 }
abc, aabbcc, aaabbbccc, aaaabbbbcccc, ...
Выпишем грамматику этого языка
S -> ABRc | ABc
R -> ABRc | eps
BA -> AB
Bc -> bc
Bb -> bb
Ab -> ab
Aa -> aa
Вывод цепочки aaabbbccc
S => ABRc => ABABRcc => ABABABRccc => ABABABccc => ABAABBccc => ...
=> AAABBBccc => AAABBbccc => ... => AAAbbbccc => AAabbbccc =>
=> Aaabbbccc => aaabbbccc
Правило BA --> AB не имеет нужного вида. Однако его можно
заменить на 3 правила:
BA --> BR
BR --> AR
AR --> AB
Получаем вывод BA => BR => AR => AB
Таким образом, язык L = { a^n b^n c^n, n > 0 }
контекстно зависимый.
Иногда добавляется еще одно возможное правило
S -> eps при условии, что S не входит в правые части правил.
(Если S входит в правые части, то вводим нплохая грамматиковый начальный нетерминал
S' и правило
S' --> S
)
2) контекстно-свободные грамматики
Правила имеют вид
A --> u
где u -- любая цепочка, в том числе и пустая.
http://mech.math.msu.su/~vvb/
http://mech.math.msu.su/~vvb/FormLang/
===============================================================
29 Sep 2021
Было рассказано:
опредление формальной грамматики и языка, порожденного ей.
Sigma -- алфавит обычных символов (терминалов) Sigma = { a, b, c, ... }
N -- алфавит метасимволов (нетерминалов)
S <- N -- начальный нетерминал N = { A, B, ..., Z }
L -- подмножество в Sigma*
A* -- множество конечных цепочек из элементов A, включая пустую
цепочку eps.
Любые цепочки обозначаются латинскими буквами из конца алфавита
s, r, t, q, x, y, z <- (Sigma U N)*
Правила граммики имеют вид
u --> v
слово u можно заменить на v
u, v <- (N U Sigma)*
В слово входит хотя бы один нетерминал.
Вывод:
один шаг вывода -- замена в цепочке
x u y => x v y
(замена по правилу u -> v).
Язык L -- это множество терминальных цепочек,
выводимых из начального метасимвола S грамматики.
Отметим, что для языка L может не существовать алгоритма определения
принадлежности произвольнолй цепочки языку.
Иерархия Хомского
0) грамматики без ограничений. В этом классе порождаются все рекурсивно
перечислимые языки, существуют языки, для которых алгоритмически
неразрешима проблема принадлежности цепочки языку;
1) контекстно-зависимые грамматики
uAv --> uwv
A <- N, |w| > 0
Для контекстно-зависимых грамматик существует алгоритм проверки
принадлежности цепочки языку.
Пример контекстно-зависимого языка:
L = { a^n b^n c^n, n >= 1 }
abc, aabbcc, aaabbbccc, ...
Как мы увидим, это пример не контекстно-свободного языка;
2) контекстно-свободные грамматики. Правила имеют вид
A -> u
A -- нетерминал, u -- любая цепочка, u <- (Sigma U N)*
Пример 1: плохая грамматика арифметических формул
S -> a | b | c | ... z
S -> S + S | S - S
S -> S*S | S/S
S -> (S)
Пример: выведем цепочку a + b*c
S => S + S => a + S => a + S*S => a + b*S => a + b*c
Вывод в КС-грамматике называется левым, если замены всегда
применяются к самому левому нетерминалу, входящему в цепочку вывода.
Аналогично определяется правый вывод (к самому правому нетерминалу).
Предложение:
любая выводимая цепочка в контекстно-свободной грамматике
имеет как левый, так и правый вывод.
Синтаксическое дерево вывода:
S
/ | \
S + S
| /|\
a S * S
| |
b c
Грамматика называется однозначной, если любая выводимая цепочка
имеет
1) ровно один левый вывод;
2) ровно один правый вывод;
3) ровно одно синтаксическое дерево вывода.
Данная грамматика арифм. формул неоднозначная:
цепочка a + b*c имеет два разных дерева вывода.
Та же цепочка имеет и другое дерево вывода:
S
/ | \
S * S
/ | \ |
S + S с
| |
a b
Вопрос: можно ли написать однозначную грамматику для того же языка?
Ответ: да, конечно.
S --> F
F --> T | F + T | F - T
T --> M | T * M | T / M
M --> E | ( F )
E --> a | b | c | ... | z
Выведем цепочку a + b*c, используя правый вывод:
S => F => F + T => F + T * M => F + T * E => F + T * c =>
=> F + M * c => F + E * c => F + b * c => T + b * c =>
=> M + b * c => E + b * c => a + b * c
Дерево вывода: S
|
F
/ | \
F + T
| /|\
T T * M
| | |
M M E
| | |
E E c
| |
a b
Любой естественный язык неоднозначный.
Примеры неоднозначных фраз.
Рассмотрим элемент x идеала I, который был определен
в доказательстве теоремы 1.
А.С.Пушкин, из путешествий Евгения Онегина:
Брега Арагвы и Куры узрели русские шатры.
Иосиф Бродский, из цикла "Часть речи":
. . .
Там звучит "ганнибал" из худого мешка на стуле,
сильно пахнут подмышками брусья на физкультуре;
что до черной доски, от которой мороз по коже,
так и осталась черной. И сзади тоже.
Дребезжащий звонок серебристый иней
преобразил в кристалл.
Насчет параллельных линий
все оказалось правдой и в кость оделось;
неохота вставать. Никогда не хотелось.
Непонятно, кто кого преобразил в кристалл (звонок в иней или
иней в звонок, т.е. что яляется подлежащим и что дополнением).
. . .
Одичавшее сердце все еще бьется за два.
каждый охотник знает, где сидят фазаны, - в лужице
под лежачим.
За сегодняшним днем стоит неподвижно завтра,
как сказуемое за подлежащим.
. . .
Опишем набор простых фраз на русском языке с помощью КС-грамматики.
<предложение> --> <группа подлежащего> <группа сказуемого>
<группа подлежащего> --> <подлежащее> |
<определение> <группа подлежащего>
<группа сказуемого> --> <сказуемое> <обстоятельство>
<подлежащее> --> автомобиль | корабль | шар
<сказуемое> --> плывет | катится | летит | едет
<определение> --> белый | быстрый | воздушный
<обстоятельство> --> по дороге | по небу | по реке
белый белый воздушный корабль летит по небу
быстрый воздушный шар катится по реке
белый автомобить плывет по дороге
быстрый быстрый воздушный автомобиль летит по реке
шар плывет по небу
Борис Гребенщиков, сонет:
Таинственный бокал похож на крюк,
вокруг него рассыпаны алмазы,
не целовался я с тобой ни разу,
мой омерзительный безногий друг.
Похоже на калейдоскоп, встряхивая который, получаем, как узоры, новые
фразы, хоть и бессмысленные, но построенные в соответствии с грамматикой
русского языка (а в любой правильно построенной фразе всегда можно найти
какой-нибудь смысл).
Не успел рассказать:
способ доказательства того, что язык не является контекстно свободным.
Лемма о разрастании (pumping lemma, лемма о накачке).
Пусть L -- бесконечный КС-язык. Тогда существует число N такое, что,
если цепочка w принадлежит L и ее длина >= N, то
она представляется в виде:
w = u x v y h, |x| + |y| > 0
и для всякого целого числа k > 1 цепочка
u x^k v y^k h также принадлежит L
u xx v yy h
u xxx v yyy h
u xxxx v yyyy h
. . .
Причем длина |x v y| <= N
Следствие: язык L = { a^n b^n c^n } не является контекстно свободным.
Дома: 3 задачи
1) придумать однозначную КС-грамматику для языка L,
который состоит из слов в алфавите Sigma = { a, b }
имеющих одну и ту же степень по обеим буквам
L = { u <- {a, b}*: deg_a u = deg_b u }
2) придумать красивую неоднозначную фразу на русском (английском) языке;
3) доказать, что язык L = { a^n b^n c^n } не является контекстно свободным.
======================================================================
6 Oct 2021
Рассмотрим язык Дика, состоящий из всех правильных
расстановок круглых скобок:
Примеры цепочек языка:
(), (()()), ()()(()), ((()))
((a+b)*(c-d)), стираем переменные и знаки операций и
получаем (()())
Задача: выписать КС-грамматику этого языка.
Плохая (неоднозначная) грамматика
S -> () | SS | (S)
Грамматика неоднозначная, потому что цепочка ()()() имеет 2 разных
правых вывода или 2 разных дерева вывода.
S
/ \
S S
/ \ / \
S S ( )
/\ /\
( ) ( )
S
/ \
S S
/ \ / \
( ) S S
/ \ /\
( )( )
Как эту грамматику преобразовать к однозначной?
Введем понятие терма: цепочка, которую невозможно представить
в виде произведения (конкатенации) двух цепочек из нашего языка.
Однозначная грамматика:
S -> T | S T
T -> () | (S)
Цепочка ()()() имеет единственной дерево вывода:
S
/ \
S T
/ \ / \
S T ( )
| / \
T ( )
/ \
( )
В языке Дика может быть цепочка (()), но не ))((
L = { слова w в алфавите Sigma = {a, b} такие, что
число букв a в слове w равно числу букв b }
ab, bbaaba, aaabbbaababb
Идея решения: разбиваем слово в произведение термов.
Терм -- это цепочка, которая уже не представима в виде
произведения двух цепочек из L.
S -> T | S T
T -> Tplus | Tminus
Tplus -> a b | a Splus b
Splus -> Tplus | Splus Tplus
Tminus -> b a | b Sminus a
Sminus -> Tminus | Sminus Tminus
vladimir_borisen @ mail.ru
Лемма о разрастании (pumping lemma)
Пусть L -- контекстно-свободный язык. Тогда существует натуральное число K
такое, что
1) если w <- L имеет длину |w| >= K, то ее можно представить виде
w = u x v y h, причем подцепочки x и y можно синхронно повторять,
т.е. для любого числа i >= 1 цепочка
u x x x x... x v y y y y... y h также принадлежит языку L
повторение i раз
в других обозначениях
u x^i v y^i h <- L
2) при этом длина подцепочки |x v y| <= K.
Пример ее применения: покажем, что язык L = { a^n b^n c^n, n >= 1 }
не является контекстно свободным.
Доказательство: цепочка из L имеет вид
aaaaa...a bbbbb...b ccccc...c
Если язык L был бы контекстно-свободным, то по лемме о разрастании
в такой цепочке можно было бы выделить фрагменты x, y, которые
можно синхронно повторять, получая новые цепочки языка.
Но цепочка x не может содержать двух разных букв
(потому что иначе при повторении появляется буква a правее буквы b
или буква b правее буквы c).
Аналогично цепочка y не может содержать двух разных букв.
Значит, какая-то из трех букв не содержится ни в x, ни в y =>
при повторении x и y нарушится равенство степеней по трем буквам.
Идея доказательства леммы о разрастании.
Обозначим через d максимум из длин правых частей правил.
Пусть число нетерминалов грамматики |N| = s
Возьмем число K = d^(s+1) + 1
Рассмотрим цепочку из L длины >= K и для нее рассмотрим
минимальное по числу вершин дерево вывода. Тогда его высота h-1 > s.
Это означает, что в дереве вывода повторится на пути от корня
к терминальной вершине (длины h - 1) какой-нибудь нетерминал.
Иерархия Хомского
=================
Класс 3. Праволинейные грамматики = леволинейные грамматики =
= автоматные языки = регулярные языки.
Праволинейные языки задаются грамматиками с правилами вида
A -> u B, где A, B <- N, u <- Sigma*
или
A -> v, v <- Sigma*
Аналогично, леволинейные грамматики задаются правилами вида
A -> B u A, B <- N
A -> v u, v <- Sigma*
Пример:
S -> 0 | 1 | 2 |... 9 | 0 S | 1 S | ... 9 S
L = { 021345, 1, 35, 778, ... }
десятичные числа без знака
Отметим, что можно считать, что |u| = 1, а правила имеют вид
A -> d B d <- Sigma
B -> eps
поскольку правило вида, например,
A -> abcdE
можно заменить на 4 правила
A -> aF
F -> bH
H -> cI
I -> dE
A => aF => abH => abcI => abcdE
Если есть правило
A -> d
то заменяем его на два правила
A -> dB
B -> eps
Автоматные языки (основная тема следующей лекции)
=================================================
13 Oct 2021
Детерминированный конечный автомат -- это ориентированный граф,
у которого ребра помечены буквами основного алфавита.
При этом ровно одна вершина отмечена как начальная,
и некоторое непустое множество вершин отмечены как конечные
вершины.
Мы на рисунке отмечаем начальную вершину входящей (из ниоткуда)
стрелкой, а конечные вершины двойным кружком.
У детерминированного автомата не может быть
1) нескольких начальных вершин;
2) нескольких переходов из одной вершины, помеченных одной и
той же буквой:
a
(1) ---> (2)
\
a \
V
(3)
3) нет стрелок, помеченных пустой цепочкой eps.
Если отказаться от этих условий, то мы получим определение
недетерминированного конечного автомата.
Язык, задаваемый конечным автоматом (детерминированным или
недетерминированным) -- это множество цепочек, которые соответствуют
всевозможным путям из какой-то начальной в какую-то конечную
вершину.
Терминология.
Вершины графа конечного автомата называют состояниями КА,
ребра -- переходами.
Предложение.
Классы языков, задаваемых детерминированными и недетерминированными
конечными автоматами, совпадают.
Есть несложный алгоритм, который по недерминированному конечному
строит эквивалентный ему детерминированный конечный автомат,
задающий тот же самый язык.
Доказательство.
Как проверить, принадлежит ли цепочка языку, с помощью детерминированного
КА?
Установим автомат в начальное состояние (оно только одно).
Подадим на вход первый символ цепочки. Если есть переход, помеченный данным
символом, то переведем автомат в состояние, сооответствующее концу
этого ребра. Если нет перехода, то сразу считаем, что цепочка не принадлежит
языку. Продолжаем действовать аналогично, пока цепочка не будет прочитана
до конца. Если по окончанию автомат находится в конечном состоянии,
то цепочка принадлежит языку, в противном случае нет.
Как быть, если автомат недетерминированный?
Используем ансамбль однотипных автоматов, но в разных состояниях.
Начинаем с автоматов во всех начальных состояниях + состояний, достижимых
из начальных по epsilon-переходам.
Подаем этому ансамблю автоматов на вход первую букву цепочки.
Если у какого автомата из ансамбля нет перехода по этой букве, то выкидываем
его из ансамбля. Если, наоборот, есть несколько переходов в разные состояния,
то создаем несколько новых автоматов и переводим их в состояния, достижимые
по переходам, помеченным данной буквой, плюс еще и состояния, достижимые
по epsilon-переходам.
a
(1) ---> (2) ---> (5)
\ eps
a \
V
(3) ---> (4)
eps
a
(1) ---> (2), (5), (3), (4)
Если в ансамбле появилось несколько автоматов в одном и том же состоянии,
то оставляем только один из них.
Совокупное состояние ансамбля автоматов можно рассматривать как
состояние одного детерминированного автомата.
Состояния этого детерминированного автомата будут
подмножества множества состояний исходного недетерминированного
автомата.
Начальное состояние -- подмножество всех начальных состояний
исходного автомата + состояний, достижимых из начальных по eps-переходам.
Состояние конечное, если в нем есть хотя бы одно конечное состояние
исходного автомата.
Переходы определяются естественным (уже рассказанным) способом.
Для примера построим ДКА, эквивалентный конкретному НКА. Нс картинке:
(a|b)*a(a|b)
Состояния построенного ДКА -- подможества состояний
исходного НКА
Получаем экпоненциальную оценку
Пусть A0 -- исходный НКА, A1 -- эквивалентный ему ДКА, построенный
данным алгоритмом.
|A1| < 2^|A0|
Пример:
для недетерминированного конечного автомата с 11 состояниями
эквивалентный ему ДКА будет иметь не меньше чем 2^10 = 1024
различный состояний.
(a|b)*a(a|b)(a|b)...(a|b)
==================
повторение 9 раз
Язык состоит из цепочек, у которых на 10-м с конца месте стоит буква a.
**********a*********
=========
9 букв
Утверждение: какой бы ДКА, эквивалентный данному, мы бы не построили,
по разным словам длины 10 мы попадаем в разные состояния ДКА. Отсюда
число состояний ДКА >= 2^10 = 1024.
Доказательство:
пусть есть 2 слова
abaa******
abab******
которые различаются на 4-й букве.
Возьмем 2 однотипных автомата и подадим на вход первому
первое слово, на вход второму -- второе слово. Утверждается,
что они перейдут в разные состояния. Подадим обоим на вход
слово длины 3, например bbb.
Тогда первому автомату будет окончательно подано слово
abaa******bbb,
второму
abab******bbb
Поскольку в первом случае буква a находится на 10-м с конца месте,
первый автомат перейдет в конечное состояние; во втором случае на 10-м
с конца месте стоит буква b => второй автомат либо перейдет либо в не
в конечное состояние, либо вообще нет такого перехода. Следовательно,
они изначально находились в разных состояниях.
============================================================
20 Oct 2021
Было рассказано
Понятие формальной грамматики и языка, заданного грамматикой
Sigma -- алфавит терминалов { a, b, c, d, ... }
N -- нетерминалы { A, B, C, ..., Z }
S <- N -- начальный нетерминал
Любые цепочки s, r, u, v, z <- (Sigma U N)*
Правила:
u --> v, u содержит хотя бы один нетерминал
Язык L -- это множесто терминальных цепочек, выводимых из
начального нетерминала.
Вывод -- последовательная замена по правилам, левая часть заменяется на
правую.
Иерархия Хомского:
0) грамматики без ограничений (очень широкий класс языков -- все рекурсивно
перечислимые языки);
1) контекстно-зависимые языки
xAy --> xuy, |u| > 0
L = { a^n b^n c^n, n > 0 }
aaabbbccc
L контекстно зависимый
2) контестно-свободные языки
A --> u (включая случай u = eps)
Лемма о разрастании
L -- КС-свободный язык, то существует число K:
если цепочка w <- L, |w| >= K, то
w можно представить в виде
w = u x v y t
и для любого i > 1 цепочка
u x^i v y^i t также принадлежит языку
u xx v yy t
u xxx v yyy t
. . .
Лемма позволяет доказать, что конкретный язык не является контектсно
свободным. В частности, что L = { a^n b^n c^n } не КС.
Также L2 = { u u , u <- {a, b}* } тоже не является КС-языком.
3) праволинейные грамматики, леволинейные грамматики,
автоматные языки
Праволинейная грамматика:
правила имеют вид
A --> u B, где u -- слово только из терминалов, B -- нетерминал
или
A --> u
Леволинейная грамматика
правила имеют вид
A --> B u, где u -- слово только из терминалов, B -- нетерминал
или
A --> u
Праволинейные языки
Любую праволинейную грамматику можно преобразовать так, что все
правила имею вид либо
A -> a B, a <- Sigma, B <- N
A -> eps
Это так, потому что правило
A -> x1 x2 ... xn B
можно заменить серией правил
A ->x1 A1
A1 -> x2 A2
. . .
A_n-2 -> x_n-1 A_n-1
A_n-1 -> x_n B
Правило
A -> a
заменяем на
A -> a A1
A1 -> eps
Автоматные языки
Был рассмотрен алгоритм построения детерминированного конечного
автомата, эквивалентного данному недетерминированному.
Оценка числа состояний ДКА экспоненциальная от чмсла состояний
исходного НКА.
Классы автоматных языков, порождаемых детерминированными и
недетерминированными КА, совпадают.
Докажем совпадение следующих классов языков:
1) языки, заданные праволинейными грамматиками;
2) атоматные языки;
3) языки, заданные леволинейными грамматиками.
(1) <=> (2)
По правиолинейной грамматике построим конечный автомат.
Пронумеруем все состояния автомата нетерминалами грамматики.
Начальному нетерминалу соответствует начальное состояние автомата.
Если есть правило
A -> a B,
то в автомате есть переход из состояния A в состояние B по букве a
a
A -----> B
Если есть правило
A -> eps
то вершина A автомата конечное.
(2) <=> (3)
A -> B a
A -> eps
Лемма о разрастании для автоматных языков.
Пусть L -- атоматный язык. Тогда существует K такое, что,
если цепочка w <- L и |w| >= K, то w представима в виде
w = u x v, где |x| > 0, |x| <= K и для всякого i >= 1
цепочка
u x^i v также принадлежит L
u xx v <- L
u xxx v <- L
u xxxx v <- L
. . .
Пример: язык L = { a^n b^n, n >= 1 } не является автоматным.
ab
aabb
aaabbb
aaaabbbb
. . .
S --> ab | aSb
контекстно-зависимые языки > контекстно свободные языки > автоматные языки
Теорема Клини о совпадении классов автоматных и регулярных языков
Определение регулярного языка
Укажем операции, позволяющие строить новые регулярные языки из
уже построенных, и одновременно укажем, как строится регулярное
выражение, задающее регулярный язык.
1) язык, состоящий только из пустой цепочки, регулярен
регулярное выражение: ()
скобка -- это специальный символ, если мы хотим записать скобку
как обычную буквы, то мы ее экранируем \(
2) язык, состоящий из одноэлементной цепочки для любой буквы "a" алфавита,
регулярен
регулярное выражение: a
3) объединение двух регулярных языков регулярно
регулярное выражение: (e1 | e2)
4) произведение двух регулярных языков регулярно
L1 L2 = { u v, u <- L1, v <- L2 }
регулярное выражение: e1 e2
5) итерация Клини регулярного языка регулярна
L* = { u1 u2 u3 ... u_n, u_i <- L, n >= 0 }
eps <- L*
регулярное выражение: (e)*
Пример: вещественная константа с фиксированной точкой языка C
0.1 -1.511 +33. .57
((+|-)|())( (0|1|2...|9)(0|1|2...|9)*.(0|1|2...9)* |
(0|1|2...|9)*.((0|1|2...|9)(0|1|2...|9)* )
(\+|\-)? ( ([0-9][0-9]*\.[0-9]*) | [0-9]*\.[0-9][0-9]* )
Теорема Клини
Классы автоматных и регулярных языков совпадают.
Причем теорема конструктивная: по регулярному выражению можно
построить КА и, обратно, по КА можно выписать регулярное выражение,
задающее тот же самый язык (в теореме Клини приводятся
соответствующие алгоритмы).
==================================================
27 Oct 2021
В иерархии Хомского мы остановились на
классе праволинейных грамматик.
Было доказано, что совпадают 3 класса языков:
1) праволинейные языки
A --> uB
A --> v, u, v <- Sigma*, A, B <- N A --> vF
F --> eps
можно уточнить правила:
A --> aB
A --> eps
2) леволинейные языки
A --> Ba
A --> eps
3) автоматные языки.
Важное определение: класс регулярных языков.
1. L = { eps } регулярен
Регулярное выражение: () обычная скобка как буква -- \(
2. L = { a } регулярен
Регулярное выражение: a
3. L1, L2 регулярны => их объединение регулярно
Регулярное выражение: (e1 | e2)
4. L1, L2 регулярны => их произведение регулярно
L1 L2 = { u v, u <- L1, v <- L2 }
Регулярное выражение: (e1 e2)
5. Итерация Клини регулярного языка регулярна
L* = { u1 u2 ... u_k, k >= 0, u_i <- L }
eps <- L*
Регулярное выражение: (e)*
Теорема Клини
Классы автоматных и регулярных языков совпадают.
Примеры регулярных выражений:
имя переменной в языке C -- начинается с буквы или знака подчеркивания _
дальше идет последовательность букв (включая _) и цифр
любой длины.
(A|B|...|Z|a|b|...|z|_)(A|B|...|Z|a|b|...|z|_|0|1|...|9)*
Расширенные регулярные выражения: можно указать диапазон символов,
используя квадратные скобки
[A-Za-z_][A-Za-z_0-9]*
В Unix имеется утилита grep для поиска регулярных выражений
в текстовых файлах.
Еще пример: написать регулярное выражение, которое задает
вещественные константы языка C.
Проблема:
константа вещественная, если она либо содержит десятичную точку,
либо порядок.
0.5, 1., .125, 1.75e+6, 2e10, .5E-8
(([0-9]+\.[0-9]* | [0-9]*\.[0-9]+)((e|E)(\+|\-)?[0-9]+)?) |
([0-9]+((e|E)(\+|\-)?[0-9]+))
e+ == (ee*)
e? == (()|e)
Регулярные выражения удобнее для человека, т.к. они записываются
в виде обычного текста. Конечные автоматы (ориентированные графы)
удобнее для компьютера, потому что интерпретатор КА легко пишется
в виде программы.
Доказательство теоремы Клини.
1. L -- регулярный язык ==> L -- автоматный язык.
(Более-менее тривиальное утверждение.)
Индукция по построению языка L.
Будем строить недетерминированный конечный автомат
с ровно одним начальным и ровно одним конечным состоянием.
eps
1) Пустая цепочка S ---> F
a
2) Однобуквенная цепочка S ---> F
3) Объединение двух языков L1 U L2 -- параллельное
соединение двух автоматов
eps eps
/ S1 --> ... --> F1 \
S F
\ S1 --> ... --> F2 /
eps eps
4) Произведение языков L1 L2 -- последовательное
слединение двух автоматов
eps
S1 --> ... --> F1 --> S1 --> ... --> F2
5) Итерация Клини
eps
+-------------+
| |
| V
S --> ... --> F
^ |
| |
+-------------+
eps
Нетривиальная часть Теоремы Клини состоит в доказательстве
обратной импликации.
L -- автоматный язык => L регулярен.
Для доказательства введем обозначение
k
L -- это язык, состоящий из меток путей, ведущих из
i,j вершины i в вершину j, причем все промежуточные
вершины пути принадлежат множеству
{ 1, 2, ..., k }
3
L 10,3,2,1,2,1,2,1,2,3,2,3,1,2,20
10, 20
Тогда L есть объединение множеств L_{i,j}^n для всех пар (i, j),
где i -- начальная вершина, j -- конечная вершина, n -- число вершин.
Достаточно доказать, что любой язык вида
k
L
i,j
регулярен. Доказательство ведется индукцией по числу k.
При k = 0 этот язык состоит из меток ребер из i-й в j-ю вершину.
Пусть доказано для k. Докажем регулярность языка L_{i,j}^k+1
Надо рассмотреть 3 случая.
1) i != k+1, j != k+1
Тогда любой путь из i в j либо вообще не проходит через вершину k+1,
т.е. принадлежит множеству
k
L
i,j
либо хотя бы один раз входит в вершину k+1:
k+1 k k k k
L = L | L (L )* L
i,j i,j i,k+1 k+1,k+1 k+1,j
2) i = k+1
k k k
L | (L )* L
i,j i,i i,j
3) j = k+1 (а также i = k+1, j = k+1) -- аналогично.
Теорема доказана.
Замечание.
Доказательство конструктивно, оно позволяет
1) по регулярному выражения построить КА,
2) обратно, по КА построить регулярное выражение.
При этом регулярное выражение, построенное по конечному автомату,
зависит от нумерации вершин КА, т.е. всего можно построить n!
эквивалентных регулярных выражений.
Пример: построить регулярное выражение для конкретного конечного автомата:
a a
+-+ ---> +-+ ---> +====+
-->|1| |2| || 3 || a(ba)*a(b(ba)*a)*
+-+ <--- +-+ <--- +====+
b b
Исполняем алгоритм из доказательства теоремы Клини.
3
L = L
1, 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) = empty
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, 3, 1) = empty
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)*
Задачи, которые засчитываются как экзамен
1. Построить по недетерминированному конечному автомату
эквивалентный ему детерминированный конечный автомат.
2. Теорема Клини: дан конечный автомат. Построить регулярное
выражением, задающее тот же самый язык.
2'. Дано регулярное выражение. Построить по нему недетерминированный
конечный автомат.
3. Дан детерминированный конечный автомат. Построить эквивалентный
ему минимальный (по числу состояний) детерминированный конечный
автомат.
Теорема. Для данного автоматного языка минимальный
детерминированный конечный автомат определен однозначно
с точностью до изоморфизма.
4. Написать алгоритм, который определяет, изоморфны ли
два детерминированных конечных автомата.a(ba)*a(b(ba)*a)*
Отсюда вытекает алгоритм проверки, эквивалентны ли два регулярных
выражения.
По регулрному выражению строим недерминированный конечный автомат,
по НКА строим детерминированный конечный автомат, по ДКА
строим минимальный ДКА, окончательно проверяем изоморфизм
двух ДКА.
vladimir_borisen@mail.ru
Subject: Формальные языки
Минимальные детерминированные коечные автоматы
Пусть G -- детерминированный конечный автомат.
Удалим из него
1) все вершины, недостижимые из начальной, и все ребра,
инцидентные им;
2) все бесполезные вершины, т.е. вершины, из которых нет пути
в какую-нибудь конечную вершину.
Язык при этом не изменится.
На множестве оставшихся вершин введем отношение эквивалентности.
v1 ~ v2, если два языка, которые получаются, если объявить
вершину v1 или v2 начальной, совпадают.
L(v1) = G(init v1)
L(v2) = G(init v2) v1 ~ v2 <===> L(v1) = L(v2)
def
Утверждение
Если склеить эквивалентные вершины (рассмотреть фактор-граф по этому
отношению эквивалентности), то мы снова получим детерминированный
конечный автомат, эквивалентный исходному.
v1 ~ v2 => v1*a ~ v2*a
поскольку, если v1*a не эквивалентно v2*a, то есть цепочка u из букв Sigma,
такая, что (v1*a)*u -- конечная вершина, и либо пути u из v2*a не существует,
либо (v2*a)*u -- не конечная вершина. Но тогда цепочка a*u различает
и исходные вершины v1 и v2.
v1*(a*u) и v2*(a*u) различаются.
v1 не эквивалентна v2 <=> когда существует различающая их цепочка u.
По этой цепочке мы переходим из одной вершины в конечное состояние,
а из другой не переходим в конечное состояние
(т.е. либо переходим в неконечное состояние, либо вообще пути по
этой цепочке нет).
После отождествления эквивалентных вершин все вершины фактор-автомата
будут не эквивалентны (т.е. каждая пара вершин будет различаться некоторой
цепочкой).
Рассмотрим конструкцию, которая по автоматному языку L строит
детерминированный конечный автомат G.
Рассмотрим множество всех слов в данном алфавите и в нем
подмножество слов, состоящих из всевозможных начал цепочек из L
U = { u: существует v такая, что uv <- L }
Цепочку v назовем продолжением цепочки u. На множестве U введем отношение
эквивалентности:
u1, u2 <- U
u1 ~ u2 <===> множество продолжений цепочки u1 совпадает
def с множеством продолжений цепочки u2
W -- U/~ фактор-множество U по отношению эквивалентности ~
Его элементами являются классы начал цепочек из L,
все элементы одного класса имеют одинаковое множество
продолжений.
Мы построили состояния автомата. Начальное состояние -- это класс
эквивалентности пустого слова. Конечное состояние -- это класс, в котором
есть слово с пустым продолжением, т.е. слово, принадлежащее L (значит,
и все слова в этом классе принадлежат L).
Осталось определить переходы.
Из вершины u по букве a есть переход в вершину ua
a
[u] ---> [ua], если цепочка ua является началом
некоторого слова из L
В противном перехода из вершины u по букве a нет.
Данный граф задает язык L. Язык автоматный, если |W| < infinity.
Пусть L -- автоматный язык, задаваемый автоматом G.
Тогда множество W конечно, поскольку,
если две цепочки u1 и u2 ведут из начального состояния автомата G
в одну и ту же вершину, то u1 ~ u2 =>
число классов эквивалентности
W не больше, чем число вершин автомата, задающего L.
Очевидно, что, если склеить эквивалентные вершины исходного автомата,
то мы получим автомат W, постороенный по началам слов языка. Он минимальный,
поскольку любые два слова из разных классов W различаются продолжениями =>
в любом конечном автомате, задающем L, эти слова приведут в разные вершины =>
число вершин любого автомата, задающего L, не меньше чем |W|.
Алгоритм построения минимального детерминированного конечного автомата
по данному детерминированному конечному автомату G.
1. Избавимся от недостижимых вершин.
2. Избавимся от бесполезных вершин.
3. Повторяем итеративно следующий процесс.
На каждом шаге имеем разбиение E_i множества вершин автомата на классы.
E_i+1 будет состоять из подклассов разбиения E_i (то есть будет более
мелким).
На нулевом шаге разбиение E_0 состоит из двух классов:
1) { все конечные вершины автомата G }
2) { все не конечные вершины }
Классы в разбиении E_0 различаются цепочками нулевой длины.
Очередная итерация:
мы можем разбить какой-либо класс разбиения E_i на несколько подклассов.
Две вершины v1 и v2 из c <- E_i не эквивалентны, если есть буква a:
v1*a и v2*a либо принадлежат разным классам разбиения E_i,
либо в одном случае есть переход по букве a, а в другом нет.
Алгоритм заканчивается, когда наступает стабилизация:
E_i+1 = E_i.
Тогда все классы разбиения E_i состоят из эквивалентных элементов
(в смысле продолжений), а вершины из разных не эквивалентны.
E_i -- это классы, элементы которых различаются цепочками
длины не больше i.
Пример:
конечный автомат
a
2 ---> 4 конечное
a/ b\ /
начальное 1 \
b\ b/ V
3 ---> 5 конечное
a
1) E_0 = { { 4, 5 }, {1, 2, 3} }
2) E_1 = { {4, 5}, {1}, {2, 3} }
3) E_2 = { {4, 5}, {1}, {2, 3} } -- стабилизация.
Получаем минимальный автомат с тремя состояниями:
{4, 5} -- конечная вершина
{1} -- начальная вершина
{2, 3}
a a
{1} ---> {2, 3} --> {4, 5}
initial ---> --> final
b b
Минимальный детерминированный КА для регулярного языка
часто называют каноническим автоматом. Это инвариант языка.
Открытый вопрос:
что будет, если рассматривать недетерминированные конечные автоматы?
Дома: придумайте пример языка, которые задается двумя НКА, каждый из
них с минимальным числом вершин, но автоматы не изоморфны.
Вопрос: какой недетерминированный конечный автомат может служить
аналогом канонического детерминированного конечного автомата (минимального
по числу состояний)? Б.Мельников в совей книге "Недетерминированные
конечные автоматы" приводит конструкцию базисного НК автомата.
Он утверждает, что этот автомат позволяет вычислить звездную высоту
регулярного языка.
Звездная высота выражения a(ba)*a(b(ba)*a)* равна 2.
Если выражение e имеет высоту n, то (e)* имеет высоту n+1.
Звездная высота сложного выражения определяется индукцией по
его построению. Итерация Клини повышает звездную высоту на 1,
остальные операции не изменяют ее.
Известная проблема: построить алгоритм вычисления звездной высоты
регулярного выражения (или конечного автомата, или просто регулярного языка).
Для любого n можно привести регулярное выражение, задающего язык с высотой
не меньше чем n.
((ab)*)* = (ab)*
Мельников: достаточно взять базисный НКА, для него выписать все n!
выражений Клини и среди них взять выражение минимальной высоты.
================================
10 Nov 2021
Операции над формальными языками
1. Автоматные (или регулярные) языки.
В этом классе возможны все теоретико-множественные операции над
языками.
-- Объединение двух автоматных (регулярных) языков
яляется автоматным языком L1 U L2
Регулярное выражение (e1 | e2) задает объединение двух
регулярных языков.
Для построения конечного автомата надо просто добавить новую
начальную вершину и 2 eps-перехода из нее в начальные вершины
обоих автоматов.
-- Дополнение к автоматному языку является автоматным языком.
Доказательство
1. Рассмотрим детерминированный КА, задающий данный язык.
Достроим его до полного автомата.
2. В достроенном полном автомате назовем вершины конечными,
если они не яляются конечными в исходном автомате, и, наоборот,
конечные вершины исходного автоматат перестают быть конечными.
Этот автомат задает дополнение исходного языка.
-- Пересечение двух автоматных языков будет тоже автоматным языком.
Для этого используется конструкция произведения двух автоматов.
Пусть есть два автоматных языка L1 и L2, которые задаются
автоматами G1 и G2. Можно считать, что G1 и G2 -- полные автоматы.
Тогда пересечение L1 и L2 задается произведением конечных автоматов
G1 x G2
Состояния G1 x G2 = { (x1, x2), x1 -- состояние G1, x2 -- состояние G2 }
Начальное состояние: (s1, s2), s_i -- нач. состояние G_i
Конечные состояния: { (f1, f2), f1 -- конечное состояние G1,
f2 -- конечное состояние G2 }
Переходы: a
(x1, x2) ----> (y1, y2),
где x1 ---> y1 в автомате G1,
a
x2 ---> y2 в автомате G2
a
Число состояний G1 x G2 равно n*m, где n = |G1|, m = |G2|
-- произведение двух автоматных языков является автоматным
L1 L2 = { u v, u <- L1, v <- L2 }
e1 e2
Соответствует последовательному соединению автоматов.
-- итерация Клини автоматного языка является автоматным языком.
С контекстно-свободными языками ситуация более сложная.
1. Объединение двух КС языков есть КС язык.
L1 задается грамматикой G1 с начальным нетерминалом S1
L2 задается грамматикой G2 с начальным нетерминалом S2
считаем, что метасимволы этих грамматик различны.
Тогда грамматика G, которая состоит из всех правил G1 и G1,
плюс дополнительные 2 правила
S -> S1 | S2
задает язык L1 U L2.
2. Произведение КС языков есть КС язык.
L1 L2 = { u v, u <- L1, v <- L2 }
S -> S1 S2
3. Но пересечение КС языков не обязательно является КС языком.
Контрпример L = { a^n b^n c^n, n >= 1 }
aaaabbbbcccc
u x v y z
u xx v yy z
u xxx v yyy z
. . .
Но L можно представить как пересение двух КС языков:
L1 = { a^n b^n c^k, n, k >= 1 }
L2 = { a^k b^n c^n, n, k >= 1 }
L1, L2 -- это КС языки
M = { a^n b^n } контекстно свободный
S -> a b | a S b
N = { c^k, k >= 1 } контекстно свободный
L1 = M N
L = пересечение(L1, L2)
4. Следовательно, также и дополнение к КС языку может не быть
КС языком.
Пересечение(A, B) = дополнение(дополнение(A) U дополнение(B))
Конкретный пример, когда дополнение к контекстно свободному языку не
является КС языком.
L = { a^n b^n c^n, n >= 1 } не КС язык
но дополнение к L -- это КС язык.
Почему?
Дополнение состоит, во-первых, из всех цепочек, которые не имеют
вид
a^n b^k c^l aaaa bbbbbb cc
поскольку все цепочки такого вида образуют автоматный язык, значит,
и дополнение к множесту таких цепочек -- тоже автоматный язык.
Теперь рассмотрим цепочки такого вида
M = { a^n b^k c^l, где либо n != k, либо k != l }
Но M можно представить как объединение двух множеств:
M1 = { a^n b^k c^l, n != k } aaa bbbbbb cccccc
M2 = { a^n b^k c^l, k != l } aaa bbb cccccccc
Достаточно показать, что M1 -- КС язык и M2 -- КС язык
M1 = M1+ C U M1- C
C = { c^l, l >= 1 }
M1+ = { a^n b^k, n < k } = { a^n b^n } B B = { b^s, s > 0 }
M1- = { a^n b^k, n > k } = A { a^k b^k } A = { a^s, s > 0 }
Операции пересечения двух языков и дополнения к языку могут вывести нас
за пределы класса контекстно свободных языков.
Положительный результат:
однако пересечение контекстно свободного языка с автоматным языком
является контекстно свободным языком.
Мы докажем это утверждение на следующей лекции, когда мы также рассмотрим
операции с контекстно свободными грамматиками:
1) избавление от цепных правил
A --> B, A, B <- N
2) избавление от eps-правил
A --> eps
(за исключением, возможно, одного правила S --> eps,
где S -- начальный метасимвол).
3) нормальную форму Хомского (квадратичные грамматики)
S --> eps
A --> BC, B, C <- N
A --> a a <- Sigma
===================================================
Махирев
17 Nov 2021
Операции над автоматными языками оставляют нас в классе автоматных
языков (объединение, пересечение, произведение, дополнение, итерация Клини).
Для контекстно-свободных языков это не выполняется для
пересечения и дополнения.
Теорема: пересечение контекстно-свободного языка и автоматного
языка будет констекстно-свободным языком (докажем в следующий раз).
Некоторые операции над контекстно-свободными грамматиками.
1. Можно считать, что начальный метасимвол грамматики S не встречается
в правых частях правил. Иначе добавим новый начальный символ
S' <- N и правило
S' -> S
2. Избавление от eps-правил, т.е. правил вида
A -> eps (пустая цепочка)
Предложение 1
В КС грамматике можно избавиться от всех правил вида
A -> eps
где A != S (A -- не начальный метасимвол грамматики).
Язык содержит пустую цепочку тогда и только тогда, когда после этого
преобразования грамматики в ней останется правило
S -> eps
Доказательство:
Сначала избавимся от S в правых частях правил.
Пусть есть правило A -> eps
Пусть в грамматике есть правило
B -> xAy x, y <- (Sigma U N)*
но при этом нет правила
B -> xy
Тогда добавим правило
B -> xy
Повторяем эту процедуру до тех пор, пока для каждого правила вида
B -> xAy
будет также и правило
B -> xy
После этого можно будет выкинуть все правила вида
A -> eps.
Предложение 1
В КС-грамматике можно избавиться от цепных правил, т.е. правил вида
A -> B, A, B <- N
Доказательство.
Пусть есть правила
A -> B
B -> u
но нет правила
A -> u
Тогда добавляем его.
Повторяем эту процедуру до тех пор, пока не будет выполняться
это условие:
если есть правила
A -> B
B -> u
то есть и правило
A -> u
После этого можно выкинуть все правила вида
A -> B
Приведение любой грамматики к некоторому каноническому виду
Наиболее известна нормальная форма Хомского контекстно-свободной
грамматики (ее также называют квадратичной грамматикой).
Теорема.
Любую КС грамматику можно преобразовать так, что правила имеют один из
трех видов:
1) S -> eps, S -- начальный метасимвол;
2) A -> BC, A, B, C <- N;
3) A -> a a <- Sigma
Доказательство
1) убираем начальный метасимвол из правых частей правил;
2) для каждого терминала a <- Sigma добавляем новый нетерминал F_a <- N
и правило
F_a -> a
3) если в правой части правила есть терминалы, то заменяем их
на соответствующие нетерминалы вида F_a
Например, правилo
A -> aBcDe заменяем на правило
A -> F_a B F_c D F_e
4) избавляемся от eps-правил;
5) правила с правой частью длины, большей 2, заменяем на последовательность
правил с правой частью длины 2, вводя новые нетерминалы. Например,
A -> BCDE
заменяем на
A -> BH
H -> CT
T -> DE
6) избавляемся от цепных правил;
7) избавляемся от бесполезных символов и правил.
(Символ бесполезный, если из него не выводятся терминальные цепочки).
Пример: язык палиндромов.
S -> a | b | aSa | bSb | eps Например, racecar, шалаш,
я с вами дима вся
1. S' -> S
S -> a | b | aSa | bSb | eps
2. S' -> S
A -> a
B -> b
S -> A | B | ASA | BSB | eps
3. Избавление от eps-правил
S' -> eps
S' -> S
A -> a
B -> b
S -> A | B | ASA | BSB
S -> AA | BB
4. Избавляемся от правил с правой частью длины > 2.
S' -> eps
S' -> S
A -> a
B -> b
S -> A | B
S -> AA | BB
Вместо правила S -> ASA используем правила
S -> AF
F -> SA
Вместо S -> BSB используем правила
S -> BH
H -> SB
5. Избавляемся от цепных правил
S' -> eps
S' -> a | b | AF | BH | AA | BB
A -> a
B -> b
S -> a
S -> b
S -> AF
F -> SA
S -> BH
H -> SB
Окончательно получаем грамматику
S' -> eps
S' -> a | b | AF | BH | AA | BB
A -> a
B -> b
S -> a | b | AF | BH
F -> SA
H -> SB
По этому примеру видно, что на практике нормальная форма
Хомского бесполезна, потому что из более-менее ясной грамматики
палиндромов мы получили грамматику с большим числом правил и
не очень ясную.
Вывод: грамматика в нормальной форме форме Хомского нужна только при
доказательстве разных теорем про контекстно-свободные языки.
=================================================================
Рассмотрим основную практическую задачу, связанную с теорией
формальных языков: задача разбора.
Дана контекстно-свободная грамматика и произвольная терминальная
цепочка. Надо
1) определить, принадлежит ли цепочка языку;
2) если да, то восстановить либо вывод этой цепочки,
либо синтаксическое дерево вывода.
В процессе восстановления вывода можно решать другие задачи:
-- перевод на другой язык, в некотором смысле эквивалентный
исходному языку;
-- вычисление значения формулы и т.п.
Задача разбора противоположна задаче вывода.
При выводе мы начинаем с начального нетерминала грамматики и,
делая замены по правилам, в конце-концов получаем терминальную цепочку.
При выводе замены по правилам выполняются слева направо:
A -> u
При разборе мы действуем наоборот:
правую часть правила мы сворачиваем (reduce) к нетерминалу
в левой части правила.
Есть два основных класса алгоритмов разбора:
1) нисходящий, или рекурсивный разбор, или LL(1)-разбор;
2) восходящий разбор, или разбор с помощью конечного автомата
со стеком (автомата с магазинной памятью), или LR(1)-разбор.
Обозначения означают:
LL(1) --
L -- Left to right, цепочка просматривается слева направо;
L -- Left строятся левые выводы;
1 -- при принятии решения об очередном действии мы учитываем
один (первый) символ необработанной части входной цепочки.
LR(1) --
L -- Left to right, цепочка просматривается слева направо;
R -- Right строится правый вывод;
1 -- при принятии решения об очередном действии мы учитываем
один (первый) символ необработанной части входной цепочки.
Теорема.
Класс грамматик, допускающих LR(1)-разбор, строго шире, чем класс
грамматик, допускающих LL(1)-разбор.
Если грамматика допускает LL(1)-разбор, то она допускает и LR(1)-разбор.
Обратное неверно.
Зачем нужен LL(1)-разбор, если есть более сильный метод LR(1)?
Ответ: ни зачем не нужен, у алгоритма LL(1) вообще нет преимуществ,
кроме единственного:
рекурсивный парсер можно написать руками, не зная никакой теории;
LR(1)-парсер практически невозможно написать руками, не используя
никаких инструментальных средств для построения таблиц конечного
автомата со стеком.
Программы, которые строят LR(1)-парсер (конечный автомат с магазинной памятью)
по контекстно-свободной грамматике, давно написаны. Эта утилита
всегда входит в состав операционной системы Unix, она называется
yacc (Yet Another Compiler Compiler -- еще один компилятор компиляторов),
в GNU эта утилита называется bison. Отметим, что лексический анализатор,
используемый для распознавания регулярных языков, называется lex
или flex в GNU.
Следующий раз мы рассмотрим рекурсивный парсер для языка арифметических
формул (включающего и стандартные функции), заодно познакомимся с
понятием хвостовой рекурсии (tail recursion).
----------------------------------------------------------------
24 Nov 2021
Задача разбора. Рекурсивный разбор
Задача разбора противоположна задаче вывода.
При выводе термимнальной строки мы начинаем с начального нетерминала
грамматики и, заменяя нетерминалы в выводимой цепочке на правые части
соответствующих правил, в конце-концов получаем терминальную цепочку языка.
При разборе мы идем в обратную сторону. Нам дается терминальная цепочка,
требуется восстановить ее вывод. При восстановлении мы как свертываем
некоторую подстроку цепочки, представляющую правую часть правила,
к нетерминалу в левой части правила. Разбор заканчивается, когда мы получаем
начальный нетерминал грамматики. (Восходящий разбор.)
При нисходящем разборе мы пытаемя отождествить начало непрочитанной части
цепочки (которая состоит из терминалов) с некоторым метасимволом грамматики,
к которому в результате она сворачивается.
Результатом разбора является либо вывод цыпочки, либо синтаксическое дерево
вывода, либо в процессе разбора мы можем сразу переводить текст с
одного языка на другой, вычислять значение формулы и т.п.
В частности, мы определяем, принадлежит ли цепочка языку.
Есть 2 популярных алгоритма разбора:
1) рекурсивный, или нисходящий разбор, или LL(1)-разбор;
L -- терминальная цепочка просматривается слева (Left) направо;
L -- алгоритм строит левые выводы (Left)
1 -- решение о том, какое именно правило применить на каждом
шаге алгоримтма, определяется по состоянию алгоритма плюс
по первому символу необработанной части цепочки
(учитываем 1 символ аванцепочки).
Дерево вывода восстанавливается сверху-вниз, слева-направо;
2) восходящий разбор, или разбор с помощью конечного автомата со
стеком (автомата с магазинной памятью), или LR(1)-разбор;
L -- терминальная цепочка просматривается слева (Left) направо;
R -- алгоритм строит правые выводы (Right);
1 -- решение о том, какое именно действие выполнять на каждом
шаге алгоримтма, определяется по состоянию алгоритма плюс
по первому символу необработанной части цепочки
(учитываем 1 символ аванцепочки).
Рассмотрим алгоритм рекурсивного разбора.
Идея очень простая
Пусть мы хотим выделить начало терминальной цепочки, которое выводится
из нетерминала A. И пусть для A есть несколько правил:
A -> aBCdE | FbAcD | ...
Выбираем, какое именно правило применить, по первому символу аванцепочки.
Если, например, аванцепочка начинается с терминала a, то выбираем первое
правило
A -> aBCdE
Если аванцепочка начинается, допустим, с терминала b и цепочки, которые
выводятся из правой части второго правила FbAcD или следуют за ней (если
из нее выводится пустая цепочка), могут начинаться с терминала b,
то выбираем второе правило, и т.д.
Допустим, мы выбрали первое правило с правой частью aBCdE.
Тогда надо пропустить терминал a,
потом обработать часть цепочки, которая выводится из B,
потом обработать часть цепочки, которая выводится из C,
потом пропустить терминал d,
потом обработать часть цепочки, которая выводится из E:
void processA() {
if (peekToken() == a) {
skipToken(a);
processB();
processC();
skipToken(d);
processE();
} else if (peekToken() == b) {
. . .
}
}
Рассмотрим язык арифметических формул. При разборе обычно в конец
цепочки добавляют маркер конца строки, традиционно он обозначается как $.
S -> F $
F -> T | F + T | F - T
T -> M | T * M | T / M
M -> E | Func
E -> number | ( F )
Func -> name ( F )
Эта грамматика не допускает рекурсивный разбор! (Забегая вперед,
метод восходящего разбора более сильный, т.е., если грамматика
допускает LL(1)-разбор, то она допускает и LR(1)-разбор.
Данная грамматика допускает LR(1)-разбор, но не допускает LL(1)-разбор.)
Есть два правила
F -> T | F + T
для нетерминала F, правая часть которых может начинаться с одного и того же
терминала (например, a)
a a + a
непонятно, какое правило применить. Также при применении правила
F -> F + T
получается бесконечная рекурсия
void processF() {
processF();
. . .
функция обращается сама к себе, не прочитав ничего из входной
цепочки.
Оказывается, можно преобразовать эту грамматику так,
чтобы она стала лево-рекурсивной.
Процедура избавления от левой рекурсии.
Пусть есть правила
A -> Au1 | Au2 | ... | Au_k | w1 | w2 | ... | w_m
Вывод с помощью этих правил имеет вид
A => A u3 => Au1 u3 => A u2 u1 u3 => ... => A u u u u ... u =>
=> w u u u u ... u
Можно правила для A заменить на
A -> w1 Atail | w2 Atail | ... | w_m Atail
Atail -> eps | u1 Atail | u2 Atail | ... | u_k Atail
Применим эту процедуру к нашей грамматике:
S -> F $
#### F -> T | F + T | F - T
F -> T Ftail
Ftail -> eps | + T Ftail | - T Ftail
#### T -> M | T * M | T / M
T -> M Ttail
Ttail -> eps | * M Ttail | / M Ttail
M -> E | Func
E -> number | ( F )
Func -> name ( F )
В результате получим грамматику, допускающую рекурсивный разбор:
S -> F $
F -> T Ftail
Ftail -> eps | + T Ftail | - T Ftail
T -> M Ttail
Ttail -> eps | * M Ttail | / M Ttail
M -> E | Func
E -> number | x | ( F )
Func -> name ( F )
Добавили, помимо констант, также переменную x.
Для этого изменили только одно правило
E -> number | x | ( F )
Задача: по формуле получить ее обратную польскую запись,
чтобы потом можно было вычислять ее значение с помощью стекового
вычислителя.
(2 + 3)*(5 - 6/7)
2, 3, +, 5, 6, 7, /, -, *
1) 2) 3) 4) 5) 6) 7) 8) 9)
Стековый вычислитель: числа просто добавляются в стек.
При выполнении операции со стека снимаются аргументы операции,
выполняется операция и ее результат добавляется обратно в стек.
1) 2 стек 2
2) 3 стек 2, 3
3) + стек 5
4) 5 стек 5, 5
5) 6 стек 5, 5, 6
6) 7 стек 5, 5, 6, 7
7) / стек 5, 5, 6/7
8) - стек 5, 29/7
9) * стек 145/7
Обратная польская запись названа в честь польского математика
Яна Лукасиевича и обозначается RPN (Reverse Polish Notation)
Любой компилятор работает в два этапа:
1) сканер, или лексический анализатор, разбивает входной поток символов
на лексемы (слова, токены). Лексемы обычно задаются с помощью регулярных
выражений. Сканер обычно создается с помощью утилиты lex (или flex --
свободная версия);
2) поток лексем подается на вход парсеру.
==============================================
1 Dec 2021
Рекурсивный компилятор формул
В связи с КС-грамматиками можно рассмотреть 2 задачи:
1) вывод цепочки в грамматике
A --> u
S => u1 => u2 => ... => u_n -- терминальная цепочка
... => vAw => vuw => ...
Левая часть правила заменяется на правую
2) разбор -- задача, противоположная выводу
Дана терминальная цепочка, надо восстановить ее вывод
Вывод (дерево вывода) можно восстанавливать либо сверху вниз,
либо снизу вверх.
Дерево восстанавливается сверху вниз при рекурсивоном разборе,
и снизу вверх при восходящем (или LR-) разборе.
Рекурсивный парсер можно написать вручную.
При восходящем разборе надо вычислить множество состояний и
заполнить таблицы конечного автомата со стеком, а это очень
трудно сделать вручную, для это существуют уже реализолванные
программы ("компиляторы компиляторов") типа YACC
(Yet Another Compiler Compiler).
=> Рекурсивный парсер можно использовать для несложных языков.
Пример -- нарисовать в окне график функции, ее текст задается
в текстовом поле.
Идея рекурсивного разбора:
мы рассматриваем грамматики с маркером конца строки
S --> F $
Идея рекурс. разбора
Пусть для нетерминала A есть 3 правила:
A --> BcAd | FGH | abCd
Разбор применим, если первые символы терминальных цепочек, выводимых
из правых частей правил, начинаются с разных терминалов.
Для каждого нетерминала A мы реализуем функцию
processA()
которая выделяет из входной цепочки максимальное начало, которое
выводится из A. (Процесс замены цепочки на A называют светкой цепочки к A.)
void processA() {
если начальный символ аванцепочки равен b
| processB();
| skip(c);
| processA();
| skip(d)
иначе если начальный символ аванцепочки равен f
| processF();
| processG();
| processH();
. . .
Избавление от левой рекурсии
A -> Au | v
A => Au => Auu => Auuu => vuuu vuuuu...uuuu vu*
A -> v Atail
Atail -> eps | u Atail
Применив эту процедуру к нашей грамматике
S -> F $
F -> T | F + T | F - T
T -> M | T * M | T / M
M -> E | Func
E -> number | ( F )
Func -> name ( F )
получим лево-рекурсивную грамматику
S -> F $
F -> T Ftail
Ftail -> eps | + T Ftail | - T Ftail
T -> M Ttail
Ttail -> eps | * M Ttail | / M Ttail
M -> E | Func
E -> number | ( F )
Func -> name ( F )
8 Dec 2021
Рекурсивный парсер
// F -> T Ftail
void processF() {
processT();
processFtail();
}
// Ftail -> eps | + T Ftail | - T Ftail
void processFtail() {
if (peekToken().token == Token::PLUS) {
skipToken(Token::PLUS);
processT();
rpn.push_back(Token(Token::PLUS));
processFtail();
} else if (peekToken().token == Token::MINUS) {
skipToken(Token::MINUS);
processT();
rpn.push_back(Token(Token::MINUS));
processFtail();
} else {
// Nothing to do...
}
}