Предисловие
Добрый день.
Это вторая часть статьи про написание своего генератора LALR-анализаторов. В этой части я расскажу про эволюции от примитивных восходящих синтаксических анализаторов до наиболее актуальных, хотя и не шибко новых, LALR-парсеров. Тем, кто не читал первую статью (ссылки — снизу), советую прочесть хотя бы первую половину последнего раздела. О том небольшом фрагменте кода я буду упоминать несколько раз.
В комментариях к прошлой статье несколько человек интересовались моими мотивами в написании своего компилятора компиляторов. К сожалению, они в этой статье не найдут ответов на этот вопрос. Не скрою, изначально я планировал написать статью без особой теории, но с оправданием задач и целей, ради которых я начал писать генератор, да и хотел поделиться нюансами и особенностями реализации. То есть по объему это довольно прилично: несколько экранов. Но затем я решил всё же описать базовую теорию популистским языком, поэтому статья разрослась до трех частей. Таким образом, дабы не ломать логику изложения, я сначала расскажу про LR/SLR/LALR-анализаторы, а завтра опубликую заключительную, и, думаю, самую интересную часть.
Зачем нужна эволюция?
Если взглянуть на примитивный код примера в прошлой части, то видно что сложность алгоритма исчисляется как O(n), где n — количество входных символов. Скажу сразу, что это очень хорошая оценка для алгоритмов. К примеру, для наиболее быстрой сортировки сложность O(n * log(n)). Однако, что же значит данное высказывание про сложность алгоритма? А оно означает то, что мы должны будем выполнить не n операций, а как минимум C * n, где C — константа. Для этого примера константа очень велика — сумма длин всех правил, и легко может равняться и 100, и 1000, и 10000. То есть для строки из 10 символов, затратим сто тысяч операций. А вот это уже очень плохо.
Вот поэтому нам и нужно улучшать алгоритм самого парсера. Базовая идея — на каждом шаге и поступившем терминале знать о том, в каких правилах этот символ вкупе с некоторым количеством предыдущих может привести к свертке (замене последних K символов, в том числе уже свернутых нетерминалов, в один нетерминал), а в каких — к переносу, то есть определение где этот терминал встал на свою позицию. Грубо говоря, если есть правила A = 012 и B = 021, то строка 01 приведет к переносу для правила A, 02 — к переносу по правилу B, а 012 — к свертке по правилу A. Такая идея позволит приблизить вышеупомянутую константу C к 1. Нетрудно заметить, что данная схема очень хорошо вписывается в концепцию FSM (конечных автоматов). Если говорить упрощенно, то это двумерная таблица, которая по номеру текущего состояния и входящему символу даёт новый номер состояния. И так до тех пор пока не достигнем конечного состояния.
Состояния FSM
Ок, хорошо. Я думаю, очевидно то, что состояния должны отображать текущую позицию символа в правилах — для вышеуказанных примеров A и B с ранее прочитанными символами 0, 1 состояние может быть описано как «мы уже прочитали первые 2 символа из 3х правила A». Если добавим правило C = 013, тогда состояние будет менее конкретным: «мы уже прочитали первые 2 символа из 3х A или C». И тогда все будет зависеть от следующего символа — 2 или 3. Если приходит 2, тогда переходим в состояние «мы прочитали 3 символа из 3х А» и тогда мы организуем свертку — превращение 012 в символ A. Для 3 и C соответственно — аналогично. Это должно быть понятно.
Кроме того, нам нужно определить с чего начать и когда остановиться. В данном примере начало это — «Мы прочитали 0 символов из 3х A или B или C». Концовка тоже вроде ясна — 3 возможных состояния «3 из 3х» для A/B/C. То есть когда происходит свертка по одному из правил, останавливаемся. Однако, если для примитива это работает, то стоит чуть усложнить, и всё ломается.
A = 0 A | 1
Такая грамматика задаёт m нулей и затем 1 в конце, то есть, например, «0000001». В чём же сложность? А в том, что мы уже не можем определить когда нужно остановиться. То есть если останавливаться на свертке A, тогда мы сразу же по первой свертке (когда прочитаем терминал 1, свернём его в A) и застопоримся, и при этом не проведём еще m свёрток (по правилу A = 0 A). Поэтому при разработке грамматики вводится ограничение на наличие одного стартового символа к которому будет собираться грамматика. S = A | B | C. Но кроме этого к парсеру автоматически добавляется специальный символ S' и правило S' = S. И тогда в случае свертки этого правила мы будем знать о том что миссия выполнена, можно идти домой. Таким образом мы одновременно определили и начальное состояние — «мы считали 0 символов из 1 по правилу S'», и конечное.
Теперь самое время подумать о кодировании состояний. Ну не напишем же мы наши пожелания и ожидания прямым текстом. Анализатор нас просто не поймет. Надо подумать о машинном представлении вышеиспользуемых сентенций. На самом деле, это элементарно видно, если сравним их между собой. В них содержатся лишь 2 определяющих момента — правило и текущая позиция в этом правиле. И, как видно из примеров, состояние может содержать несколько таких наборов. Сами наборы в классике называются пунктами (items). И выглядят так: A = 01 · 2, то есть прочитали 2 символа в правиле A = 012.
Таблица FSM
Осталось только задать сам FSM и парсер фактически готов. Таблица переходов между состояниями строится очень просто — свертка определяется когда мы встречаем состояние, содержащее правило со всеми прочитанными символами. То есть маркер (·) стоит в самом конце. Кроме того, так как в таблице колонки задаются текущим символом, то мы должны выяснить все возможные терминалы, которые могут следовать после сворачиваемого символа. Если образовалось свертка, но дальше следует символ, ну который никак не мог там очутиться по общей логики грамматики, то это ошибка. Пример:
#start A
A = B 2
B = 01
Здесь, во время свертки B мы должны проверить то, что следом идёт 2, а не любой другой символ. Логика вычисления данного множества думаю понятна, а если нет, то ниже будет псевдоалгоритм. Кроме этого момента при свертке нужно учесть то, что необходимо отслеживать по какому родительскому правилу идёт разбор. То есть ведь символ для свертки может легко участвовать в нескольких правилах, а нам нужно четко знать в каком именно правиле в данный момент идёт эта операция дабы перейти в соответствующее состояние. Решается это ведением стека состояний. При сдвиге (получении терминала и смене состояния) мы кладём в стек номер состояния. А при свертке мы извлекаем из стека L элементов, где L — длина правой части выражения (набор элементов, которые сворачиваются в один нетерминал). И кладём индекс нового состояния, который определяется по той же FSM-таблице, с номером колонки равной нетерминалу левой части свернутого правила и номером строки — состоянием на вершине стека. Звучит возможно громоздко, но на самом деле всё просто. Проиллюстрирую работу алгоритма на вышеприведенной грамматике.
шаг 0. считали 0
шаг 1. перенос, состояние s0 {A = · B 2}, стек {0}
шаг 2. перенос, новое состояние = [s0, 0] = s1 {B = 0 · 1} , стек {0}, считали 1
шаг 3. перенос, новое состояние = [s1, 1] = s2 {B = 0 1 ·} , стек {0, 1}, считали 2
шаг 4. свёртка, так как [s2, 2] содержит об этом информацию (2 - ожидаемый символ), новое состояние = [s2, 2] = s3 {A = B · 2}, стек {B}
шаг 5. перенос, новое состояние = [s3, 2] = s4 {A = B 2 ·} , стек {B, 2}, считали EOF (знак окончания входного потока)
шаг 6. свертка, новое состояние = [s4, EOF] = s5 {S = A ·}, стек {A}
шаг 7. свертка, новое состояние = [s5, EOF] = s6 стек {S}, финальное состояние, так как мы свернулись в наш псевдотерминал, который обозначает конец разбора синтаксического выражения
Со сверткой разобрались, однако пока неясно как мы определяем переходы между состояниями и откуда они вообще берутся. А разрешается всё тривиально — мы просто перебираем все доступные символы (терминалы и нетерминалы), применяя к текущему анализируемому состоянию. Если оно содержит пункт вида {A =… · X ...}, где X — это подставляемый символ, тогда мы передвигаем маркер (это как раз и есть применение символа X) и получаем пункт нового состояния {A =… X · ...}. Само собой, если у нас несколько таких пунктов для X, то и новое состояние тоже будет содержать несколько записей. Кроме этого, во время данного процесса мы строим искомый FSM: [sOld, X] = sNew. Это практически готовая строчка таблицы. Нужно только добавить к ней элементы свертки.
Еще один немаловажный момент. Опять же если обратимся к последнему примеру, то видно что из стартового состояния {A = · B 2} можно получить только {A = B · 2} и [s0, B] = sX. Но это неверно и никогда не сработает. Просто потому что на входе стартового состояния мы никак не получим нетерминал (B), а только входной терминал (0, 1, 2). Дабы обеспечить работу алгоритма необходимо учитывать возможные развороты (операция обратная свертке). То есть в данном случае из грамматики мы видим то, что можно развернуть B и получить условно говоря {A = · 0 1 2}, что полностью соответствует логике. Формализуя то, что я описал, можно записать как: «если состояние содержит {X =… · Y ...}, то оно должно содержать и пункты вида {Y = · ...}». Этот процесс расширения называется замыкание.
Всё, теперь теории достаточно для составления как алгоритма генерации FSM, так и самого анализатора на основе FSM. Псевдокод постройки:
/*
определяем первые возможные терминальные символы нетерминала,
который получается после цепочки разворотов
*/
function firstTerminal(X)
{
if (X.type == Terminal)
return X;
result = [];
for (rule in rules)
{
// правила X = Y ...
if (rule.left == X)
{
// разворачиваем дальше, first(Y)
result[] = first(rule.right[0])
}
}
return result;
}
// определяем возможные терминальные символы, которые идут после нетерминала
function nextTerminal(X)
{
result = [];
for (rule in rules)
{
// правила Y = ... X
if (rule.right.end(X))
{
/*
так как X завершает правило Y, то после X могут идти
только те терминалы, которые идут за Y
*/
result[] = nextTerminal(rule.left);
} else
{
// правила Y = ... X ...
if (rule.right.has(X))
{
// первый терминал следующего символа и будет искомым терминалом
result[] = firstTerminal(rule.right.next(X));
}
}
}
return result;
}
// замыкание
function closeItem(I)
{
for (item in I)
{
// проверяем то что в пункте Y = ... · X ..., X это нетерминал
if (item.markered.type == NonTerminal)
{
for (rule in rules)
{
// правила X = ...
if (rule.left == item.markered)
{
// добвляем пункт X = · ...
I[] = {rule: rule, marker: 0};
}
}
}
}
}
// ищем возможные свертки и добавляем их в FSM
function addReducing(I, FSM)
{
for (item in I)
{
// пункты X = ... ·
if (item.markered == item.end)
{
// проверяем стартовое синтетическое правило S = A, где A - стартовый символ
if (item.rule.left == _START_)
{
// если это так, то мы достигли успеха, заносим эту информацию
FSM[I.index, EOF] = Success;
} else
{
// перебираем все возможные терминалы, которые идут после сворачиваемого символа
for (term in nextTerminal(item.rule.left))
{
/*
rule нам понадобится для определения двух вещей:
сколько снимать со стека и какой символ класть на вершину
*/
FSM[I.index, term] = {operation: Reduce, rule: item.rule};
}
}
}
}
}
// строим состояния после переноса I под воздействием символа X
function shiftState(I, X)
{
result = [];
for (item in I)
{
// пункты Y = ... · X ...
if (item.markered == X)
{
// сдвигаем маркер на следующий символ
result[] = {rule: item.rule, marker: item.marker + 1};
}
}
return closeItem(result);
}
// собственно строим таблицу
function buildFSM()
{
FSM = {};
// инициируем состояния замканием пункта S = · A
states = [closeItem({rule: {S = A}, marker: 0})];
for (state in states)
{
// определяем свертки дял каждого состояния
addReducing(state, FSM);
for (X in symbols)
{
new = states[] = shiftState(state, X);
// записываем переход
FSM[state.index, X] = {operation: Shift, index: new.index};
}
}
}
Код алгоритма:
input >> term;
accepted = false;
/*
в стеке 0 состояние, каждый символ отражается состоянием на стеке,
количество состояний == количество символов
*/
stack = [0];
while (!accepted)
{
// текущее состояние - stack.top()
state = FSM[stack.top(), term];
switch (state)
{
case Success:
accepted = true;
break;
case Shift:
// просто перенос на новое состояние
stack.push(state.index);
input >> term;
break;
case Reduce:
// извлекаем L символов
stack.pop(state.rule.right.length);
// state.rule.left - символ в который сворачиваем
// stack.pop() - родительское правило, которое содержит X
stack.push(FSM[stack.pop(), state.rule.left]);
// в итоге заменяем стек {..., Y, ..., Z} на {..., X} для правила X = Y ... Z
break;
default:
throw SyntaxError;
}
}
Дальнейшее совершенствование алгоритма. SLR(1)
Мы получили довольно быстрый и хороший алгоритм, но есть в нём один изъян, который трудно обнаружить. Он кроется в несовершенстве определения символа, который идёт после сворачиваемого нетерминала (функция nextTerminal). Небольшой пример:
A = B 2 | C
B = C 0 | 1
C = B
States:
S0: [{S = · A}, {A = · B 2}, {A = · C}, {B = · C 0}, {B = · 1}, {C = · B}]
S1: [{S = A ·}], переход из S0 по нетерминалу A
S2: [{A = B · 2}, {C = B ·}], переход из S0 по нетерминалу B
...
SX: [{A = B 2 ·}], переход из S2 по терминалу 2
Грамматика описывает строки вида 10...02 и 10...0. nextSymbol© = [0, 2, EOF]. И тогда мы получаем, что для FSM[S2, 2] мы должны сделать свертку по правилу C = B, но в тот же самый момент по правилу A = B 2 мы должны сделать перенос в SX по тому же самому терминалу 2 для состояния S2. Это печально. Так произошло потому что в состоянии S2 для пункта C = B мы должны ждать только EOF, исходя из A = C EOF, и никаких 2 или 0. Они могут появиться только в дальнейшем.
Да. это синтетический пример, но и в реальности встречаются грамматики с такого рода ловушками. Причём, не так уж и редко. Решение очевидно — детерминирование пунктов, порождающих свертку, по ожидаемому символу. То есть {C = B ·} трансформируется условно в {C = B · [expect EOF]} или для краткости {C = B ·, EOF}. Затрагиваются всего 2 момента — генерация пунктов (необходимо создавать пункты нового формата) и генерация ячеек со сверткой. То есть всего 2 функции closeItem() и addReducing():
// замыкание
function closeItem(I)
{
for (item in I)
{
// проверяем то что в пункте Y = ... · X ..., X это нетерминал
if (item.markered.type == NonTerminal)
{
for (rule in rules)
{
// правила X = ...
if (rule.left == item.markered)
{
// X - последний символ
if (item.nextMarkered == item.end)
{
// тогда наследуем возможные продолжения этого пункта
first = item.expect;
} else
{
// иначе смотрим на первый темринал следующего символа
first = firstTerminal(item.nextMarkered);
}
// добавляем все возможные пункты
for (expect in first)
{
// добвляем пункт X = · ...
I[] = {rule: rule, marker: 0, expect: expect};
}
}
}
}
}
}
// ищем возможные свертки и добавляем их в FSM
function addReducing(I, FSM)
{
for (item in I)
{
// пункты X = ... ·
if (item.markered == item.end)
{
// проверяем стартовое синтетическое правило S = A, где A - стартовый символ
if (item.rule.left == _START_)
{
// если это так, то мы достигли успеха, заносим эту информацию
FSM[I.index, EOF] = Success;
} else
{
/*
перебирать возможные следующие символы нет нужды,
ибо пункт итак содержит эту информацию
*/
FSM[I.index, item.expect] = {operation: Reduce, rule: item.rule};
}
}
}
}
Вершина — LALR(1)
Недостаток предыдущего алгоритма заметен невооруженным взглядом — там где мы использовали 1 пункт и 1 состояния, теперь возможно несколько пунктов и несколько состояний, различающихся лишь ожидаемым символом. Соответственно разбухает таблица FSM, причём настолько, что её размер может на пару порядков превышать соответствующую таблицу LR(0). Нехорошо.
Найти выход не составляет труда — объединяем состояния, которые отличаются только ожидаемым символом. Например: [{A = B, 0}, {B = C, 0}] и [{A = B, 1}, {B = C, 1}]. Почему это безопасно?
- При постройке нового состояния при переходе мы никак не используем expect-символ, поэтому если s0 и s1 идентичны по ядру (часть пункта за исключением ожидаемого символа), то s2 порожденный по X из s0 и s3 порожденный по X из s1 так же идентичны по ядру. Таким образом мы легко можем объединить s0 и s1 в sn0, s2 и s3 в sn1, и создать между ними связь. Это полностью корректно.
- Вторая часть FSM-таблицы — это свертки. Но здесь очевидно что они по определению не могут пересекаться, так как в состояниях разные expect-символы, то и свертки записаны только в 1 ячейку для соответствующего expect-символа. И они могут быть безболезненно совмещены.
Таким образом в итоге мы получаем тот же LR(0), но без ограничения грамматики.
Части статьи
- Часть 1. Базовая теория
- Часть 2. Описание LR-генераторов
- Часть 3. Особенности написания и возможные фичи LR-генераторов
Автор: mark_ablov
