Главная » Документация » Использование языка скриптов в играх

RSS

Использование языка скриптов в играх

Трансляция

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

Виртуальная машина языка эмулирует CPU. Для COG, мы используем очень простую модель, называемую «стековая машина». Свое название стековая машина получила из того факта, что она выполняет все операции на одиночном стеке. Любой, кто использовал программируемый калькулятор, знаком с этой системой. Чтобы добавлять 5 и 10 на стековой машине, мы выполнили бы такие коды операций

Push 5
Push 10
Add

Стековая машина содержит немного кодов операции, выполняя их весьма просто и эффективно. Наша цель, чтобы быстро компилировать исходный текст, написанный дизайнером в наши коды операции стековой машины. Любая допустимая последовательность команд на языке COG может быть транслированна в эти базисные операции, точно так-же как код C может транслироваться в машинные коды вашего CPU.

Трансляция GOC проходит в два этапа. Сначала, код делится на релевантные части языка или лексемы. COG лексемы, точно так же как лексемы C, включают все ключевые слова языка (if, then, else) и операторы (+, *, &&). Эта стадия трансляции называется лексическим анализом.

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

(additionExpression) : (expression) + (expression)

Это определяет выражение сложения как два отдельных выражения, отделяемые лексемой «+». Так как выражение сложения – только одно из многих возможных определений более общего «выражения», Вы можете видеть, как обработка языка быстро становится рекурсивной проблемой. Самый низкий уровень спецификации – «атомы» языка – являются константами и переменными.

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

Возвращаясь к простому примеру сложения, наш синтаксический анализатор должен создать такое дерево синтаксического анализа для исходного текста а = 5 + 10.

Потому что синтаксический анализ языка выполняется рекурсивно, синтаксический анализ автоматически обрабатывает обычно сложные проблемы типа вложения и порядка операций автоматически. Когда код a=(5*2)+(a^2) анализируется, синтаксический анализатор распознает подвыражения 5*2 и a^2 первыми, и передаст завершенные деревья синтаксического анализа для этих подвыражений к коду, который создает дерево для выражения добавления, приводящего к одиночному дереву для всего выражения.

Наиболее сложные выражения, для анализа – это циклы и ветвление. Эти выражения требуют порождения кода, используя коды перехода, что означает, что синтаксический анализатор должен знать адрес, к которому нужно перейти. Например, чтобы генерировать такой код if <condition> then <expression>, синтаксический анализатор должен знать об адресе кода сразу после поддерева выражения, чтобы генерировать код операции GO FALSE, чтобы перейти к этому коду если условное выражение ложно.

При создании кода для этих ветвей код должен генерироваться в двух проходах. Первый проход, известный как «backpatching», не генерирует код, он просто считает число кодов операции, произведенных каждым узлом дерева синтаксического анализа. В течение первого прохода, поскольку с каждым узлом сталкиваются при пересечении дерева, адрес кода (индекс в массиве кодов операции) отмечен, до и после того как коды операции из узла добавлены. После первого прохода, каждый узел содержит адрес кода только до и только после кода собственного поддерева. На второй проход, ветви, которые были предварительно выражены в терминах end of node <expression>, можгут быть выражены как фактические адреса кода.

Это весьма сложная тема, которую мы исследовали только поверхностно. Для подробной информации относительно теории синтаксического анализа и использования деревьев синтаксического анализа, посмотрите – Compilers: Principles, Techniques, and Tools by Aho, Sethi, and Ullman

Opcode
Описание
Push Помещает константу символа на стек выполнения
Pop Получает следующее значение из стека выполнения
GoFalse Получает верхнее значение стека и переходит к новому адресу выполнения, если
условие равно 0
Go Переход к новому адресу выполнения
Stop Останавливает выполнение
CallFunc Получает следующее значение из стека как указатель на функцию C и вызывает
эту функцию
Add Получает следующие два значения из стека, складывает их, и помещает результат
на стек
Assign Получает следующие два значения из стека, и присваивает первой переменной
значение второй.

Таблица 3. Пример COG «stack machine» opcodes

Золотая середина

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

Одна бесплатная программа, под названием LEX обычно используется, чтобы генерировать код C, выполняющий лексический анализатор, основанный на обеспеченной пользователем спецификации грамматики. С тех пор как COG следует за синтаксисом C, мы изменили существующий файл спецификации C для Lex, чтобы создать лексический анализатор для языка.

Точно так же другая бесплатная программа, называемый YACC (Yet Another Compiler Compiler) может использоваться, чтобы трансформировать формальную спецификацию языка в модуль C. Yacc и Lex разработаны, чтобы работать вместе, так что возникающие в результате модули исходного текста могут просто компилироваться и линковаться, чтобы создать полностью функциональный синтаксический анализатор. Для COG, тот же самый сайт Интернета выдал полную спецификацию грамматики C для Yacc, который был урезан до наших потребностей и использовался, чтобы создать модуль синтаксического анализатора.

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

И Lex и Yacc доступены во многих формах ; некоторый бесплатны, некоторый нет. И в то-же время как Lex и Yacc – наиболее общие инструментальные средства разработки компиляторов, имеется нескоторые другие, включая полномасштабные среды конструкции языка типа VisualParse++ by Sandstone Technologies. Какой-бы инструмент Вы не использовали, конечный результат тот же самый – поток кодов, которые могут быть выполнены быстро и эффективно вашей виртуальной машиной. Проверьте общедоступный каталог компиляторов, упомянутый ранее, для связей с этими и другими полезными инструментальными средствами.

Для более подробной информации относительно инструментальных средств Lex и Yacc, обратитесь к Lex Yacc by Levine, Mason, and Brown in the O’Reilly Associates UNIX Programming Series.

Страницы : 1 2 3 4

Таги: