Варианты заданий (1114804), страница 10
Текст из файла (страница 10)
Такой подход имеет множество серьезных недостатков. Прежде всего, разумеется, ни в коем случае не следует в явном виде указывать в программе числа, соответствующие типамлексем; для этого следует ввести и использовать перечислимый тип. Программа, написанная с использованием перечислимого типа, гораздо лучшечитается.Далее, не следует, разумеется, формировать таблицы лексем в глобаль13В этом случае операция ungetc() отрабатывается рекурсивным вызовом Step() с тем же символом49ных переменных. Единственная таблица, которая может быть описана глобально – это таблица ключевых слов14, поскольку эта таблица не подлежитизменению.Один из возможных подходов состоит в том, чтобы хранить таблицы вобъекте лексического анализатора.
Также можно описать для таблиц отдельный класс, создать его объект и передать адрес этого объекта в конструктор лексического анализатора.Наконец, можно работать и вообще без таблиц; например, объект “лексема” может представлять собой структуру, одно поле которой – это идентификатор типа лексемы, а второе – указатель на строку, хранящую самулексему.
Для этой структуры весьма желательно предусмотреть деструктор, уничтожающий соответствующую строку при уничтожении лексемы.Также могут существенно облегчить жизнь конструктор копирования иоператоры сравнения и присваивания.Учтите, что при выдаче сообщений об ошибке следует указывать номерстроки в анализируемом тексте. Для этого в объекте “лексема” рекомендуется предусмотреть еще одно поле, хранящее номер строки анализируемоготекста, в которой данная лексема была обнаружена.4.4.2Синтаксический анализаторНа этапе синтаксического анализа мы работаем с лексемами в качествесимволов.Производить синтаксический анализ следует наиболее простым из пригодных методов, а именно методом рекурсивного спуска. Для этого преждевсего необходимо выписать грамматику избранного языка и проверить еена применимость рекурсивного спуска.
При необходимости следует преобразовать грамматику.Метод рекурсивного спуска предполагает описание значительного количества процедур (по одной на каждый нетерминальный символ грамматики). Кроме того, при описании метода рекурсивного спуска обычно упоминается глобальная переменная, хранящая текущий символ (т.е. текущуюлексему).Ясно, что при работе на языке C++ эти функции и переменную следуетинкапсулировать в один объект.Как и в случае лексического анализа, возможны разные подходы к проектирсованию класса синтаксического анализатора. Общим в них является14Можно обратить внимание, что лексемы, соответствующие знакам операций +, -, *, / и т.п.
такжеявляются ключевыми словами; после фазы лексического анализа никакой разницы между обычнымиключевыми словами и разделителями нет50PolizItemPolizItemppnextPolizElemnextPolizItem...PolizElempnextPolizElemРис. 2: Список элементов ПОЛИЗато, что функции, соответствующие символам грамматики, оформляются ввиде методов в приватной части класса. Также в приватную часть необходимо поместить поле данных, хранящее текущую лексему. Приватнойбудет и функция “переход на следующую лексему”.При обнаружении ошибки для выхода из процедур рекурсивного спускаследует использовать механизм исключений языка C++.Рекомендуется сначала создать синтаксический анализатор, способныйпроверить входную цепочку лексем на соответствие заданной грамматикеи при ошибке выдающий осмысленную диагностику с указанием номерастроки в анализируемом тексте.После отладки в анализатор следует вставить код генерации внутреннего представления программы.
Для этого необходимо преобразоватьисходную грамматику в грамматику с действиями для синтаксическиуправляемого перевода, после чего вставить соответствующие действия внужные места кода синтаксического анализатора.4.5Интерпретация. ПОЛИЗРезультатом работы анализатора должно стать внутреннее представлениесценария, удобное для дальнейшей интерпретации. В качестве такого представления мы рекомендуем использовать ПОЛИЗ (см. [5]).4.5.1Примерная структура данныхСледует заметить, что элементы ПОЛИЗа относятся к разным типам, однако имеют и общие свойства; более того, они должны храниться в видепоследовательной структуры данных (массива или списка), при этом обрабатываться схожими методами, работающими в зависимости от типа данного элемента ПОЛИЗа.
Ясно, что понятие “элемент полиза” представляетсобой пример предметной области, для моделирования которой прекрасно51подходит полиморфная иерархия классов.Хранить элементы ПОЛИЗа можно, например, в односвязном списке, аметки, используемые операциями переходов, представлять указателями насоответствующее звено списка (в отличие от значения индекса в массивеэлементов, как это предлагается в пособии [5]).
Поскольку разные элементыПОЛИЗа представляются объектами разных классов, звенья списка должны, по-видимому, хранить указатель на соответствующий объект, а не самобъект.Далее в этом параграфе мы предполагаем, что базовый класс иерархии“элементы ПОЛИЗа” называется PolizElem, а структура для звена списка –PolizItem. Пример структуры данных, представляющей список элементовПОЛИЗа, показан на рис.
2.Заметим, что такая структура данных пригодна как для хранения самого ПОЛИЗа, так и для организации стека значений, необходимого в процессе интерпретации.4.5.2Типы элементов ПОЛИЗаРассмотрим теперь множество необходимых типов элементов ПОЛИЗа.Прежде всего, ПОЛИЗ может содержать целочисленные константы (иликонстанты типа float, если в вашем языке предусмотрена арифметика сплавающей точкой). Кроме того, в языке фигурируют строковые литералы (строковые константы), для которых тоже необходимо предусмотретьвозможность включения в ПОЛИЗ.Вообще, константой называют любой элемент ПОЛИЗа, который, будучи встречен в процессе интерпретации, сразу же заносится в стек, послечего интерпретация продолжается со следующей позиции.Можно заметить, что константами в этом смысле также являются метки, т.е.
значения, задающие позицию в ПОЛИЗе для операций условного ибезусловного перехода. В нашем примере таковые реализуются указателями на звено списка (т.е. на структуру типа PolizItem).Наконец, напомним, что переменные могут входить в ПОЛИЗ двумяспособами: как обращение к переменной (при интерпретации заменяетсяна значение переменной, которое и заносится в стек) и как адрес переменной, используемый обычно в левой части операторов присваивания 15. Вотличие от обращения, адрес не преобразуется к значению переменной, азаносится в стек как таковой, чтобы затем операция присваивания, используя сохраненный на стеке операнд, могла занести вычисленное значение в15При изображении ПОЛИЗа на письме адреса переменных обычно подчеркивают, чтобы отличитьих от обращений к переменным52PolizElemPolizOpGoPolizConstPolizOpGoFalsePolizFunctionPolizIntPolizFunPlusPolizVarPolizStringPolizFunMinus...PolizVarAddrPolizLabelPolizSell...PolizEndturnРис.
3: Иерархия классов для представления ПОЛИЗанужное место. Таким образом, элемент ПОЛИЗа “адрес переменной” такжеявляется константой.В простейшем случае перечисленными четырьмя типами исчерпывается список константных типов элементов ПОЛИЗа. Все остальные элементы представляют собой операции, т.е. их интерпретация подразумевает, вобщем случае, извлечение из стека некоторого количества операндов, вычисление некоторого значения, которое потом заносится обратно в стек, и,возможно, выполнение некоторых иных действий. Количество операндов,подлежащих извлечению из стека при выполнении, может быть любым,в том числе и нулевым (например, для операции “обращение к переменной”).
В нашем примере максимальная “арность” операции равна двум, т.е.больше двух аргументов ни одной операции не требуется.Также существуют и операции, не вычисляющие значений, т.е. после ихисполнения в стек ничего не заносится. Примеры таких операций – условный и безусловный переходы. Кроме того, для рассматриваемого языканеобходимо предусмотреть операции, соответствующие операторам совершения игровых действий (см. §4.2.6) и оператору отладочной печати (см.53§4.2.7).Как можно заметить, некоторые из операций должны иметь возможность влиять на процесс интерпретации путем явного изменения указателяна текущий интерпретируемый элемент.
В нашем примере таких операцийдве: “безусловный переход” и “переход по лжи”.Наконец, можно считать, что константы представляют собой частныйслучай операции, а именно, нуль-местную операцию, результат которой равен самому элементу, представляющему операцию.Таким образом, понятие выполнения (вычисления) элемента ПОЛИЗастановится универсальным свойством всех объектов нашей иерархии.Забегая вперед, договоримся избегать разделения структур данных, т.е.участия одних и тех же объектов в разных фрагментах структур данных.Это означает, например, что значения, заносимые в стек, всегда представляют собой специально порожденные для этого объекты; в некоторых случаях это будут копии объектов из ПОЛИЗа (при вычислении константы),в других случаях – только что созданные новые объекты (например, результат операции сложения).Сразу же отметим, что копированию будут подвергаться только константные выражения, поскольку операции никогда в стек не заносятся.
Таким образом, все константы, входящие в ПОЛИЗ, имеют как минимум однуобщую операцию, отсутствующую для всех других классов иерархии. Имеется в виду операция создания копии. Это соображение сразу же наводитнас на мысль о создании общего предка для всех констант – абстрактногокласса PolizConst, в котором вводится специальный метод для созданиякопии.Как станет ясно из дальнейшего изложения, реализовывать операцииПОЛИЗа, не нуждающиеся в доступе к указателю на текущий интерпретируемый элемент (то есть все операции, кроме двух операций перехода)будет несколько проще, если ввести еще один абстрактный класс (мы назовем его PolizFunction), от которого будут наследоваться все операции,кроме операций перехода.Окончательно наша иерархия классов примет вид, показанный нарис. 3.4.5.3МетодыМетоды базового класса Сформулируем теперь требования к наиболее общему виду операции “вычисление элемента ПОЛИЗа” (далее предполагаем, что этот метод классов иерархии элементов ПОЛИЗа называетсяEvaluate).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
