Файл: Отчеты оформляются в виде файлов формата Microsoft Word (файлы других форматов не принимаются), размер шрифта 1214.docx

ard + =

Затем аналогичным образом должна быть выполнена операция сложения значений rи d (результат сложения обозначим так же: r), после чего запись оператора будет выглядеть так:

ar =

Окончательно после выполнения операции присваивания запись оператора получит видr,где под r можно понимать (как это делается в языке С/С++) результат выполнения всего оператора присваивания.

Главной особенностью постфиксной записи по сравнению с привычной для человека смесью инфиксной (знак операции находится между наименованиями операндов, например: a+b) и префиксной (знак операции находится перед наименованиями своих операндов, например: sin(x)) форм записи является то, что порядок следования знаков операций в записи строго совпадает с требуемым порядком их выполнения при полном отсутствии необходимости в скобках, меняющих этот порядок.

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

Однако следует заметить, что:

• 
  в явном виде дерево разбора не строится никаким синтаксическим акцептором (во всяком случае, теми, которые были изучены в работах 3-5). Следовательно, прямое применение вышеописанных процедур невозможно или требуется их модификация;
  
• 
  в простой грамматике G_a1нет правил, содержащих в правой части более одного знака операции (на чем и основана данная процедура). При наличии таких правил придется существенно усложнять шаг 2 процедуры преобразования дерева разбора в дерево операций;
  
• 
  для реальных языков программирования не всегда возможно построить такую грамматику, чтобы все семантические правила, определяющие требуемую последовательность (следующую из приоритетов) выполнения операций, были использованы в синтаксических порождающих правилах. В подобных случаях дерево разбора невозможно преобразовать в дерево операций с помощью вышеописанной процедуры.
  

3. 
   Включение действий в грамматику для преобразования предложения в постфиксную форму записи
   

Для арифметических выражений и операторов присваивания существуют достаточно простые определения постфиксной формы записи.

1. 
   Постфиксной записью пустой цепочки символов  является .
   
2. 
   Постфиксной записью идентификатора i является идентификатор i.
   
3. 
   Постфиксной записью константы c является константа c.
   
4. 
   Если E – произвольное выражение, то постфиксной записью выражения, взятого в скобки, т.е. ( E ) будет просто ПФЗ(E).
   
5. 
   Если E – выражение вида 2, 3 или 4, то постфиксной записью выражения –E (изменение знака значения E) будет ПФЗ(E) – .
   
6. 
   Если E – выражение вида 2, то постфиксной записью выражений
   ++E (– –E ) является ПФЗ(++E) = ПФЗ( incPre(&E) ) = E & incPre(ПФЗ(– –E) =
   = ПФЗ( decPre(&E) ) = E & decPre), где & – знак операции взятия адреса, а incPre (decPre) – имя функции (знак операции), увеличивающей (уменьшающей) значение своего аргумента на единицу и возвращающей измененное значение.
   
7. 
   Если E – выражение вида 2, то постфиксной записью выражений E++ (E – –) является ПФЗ(E++) = ПФЗ( incPost(&E) ) = E & incPost (ПФЗ(E– –) =
   = ПФЗ( decPost(&E) ) = E & decPost), где & – знак операции взятия адреса, а incPost (decPost) – имя функции (знак операции), увеличивающей (уменьшающей) значение своего аргумента на единицу и возвращающей еще не измененное значение.
   
8. 
   Если E ₁ , E ₂ , … E_k– выражения вида 2…9, то постфиксной записью выражения ○ (E ₁ , E ₂ , … E_k) является ПФЗ(E ₁) ПФЗ(E ₂) ... ПФЗ(E_k) ○, где ○ – знак любой k-арной операции (функции с k аргументами), а ПФЗ(E ₁), ПФЗ(E ₂) … ПФЗ(E_k) – постфиксные записи выражений E ₁ , E ₂ … E_k соответственно.
   
9. 
   Если E ₁ и E ₂ – выражения вида 2…7, то постфиксной записью выражения E ₁ ○ E ₂ является ПФЗ(E ₁) ПФЗ(E ₂) ○, где ○ – знак любой бинарной операции (присваивания, сложения, вычитания, умножения, …), а ПФЗ(E ₁) и ПФЗ(E ₂) – постфиксные записи выражений E ₁ и E ₂ соответственно.
   
10. 
    Если E ₁ , E ₂ , E ₃ – выражения вида 2…8, то постфиксной записью выраженияЕ ₁ ○ E ₂ ● E ₃ (где ○ и ● – знаки бинарных операций) является ПФЗ(E ₁) ПФЗ(E ₂) ○ ПФЗ(E ₃) ●, если приоритет знака операции ○ не меньше приоритета знака операции ●, и ПФЗ(E ₁) ПФЗ(E ₂) ПФЗ(E ₃) ● ○ – в противном случае.
    
11. 
    Если E ₁ – выражение вида 2, а E ₂ – выражение вида 2…9, то постфиксной записью выражения E ₁○E ₂ ; является ПФЗ(E ₁) ПФЗ(E ₂) ○, где ○ – знак операции присваивания (напомним, что в языке С/С++, например, существует не один, а несколько знаков операции присваивания: =, +=, *=, …).
    

---

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

Пусть дана грамматика операторов присваивания (расширенная грамматика G_a1). Будем считать, что имеется функция, выполняющая добавление одного терминального символа (токена) к формируемому в процессе синтаксического анализа промежуточному представлению программы (постфиксной записи), прототип которой выглядит так:

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 ₁ формируется первым действием в данном правиле, а ПФЗ выражения E ₂ будет сформировано при разборе той части входной цепочки, которая выводится из нетерминала S.
В этом процессе будут использоваться правила для этого и других нетерминалов и выполняться вставленные в них действия. В тот момент, когда вся цепочка символов, выводимая из S и представляющая собой правую часть оператора присваивания, будет обработана и текущим входным символом станет ограничитель ;, автомат выполнит второе действие и завершит тем самым формирование постфиксной записи оператора присваивания в целом.

Действия, вставленные в правые части правила 2 ({ PutToPFR(“+”); }) и правила 4 ({ PutToPFR(“+”); }), точно так же обусловлены определением постфиксной записи для выражений, образуемых с использованием бинарных знаков операций. Точки вставки этих действий так же обусловлены этим определением и для данной грамматики не могут быть изменены. Действия, вставленные в правила 7 и 8, уже описаны.

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

Легко видеть, что расширенный таким образом LALR(1)-автомат, который можно построить по данной грамматике действий, обеспечит преобразование любого правильного оператора присваивания в постфиксную форму записи без построения в явном виде дерева грамматического разбора и преобразования его в дерево операций с последующим обходом последнего.

---

Для многих синтаксических конструкций языков программирования преобразование в постфиксную запись требует значительно больших усилий. Это объясняется необходимостью формирования уникальных меток и операций передач управления при выявлении линейной последовательности операций для операторов цикла, условных операторов и переключателей.

4. 
   Преобразование управляющих конструкций языка программирования в постфиксную форму записи
   

Такое преобразование, как правило, связано с необходимостью решения ряда дополнительных задач. Рассмотрим источники их возникновения и один из возможных методов решения на простом примере оператора цикла 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); – возвратить значение, удалив его с верхушки стека;

---