Лексема что это в программировании
Важно отметить, что препроцессор не знает синтаксиса С.
2.3.2. Пространство между лексемами
Пространство между лексемами определим как множество символов (пробелы, вертикальные и горизонтальные табуляции, символы перевода строки, комментарии), которые игнорируются при трансляции. Эти символы могут служить для определения начала или конца лексемы, но в процессе трансляции они удаляются.
Например, рассмотрим две последовательности: int i; int j;
и
int i;
int j;
2.3.3. Запись длинных строк
Для записи длинных строк символов используется обратная косая черта (\). Она ставится в конце строки. Обратная косая черта и символ перевода строки игнорируются, две строки (и более) воспринимаются как одно целое. Например: “Томский государственный\ университет систем управления\ и радиоэлектроники”
Здесь записана одна длинная строка символов.
2.3.4. Комментарии
Комментарии представляют собой фрагменты текста, предназначенные для записи пояснений. Комментарии предназначены для программистов, которые будут читать исходный текст. Комментарии в процессе трансляции программы игнорируются. Комментарии можно записать двумя способами. В первом способе комментарий открывается парой символов /*, а закрывается символами */. Например: int /* объявить */ i /* счетчик */ ;
В процессе трансляции будет получено всего три лексемы: int, i, ;
Второй способ записи комментария в С++ состоит в записи двух подряд символов «косой черты» (//). Комментарий начинается от этих символов (//) и заканчивается символом перевода строки. Например: class X // это комментарий;
. ;
Следует быть осторожным в использовании /* и // одновременно. Это может привести к нежелательным последствиям. Например: int i = j //* разделить на k */k;
+m;
Введение в теорию компиляторов: лексический анализ языка Pascal средствами C#
Введение
В последнее время большинство новичков в программировании начинают с высокоуровневых языков, таких, как Java, Python, C#, или любой другой язык, содержащий в себе “джентльменский набор” в виде сборщика мусора, готовых структур данных и так далее. Конечно, такой подход имеет свои плюсы, но, как правило, начинающий разработчик, использующий готовый функционал языка, упускает самое главное – его устройство и механизмы работы и имплементации.
Я не буду вдаваться в подробности распределения памяти и способы интерпретации кода, а наоборот, хотелось бы поговорить о самом устройстве компилятора, а именно о лексическом анализаторе и попробовать реализовать его на языке C#. Язык, который мы будем анализировать, знает подавляющее большинство — это Pascal.
Лексический анализатор – первый из “слоев” компилятора, отвечающий за выделение лексем для последующей обработки.
Лексема – минимальная единица некоего словаря, представляющего наш язык. В роли лексемы могут служить служебные слова, операторы, идентификаторы и так далее.
Реализация
Описание структуры
Формальное описание языка будет храниться в двух массивах: в первом — служебные слова, а во втором — ограничители и список с найденными лексемами
Сама лексема будет в себе хранить ключ, с помощью которого будет определяться принадлежность к типу (служебные слова, операторы, идентификаторы, числа), id лексемы и само значение.
Наилучшим решением для обработки лексем будет служить некий конечный автомат. Это позволит избавиться от лишних if-ов, а также даст возможность легко вносить изменения в цикл. S — начальное состояние, NUM, DLM, ASGN, ID — состояния соответствующих видов лексем, ER будет использоваться для ошибки, а FIN для конечного состояния.
Основными методами являются SearchLex, который ищет лексему в нашем массиве и возвращает ее id и значение в кортеже (да, кортежи тоже бывают полезными), а также PushLex, который добавляет новую лексему в словарь.
Реализация алгоритма
Первым делом стоит определить конец работы цикла — состояние FIN, а также реализовать начальное состояние, которое будет
Метод GetNext позволяет получить следующий символ в строке, ClearBuf, соответственно, очищает буфер, хранящий в себе лексему
Особое внимание стоит уделить оператору присваивания «:=», который состоит из двух отдельных операторов. Самым простым способом определения данного оператора является добавление условия и запись промежуточного значения в буфер. Для этого было реализовано отдельное состояние ASGN (в переводе assign — присваивание). В случае определения буфера как «:», алгоритм просто добавит новую лексему, а если следующим знаком является «=», то будет добавлен уже один оператор присваивания.
Конечное состояние и состояние с ошибкой реализованы только служебными сообщениями. Можно доработать данный вариант и проверять также ошибку, но, пожалуй, данный функционал можно перенести уже в синтаксический анализатор.
Тестирование
Протестировать алгоритм можно по-разному: указать напрямую путь .pas файла, программно создать строку или любой другой удобный вариант. Так как мы пишем на C#, не составит труда добавить форму в приложение, на которой будет 2 textBox-а, первый для ввода кода программы, второй — выводит результат работы алгоритма.
По нажатию кнопки будем запускать анализ текста, а полученный результат будем обрабатывать с помощью switch конструкции: дополнительно выведем к какому типу относится найденная лексема.
Входные данные
Выходные данные
Полный алгоритм
Заключение
Может показаться, что лексический анализатор штука не очень понятная, да и собственно не очень важная. Почему нельзя вынести все это в синтаксический анализатор? Как работать со сложными конструкциями? Да, способы реализации лексического анализатора разнятся от компилятора к компилятору, но при разборе всех этих принципов появится не только понимание работы языка программирования X, но и появится фундамент для разработки собственного языка программирования: второй Python, или язык для вашей предметной области — все это можно реализовать при понимании всех специфик работы и устройства компилятора в общем виде.
Основы конструирования компиляторов. Лексический анализ на C#
Задачей лексического анализа является разбить входную последовательность (в моем случае код на языке «Паскаль») на слова и лексемы.
Для начала я создал 5 типизированных листов для хранения данных, а именно: идентификаторов, констант, ключевых слов, разделителей и свертки. Также необходим массив разделителей
и массив ключевых слов. Я ограничился одиннадцатью ключевыми словами, так как статья написана как начальный пример реализации лексического анализа языка «Паскаль» на языке C#.
Итак, массив ключевых слов:
В цикле for берем последовательно каждый символ из AllTextProgram и отправляем его в метод Analysis. Отдельно я рассматриваю лишь два исключения. Первое – это апострофы, которые в моем случае встречаются при использовании ключевого слова «writeln». Если встречаем апостроф, то отходим от правил и идем по переменной AllTextPorgram, пока ни найдем второй апостроф. Второе – это комментарии в программе. Для последних я просто считаю число открывающихся и закрывающихся фигурных скобок и ожидаю пока разница ни будет равна нулю.
Казалось бы программа должна зациклиться, если последующий апостроф не найден или кол-во фигурных скобок не равно 0. Да, это верно, в этих циклах необходимо добавить дополнительные условия выхода из проверки. Эти условия для систематизации я решил сделать на этапе синтаксического анализа.
Переменная type отвечает за номер таблицы, к которому относится лексема.
Идентификаторы – таблица 1
Константы – таблица 2
Ключевые слова – таблица 3
Разделители – таблица 4
Теперь настало время поговорить что же происходит в методе Analysis. Это лучше сделать в виде комментариев к коду. Сразу отмечу, что в переменной temp будем хранить промежуточный результат работы, пока ни встретим разделитель. Встретив разделитель, нам необходимо отправить переменную temp в метод Result, чтобы определить к идентификатору, константе или ключевому слову относится нынешняя лексема.
Заключительным для рассматрения является методе Result, где мы определяем, что же мы нашли. В самом начале проверяем переменную temp на принадлежность к ключевым словам. Проверяем в начале, чтобы не перепутать найденную лексему с идентификатором. Если найденное не является ключевым словом, то через switch проверяем тип таблицы, определенный заранее в методе Analysis. Не зыбываем проверить, чтобы найденный идентификатор/константа/разделитель уже не значился в таблице.
И легкий пример, чтобы показать как это все работает.
На входе программа:
Лексемы
Алфавит языка
Лекция1 Состав языка
Вводятся базовые для всего дальнейшего изложения понятия: из каких простейших «кирпичиков» состоят все тексты на языке программирования, что понимают под типом данных, какие встроенные типы данных есть в языке C++.
Все тексты на языке пишутся с помощью его алфавита. Алфавит C++ включает:
Из символов базового набора составляются лексемы языка и директивы препроцессора. Символы из набора реализации используются для написания комментариев. Компилятор комментарии игнорирует.
Существуют следующие виды лексем:
Границы лексем определяются другими лексемами, такими, как разделители или знаки операций.
Лексемы языка программирования аналогичны словам естественного языка. Например, лексемами являются константа 128 (но не ее часть 12), имя Vasia, ключевое слово goto и знак операции сложения +. Из лексем составляются выражения и операторы.
Каждый элемент языка определяется синтаксисом и семантикой. Синтаксические определения устанавливают правила построения элементов языка, а семантика определяет их смысл и правила использования.
Объединенная единым алгоритмом совокупность описаний и операторов образует программу.
Создание языка программирования с использованием LLVM. Часть 1: Введение и лексический анализ
Добро пожаловать в учебник «Создание языка программирования с LLVM». Этот учебник знакомит вас с созданием простейшего языка программирования, и при этом показывает, каким оно может быть легким и интересным, а также даёт вам начальные знания, которые вы затем сможете применить на других языках программирования. Код в этом учебнике также может быть использован в качестве стартовой площадки для ваших творений с помощью LLVM.
Целью данного учебника является постепенное представление нашего языка, описание его пошагового создания. Это позволит нам охватить достаточно широкий спектр вопросов проектирования языков и использования LLVM, попутно показывая и объясняя код без огромного количества ненужных деталей.
Полезно отметить заранее, что этот учебник действительно обучает некоторым техникам компиляции и специфике LLVM, но не обучает современным принципам разработки программного обеспечения. На практике это означает, что мы будем использовать максимально упрощённые и сокращённые решения, чтобы упростить изложение. Так, например, код работы с памятью повсюду использует глобальные переменные, не используя прекрасные шаблоны проектирования, такие как Visitor и другие — это не лучший способ, но зато это очень просто и понятно. Если вы разбираетесь в коде и используете его в качестве основы для будущих проектов, то исправление таких недостатков не будет для вас проблемой.
И ещё кое-что: мы ждём от вас, что вы будете расширять язык и играть с ним по своему усмотрению. Возьмите код и начинайте неистово программировать, сойдите с ума, компиляторы не должны вас пугать — ведь это так весело — играть с языками!
Язык Kaleidoscope
Этот учебник проиллюстрирует игрушечный язык программирования, который мы назвали «Kaleidoscope» (название происходит от трёх греческих слов: «красивый», «вид» и «смотрю, наблюдаю»). Kaleidoscope является процедурным языком, что позволяет определять функции, использовать условия, математику и т.д. В ходе изучения мы расширим Kaleidoscope для поддержки конструкций if/then/else, циклов, пользовательских операторов, JIT-компиляции с простым консольным интерфейсом и т.д.
Для простоты в Kaleidoscope есть только один тип данных — 64-битное число с плавающей точкой (как «double» в языке C). Таким образом, все значения — это действительные числа двойной точности и язык не требует объявления типов. Это делает язык очень красивым и упрощает синтаксис. Например, следующий простой пример вычисляет числа Фибоначчи:
Мы также позволили Kaleidoscope вызывать стандартные библиотечные функции (LLVM JIT делает это вполне тривиальным). Это значит, что вы можете использовать ключевое слово «extern» для объявления функции перед её использованием (это также полезно для взаимно рекурсивных функций). Например:
Более интересный пример приведён в Главе 6, где мы напишем на Kaleidoscope небольшое приложение, которое отображает множество Мандельброта в разных степенях приближения.
А теперь погрузимся в реализацию этого языка!
Лексический анализатор
Когда дело доходит до реализации языка программирования, первое, что необходимо, так это способность обрабатывать текстовый файл и распознавать в нём код. Традиционный способ сделать это состоит в использовании «лексического анализатора» (или «сканера»), для разбития входного потока на «токены». Каждый токен возвращаемый лексическим анализатором включает единицу кода и потенциально некоторые метаданные (например, числовое значение). Во-первых, мы определим возможности:
Каждый токен, возвращаемый нашими лексическим анализатором будет либо одним из значений перечисления Token или это будет «неизвестное» вроде символа «+», которое возвращается в качестве значения ASCII. Если текущий токен является идентификатором, то глобальная переменная IdentifierStr содержит имя идентификатора. Если текущий токен является числовым литералом (например, 1.0), NumVal содержит его значение. Обратите внимание, что мы используем глобальные переменные для простоты, но это далеко не лучший выбор для реального применения :).
Фактически, наш лексический анализатор реализован одной функцией с именем gettok. Функция Gettok при вызове возвращает следующий токен из стандартного потока ввода. Её определение начинается так:
gettok вызывает C-функцию getchar(), чтобы читать символы по одному из стандартного ввода. Она распознает их и сохраняет последний прочитанный символ в LastChar, но не обрабатывает. Первое, что она должна делать — это игнорировать пробелы между лексемами. Это достигается в вышеприведённом цикле.
Следующее действие gettok — это распознание идентификаторов и специальных ключевых слов, таких как «def». Kaleidoscope делает это с помощью этого простого цикла:
Обратите внимание, что этот код собирает глобальную переменную «IdentifierStr», пока анализирует идентификатор. Кроме того ключевые слова языка проверяются в этом же цикле. Для численных значений всё аналогично:
Это довольно простой код для обработки входных данных. При чтении числового значения, мы используем C-функцию strtod для преобразования его в числовое значение, которые мы сохраняем в NumVal. Отметим, что здесь не происходит достаточной проверки ошибок: значение «1.23.45.67» будет считано и обработано так, как если бы вы ввели в «1.23». Вы легко можете дополнить код проверкой на подобные ошибки :). Теперь разберёмся с комментариями:
Определив комментарий, мы пропускаем символы до конца строки, а затем возвращаем следующий токен. Затем, если ввод не совпадает с одним из указанных выше случаев, то это либо оператор вроде «+», либо конец файла. Они обрабатываются этим кодом:
При этом, мы имеем полноценный лексический анализатор для языка Kaleidoscope (полный листинг кода лексического анализатора доступен в следующей главе из учебника). Дальше мы разработаем простой синтаксический анализатор, который используем для построения Abstract Syntax Tree. Затем мы сможем использовать лексический и синтаксический анализатор вместе.