Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214
 Скачать 452.53 Kb.
|
Лабораторная/практическая работа № 6Название работы: «Синтаксис языков программирования. Преобразование транслируемой программы в постфиксную форму записи». Цели работы: изучение задач и методов преобразования текста транслируемой программы постфиксную форму записи (ПФЗ) для выявления заложенной в алгоритм последовательности операций, приобретение навыков разработки действий, реализующих преобразования. Основные теоретические сведения: Постфиксная форма записи Конечной целью работы транслятора является эквивалентное преобразование текста программы на исходном языке в код, который может исполнять реальная или виртуальная вычислительная машина. Компиляторы формируют машинный код для реального компьютера, интерпретаторы – для виртуальной машины. Требование эквивалентности преобразования означает, что результаты выполнения исходной (мысленного) и преобразованной (физического) программ при одинаковых обрабатываемых данных должны быть идентичными. Процессы (истории) выполнения программ, записанных на различных языках, можно рассматривать как последовательности выполнения различных по сложности операций. В исходной программе это могут быть операции уровня вычисления сложного выражения, выполнения итерации цикла или ветки условного оператора или переключателя. В машинном или в виртуальном коде это операции уровня сложения двух чисел, сравнения значений, условной или безусловной передачи управления из одной точки программы в другую. При формальных преобразованиях, выполняемых трансляторами, добиться эквивалентности можно только в том случае, если гарантируется, что в любой паре историй работы выполнению каждой операции исходной программы соответствует выполнение эквивалентной ей последовательности из одной или нескольких операций машинного или виртуального кода (далее машинный или виртуальный код будет называться объектным). Таким образом, транслятор рано или поздно обязан выяснить, какие операции и в какой последовательности должны выполняться согласно алгоритму обработки данных, определенному текстом исходной программы. Здесь очень важным моментом является соотношение между синтаксисом (определяющим способ записи последовательности операций) и семантикой (определяющей способ выполнения этой последовательности) для языков разного уровня. Любой язык программирования высокого уровня ориентирован на предоставление максимальных удобств разработчику программ. Поэтому, как правило, последовательность появления знаков операций в тексте исходной программы не совпадает с последовательностью их выполнения в истории работы программы. Приведем простейший пример. Пусть в тексте программы на языке С/С++ записан оператор присваивания a=b*c+d; Последовательность появления знаков операций в тексте такова: = * + . Однако выполнение этого оператора, в целом определяемое семантикой языка, эквивалентно последовательности выполнения трех элементарных операций, эквивалентных машинным командам: умножить значение b на значение c(операция *); сложить полученное значение со значением d(операция +); присвоить последнее полученное значение переменной a(операция =). Следовательно, в объектном коде знаки операций должны быть записаны в последовательности * + = , поскольку семантика машинно-ориентированных языков предусматривает последовательную выборку выполняемых команд из линейно организованной памяти. Легко можно привести множество других примеров, из которых следует, что привычная для человека форма записи выражений, операторов присваивания и других операторов языков программирования существенно отличается от того вида, в котором они должны быть представлены в объектном коде. Весьма существенные отличия форм представления исходной и объектной программ характерны для управляющих конструкций языков программирования, таких как условные операторы, переключатели и операторы цикла. Синтаксис таких конструкций не предусматривает явной записи операций передач управления, подразумеваемых семантикой языка, и ориентирован на удобство использования человеком. Однако в процессе эквивалентного преобразования исходной программы эти операции, очевидно, должны появиться в тексте объектной программы. Например, пусть в тексте программы на языке С/С++ записан условный оператор: if ( c>0 ) a = b * c + d; else a = ( d – b ) * c; Смысл этой записи совершенно ясен человеку и сводится к тому, что должна быть выполнена определенная последовательность действий: Вычислить результат сравнения значения c с нулем и получить булевское значение true или false. Если результат сравнения есть false, то перейти к шагу 7 (к выполнению оператора, записанного внутри ветки else). Перемножить значения b и c. Сложить полученное значение с d. Присвоить полученное значение переменной a. Перейти к шагу 10. Вычесть значение b из значения d. Умножить результат вычитания на значение c. Присвоить полученное значение переменной a. … ( Следующий по тексту оператор программы. ) Именно в этой последовательности должны быть записаны операции в тексте объектного кода, для того чтобы процессор компьютера (или виртуальная машина) мог выбирать их из оперативной памяти и выполнять. В этом представлении появились операции переходов (передач управления) на шагах 2 и 6, отсутствующие в явном виде в исходном тексте, но подразумеваемые семантикой входного языка. Постфиксная форма записи (ПФЗ), эквивалентная исходному оператору и содержащая близкие к машинно-ориентированному языку элементы, может выглядеть так: c 0 >labelF JmpF a b c * d +=labelEnd Jmp labelF: a d b – c *=labelEnd: В этой записи жирным шрифтом выделены слова, добавленные при преобразовании, и подчеркнуты знаки операций, в том числе операции условной (JmpF) и безусловной (Jmp) передачи управления. Операнды каждой операции записаны перед знаком этой операции. Все знаки операций, кроме унарной безусловной передачи управления, являются бинарными (используют два операнда). Унарная операция Jmp имеет единственный операнд – метку labelEnd. Метки, именующие некоторые операторы программы и используемые в операциях перехода, введены при преобразовании исходного кода в постфиксную форму записи. Особо отметим, что в постфиксной записи второго оператора присваивания отсутствуют скобки, изменяющие порядок выполнения операций в исходном операторе программы. Постфиксная форма записи уникальна тем, что: – последовательность появления в ней знаков операций совпадает с требуемым порядком их выполнения; – не нужны скобки для изменения порядка выполнения операций. Задача выявления последовательности операций, эквивалентной исходной программе, хотя и определяется во многом семантикой двух языков, но имеет глубокие внутренние связи с задачей восстановления дерева грамматического разбора и решается, как правило, на этапе синтаксического анализа. Синтаксические деревья и постфиксная форма записи Синтаксическим деревом или деревом операций называется такое графическое представление совокупности операций, связанных значениями обрабатываемых данных (операндами), в котором: узлы (вершины дерева, из которых выходят дуги, ведущие к потомкам) помечены знаками операций; листья (концевые вершины дерева, не имеющие потомков) помечены наименованиями операндов; нет вершин, помеченных какими-либо другими символами. Синтаксическое дерево оператора присваивания a=b*c+d; может выглядеть так, как показано на рис. 6.1, а. На рис. 6.1, б для сравнения показано дерево грамматического разбора этого оператора в грамматике Ga1, расширенной путем добавления правила P : i = S ; для нового начального нетерминала P.  а б Рис. 6.1. Связь дерева операций и дерева разбора: а – дерево операций; б – дерево грамматического разбора Синтаксическое дерево (рис. 6.1., а) в наглядной форме показывает зависимость операций друг от друга и может быть использовано для определения последовательности их выполнения. Ясно, что до тех пор, пока не вычислено произведение значений b и c, не может быть выполнена операция сложения. В свою очередь, операция присваивания зависит от результата выполнения операции сложения и может быть выполнена только после нее. Может быть определена точная процедура обхода синтаксического дерева для построения требуемой последовательности операций в линейном представлении. Дерево грамматического разбора, восстанавливаемое при проверке правильности данного оператора присваивания и показанное на рис. 6.1., б, также содержит всю необходимую информацию для решения этой задачи. Однако это дерево содержит «лишние» с точки зрения выявления последовательности операций элементы: вершины, помеченные нетерминалами и выходящими их них дугами, а также вершину, помеченную ограничителем оператора присваивания (;) вместе со всеми дугами, ведущими к таким вершинам. В данном операторе не использовались скобки (), но если бы они и были, то также считались бы «лишними». Дерево грамматического разбора может быть преобразовано в дерево операций путем применения следующей процедуры. Шаг 1. Удалить все листья (вершины, помеченные терминальными символами), пометки которых не являются знаками операций и наименованиями операндов. Шаг 2. Просмотреть узлы дерева (вершины, имеющие исходящие дуги), начиная с корня. Для каждого просматриваемого узла сохранять в стеке перечень дочерних узлов. Если какая-либо из дочерних вершин помечена знаком операции, то просматриваемый узел пометить этим знаком и удалить из дерева дочернюю вершину, но только в том случае, если она является листом. Если после обработки очередного узла стек не пуст, то перейти к обработке узла, номер которого снимается с верхушки стека. Если же стек опустел, то повторять шаг 2 до тех пор, пока состояние дерева не перестанет изменяться. Шаг 3. Для каждого листа, помеченного операндом, проверить пометку родительского узла. В том случае если родительский узел помечен нетерминалом, перенести в него наименование операнда из дочернего листа и удалить этот лист. Продолжать выполнение шага 3 до тех пор, пока состояние дерева не перестанет изменяться. Если применить эту процедуру к приведенному выше дереву разбора, то будет получено именно такое дерево операций, которое приведено на рис. ?, а. Для данной грамматики применение этой процедуры позволит получить желаемый результат из дерева разбора любого оператора присваивания. Объясняется это тем, что вся семантика, определяющая последовательность выполнения операций сложения, вычитания и присваивания, а также изменение порядка их выполнения при использовании скобок в любом выражении неявным образом заложена в совокупность порождающих правил, описывающих синтаксис языка операторов присваивания. Из дерева операций легко можно получить постфиксную форму записи линейной последовательности знаков операций (с их операндами) такую, в которой порядок появления операций совпадает с требуемым порядком их выполнения. Процедура преобразования дерева операций в постфиксную форму записи является рекурсивной и может быть определена следующим образом. Шаг 1. Взять корень дерева операций в качестве текущей вершины. Шаг 2. Если текущая вершина не является листом, перейти к шагу 3, иначе выдать ее пометку (наименование операнда) на выход и завершить обход поддерева. Шаг 3. Обойти левое поддерево данного корня (рекурсивно вызвать шаг 2 процедуры для корня левого поддерева текущей вершины). Шаг 4. Обойти правое поддерево данного корня (рекурсивно вызвать шаг 2 процедуры для корня правого поддерева текущей вершины). Шаг 5. Выдать пометку текущей вершины (знак операции) на выход. Завершить обход поддерева. Применение этой процедуры к дереву операций, построенному нами для оператора присваивания a=b*c+d;,позволит получить такую постфиксную запись: abc * d + = Ее смысл (семантика) состоит в следующем. Сначала должна быть выполнена операция умножения значений bи c, наименования которых записаны перед знаком *. Можно считать, что в результате выполнения операции умножения получено промежуточное значение, которое мы обозначим через r, а исходная ПФЗ превратилась в такую: ard + = Затем аналогичным образом должна быть выполнена операция сложения значений rи d (результат сложения обозначим так же: r), после чего запись оператора будет выглядеть так: ar = Окончательно после выполнения операции присваивания запись оператора получит видr,где под r можно понимать (как это делается в языке С/С++) результат выполнения всего оператора присваивания. Главной особенностью постфиксной записи по сравнению с привычной для человека смесью инфиксной (знак операции находится между наименованиями операндов, например: a+b) и префиксной (знак операции находится перед наименованиями своих операндов, например: sin(x)) форм записи является то, что порядок следования знаков операций в записи строго совпадает с требуемым порядком их выполнения при полном отсутствии необходимости в скобках, меняющих этот порядок. Таким образом, если построено дерево разбора правильного предложения, то известен и метод решения основной задачи синтаксического анализа: преобразование предложения в такую промежуточную форму записи, в которой положение знаков операций совпадает с требуемым порядком их выполнения. Однако следует заметить, что: в явном виде дерево разбора не строится никаким синтаксическим акцептором (во всяком случае, теми, которые были изучены в работах 3-5). Следовательно, прямое применение вышеописанных процедур невозможно или требуется их модификация; в простой грамматике Ga1нет правил, содержащих в правой части более одного знака операции (на чем и основана данная процедура). При наличии таких правил придется существенно усложнять шаг 2 процедуры преобразования дерева разбора в дерево операций; для реальных языков программирования не всегда возможно построить такую грамматику, чтобы все семантические правила, определяющие требуемую последовательность (следующую из приоритетов) выполнения операций, были использованы в синтаксических порождающих правилах. В подобных случаях дерево разбора невозможно преобразовать в дерево операций с помощью вышеописанной процедуры. Включение действий в грамматику для преобразования предложения в постфиксную форму записи Для арифметических выражений и операторов присваивания существуют достаточно простые определения постфиксной формы записи. Постфиксной записью пустой цепочки символов является . Постфиксной записью идентификатора i является идентификатор i. Постфиксной записью константы c является константа c. Если E – произвольное выражение, то постфиксной записью выражения, взятого в скобки, т.е. ( E ) будет просто ПФЗ(E). Если E – выражение вида 2, 3 или 4, то постфиксной записью выражения –E (изменение знака значения E) будет ПФЗ(E) – . Если E – выражение вида 2, то постфиксной записью выражений ++E (– –E ) является ПФЗ(++E) = ПФЗ( incPre(&E) ) = E & incPre(ПФЗ(– –E) = = ПФЗ( decPre(&E) ) = E & decPre), где & – знак операции взятия адреса, а incPre (decPre) – имя функции (знак операции), увеличивающей (уменьшающей) значение своего аргумента на единицу и возвращающей измененное значение. Если E – выражение вида 2, то постфиксной записью выражений E++ (E – –) является ПФЗ(E++) = ПФЗ( incPost(&E) ) = E & incPost (ПФЗ(E– –) = = ПФЗ( decPost(&E) ) = E & decPost), где & – знак операции взятия адреса, а incPost (decPost) – имя функции (знак операции), увеличивающей (уменьшающей) значение своего аргумента на единицу и возвращающей еще не измененное значение. Если E 1 , E 2 , … Ek– выражения вида 2…9, то постфиксной записью выражения ○ (E 1 , E 2 , … Ek) является ПФЗ(E 1) ПФЗ(E 2) ... ПФЗ(Ek) ○, где ○ – знак любой k-арной операции (функции с k аргументами), а ПФЗ(E 1), ПФЗ(E 2) … ПФЗ(Ek) – постфиксные записи выражений E 1 , E 2 … Ek соответственно. Если E 1 и E 2 – выражения вида 2…7, то постфиксной записью выражения E 1 ○ E 2 является ПФЗ(E 1) ПФЗ(E 2) ○, где ○ – знак любой бинарной операции (присваивания, сложения, вычитания, умножения, …), а ПФЗ(E 1) и ПФЗ(E 2) – постфиксные записи выражений E 1 и E 2 соответственно. Если E 1 , E 2 , E 3 – выражения вида 2…8, то постфиксной записью выраженияЕ 1 ○ E 2 ● E 3 (где ○ и ● – знаки бинарных операций) является ПФЗ(E 1) ПФЗ(E 2) ○ ПФЗ(E 3) ●, если приоритет знака операции ○ не меньше приоритета знака операции ●, и ПФЗ(E 1) ПФЗ(E 2) ПФЗ(E 3) ● ○ – в противном случае. Если E 1 – выражение вида 2, а E 2 – выражение вида 2…9, то постфиксной записью выражения E 1○E 2 ; является ПФЗ(E 1) ПФЗ(E 2) ○, где ○ – знак операции присваивания (напомним, что в языке С/С++, например, существует не один, а несколько знаков операции присваивания: =, +=, *=, …). Подобные определения можно сформулировать и для других синтаксических конструкций языка программирования. Руководствуясь этими определениями, можно достаточно просто осуществить преобразование заданной грамматики в грамматику действий таким образом, чтобы построенный на ее основе автомат обеспечивал построение постфиксной формы записи входной цепочки терминальных символов в процессе проверки ее правильности. Пусть дана грамматика операторов присваивания (расширенная грамматика Ga1). Будем считать, что имеется функция, выполняющая добавление одного терминального символа (токена) к формируемому в процессе синтаксического анализа промежуточному представлению программы (постфиксной записи), прототип которой выглядит так: voidPutToPFR(Lexem); В правила грамматики будем включать действия (фрагменты программного кода) заключаемые в фигурные скобки. Грамматика операторов присваивания, расширенная действиями по формированию постфиксной записи может выглядеть следующим образом: 0. Z : P ► 1. P : { PutToPFR(CurrentLexem); } i = S { PutToPFR(“=”); } ; 2. S : S + T { PutToPFR(“+”); } 3. S : T 4. T : T * V { PutToPFR(“*“); } 5. T : V 6. V : ( S ) 7. V : { PutToPFR(CurrentLexem); } i 8. V : { PutToPFR(CurrentLexem); } c Действия включаются пакетом ВебТрансБилдер в код парсера таким образом, чтобы они выполнялись по ходу движения парсера по правилам грамматики (нужно помнить, что любой парсер в процессе восстановления дерева разбора движется по правым частям правил слева направо). В правило 1 добавлены два действия. Первое действие ({PutToPFR(CurrentLexem);}) обеспечивает преобразование идентификатора, находящегося в левой части оператора присваивания, в постфиксную форму (в соответствии с определением ПФЗ для идентификатора). Действие вставлено в правило до терминального символа i по той простой причине, что при функционировании любого (нисходящего или восходящего) автомата оно должно быть выполнено в тот момент, когда текущим входным символом (значением переменной CurrentLexem) является идентификатор из левой части оператора присваивания. При переходе нисходящего акцептора в состояние, соответствующее знаку оператора присваивания, а восходящего – в состояние, соответствующее точке между терминалами iи = в этом правиле, текущим входным символом уже будет слово =. Поэтому для помещения лексемы, прочитанной из входной цепочки, в постфиксную запись вызов функции PutToPFR должен помещаться в правило непосредственно перед терминалом, обозначающим группу слов типа идентификаторов (или констант). Аналогичные действия в тех же точках можно увидеть в правилах 7 и 8. Здесь приведено обоснование точек вставки подобных действий как для нисходящего, так и для восходя щего методов синтаксического акцепта, несмотря на то что рассматриваемая грамматика годится только для восходящего. Второе действие в правиле 1 ({ PutToPFR(“=”); }) находится между нетерминалом S и ограничителем оператора присваивания ;. Для простоты будем предполагать, что функция PutToPFR способна преобразовать строку в лексему. Точка вставки этого действия строго соответствует определению постфиксной записи выражений, образованных с помощью бинарного знака операции присваивания. При этом ПФЗ выражения E 1 формируется первым действием в данном правиле, а ПФЗ выражения E 2 будет сформировано при разборе той части входной цепочки, которая выводится из нетерминала S. В этом процессе будут использоваться правила для этого и других нетерминалов и выполняться вставленные в них действия. В тот момент, когда вся цепочка символов, выводимая из S и представляющая собой правую часть оператора присваивания, будет обработана и текущим входным символом станет ограничитель ;, автомат выполнит второе действие и завершит тем самым формирование постфиксной записи оператора присваивания в целом. Действия, вставленные в правые части правила 2 ({ PutToPFR(“+”); }) и правила 4 ({ PutToPFR(“+”); }), точно так же обусловлены определением постфиксной записи для выражений, образуемых с использованием бинарных знаков операций. Точки вставки этих действий так же обусловлены этим определением и для данной грамматики не могут быть изменены. Действия, вставленные в правила 7 и 8, уже описаны. При построении конечного автомата на основе грамматики действий должно быть обеспечено выполнение этих действий в требуемые моменты времени. Любой преобразователь грамматик в синтаксические анализаторы это делает либо путем добавления специальных полей в управляющую таблицу автомата, либо путем формирования дополнительных структур с указателями на функции, в которые преобразуются действия. Легко видеть, что расширенный таким образом LALR(1)-автомат, который можно построить по данной грамматике действий, обеспечит преобразование любого правильного оператора присваивания в постфиксную форму записи без построения в явном виде дерева грамматического разбора и преобразования его в дерево операций с последующим обходом последнего. Для многих синтаксических конструкций языков программирования преобразование в постфиксную запись требует значительно больших усилий. Это объясняется необходимостью формирования уникальных меток и операций передач управления при выявлении линейной последовательности операций для операторов цикла, условных операторов и переключателей. Преобразование управляющих конструкций языка программирования в постфиксную форму записи Такое преобразование, как правило, связано с необходимостью решения ряда дополнительных задач. Рассмотрим источники их возникновения и один из возможных методов решения на простом примере оператора цикла while языка программирования С/С++. Допустим, что синтаксис оператора while определен в грамматике следующим образом: Operator : while ( Expression ) Block Предполагается, что определены и другие операторы (присваивания, условный, … в том числе – оператор break, семантика которого состоит в выходе из тела цикла), что Expression определено как выражение, значение которого можно преобразовать в логическое значение, и что Block определен как одиночный оператор либо как последовательность операторов, заключенная в фигурные скобки. Запишем желаемый вид постфиксной записи для оператора цикла while, используя введенные определения ПФЗ для Expression и предполагая, что способ формирования ПФЗ для Block также известен (на самом деле, он индуктивно зависит от способа формирования ПФЗ оператора while, поскольку этот блок может содержать один или несколько операторов while): ПФЗ( while ( Expression ) Block ) = Label1'>Label1: ПФЗ( Expression ) Label2 JmpFПФЗ( Block ) Label1 Jmp Label2: В этом определении жирным курсивом выделены: Label1: – наименование первого элемента постфиксной записи вычисления значения выражения. JmpF – бинарный знак операции условного перехода, использующий в качестве первого операнда для определения необходимости передачи управления значение, вычисляемое ПФЗ(Expression), в качестве второго – наименование (Label2) первого элемента постфиксной записи, следующего непосредственно после ПФЗ данного оператора цикла. Jmp – унарный знак операции безусловного перехода, использующий в качестве операнда наименование Label1. Label2: – определение наименования для оператора выхода из цикла (условный переход JmpF). Согласно этому определению выполнение оператора while должно протекать так: вычисляется значение выражения, если оно имеет значение true, то оператор JmpF не передает управление на оператор, помеченный именем Label2:, выполняются действия постфиксной записи блока и оператором Jmp управление возвращается на начало вычисления выражения (операцию, помеченную Label1:); если же значение выражения есть false, то оператор JmpF передает управление, используя Label2 в качестве адреса. Если бы требовалось преобразовать в постфиксную запись единственный оператор цикла, то такого определения его ПФЗ было бы достаточно. Однако в тексте программы может встретиться несколько операторов while, в том числе и внутри блока, являющегося телом данного цикла. Для того чтобы при преобразовании в постфиксную запись не формировались идентичные наименования для разных точек переходов, что создаст проблемы при генерации объектного кода, необходимо в приведенном определении ПФЗ все метки понимать как уникальные, однозначно сопоставленные с конкретным оператором цикла. Уникальность меток можно обеспечить при реализации преобразования в постфиксную запись, т. е. при вставке действий в грамматику. Для обеспечения уникальности меток, создаваемых для машинно-ориентированного эквивалента оператора while можно: используя специально определенную для этой цели переменную (счетчик), присваивать уникальный номер каждому оператору цикла, встретившемуся во входной программе при восстановлении дерева ее разбора; при увеличении значения счетчика сохранять его во вспомогательном стеке, доступном из действий, вставляемых в грамматику; использовать значение, находящееся на верхушке вспомогательного стека, для формирования наименований адресов перехода; удалять верхнее значение из стека в момент завершения обработки оператора цикла. Приведем пример реализации, предполагая, что счетчик имеет целое значение и называется WhileCount, и что для операций над вспомогательным стеком имеются функции с прототипами: voidPush(int); – поместить значение аргумента на верхушку стека; intPop(void); – возвратить значение, удалив его с верхушки стека; intTop(void); – вернуть значение с верхушки, не удаляя его из стека. Для краткости записи будем считать, что при написании действий можно использовать бинарную инфиксную операцию #, преобразующую свои операнды в строковые представления и возвращающую конкатенацию этих строк. Функция PutToPFR будет преобразовывать такие строковые аргументы в лексемы. Теперь рассматриваемое правило грамматики, расширенное действиями на основе определения ПФЗ оператора цикла while, будет выглядеть так: Operator : while {Push(++WhileCount); PutToPFR(“Label1” # Top() # “:”);} ( Expression ) { PutToPFR(“Label2” # Top()); PutToPFR(“JmpF”);} Block { PutToPFR(“Label1” # Top()); PutToPFR(“Jmp”); PutToPFR(“Label2” # Pop() # “:”); } Кроме операторов цикла while язык программирования, как правило, содержит другие формы операторов цикла (for, do, …), условные операторы, переключатели и т. д. Все метки, генерируемые при формировании постфиксной формы записи этих конструкций, должны быть уникальны в пределах одной транслируемой программной единицы. Поэтому разработчику транслятора придется решать следующие вопросы: – требуется ли поддерживать отдельные счетчики для разных типов управляющих конструкций или для всех таких операторов использовать один счетчик; – поддерживать ли несколько вспомогательных стеков или можно обойтись одним. Порядок выполнения работы(рекомендуется использовать в качестве примера систему правил Samples/Sample6): Реализовать полную грамматику языка, заданного на курсовую работу. Используя пакет ВебТрансБилдер, изучить и освоить: способы включения структур данных и операций в грамматику, полученную в результате выполнения предыдущих лабораторных работ; структуру и механизмы функционирования нисходящего и восходящего синтаксических анализаторов, способы вызова и моменты активизации действий, расширяющих функциональность синтаксических акцепторов; методику разработки и отладки (трассировки) системы действий, обеспечивающих преобразование в постфиксную запись последовательности лексем, получаемой от лексического анализатора. Использовать полученные навыки для разработки преобразователя в ПФЗ для выражений, операторов присваивания и по меньшей мере одного управляющего оператора языка, заданного на курсовую работу. Подготовить, сдать и защитить отчет к лабораторной работе. Требования к содержанию отчета. Отчет должен содержать: цель работы; краткое описание свойств постфиксной записи и методов ее формирования; реализацию действий для формирования ПФЗ, включенных в грамматику языка, заданного на курсовую работу; описание структур данных и алгоритмов преобразователя анализируемой программы на заданном языке в ПФЗ в качестве фрагмента расчетно-пояснительной записки; примеры результатов преобразования тестовых программ в ПФЗ; выводы и заключение. Контрольные вопросы Для чего операторы программы преобразуются в постфиксную форму записи? Эквивалентны ли абстрактное синтаксическое дерево и постфиксная форма записи программы? Что такое детерминированное (безвозвратное) восстановление дерева грамматического разбора? Сформулируйте основные принципы преобразования арифметических выражений в постфиксную запись. Почему леворекурсивная грамматика не может быть преобразована в нисходящий синтаксический акцептор? Что такое постфиксная запись? Каковы свойства постфиксной формы записи? В чем состоят отличия алгоритма преобразования управляющих конструкций в постфиксную запись от алгоритма преобразования арифметических выражений. |