Внутреннее представление программы
Результатом работы анализатора должна быть некая внутренняя запись программы, отражающая её синтаксическую структуру.
Основные свойства языка внутреннего представления программы.
(Внимание! Это вопрос с зачёта!)
-
Позволяет фиксировать синтаксическую структуру исходной программы.
-
Текст на нём можно автоматически генерировать во время синтаксического анализа.
-
Его конструкция должна просто транслировать в объектный код, либо достаточно эффективно интерпретировать.
Вставляем в грамматику действия в определённых местах, чтобы ПОЛИЗ преобразовывался автоматически.
При переходе в ПОЛИЗ необходимо следить, чтобы не изменялся порядок операндов.
(Например, нельзя даже заменять A<=B на B>=A.)
Будем получать ПОЛИЗ автоматически путём подстановки действий в грамматику, а не по алгоритму.
-а - специальное представление унарного минуса
0-а &a
- для унарного минуса здесь надо вводить спец. значок, например &.
++
- -
+=
++ i=i+1
| |
единая или такая
одномерная расшифровка
операция операции
Пример. sin(x) в ПОЛИЗе записывается x, sin.
| -операнд | - операция
название операнд
операции
Пример. I:=E записывается: I, E, :=
Лекция 11. 23/04/2004.
Перевод операторов в ПОЛИЗ.
Итак, в запись программы надо включать некоторые дополнительные элементы для перевода оператора в ПОЛИЗ.
Например, I:=E записывается: I, E, :=
Для некоторых переменных нужен адрес, а не значение, будем подчёркивать такие переменные.
Е – некоторое выражение, записанное в ПОЛИЗе.
На зачёте могут встретиться операции из других языков программирования.
++ +=
i=i+1 Полиз: i,i,1,+,:=,
i++ i,++,
Т.о. при использовании этой операции как одноместной, не забывать её (i) подчёркивать.
i+=1 => i,1,+=
Специальные операции ПОЛИЗа:
!, !F - внутренние операции ПОЛИЗа.
! – безусловный переход (GO TO)
p,! p – метка ПОЛИЗа, позиция, на которую надо передать управление, начиная откуда выполняется оператор.
B,p,!F !F – переход при невыполнении условия, B – условие, логическое выражение.
Эти операции будут считываться наравне с привычными.
Запишем в ПОЛИЗе операторы модельного языка:
if E then S1 else S2
if (!E) goto L2; S1; goto L3; L2:S2; L3:……
E, p2, !F, S1, p3, !, S2
Вместо р потом подставляем позицию в ПОЛИЗе.
S1 – некий оператор.
L0: if (!E) goto L1; S; goto L0; L1:……
E, p1, !F, S, p0, !, …
write (E) => E, write, …
Перевод цепочек с одного языка в другой происходит в синтаксическом анализе, цепочки другого языка вставляются в исходный язык предварительно.
Будем пользоваться синтаксически управляемым переводом. Действия вставляем предварительно.
Пример. Даны 2 языка:
L1 = {0n1m | n>=0, m>0}
L2 = {ambn | n>=0, m>0}
Синтаксически управляемый перевод: написать грамматику, вставляя действия из одного языка в другой.
L1: S -> 0S | 1A
A -> 1A | ε
Грамматика L1 должна быть такой, чтобы к ней был применим МРС.
S -> 0S < ‘b’; > | 1< ‘a’;> A
A -> 1 < ‘a’;> A | ε
Символов b столько же, сколько нулей в исходной L1.
Пример. №82.
Пусть задан язык.
L1 = {w & | w принадлежит {a,b}+, Σa = n, Σb = m}
L2 = {a[n/2]b[m/2] | n>=0, m>=0}
S -> aA & | bA &
A -> aA | bA | ε
S -> a A&
//для введения счётчиков и присвоения им начального значения
A -> a < if(n) {cout<<�‘a’; n=0; }
else n=1; > A |
bA <<�‘b’; m=0; } else m=1; > |
ε
//для выделения целой части
А отделяет: сначала вывод ‘a’, потом вывод ‘b’.
Подведём некоторые итоги:
-
:=, F, !F, read, write – новые операции
-
в ПОЛИЗе храним лексемы.
Понятие лексем надо расширить – ввести ‘p’ – метки ПОЛИЗа.
Тип (0,р) – лексемы метки.
Тип (5,А) – адрес лексемы.
class poliz {
lex *p;
int size;
int free;
public:
poliz (int max_size)
{p=new lex[size=max.size]; free=0;}
~poliz( ) {delete[ ]p;}
void put_lex (lex e) {p[free++] = l;}
void put_lex (lex e, int place) {p[place] = e;}
void blank( ) {free++;}
int get_free( ) {return free;}
lex &operator[ ] (int index)
{if (index>size) throw “POLIZ: out of array”;
else if (index>free) throw “POLIZ: element out of array”;
else return p[index];
};
void print ( ) {
for (int i=0; i
}
};
В конце каждой альтернативы вставить функцию putlex, и текущую лексему вставить в ПОЛИЗ.
poliz prog (1000);
S -> I
>:= - 5-класс адресов
Адрес – номер строки в таблице идентификаторов.
E
//-заносится в ПОЛИЗ
S -> if E
prog.put_lex(lex(1,TW.look(“!F”)));>
then S1
prog.put_lex(lex(1,TW.look(“!”)));
prog.put_lex(lex(0,prog.get_free( )), pl2);
//формируем лексему и заносим в адрес pl2 сформированные ранее
else S2
S -> while
E
prog.put_lex (lex (1,TW.look(“!F”)));>
do S
prog.put_lex (lex (0,prog.get_free( )), p(1);>
S -> read (I )
S -> write(E)
В результате выполнения программы-анализатора по МРС будет записан массив
poliz prog (1000);
Встречающийся операнд заносим в стек. Операция – сдвиг нужного количества операндов, соответствующих операции, и выполнение операции.
При выполнении вспомогательной операции (например, условной) ничего записывать в стек не надо.
По окончании операции в стеке останется 1 значение, и будут выполнены действия.
class executer {
lex curr_lex;
public:
void execute( );
};
Внутри функции вводится шаблонный класс stack.
|
