История одного лексического анализатора

В данной статье будет рассмотрено самостоятельное построение лексического анализатора (далее ЛА). В нем нуждаются как начинающие программисты (желая получить больше свободы и писать так, как вздумается), так и опытные (с целью поддержки собственных API, создания скриптов)…

by Utkin utkin295@yandex.ru

Зачем это надо

Лексический анализатор – самостоятельная программа (или ее фрагмент), реализующая функцию лексического анализа. Лексический анализ – это разложение и преобразование входящего текста на определенные последовательности символов (не обязательно текстового представления), именуемые токенами. Каждый токен – это последовательность символов (не обязательно текстовых), однозначно характеризующих лексему. Лексема – это последовательность символов и слов, однозначно определяющих какую-либо составляющую языка.

Немного проясним ситуацию. Предста- вим, что имеется определенный язык (нам ближе язык программи- рования), хотя его назначение на данном этапе роли не играет. Пусть Паскаль. Вот фрагмент записи:

Этот фрагмент программы ответ- ственен за организацию цикла. Транслятору важно знать, когда кончается слово for и начинается переменная i. Таким образом, он дробит указанную строчку на лексемы: for, i, to, :=, 0, 100. Они определяют ключевые слова, имена переменных, числа и т.д. Однако внутри программы хранить данные в виде записи неудобно и медленно. Примем обозначения: для ключевых слов будем использовать букву k с числовым индексом, однозначно определяющим ключевое слово. Для имен переменных – букву n, для знаков операций – букву o, для чисел же – букву x.

Теперь мы имеем следующую последовательность: k1, n1, o1, x1, k2, x2, k3. Это и есть таинственные токены. Иногда, особо дотошные и ответственные трансляторы кодируют и разделители между лексемами, но, на мой взгляд, такая информация является избыточной. А уже оперируя токенами, можно проверить порядок их следования и осуществлять поиск логических ошибок. Иными словами, лексический анализатор – это средство, с помощью которого осуществляется разбор операторов языка программирования (в нашем случае).

Как это было сделано

Стандартная мето- дика работы сле- дующая: берется сплошной поток символов, разби- вается на токены, анализируется, и (в зависимости от типа транслятора) выполняются пос- ледующие дейст- вия – компиляция либо исполнение. Но, как это обычно бывает, современные тех- нологии ушли далеко вперед, а методы преподносятся те же самые. Более того, сухое изложение теории данного вопроса совершенно не способствует появлению интереса в глазах студентов. Здесь же мы рассмотрим лексический анализатор, полученный немного другим способом.

Сначала выработаем некое множество абстрактных языков, с которыми будет работать наш лексический анализатор. Это важно, так как, в конечном счете, все лексические анализаторы имеют ограничения и способны работать только под контролем жестких запретов, наложенных многочисленными правилами (грамматикой) языка. Итак, наш язык программирования, в целях упрощения изложения, предполагает построение по строковому принципу – иными словами, одна строка может содержать только одну команду.

Действительно, работать с потоком символов неудобно (но быстрее), в то же время имеется большое количество классов, ориентированных на работу с наборами строк. Кроме того, наличие нескольких команд в одной строке было вызвано историческими причинами: ранние редакторы были экраноориентированными, и большое количество строк являлось непозволительной роскошью. В то же время, мы не стеснены обязательствами совместимости с предыдущими версиями нашего языка. Далее введем такой термин, как конструкция. Конструкция – это символьное представление команды языка программирования. Казалось бы, зачем такое усложнение концепций? Но мы ведь не собираемся отставать от современных технологий и будем равняться на .Net (конечно, условно). Здесь для нас важнейшей чертой .Net является многообразие языков программирования, выполняющих по сути одну и ту же работу (возможно, с разных точек зрения, – сейчас это не принципиально). Хоть С#, хоть Дельфи с приставкой .Net – все они различны внешне, но построены на одной платформе, и это чувствуется, несмотря на различный синтаксис. Именно с целью легкой смены синтаксиса и вводится термин «конструкция». Итак, общий вид конструкции языка программирования у нас следующий:

Таким образом, в конструкции может быть не более восьми лексем. Здесь следует оговориться: разделители лексемами не являются (в других языках это может быть не так). Практика показывает, что восьми лексем хватает для кодирования подавляющего большинства команд языка. Большее количество лексем избыточно и ведет к затруднению восприятия (но, естественно, после усвоения принципов построения лексических анализаторов каждый может подобрать оптимальное количество лексем самостоятельно) и уменьшает скорость работы анализатора. Наши лексемы представлены либо частью команды, либо командой, либо выражениями нескольких видов (последнее не оговаривается: разбор выражений – это другая большая тема). Так что все упоминания переменных и чисел относятся к выражениям. Сама команда может рассматриваться как комбинация служебных слов (в некоторых источниках литературы их называют ключевыми) и параметров. Тот же пример с циклом в новом свете выглядит так:

И к тому же содержит пять лексем. То есть нужно учитывать тот факт, что команда не обязательно занимает все восемь лексем, а может и меньше (но не больше, иначе наш лексический анализатор будет непригоден). Теперь идентификатор, если хотите, можно с натяжкой назвать токеном http://ru.wikipedia.org/wiki/Токен, но токеном глобальным.

Он отвечает не за конкретную лексему, а за всю команду. Это вполне естественно: если в строке может быть только одна команда, то ее можно условно обозначить определенным числом. Нет смысла на каждый кусок конструкции заводить свое число. Достаточно помнить саму команду (в виде числа) и ее параметры. Теперь поле Remark – это просто описание команды, которое можно, например, выводить во всплывающей подсказке при наведении на команду (что полезно начинающим), в скриптах или в языках программирования, ориентированных на предметные области (математика, физика, бухгалтерия и т.д.). Это описание одной конструкции языка. Соответственно, чтобы описать весь язык, нужен массив таких вот записей. Это несложно, но есть нюансы: в описание команды нужно запихнуть параметры, а также учесть строковые константы (если они будут в языке). Первое решается просто и универсально, место, где должен находиться параметр, будем обозначать цифрой от 1 до 8 (зачем – объясню немного ниже). А вот со строковыми константами нужно объясниться. Дело в том, что в них может содержаться фрагмент текста, внешним видом сильно напоминающий конструкцию. Конечно, такая ситуация редка и в ряде языков просто невозможна, но мы ведь не ищем легких путей. Поэтому, чтобы лексический анализатор был максимально независим от остальной реализации программы, нам нужно знать как минимум признак строковой константы (для Паскаля это текст между апострофами).

То есть если, к примеру, встретилась строка for i:=’ to ‘ do, лексический анализатор должен сразу определить, что перед ним не операция, обозначающая цикл, а нечто совершенно другое (а именно for параметр1 do).

Теперь, как и обещал, немного подробнее рассмотрим кодирование параметров. Для начала покажем, как мы будем представлять параметры внутри лексического анализатора:

Здесь все просто, потому что, по сути, лексическому анализатору параметры конструкции абсолютно не нужны – они требуются далее, при трансляции кода. Мы не будем обрабатывать данные параметры (в подавляющем большинстве случаев это математические выражения), а просто предоставим возможность их получения из лексического анализатора. Теперь вернемся к цифрам. Они обозначают соответствующий индекс от 1 до 8. Это нужно для придания универсальности лексическому анализатору: как уже было сказано выше, синтаксис для нас – вещь условная, и мы будем строить код таким образом, чтобы иметь возможность сменить синтаксис любой конструкции (то есть ключевым полем для лексического анализатора является идентификатор конструкции). Сейчас продемонстрируем это, представив следующую ситуацию. Имеется среда разработки, поддерживающая, помимо стандартов языка Паскаль, также и его русскоязычный вариант. Примером может служить известная многим серия бухгалтерских программ от фирмы 1С: в них используется язык программирования, в котором команды записаны как на латинице, так и на кириллице.

Оставим вопрос эффективности такого подхода: для нас важна самая возможность, факт существования такого явления. Поэтому в нашем примере мы наряду с латиницей будем использовать и конструкцию, выраженную в национальном алфавите. Итак, в нашем примере появляется вторая конструкция цикла:

Переведем это во внутреннее представление лексического анализатора:

Присвоим нашим конструкциям идентификаторы. Поскольку это, по сути, одна и та же команда, то идентификатор у них будет общий:

Вот тут хитрые циферки нам и потребуются: это адреса в TConstrParam, куда и будут перенесены параметры. Таким образом, после распознавания строки будет получен идентификатор (единица) и скопированы параметры, но так, что, независимо от конструкции, каждый параметр будет находиться строго на своем месте. Далее транслятор, получив идентификатор, уже «знает», что переменная цикла и инициализирующее значение находятся в TConstrParam.Param[1], а верхнее значение, до которого должны производиться итерации, – в TConstrParam.Param[2], хоть в первом, хоть во втором случаях. Остальные параметры будут просто пустыми строками. То есть единственное, что требуется, – это выработать соглашение для транслятора, чтобы согласовать идентификаторы. Вот, к примеру, цикл – 1, условие – 2, математическое выражение – 3 и т. д. Соответственно, нужно решить, при каком идентификаторе, какой параметр, на каком месте находится. И все это независимо от обозначения самой конструкции во входящем тексте программы.

Промежуточные итоги вышесказанного:

• мы можем создавать различные конструкции, выполняющие одни и те же функции;
• мы можем менять порядок следования параметров в некоторых пределах без перестройки транслятора;
• поскольку описание всех конструкций – есть записи, состоящие из простых полей, мы можем их сохранять и считывать из внешних источников – файлов, получать по сети, генерировать во время работы и т.д., и все это прямо время работы транслятора;
• имея четкое и простое внутреннее представление, мы можем подготавливать различные отчеты по своему языку, например, автоматически генерировать форму Бэкуса-Наура (форма описания синтаксиса языка программирования);
• при определенной сноровке мы можем описывать синтаксис, выражение которого обычными средствами трудно, либо невозможно.

Однако на этом полезности нашего лексического анализатора не заканчиваются. Многие языки программирования вводят так называемый синтаксический сахар – это различные представления одного и того же механизма. Эффекта от них немного, но это просто удобно для восприятия человеком. В частности, наши двойные конструкции – на латинице и на кириллице – уже сам по себе синтаксический сахар, поскольку новых возможностей, позволяющих эффективнее решать задачи, программист не получил. Но представим, что после жарких дебатов было решено ввести еще одну конструкцию цикла, так как это ближе к аналогичным реализациям у конкурентов.

Например, русскоязычным вариантом Паскаля является язык программирования Глагол, наименование конструкций в котором по большей части является прямым переводом слов с английского языка. Старые же конструкции, в силу совместимости с прошлыми версиями, мы выкинуть не можем. Кроме того, не всем понравилась конструкция с переменной в конце команды, а не в начале, как это заложено в традиционном Паскале.

Чтобы отвечать всем требованиям, введем еще пару конструкций:

На самом деле, чрезмерное обилие конструкций, выполняющих одно и то же действие, может приводить к путанице, но только в случае их безграмотного обозначения (что у нас и наблюдается). Но для нашего учебного примера подойдет и такой образец того, «как делать не надо».

Теперь взглянем на это с другой стороны – с позиций лексического анализатора. Каждая конструкция есть соответствующая строчка в массиве конструкций, которые перебираются до тех пор, пока не будет найдено совпадение строки с образцом. Процесс разбора строки есть занятие трудоемкое, и производится он каждый раз заново, пока не будет найден нужный элемент либо пока весь массив не будет просмотрен до конца (в таком случае возвращается специальный идентификатор – неизвестная конструкция). Изменить же такой порядок (в смысле разложения строки на составляющие) не представляется возможным: требуется кардинальная перестройка алгоритма, и не факт, что новый вариант будет производительней (а для нас немалую значимость представляет и простота внутреннего устройства).

Поэтому возникла идея объединять похожие конструкции. Взгляните на последние две: они отличаются только одним словом – почему бы их не рассматривать одновременно, как одну строку?

Для этого в лексическом анализаторе есть соглашение: если в лексеме есть слово, содержащее пробел, то это два слова (соответственно, сколько пробелов, столько слов плюс еще одно):

Сам пробел все равно в конструкциях участвовать права не имел, так как является разделителем между лексемами. При разборе строки конструкция будет засчитана, если первое слово Цикл или Для, и далее осуществляется соответствие остальным лексемам конструкции. То есть строка будет разобрана в цикле на один раз меньше, что в целом ускоряет работу лексического анализатора (альтернативное направление – правильное расположение конструкций в массиве, чтобы часто используемые конструкции находились в начале массива).

Это совсем не излишество еще и по другой причине. Наш лексический анализатор заточен не только на классические языки программирования, но и на лексический анализ в целом. Это дает ему и другие сферы применения, например, использование в качестве составляющей бота, как для сканирования страниц на предмет наполнения определенным контентом (не по ключевым словам, которые могут завлекать случайных прохожих на сайты, содержащие совсем другую тематику), так и в роли робота, общающегося в чате с посетителями, не могущими отличить настоящего человека от программы.

Кроме того, можно из пушки стрелять по воробьям, а именно – заниматься парсингом* различных табличных отчетов, логов и другим.

Особенности реализации

Лексический анализатор представлен в виде класса, что дает программам, его использующим, большую гибкость:

Пользование готовым лексическим анализатором никаких хлопот не доставляет, тем более что он хорошо документирован в виде комментариев к коду. Добавление конструкций в их набор (по сути, описание языка) осуществляется в виде строки, где каждое поле отделено символом табуляции. Сделано это также для простоты и для последующей возможности сброса конструкций в текстовый файл CSV формата (поля разделяются определенным символом). Сам класс анализатора сохранять и читать в файл не умеет (для придания универсальности), но умеет это делать в список строк TStringList, где список конструкций можно обработать либо просто сохранить напрямую. Читать из набора конструкции можно также в виде строк. Самая главная и ответственная функция здесь GetID, которая в цикле сравнивает строку с конструкциями посредством самой хитрой и интересной функции CompareStrId. Последняя совсем не проста, она разлагает строку с учетом многих параметров: количество лексем в конструкции, порядок следования параметров, наличие в строке строковых констант и т.д. Также в секции protected содержится ряд довольно-таки мощных вспомогательных функций по обработке строк, которые обязательно понадобятся для обработки строк.

Теперь касательно лексем

В лексемах запрещены символы табуляции (поскольку вы не сможете правильно сохранить и прочесть данную конструкцию в последующем), символы пробела (они являются разделителями служебных слов внутри лексем), любые самостоятельные целые числа (так как они обозначают местоположение параметров, но разрешены, например, шестнадцатеричные) и символ апострофа, как признак текстовой константы (в данный момент это жестко прописано в лексическом анализаторе, но можно исправить в функции GetEnd), да и перевод строки тоже не желателен, хотя и возможен при определенных манипуляциях со TStringList. Зато все остальное, включая непечатные символы, вполне допустимо. Это позволяет использовать такие конструкции, использование которых при традиционных лексических анализаторах невозможно: многократное использование точечной нотации (как для определения структур данных, так и для определения конструкций), скобочной нотации и т.д. Возможно это потому, что лексический анализатор не выделяет токены лексем, в час- тности, разделителей (скобки, точки, запятые и прочие спецзна-ки). При правильной расстановке конструкций в наборе допускается использование и арифметических знаков в составе лексем конструкций. Все это ведет к более широкому использованию контекстно зависимых грамматик (для справки: на данный момент большинство языков программирования подчиняется усеченному множеству контекстно зависимых грамматик – контекстно свободным грамматикам), что позволяет писать программы на языках, более приближенных к естественным (это приводит к уменьшению числа логических ошибок в программах). В целях упрощения работы с лексическим анализатором лексемы (но не параметры) сравниваются со строкой без учета регистра (кому интересно, может это исправить самостоятельно).

Заключение

Данный пример, хоть и представляет вполне рабочий лексический анализатор, все же является учебным. Однако на нем вполне можно построить, например, интерпретатор. Читателям, в качестве самостоятельных занятий, рекомендуется для лучшего закрепления знаний о лексическом анализаторе написать интерпретатор без посторонней помощи. Дам единственную подсказку: следует серьезно отнестись к разбору математических выражений либо использовать уже имеющиеся (либо адаптировать иные компоненты, например TParser). Что касается простых скриптов, то лексический анализатор уже сейчас можно использовать для этих целей. Например:

И так далее. Сам скрипт мог бы выглядеть так:

Согласитесь, такой скрипт использовать приятней, чем, скажем, .DFM файл или ему аналогичный. Обработку можно осуществлять по идентификатору через case of. А на вход лексического анализатора желательно также подавать обработанные строки, так как, например, строка х=у+1 будет неопределенной, в то время как х = у+1 легко определяется. Все упомянутые в статье исходные коды и тестовый проект приведены в виде ресурсов в теме «Журнал клуба программистов. Седьмой выпуск» или непосредственно в архиве с журналом.

Ресурсы