Написание интерпретатора скриптов на С++. Часть 1: Обзор.
Тянулся нудный осенний вечер; делать как всегда было нечего. И вдруг, ни с того ни с сего, пришла мне в голову идея написать статью по созданию интерпретатора. «Делать тебе нечего. – иди лучше к коллоквиуму по вышке готовься», — раздался внутренний голос. И я уже было потянулся к розетке, чтобы вырубить мой компьютер, но внезапно вспомнил. Вспомнил, как я сам писал систему обработки сценариев. Вспомнил, сколько времени, усилий и нервов было впустую затрачено на поиск исчерпывающей информации по этой теме. Вспомнил бессонные ночи, проведенные за отладкой. И еще много чего вспомнил, а потом. послал свой внутренний голос и принялся за работу.
Этот цикл статей предназначен, прежде всего, для читателя, не имеющего опыта работы в области написания интерпретаторов. Я постараюсь рассмотреть этот процесс настолько подробно, на сколько позволяют мои знания и опыт. Итак:
Тема работы: написание системы обработки сценариев на С++.
Цель работы:
1) ознакомление читателя с темой;
2) создание работоспособного интерпретатора с нуля;
3) его «внедрение» в какое-либо приложение.
Приборы и оборудование: базовые навыки владения С++, ООП и STL.
Постановка задачи:
Написание полноценного интерпретатора какого-либо языка – дело сверхтрудоемкое и для меня непосильное. Поэтому я ограничил скриптовый язык подмножеством языка Си и, следуя принципу «достижения результатов наименьшими усилиями» внес в это подмножество кое-какие изменения. Итак, вот что получилось:
Возможности языка
По существу, наша система обработки сценариев состоит из следующих основных компонентов:
— Lexer – преобразует входные данные (обычно, файл) в поток лексем (таких как ключевые слова, операторы и т.д.);
— Generator – генерирует байт код для последующего выполнения виртуальной машиной;
— Executor – выполняет байт код.
А вот наглядное изображение взаимодействия этих компонентов:
Термины и понятия:
Ниже я привожу словарь терминов и понятий, которые будут периодически использоваться в последующих статьях цикла. Все нижеперечисленные определения рассматриваются в контексте скриптов ESL.
аргумент (или параметр) – это значение, передаваемое в функцию. Например в случае вызова функции IntToStr(123) аргументов является число 123.
выражение – это то, что приводит к некоторому значению. Например, как простая переменная, так и формула (x*n-1)/y2k являются выражениями. Любое выражение можно превратить в инструкцию, добавив после него «;». Операции присваивания также являются выражениями. Примеры выражений: x, y = x, func1(), y = func1().
идентификатор – это имя, определенное в скрипте. Любое слово в программе (за исключением комментариев и ключевых слов) является идентификатором. Все имена стандартных и игровых функций также являются идентификаторами.
инструкция – базовый элемент скрипта. Пример: for(. ), if(. ), a = b;.
ключевое слово – это имя, определенное в самом ESL. Сюда не включаются имена стандартных и программных функций, которые являются идентификаторами. Примеры: if, for, end.
комментарии – строки (или части строк), содержащие игнорируемый лексером текст. Комментарии введены для пояснения скриптов. Комментарием считается текст, заключенный между «%» и концом строки. Например:
%это комментарий, находящийся справа от кода
%это комментарий, находящийся в новой строке
операнд – это подвыражение, которое при помощи операторов комбинируется в более сложное выражение. Например, в выражении x + y оператор «+» имеет два операнда x и y.
оператор – символ, определенный в ESL, при помощи которого подвыражения (операнды) комбинируются в более сложные выражения. Например +,-,*.
определение – создание новой переменной.
переменная – именованный фрагмент памяти для хранения данных. Названия переменных не должны совпадать с ключевыми словами и функциями и могут состоять из латинских или русских букв, цифр и символа подчеркивания. Пример: a, _string1_.
составная инструкция – группа инструкций, заключенных в фигурные скобки. Пример:
строка (string) – тип переменной в ESL, представляющий собой совокупность символов.
управляющая структура – это инструкция, имеющая возможность изменять ход выполнения программы на основе каких-либо условий. Управляющими структурами в ESL являются if-else, while и for.
функция – группа инструкций, исполняемая как единое целое и предназначенная для выполнения некоторых действий или получения значения. В ESL имеются стандартные (встроенные в исходный код программы ESL) и внешние (встроенные в исходный код вызывающей программы) функции. Возможность создания новых функций в скриптах (пока) отсутствует.
Уфф. кажется все. Первая, думаю самая сложная для написания, статья готова. Теперь читатель ознакомлен с общими принципами языка ESL, поэтому, следующие части будут посвящены более интересным вопросам — непосредственно реализации системы сценариев.
Готов выслушать все вопросы, предложения и критику.
Unril’s Blog
Многие C++ программисты слышали про разработку через тестирование. Но почти все материалы по данной теме касаются более высокоуровневых языков и сосредоточены больше на общей теории, чем на практике. Итак, в данной статье я попробую привести пример пошаговой разработки через тестирование небольшого проекта на C++. А именно, как можно предположить из названия, простого интерпретатора математических выражений. Такой проект также является неплохой code kata, так как на его выполнение затрачивается не более часа (если не писать параллельно статью об этом).
- Читать первую часть.
- Читать вторую часть.
- Читать третью часть.
Учебники. Программирование для начинающих.
Programm.ws — это сайт, на котором вы можете почитать литературу по языкам программирования , а так-же посмотреть примеры работающих программ на С++, ассемблере, паскале и много другого..
Программирование — в обычном понимании, это процесс создания компьютерных программ.
В узком смысле (так называемое кодирование) под программированием понимается написание инструкций — программ — на конкретном языке программирования (часто по уже имеющемуся алгоритму — плану, методу решения поставленной задачи). Соответственно, люди, которые этим занимаются, называются программистами (на профессиональном жаргоне — кодерами), а те, кто разрабатывает алгоритмы — алгоритмистами, специалистами предметной области, математиками.
В более широком смысле под программированием понимают весь спектр деятельности, связанный с созданием и поддержанием в рабочем состоянии программ — программного обеспечения ЭВМ. Более точен современный термин — «программная инженерия» (также иначе «инженерия ПО»). Сюда входят анализ и постановка задачи, проектирование программы, построение алгоритмов, разработка структур данных, написание текстов программ, отладка и тестирование программы (испытания программы), документирование, настройка (конфигурирование), доработка и сопровождение.
Си для профессионалов
Глава 6. Интерпретаторы языка
Вы когда-нибудь хотели создать свой язык программирования? Большинство программистов призывают к поиску идеи создания, управления и модификации своих языков программирования. Однако, лишь немногие программисты могут легко и непринужденно создать язык программирования. Создание полного компилятора является многообязывающей задачей, но гораздо проще создать интерпретатор языка. Методы, используемые для создания итерпретаторов языка, изучаются редко или изучаются довольно абстрактно. В этой главе на практических примерах вы будете изучать секреты интерпретации языка и грамматического разбора выражений.
Интерпретаторы важны по трем очень важным причинам. Во-первых, они могут обеспечивать удобную интерактивную среду (как доказательство — интерпретатор стандартного языка BASIC, которыми снабжаются большинство персональных компьтеров). Многие пользователи-новички находят, что интерактивная среда более удобна, чем компилятор. Во-вторых, интерпретаторы языка обеспечивают превосходные интерактивные отладочные возможности. Даже ветераны-программисты при отладке трудных программ прибегают к помощи интерпретатора языка, потому что он позволяет динамично устанавливать значения переменных и условий. В-третьих, большинство языков запросов к базе данных работают в режиме интерпретации.
В этой главе будет разработан интерпретатор для подмножества языка BASIC, который еще называют «SMALL BASIC». BASIC выбран вместо Cи, потому что BASIC легче интерпретируется, чем Cи или другой структурный язык. Интерпретатор для структурного языка, такого как Cи более труден, чем для BASIC из-за автономных функций с локальными переменными, которые обеспечивают интерпретатору многозначность. Принципы, используемые в интерпретаторе BASIC, применимы и для других языков, и вы можете использовать написанные программы в качестве отправной точки. Прежде, чем начать работу, необходимо изучить сущность языковой интерпретации, особенно перед тем, как браться за интерпетацию такого сложного языка, как Cи. Если вы не знаете BASIC, не беспокойтесь, команды используемые в SMALL BASIC очень легкие для понимания.
Мы начинаем с сердца любого интерпретатора: синтаксического анализатора выражений.
Наиболее важной частью интерпретатора языка является синтактический анализатор выражений, который преобразует числовые выражения, такие как (10-X)/23, в такую форму, чтобы компьютер мог понять ее и вычислить. В книге по языку Cи: The Complete Reference (Osborne/McGraw-uill, 1987) вступительная глава посвящена синтаксическому анализу выражений. Подобного же рода синтаксический анализ, основанный на принципах, изложенных в вышеупомянутой книге, (правда, с небольшими изменениями) будет использоваться для построения интерпретатора SMALL BASIC в данной главе нашей книги. (Так как эта глава содержит только краткие сведения о синтаксическом анализе выражений, то для более детального изучения этой проблемы советуем вам обратиться к источнику: The Compelete Reference.
Синтаксический анализ выражений является довольно сложной задачей, однако в некоторых случаях она облегчается тем, что в процессе синтаксического анализа используются довольно строгие правила алгебры. Синтаксический анализатор, описанный в этой главе, в общем может быть классифицирован как синтаксический анализатор рекурсивного спуска.
Перед тем, как приступить к детальной разработке синтаксического анализатора, вы должны иметь представление о выражениях. Поэтому наш следующий параграф посвящен именно этому вопросу.
Хотя выражения могут быть составлены в принципе из любых типов данных, в этой главе мы будем иметь дело только с числовыми выражениями. Будем считать, что для наших целей числовые выражения могут строится из следующих элементов:
Символ ‘^’ означает экспоненту, а символ ‘=’ используется как оператор присваивания, а также как знак равенства в операциях сравнения. Элементы выражения можно комбинировать согласно правилам алгебры.
Вот некоторые примеры выражений:
Что касается языка BASIC, старшинство операторов не определено. В процессе работы синтаксический анализатор присваивает операторам следующие приоритеты:
Операторы равного приоритета выполняются слева направо.
Синтаксис языка SMALL BASIC предполагает, что все переменные обозначаются одной буквой. Это позволяет оперировать в программе двадцати шестью переменными (буквы от A до Z). Хотя интерпретаторы языка BASIC поддерживают обычно большее число символов в определении переменной, (например, переменные типа Х27), но для простоты изложения основных принципов построения интерпретаторов наш интерпретатор языка SMALL BASIC этого делать не будет. Будем считать также, что переменные разных регистров не отличаются друг от друга и, поэтому, переменные «a» и «A» будут трактоваться как одна и та же переменная. Условимся, что все числа являются целыми, хотя вы без особого труда можете написать
программы для манипулирования другими типами чисел. Хотя
символьные переменные в нашей версии языка и не поддерживаются,
будем считать, что возможен вывод ограниченных символьных
констант на экран в виде различных сообщений.
Итак, будем строить синтаксический анализатор исходя из перечисленных выше допущений. Теперь давайте рассмотрим такое базовое понятие теории синтаксического анализа как лексема.
Перед тем, как построить синтаксический анализатор, разбирающий значения выражений, вы должны иметь несколько вариантов разбиения строки, содержащей выражение, на составляющие части. Например, выражение
содержит компоненты «А», «*», «В», «-«, «(«, «W», «+», «10» и
«)». Каждый компонент представляет собой неделимый элемент
выражения. Такой компонент или независимая часть выражения
называется лексемой. Функция, разбивающая выражение на составные
части, должна решать четыре задачи: (1) игнорировать пробелы и
символы табуляции, (2) извлекать каждую лексему из текста, (3)
если необходимо, преобразовывать лексему во внутренний формат,
(4) определять тип лексемы.
Каждая лексема имеет два формата: внешний и внутренний. Внешний формат — это символьная строка, с помощью которой вы пишите программы на каком-либо языке программирования. Например, «PRINT» — это внешняя форма команды PRINT языка BASIC. Можно построить интерпретатор из расчета, что каждая лексема используется во внешнем формате, но это типичное решение проблемы программистом-непрофессионалом, который лишь два часа назад оторвался от материной юбки и час назад увидел настоящий компьютер. Настоящие мужчины ориентируются на внутренний формат лексемы, который является просто числом, и разрабатывают интерпретаторы исходя из этой профессиональной точки зрения на проблему. Поясним этот подход. Например, команда PRINT может иметь порядковый внутренний номер 1, команда INPUT — 2 и т.д. Преимущество внутреннего формата заключается в том, что программы, обрабатывающие числа, более быстродействующие, чем программы, обрабатывающие строки. Для реализации такого подхода необходима функция, которая берет из входного потока данных очередную лексему и преобразует ее из внешнего формата во внутренний. Помните, что не все лексемы имеют разные форматы. Например, операторы не подлежат преобразованию потому, что они могут трактоваться как символы или числа в своих внешних форматах.
Очень важно знать, какой тип лексемы возвращен. Например, анализатору выражений необходимо знать, является ли следующая лексема числом, оператором или переменной. Значение типа лексемы для процесса анализа в целом станет очевидным, когда вы приступите непосредственно к разработке интерпретатора.
Функция, которая возвращает следующую лексему в выражении, называется get_token( ). Она работает из расчета того, что в языке SMALL BASIC, программа хранится как одна строка, ограниченная в конце символом завершения строки (