Я медленно работаю, чтобы закончить свою степень, и этот семестр - Компиляторы 101. Мы используем Книгу Дракона . Вскоре в курсе, и мы поговорим о лексическом анализе и о том, как он может быть реализован с помощью детерминированных конечных автоматов (далее DFA). Настройте различные состояния лексера, определите переходы между ними и т. Д.
Но и профессор, и книга предлагают реализовать их через таблицы переходов, которые составляют гигантский двумерный массив (различные нетерминальные состояния как одно измерение и возможные входные символы как другое) и оператор switch для обработки всех терминалов а также отправка в таблицы перехода, если в нетерминальном состоянии.
Теория все хорошо и хорошо, но, как тот, кто на самом деле писал код на протяжении десятилетий, реализация мерзка. Это не тестируемое, не обслуживаемое, не читаемое, отладка через полтора года. Что еще хуже, я не понимаю, как это было бы отдаленно практично, если бы язык был UTF-совместимым. Приблизительно миллион записей таблицы переходов на нетерминальное состояние становится спешкой.
Так в чем же дело? Почему окончательная книга на эту тему говорит, что это так?
Действительно ли накладные расходы на вызовы функций настолько велики? Это то, что хорошо работает или необходимо, когда грамматика не известна заранее (регулярные выражения?)? Или, может быть, что-то, что обрабатывает все случаи, даже если более конкретные решения будут работать лучше для более конкретных грамматик?
( примечание: возможный дубликат « Зачем использовать ОО-подход вместо гигантского оператора switch? » близок, но я не забочусь о ОО. Функциональный подход или даже более разумный подход с автономными функциями подойдет.)
И в качестве примера рассмотрим язык, который имеет только идентификаторы, и эти идентификаторы есть [a-zA-Z]+. В реализации DFA вы получите что-то вроде:
private enum State
{
Error = -1,
Start = 0,
IdentifierInProgress = 1,
IdentifierDone = 2
}
private static State[][] transition = new State[][]{
///* Start */ new State[]{ State.Error, State.Error (repeat until 'A'), State.IdentifierInProgress, ...
///* IdentifierInProgress */ new State[]{ State.IdentifierDone, State.IdentifierDone (repeat until 'A'), State.IdentifierInProgress, ...
///* etc. */
};
public static string NextToken(string input, int startIndex)
{
State currentState = State.Start;
int currentIndex = startIndex;
while (currentIndex < input.Length)
{
switch (currentState)
{
case State.Error:
// Whatever, example
throw new NotImplementedException();
case State.IdentifierDone:
return input.Substring(startIndex, currentIndex - startIndex);
default:
currentState = transition[(int)currentState][input[currentIndex]];
currentIndex++;
break;
}
}
return String.Empty;
}
(хотя что-то, что правильно обработало бы конец файла)
По сравнению с тем, что я ожидал:
public static string NextToken(string input, int startIndex)
{
int currentIndex = startIndex;
while (currentIndex < startIndex && IsLetter(input[currentIndex]))
{
currentIndex++;
}
return input.Substring(startIndex, currentIndex - startIndex);
}
public static bool IsLetter(char c)
{
return ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z'));
}
С кодом в NextTokenрефакторинге в свою собственную функцию, если у вас есть несколько пунктов назначения с начала DFA.
источник
Ответы:
На практике эти таблицы генерируются из регулярных выражений, которые определяют токены языка:
У нас были утилиты для генерации лексических анализаторов с 1975 года, когда был написан lex .
Вы в основном предлагаете заменить регулярные выражения процедурным кодом. Это расширяет пару символов в регулярном выражении на несколько строк кода. Рукописный процедурный код для лексического анализа любого умеренно интересного языка имеет тенденцию быть неэффективным и сложным в обслуживании.
источник
Мотивация для конкретного алгоритма в значительной степени заключается в том, что это учебное упражнение, поэтому он старается держаться ближе к идее DFA и сохранять состояния и переходы очень явными в коде. Как правило, никто не будет писать этот код вручную в любом случае - вы будете использовать инструмент для генерации кода из грамматики. И этот инструмент не будет заботиться о читабельности кода, потому что это не исходный код, а вывод, основанный на определении грамматики.
Ваш код чище для тех, кто поддерживает рукописный DFA, но немного дальше от понятий, которым учат.
источник
Внутренний цикл:
имеет много преимуществ в производительности. Здесь вообще нет веток, потому что вы делаете одно и то же для каждого входного символа. Производительность компилятора может контролироваться лексером (который должен работать в масштабе каждого символа ввода). Это было еще более верно, когда была написана Книга Дракона.
На практике, кроме студентов CS, изучающих лексеры, никто не должен реализовывать (или отлаживать) этот внутренний цикл, потому что он является частью шаблона, который поставляется с инструментом, который создает
transitionтаблицу.источник
По памяти - я давно прочитал книгу, и я уверен, что не читал последнее издание, я точно не помню что-то похожее на Java - эта часть была написана с код должен быть шаблоном, таблица заполняется лексоподобным генератором лексеров. Тем не менее из памяти был раздел о сжатии таблиц (опять же из памяти, он был написан таким образом, что он также был применим к анализаторам, управляемым таблицами, что, возможно, дальше в книге, чем то, что вы уже видели). Точно так же в книге, которую я помню, предполагалось использовать 8-битный набор символов, я бы ожидал раздел о работе с большим набором символов в более поздних изданиях, возможно, как часть сжатия таблицы. Я дал альтернативный способ справиться с этим в качестве ответа на такой вопрос.
В современной архитектуре есть определенное преимущество в производительности, заключающееся в том, что данные с жестким циклом управляются: это достаточно удобно для кэширования (если вы сжали таблицы), а предсказание переходов максимально возможно (одно промах в конце лексемы, возможно, одно пропустите переключение, отправляющее код, который зависит от символа; это предполагает, что декомпрессия вашей таблицы может быть выполнена с помощью предсказуемых переходов). Перемещение этого конечного автомата в чистый код снизит производительность прогнозирования перехода и, возможно, увеличит нагрузку на кэш.
источник
Проработав ранее «Книгу Дракона», основная причина наличия рычагов и парсеров, управляемых таблицами, заключается в том, что вы можете использовать регулярные выражения для генерации лексера и BNF для генерации парсера. В книге также рассказывается, как работают такие инструменты, как lex и yacc, и по порядку, чтобы вы знали, как работают эти инструменты. Кроме того, для вас важно проработать несколько практических примеров.
Несмотря на множество комментариев, это не имеет ничего общего со стилем кода, который был написан в 40-х, 50-х, 60-х ..., это связано с получением практического понимания того, что инструменты делают для вас и что у вас есть сделать, чтобы заставить их работать. Все это связано с фундаментальным пониманием работы компиляторов как с теоретической, так и с практической точки зрения.
Надеемся, что ваш инструктор также разрешит вам использовать lex и yacc (если только это не выпускной класс и вы не напишете lex и yacc).
источник
Поздно к вечеринке :-) Жетоны сопоставляются с регулярными выражениями. Поскольку их много, у вас есть движок multi-regex, который, в свою очередь, является гигантским DFA.
«Что еще хуже, я не понимаю, как это было бы отдаленно практично, если бы язык был способен UTF».
Это не имеет значения (или прозрачно). Кроме того, UTF обладает хорошим свойством, его сущности не перекрываются даже частично. Например, байт, представляющий символ «A» (из таблицы ASCII-7), больше не используется ни для какого другого символа UTF.
Итак, у вас есть один DFA (который является регулярным выражением) для всего лексера. Как лучше записать это, чем 2d массив?
источник