Каковы хорошие ресурсы о том, как написать лексер на C ++ (книги, учебные пособия, документы), каковы некоторые хорошие методы и практики?
Я посмотрел в Интернете, и все говорят, чтобы использовать генератор лексера, как лекс. Я не хочу этого делать, я хочу написать лексер от руки.
Ответы:
Имейте в виду , что каждый конечный автомат соответствует регулярному выражению, которое соответствует структурированной программы с использованием
if
иwhile
отчетности.Так, например, для распознавания целых чисел у вас может быть конечный автомат:
или регулярное выражение:
или структурированный код:
Лично я всегда пишу лексеры, используя последние, потому что ИМХО это не менее понятно, и нет ничего быстрее.
источник
*pc
, верно? Какwhile(isdigit(*pc)) { value += pc; pc++; }
. Затем после}
вы конвертируете значение в число и назначаете его токену.n = n * 10 + (*pc++ - '0');
. Это становится немного сложнее для чисел с плавающей запятой и 'e', но неплохо. Я уверен, что мог бы сохранить небольшой код, упаковав символы в буфер и вызвавatof
или что-то еще. Это не будет работать быстрее.Лексеры - это конечные автоматы. Следовательно, они могут быть созданы любой универсальной библиотекой FSM. Однако в целях своего образования я написал свои собственные, используя шаблоны выражений. Вот мой лексер:
Он опирается на библиотеку конечного автомата с обратным слежением, основанную на итераторах, длиной ~ 400 строк. Тем не менее, легко увидеть, что все, что мне нужно было сделать , - это создать простые логические операции, такие как
and
,or
иnot
, и пару операторов в стиле регулярных выражений, например,*
для нуля или более,eps
чтобы означать «соответствовать чему-либо» иopt
означать «соответствовать». ничего, кроме как потреблять это ". Библиотека полностью универсальна и основана на итераторах. Материал MakeEquality - это простой тест на равенство*it
и переданное значение, а MakeRange - простой<= >=
тест.В конце концов, я планирую перейти от отслеживания к прогнозированию.
источник
MakeEquality
фрагментом? В частности, объект, возвращаемый этой функцией. Выглядит очень интересно.Прежде всего, здесь происходят разные вещи:
Как правило, мы ожидаем, что лексер выполнит все 3 шага за один раз, однако последний по своей природе более сложен, и есть некоторые проблемы с автоматизацией (подробнее об этом позже).
Самый удивительный лексер, о котором я знаю, это Boost.Spirit.Qi . Он использует шаблоны выражений для генерации выражений лексера, и когда-то привыкнув к его синтаксису, код кажется действительно аккуратным. Хотя он компилируется очень медленно (тяжелые шаблоны), поэтому лучше выделять различные части в выделенных файлах, чтобы не перекомпилировать их, когда они не были затронуты.
В производительности есть некоторые подводные камни, и автор компилятора Epoch объясняет, как он получил ускорение в 1000 раз благодаря интенсивному профилированию и исследованию работы Qi в статье .
Наконец, есть также сгенерированный код с помощью внешних инструментов (Yacc, Bison, ...).
Но я обещал написать, что было не так с автоматизацией проверки грамматики.
Например, если вы посмотрите на Clang, вы поймете, что вместо использования сгенерированного парсера и чего-то вроде Boost.Spirit вместо этого они намеревались проверять грамматику вручную, используя общую технику анализа спуска. Конечно, это кажется отсталым?
На самом деле, есть очень простая причина: восстановление после ошибок .
Типичный пример в C ++:
Заметили ошибку? Недостающая точка с запятой сразу после объявления
Foo
.Это распространенная ошибка, и Clang аккуратно восстанавливается, понимая, что он просто отсутствует и
void
не является экземпляром,Foo
а частью следующего объявления. Это позволяет избежать трудной диагностики загадочных сообщений об ошибках.Большинство автоматизированных инструментов не имеют (по крайней мере очевидных) способов определения этих вероятных ошибок и способов их устранения. Зачастую восстановление требует небольшого синтаксического анализа, так что это далеко не очевидно.
Таким образом, использование автоматизированного инструмента связано с компромиссом: вы быстро получаете парсер, но он менее удобен для пользователя.
источник
Поскольку вы хотите узнать, как работают лексеры, я полагаю, вы действительно хотите знать, как работают генераторы лексеров.
Генератор лексера принимает лексическую спецификацию, которая представляет собой список правил (пары регулярных выражений-токенов), и генерирует лексер. Этот результирующий лексер может затем преобразовать входную (символьную) строку в строку токена в соответствии с этим списком правил.
Наиболее часто используемый метод состоит в преобразовании регулярного выражения в детерминированные конечные автоматы (DFA) с помощью недетерминированных автоматов (NFA) плюс несколько деталей.
Подробное руководство по выполнению этой трансформации можно найти здесь . Обратите внимание, что я сам не читал, но выглядит довольно хорошо. Кроме того, практически в любой книге по построению компилятора это преобразование будет описано в первых нескольких главах.
Если вас интересуют слайды лекционных курсов по данной теме, их, несомненно, можно найти в бесчисленном количестве курсов по построению компиляторов. В моем университете вы можете найти такие слайды здесь и здесь .
Есть еще несколько вещей, которые обычно не используются в лексерах или не рассматриваются в текстах, но тем не менее весьма полезны:
Во-первых, обработка Unicode несколько нетривиальна. Проблема состоит в том, что вход ASCII имеет ширину всего 8 бит, что означает, что вы можете легко иметь таблицу переходов для каждого состояния в DFA, поскольку они имеют только 256 записей. Однако для Unicode шириной 16 бит (если вы используете UTF-16) требуются таблицы по 64 КБ для каждой записи в DFA. Если у вас сложные грамматики, это может начать занимать довольно много места. Заполнение этих таблиц также начинает занимать довольно много времени.
Кроме того, вы можете генерировать интервальные деревья. Например, дерево диапазона может содержать кортежи ('a', 'z'), ('A', 'Z'), что намного более эффективно использует память, чем заполненная таблица. Если вы поддерживаете непересекающиеся интервалы, вы можете использовать любое сбалансированное двоичное дерево для этой цели. Время выполнения является линейным по количеству битов, необходимых для каждого символа, поэтому O (16) в случае Unicode. Однако, в лучшем случае, это обычно будет немного меньше.
Еще одна проблема заключается в том, что лексеры, которые обычно генерируются, на самом деле имеют квадратичную производительность в худшем случае. Хотя это наихудшее поведение обычно не наблюдается, оно может вас укусить. Если вы столкнулись с проблемой и хотите ее решить, документ , описывающий , как достичь линейного времени можно найти здесь .
Возможно, вы захотите описать регулярные выражения в виде строк, как они обычно появляются. Однако анализ этих описаний регулярных выражений в NFA (или, возможно, сначала в рекурсивной промежуточной структуре) представляет собой проблему куриного яйца. Для анализа описаний регулярных выражений очень подходит алгоритм Shunting Yard. В Википедии, кажется, есть обширная страница об алгоритме .
источник