Лексический анализатор
Тема лексического анализа хорошо освещена в литературе. Не будем возвращаться к теории, к ней лишь хотелось бы добавить сугубо практические вопросы,
на которые свет был пролит в недостаточном количестве.
Загрузка родного языка
Из широко известных языков программирования только Алгол-68 имеет поддержку различных
национальных языков вплоть до национальных версий ключевых слов.
Как выполнена эта поддержка, автору этих строк не известно.
В нашем же языке есть специальная команда загрузки родного языка в программу:
##русский
или
##english
Поскольку лексика языка программирования, с которой работает лексический анализатор, становится зависимой от выбора языка,
то это обязывает лексический анализатор выполнить следующие действия:
-
загрузка алфавита (точнее — массива признаков) из внешнего файла,
-
загрузка перечня ключевых слов,
-
загрузка перечня сообщений об ошибках компиляции.
Разбиение символов алфавита языка на непересекающиеся подмножества
Оно очень желательно, ибо позволяет значительно упростить и убыстрить лексический анализ.
Лексический анализатор должен иметь массив признаков для каждого символа, описывающий возможность использования в каких-либо лексемах.
Доступ к признакам — по индексу, а индексом является код символа. Например:
Признаки [код символа] & ЗНАК ОПЕРАЦИИ
Признаки [код символа] & ДВОИЧНАЯ ЦИФРА
Признаки [код символа] & ПЕРВЫЙ СИМВОЛ ИДЕНТИФИКАТОРА
Признаки [код символа] & ПОСЛЕДУЮЩИЙ СИМВОЛ ИДЕНТИФИКАТОРА
Подав на вход такого выражения символ «1», мы получим значение «истина» во втором и четвёртом выражениях, в остальных — «ложь».
Буква «а» даст «истину» в третьем и четвёртом случае.
Подробности можно посмотреть здесь: выбор кодировки для компилятора.
Массив признаков загружается директивой:##самоназвание языка
Анализ вложенности скобок
Разработанный для нового языка программирования стиль подразумевает наличие
открывающей и закрывающей скобки для любого синтаксического блока.
Согласованность и открывающих скобок, как пишут классики, не решаются грамматиками типа 3.
Т.е. не получится выполнить разбор с помощью регулярных выражений.
Однако эта проблема легко решаема.
В лексическом анализаторе необходимо завести переменную «уровень вложенности скобок».
При появлении открывающей скобки её значение увеличивается на 1, при появлении закрывающей — уменьшается на 1.
В разрабатываемом языке есть ещё одна сложность, связанная со скобками. Например, когда встречается
(если ...
...)
то символам «(если» должна соответствовать лексема «начало условного выражения».
Но как быть, когда ключевое слово не следует сразу же за открывающей скобкой?
( ...
пока условие)
Это тоже решаемо. В лексическом анализаторе должен быть массив указателей на лексемы «открывающая скобка — начало блока».
Когда встречается открывающая скобка, то происходит инкремент уровня вложенности,
затем в выходной буфер лексического анализатор помещается лексема «открывающая скобка — начало блока»,
а в завершение в этот массив указателей записывается указатель на свежеиспечённую лексему.
Далее, когда на уровне вложенности n у нас встретилось «блочное» ключевое слово (например, «пока», «цикл», «структура»), то:
-
из массива по индексу n получаем указатель на лексему «открывающая скобка — начало блока»,
-
по полученному адресу переписываем значение лексемы на новое, соответствующее встреченному ключевому слову, например, «цикл пока — начало блока».
Открывающая скобка может начинать не только какой-то блок, но и список параметров функции.
В этом случае лексический анализатор должен «заглянуть» на ход назад.
И если скобке предшествует идентификатор, то этой скобке должна соответствовать лексема «начало списка параметров».
Лексический анализ — отдельный проход компилятора
В большом количестве компиляторов лексический анализ не выделен в отдельный проход.
Отдельный проход — это роскошь, которая тянет за собой дополнительный расход памяти.
Поэтому большинство компиляторов делает лексический анализ примерно так:
лексема = получить очередную лексему (символьный входной поток);
Эта функция вызывается из синтаксического анализатора.
Это простое решение экономит память хотя бы потому, что не требуется хранить все встреченные лексемы.
Но всегда ли оно возможно? В рассмотренном выше примере
( ...
пока условие)
необходимо загружать лексемы до той поры, пока не встретится ключевое слово «пока» —
чтобы правильно идентифицировать, какой именно лексеме соответствует открывающая скобка.
Это подводит нас к тому, что лексический анализ должен быть отдельной фазой компиляции и иметь,
соответственно, некое промежуточное представление для хранения полученных лексем.
По окончании лексического анализа начинается работа синтаксического анализатора, который получает лексемы так:
лексема = получить очередную лексему (входной поток лексем);
Другие проблемы лексического анализа
Поскольку описание их решения не вписывается в пару абзацев, это вынесено в отдельные статьи:
Существует так же проблема, как отличить унарную операцию получения ссылки «&» от бинарной операции «И».
Это делается точно так же, как и для унарного минуса.
Интересное наблюдение от «классика»
Робин Хантер, «Проектирование и конструирование компиляторов», стр. 52:
Процесс лексического анализа может быть достаточно простым, но в смысле времени компиляции он оказывается довольно дорогим.
Больше половины времени, затрачиваемого компиляторами на компиляцию программы, приходится на лексический анализ
(в основном из-за литерного характера ввода).
Если бы для какого-то компилятора на это потребовалось меньшее время, то мы могли бы предположить,
что какие-то другие фазы компилятора были не в полной мере эффективными.
Интересное, конечно, утверждение. Оно, скорее всего, недалеко от истины.
Однако почему компиляторы одного и того же языка имеют такую разную скорость работы?
Ведь лексический анализатор, по идее, наименее «интеллектуальная» часть компилятора.
Поэтому алгоритмы банальны, а скорость разбора лексем можно считать для разных компиляторов одинаковой.
Но TinyCC работает в девять (в девять, Карл!) раз быстрее GCC.
Да, грамматика языка C проще, чем C++ (TinyCC работает только с C, но не с C++, в отличие от GCC).
И в GCC последующие фазы компиляции сложнее, ибо сложнее сам язык.
Но осадочек всё равно остаётся.
Опубликовано: 2016.06.01, последняя правка: 2018.10.29 15:54
Отзывы
✅ 2016/06/03 02:58, rst256 #0
Доступ к признакам по индексу, а индексом является код символа. Ну это, может, и чуть быстрее сравнения интервалов, если, конечно, это массив, а не хеш. Но это же сколько памяти отъесть + время на загрузку этого бреда при старте? А тип элементов массива, надо полагать, однобайтовый char?✅ 2016/06/03 11:39, Автор сайта #1
Беда интервалов в том, что для разных алфавитов они разные. Идея в том, чтобы с помощью массива как ускорить работу, так и упростить. Массив обычный, классический. Тип char не пойдёт, в нём всего 8 бит. Если у нас 32 признака, то нужен 32-битовый элемент массива. Если по директиве ##english будет загружен соответствующий массив признаков, то элементов в нём будет меньше 128. Памяти потребуется немного. А вот для китайского побольше, конечно.✅ 2016/06/03 03:17, rst256 #2
Согласованность и открывающих скобок, как пишут классики, не решаются грамматиками типа 3. Т.е. не получится выполнить разбор с помощью регулярных выражений. Вообще-то многие регулярки это умеют, просто это не соответствует математической модели грамматик 3-го типа. Ну и, конечно, это мало востребовано. Например, даже самый простой язык, имеющий строковые константы или комментарии...✅ 2016/06/03 11:45, Автор сайта #3
Всё равно конструкции вида «( ... пока условие)» придётся разбирать иным способом, нежели регулярные выражения. Так причин отказа от них несколько.✅ 2016/06/03 04:13, rst256 #4
Больше половины времени, затрачиваемого компиляторами на компиляцию программы, приходится на лексический анализ. А 99% времени уходит на написание кода, в основном по причине того, что приходиться писать кучу незначащего кода. Например потому, что лексеру сложно было на 3-4 лексемы заглянуть вперед:с++: type = new type(...) с/с++: "->" и "." для доступа к полям структур.
Может лучше моё время всё же оптимизировать, а не компилятора?✅ 2016/06/03 12:04, Автор сайта #5
Хантер пишет о времени, которое тратит лексический анализатор, а не программист. Лексеру необязательно заглядывать вперёд. Он просто может оглядываться назад. Как в случае с конструкцией «( ... пока условие)».✅ 2016/12/31 15:14, rst256 #6
Эта функция вызывается из синтаксического анализатора. Это простое решение экономит память хотя бы потому, что не требуется хранить все встреченные лексемы. Но всегда ли оно возможно? В рассмотренном выше примере ( ... пока условие) необходимо загружать лексемы до той поры, пока не встретится ключевое слово «пока» чтобы правильно идентифицировать, какой именно лексеме соответствует открывающая скобка. Подобный подход оправдан, только если АСТ при компиляции мы строить не собираемся. Если так, то все вроде бы правильно (ну кроме разве что самого отказа от АСТ :-) ).
В противном случае, если мы собираемся строить АСТ, в подобном просто нет смысла! В структурах АСТ тело цикла можно описать той же структурой, что и любой иной блок кода. Какой смысл тогда ещё на стадии лексического анализа нам отмечать особую лексему "начало тела цикла пока", если это фактически никак не отразится на структуре АСТ?
Если в языке существуют конструкции, специфичные по синтаксису в контексте обычного блока кода и тела цикла, то это уже будет язык с КЗ-грамматикой. Но я что-то таких операций в описании языка здесь не встречал, а break и continue к ним хоть и относятся, но это, можете мне поверить, совсем не тот случай.✅ 2017/05/05 14:56, utkin #7
Но это же сколько памяти отъесть + время на загрузку этого бреда при старте? О, прям вот столько памяти. Операционка при загрузке ОЗУ выдает блоки фиксировано килобайтами или мегабайтами. Выдаст Вам в программу, например, 2 мегабайта, а Вам надо полтора. И сколько памяти тут отъедите? Да нисколько. И когда программа её высвобождает, это не значит, что прям вот она сразу высвободилась. Надо будет операционной системе — и ОЗУ заберет, и в виртуалку скинет. А если памяти много, то как она висела за программой, так и будет висеть. Можете сами провести эксперименты и убедится. Меня умиляют эти стереотипы из 80-х годов. Не забывайте, что программисты давно уже не распоряжаются ресурсами компьютера самостоятельно. Поэтому экономия на байтах такая же, как экономия на спичках и местами просто вредна.А тип элементов массива, надо полагать, однобайтовый char? Автор хочет разные языки, значит Юникод.Лексеру необязательно заглядывать вперёд. Но это очень полезно. Пишу как тот, кто писал и пишет лексические анализаторы. Даже в Вашем случае это удобно: можно начитать рекурсивно все лексемы от скобки до скобки (а не построчно) этим Вы решите половину описываемых в Ваших статьях проблем. И никакой отдельной фазы компиляции не потребуется. Про память уже писал — не экономьте на спичках. Если Вы не собираетесь компилировать на однокристальном микроконтроллере, грузите свои лексемы и заглядывайте наперед. Листья в Вашем языке маленькие (простые операторы), а ветви (блоки кода) легко раскладываются в рекурсии. Много памяти это у Вас не съест.ну кроме разве что самого отказа от АСТ :-) От синтаксического дерева сложно отказаться по той причине, что язык обладает вложенностью сам по себе. Можно, конечно, прикрываться всякой фигней типа рекурсии или таблицами, но все равно фактически это будет реализация обхода дерева. Без АСТ можно справиться только с очень простым входящим потоком, без вложенностей, как это было в первых Бейсиках или ассемблерах.В структурах АСТ тело цикла можно описать той же структурой, что и любой иной блок кода. Верно. Нужно просто для себя раз и навсегда признать, что программа это система, описываемая деревом элементов. Задача всех трансляторов (хоть компилятор, хоть интерпретатор) выполнить обход этого дерева. Когда трансляция рассматривается под таким углом зрения, многие вещи становятся простыми и понятными. В том числе и скобки. Их в таком ключе можно не считать вообще. Ошибка будет всплывать сама по себе. Добавить свой отзыв
Написать автору можно на электронную почту mail(аt)compiler.su
|