Войти
Уголок tool-программСтатьи

Унифицированный скриптовый движок с настраиваемой грамматикой

Автор:

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

Для кого предназначена эта статья
Зачем оно надо
Краткий обзор структуры компилятора
  Итоги обзора
Немного лирики
Лексический анализатор
Синтаксический анализатор
  Еще немного лирики…
Получаем данные
Получаем варианты обработки синтаксической цепи
Нотификатор обработки скрипта
Хватит теорий!
Заключение

Для кого предназначена эта статья

Эта статья предназначена, в основном, для новичков, малознакомых с проблемами реализации различных интерпретаторов. В ней я коснусь некоторых основных проблем, а также опишу свою идею унификации грамматического интерпретатора. Основные термины я буду вводить и объяснять по ходу статьи, но было бы не лишним зайти на http://ru.wikipedia.org и поискать там следующие термины: Иерархия Хомского, Нотация Бэкуса-Наура, Лексема, Токен, Синтаксис. Некоторые определения, данные мной отличаются от классических, и будут действовать только в рамках данной статьи. К статье прилагаются исходные коды написанной мной библиотеки. Ограничений на использование нет. Вначале класс для работы со строками: String.zip. А вот и сама библиотека: UniScript.zip.

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

Итак, вы пишете очередной игровой движок в надежде сделать на его основе самую крутую игру всех времен и народов и заработать на ней миллион баксов :). Перед вами как всегда встает куча проблем, одной из которых является хоть какое-то подобие открытой архитектуры, принципа Data-Driven и прочего. Думаю, всем давно уже известно, что чем универсальнее некоторый кусок кода вашего движка, тем больше шансов на его повторное использование и тем гибче становиться сам код. У меня нет желания распространяться по поводу того, зачем вообще нужны скрипты, уверен, вам это прекрасно известно, ну а если нет, то эта статья не для вас. По поводу принципа Data-Driven: Разумеется, никто не хочет зашивать в код управление персонажем, также никому не хочется писать кучу дополнительных утилит для, ну скажем, создания и редактирования материалов, создания пользовательского интерфейса. Эти и подобные им задачи решаются путем настройки соответствующих конфигураций. В больших проектах это крайне спорный вопрос, и там обычно пишут большущие редакторы, сохраняющие конфиги в бинарный формат, однако, для какой-нибудь шаровары вполне достаточно создать простой текстовый файл со всеми настройками.

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

1) Широту настроек игры почти всегда удобнее сохранять в текстовом формате.
2) Многие при экспорте моделей и сцен из 3ds Max’а активно используют поле пользовательских настроек для задания объекту или сцене специфических свойств. Отсюда требование к экспортеру, чтобы он распознавал текст, содержащийся в этом поле.
3) Если используется единая система материалов, то их иногда также удобно хранить как текстовые конфигурации.
4) Еще может понадобиться игровая консоль. Та ее часть, где пользователь может ввести текстовые команды – чем не скрипт?
5) Собственно, сами скрипты, игровые сценарии, у некоторых AI видел на скриптах и т.д.

И вот тут-то перед нами и встает другая проблема: Что, если в проекте используются все вышеперечисленные пункты? Ведь каждый из них требует своей строго определенной грамматики, синтаксиса, наконец, логики выполнения. Будем писать 5 разных интерпретаторов? Что-то неохота…. :) Лучше написать один, который будет работать со всеми грамматиками. Но выполнима ли такая задача? Чтобы ответить на этот вопрос, нам предстоит понять, как можно описывать грамматику различных языков, но для начала посмотрите, из чего состоит любой полноценный компилятор.

Краткий обзор структуры компилятора

Изображение

Лексер. Изначально загруженный текст скрипта представляет собой поток отдельных символов. Дабы облегчить анализ текста, нам нужно преобразовать его в поток чего-то более осмысленного. Один символ ничего для нас не значит. Зато значение имеет ключевое слово, строка, число и что-то еще. Поэтому то, что нам сейчас нужно – это распознать в тексте все эти элементы. Это и делает лексер.

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

Синтаксический анализатор. Итак, теперь у нас есть поток «слов» нашего языка – лексем (смотри определение ниже). Но этот поток все равно не помогает понять тупой железке, чего мы от нее хотим. Отдельные слова все еще не имеют значения, достаточного для того, чтобы понять, какое действие мы хотим совершить. Для этого нам нужно объединить слова в выражения и структуры на нашем языке. Также было бы неплохо сделать это объединение таким образом, чтобы потом можно было преобразовать все это в набор низкоуровневых инструкций, причем, сделать это преобразование как можно легче и эффективнее. Так что, нужно не просто запомнить само выражение и структуру, но и то, что ее составляет – будем хранить все это в виде списка деревьев. Их корни – само выражение/структура, их листья и узлы – информация о том, как все это должно выполняться.

Генератор байт-кода. Обрабатывает синтаксические деревья и строит блоки кода для выполнения действий, связанных с каждым из них.

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

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

Итоги обзора

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

Страницы: 1 2 3 4 5 Следующая »

#скрипты

12 октября 2007

Комментарии [7]