![]() Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву ![]() Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Интерпретатор ПОЛИЗа для модельного языка⇐ ПредыдущаяСтр 11 из 11
Польская инверсная запись была выбрана нами в качестве языка внутреннего представления программы, в частности, потому, что записанная таким образом программа может быть легко проинтерпретирована. Идея алгоритма очень проста: просматриваем ПОЛИЗ слева направо; если встречаем операнд, то записываем его в стек; если встретили знак операции, то извлекаем из стека нужное количество операндов и выполняем операцию, результат (если он есть) заносим в стек и т.д.
Итак, программа на ПОЛИЗе записана в массиве P; пусть она состоит из N элементов-лексем. Каждая лексема - это структура struct lex {int class; int value;}, возможные значения поля class: 0 - лексемы-метки (номера элементов в ПОЛИЗе) 1 - логические константы true либо false (других лексем - служебных слов в ПОЛИЗе нет) 2 - операции (других лексем-ограничителей в ПОЛИЗе нет) 3 - целые константы 4 - лексемы-идентификаторы (во время интерпретации будет использовать-ся значение) 5 - лексемы-идентификаторы (во время интерпретации будет использовать-ся адрес). Считаем, что к моменту интерпретации распределена память под константы и переменные, адреса занесены в поле address таблиц TID и TNUM, значения констант размещены в памяти. В программе-интерпретаторе будем использовать некоторые переменные и функции, введенные нами ранее.
void interpreter(void) { int *ip; int i, j, arg; for (i = 0; i<=N; i++) {curr_lex = P[i]; switch (curr_lex.class) { case 0: ipush (curr_lex.value); break; /* метку ПОЛИЗ - в стек */ case 1: if (eq ("true")) ipush (1); else ipush (0); break; /* логическое значение - в стек */ case 2: if (eq ("+")) {ipush (ipop() + ipop()); break}; /* выполнили операцию сложения, результат - в стек*/ if (eq ("-")) {arg = ipop(); ipush (ipop() - arg); break;} /* аналогично для других двухместных арифметических if (eq ("not")) {ipush (!ipop()); break;}; if (eq ("!")) {j = ipop(); i = j-1; break;}; /* интерпретация будет продолжена с j-го элемента if (eq ("!F")) {j = ipop(); arg = ipop(); if (!arg) {i = j-1}; break;}; /* если значение arg ложно, то интерпретация будет if (eq (":=")) {arg = ipop(); ip = (int*)ipop(); *ip = arg; break;}; if (eq ("R")) {ip = (*int) ipop(); scanf("%d", ip); break;}; /* "R" - обозначение операции ввода */ if (eq ("W")) {arg = ipop(); printf ("%d", arg); break;}; /* "W" - обозначение операции вывода */ case 3: ip = TNUM [curr_lex.value].address;
ipush(*ip); break; /* значение константы - в стек */ case 4: ip = TID [curr_lex.value].address; ipush(*ip); break; /* значение переменной - в стек */ case 5: ip = TID [curr_lex.value}.address; ipush((int)ip); break; /* адрес переменной - в стек */ } /* конец switch */ } /* конец for */ } Задачи.
63. Представить в ПОЛИЗе следующие выражения: а) a+b-c b) a*b+c/a c) a/(b+c)*a d) (a+b)/(c+a*b) e) a and b or c f) not a or b and a g) x+y=x/y h ) (x*x+y*y < 1) and (x > 0)
64. Для следующих выражений в ПОЛИЗе дать обычную инфиксную запись: а ) ab*c+ b) abc*/ c) ab+c* d) ab+bc-/a+ e) a not b and not f) abca and or and g ) 2x+2x*<
65. Используя стек, вычислить следующие выражения в ПОЛИЗе: а) x y*x y /+ при x = 8, y = 2; b) a 2+b / b 4*+ при a = 4, b = 3; c) a b not and a or not при a = b = true; d) x y*0 > y 2 x - < and при x = y = 1.
66. Записать в ПОЛИЗе следующие операторы языка Си и, используя стек, выполнить их при указанных начальных значениях переменных: а) if (x!= y) x = x+1; при x = 3; b) if (x > y) x = y; else y = x; при x = 5, y = 7; c) while (b > a) b = b-a;; при a = 3, b = 7; *d) do {x = y; y = 2*y;} while (x < k); при y = 2; k = 15; e) S = 0; for (i = 1; i <= k; i = i + 1) S = S + i*i; при k = 3; f) switch (k) { case 1: a = not a; break; case 2: b = a or not b; case 3: a = b; } при k = 2, a = b = false.
*67. Используя стек, выполнить следующие действия, записанные в ПОЛИЗе, при x = 9, y = 15 (считаем,что элементы ПОЛИЗа перенумерованы с 1). z, x, y, *,:=, x, y, <>, 30,!F, x, y, <, 23,!F, y, y, x, -,:=, 28,!, x, x, y, -,:=, 6,!, z, z, x, /,:= Описать заданные действия на Си, не используя оператор goto.
68. Предложить ПОЛИЗ для следующих операторов. Вставить в грамматику действия для ее порождения (генерация происходит во время синтаксического анализа методом рекурсивного спуска). a) for I:= E1 to E2 do S (оператор цикла в Паскале)
b) case E of (оператор выбора в Паскале) c1: S1; c2: S2;... cn: Sn end
c) repeat S1; S2;...;Sn until B (оператор цикла в Паскале)
*d) вставить в грамматику действия для порождения ПОЛИЗа оператора goto. P ® program D; S { S } end D ®... S ® L: S’ | S’ S’ ®... | goto L |... L - идентификатор
*e) if (E) S1; S2; S3 семантика этого оператора такова: вычисляется значение выражения Е; если его значение меньше 0, то выполняется оператор S1 ; если равно 0 - оператор S2, иначе - оператор S3 *f) choice (S1; S2; S3), E семантика этого оператора такова: вычисляется значение выражения Е; если его значение равно i, то выполняется оператор Si для i = 1, 2, 3; иначе оператор choice эквивалентен пустому оператору.
*g) cycle (E1; E2; E3), S семантика этого оператора отличается от семантики оператора for в языке Си только тем, что оператор S выполняется, по крайней мере, один раз (т.е. после вычисления выражения Е1 сразу выполняется оператор S, затем вычисляется значение Е3, потом - значение Е2, которое используется для контроля за количеством повторений цикла также, как и в цикле for).
69. Записать в ПОЛИЗе следующие фрагменты программ на Паскале:
a) case k of 1: begin a:=not(a or b and c); b:=a and c or b end; 2: begin a:=a and (b or not c); b:= not a end; 3: begin a:=b or c or not a; b:==b and c or a end end b) S:=0; for i:=1 to N do begin d:=i*2; a:=a+d*((i-1)*N+5) S:=-a*d+S end c) c:=a*b; while a<>b do if a < b then b:=b-a else a:=a-b; c:=c/a
70. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, / и скобки (), где операции должны выполняться строго слева направо, но приоритет скобок сохраняется. Определить действия по переводу таких выражений в ПОЛИЗ.
71. Изменить приоритет операций отношения в М - языке (сделать его наивысшим). Построить соответствующую грамматику, отражающую этот приоритет. Написать синтаксический анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ.
72. Написать КС-грамматику, аналогичную данной, E ® T {+T} T ® F {*F} F ® (E) | i с той лишь разницей, что в новом языке будет допускаться унарный минус перед идентификатором, имеющий наивысший приоритет (например, a*-b+-c допускается и означает a*(-b)+(-c). В созданную грамматику вставить действия по переводу такого выражения в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Cи.
73. Дана грамматика, описывающая выражения:
E ® TE’ E’ ® +TE’ | e T ® FT’ T’ ® *FT’ | e F ® PF’ F’ ® ^PF’ | e P ® (E) | i
Включить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си.
74. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *, /, ** и скобки () с обычным приоритетом операций и скобок. Включить в эту грамматику действия по переводу этих выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.
75. В грамматику, описывающую выражения, включить действия по переводу выражений из инфиксной формы (операция между операндами) в функциональную запись. Например, а+b ==> + (a, b) a+b*c ==> + (a, * (b, c))
*76. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу L1 в L2. L1 = { 1m 0n | n,m>0} L2 = { 1m-n | если m>n; 0n-m | если m<n; e | если m=n} (Эта задача аналогична задаче выдачи сообщений об ошибке в балансе скобок).
77. Построить грамматику для языка L1, вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2. L1 = {1n 0m 1m 0n | m,n > 0} L2 = {1m 0n+m | m,n > 0}
78. Построить регулярную грамматику для языка L1, вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2. L1 = {bi | bi =(i)2, т.е. bi -это двоичное представление числа i Î N} L2 = {(bi+1)R | bi+1=(i+1)2, wR - перевернутая цепочка w}
79. Построить грамматику, описывающую целые двоичные числа (допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел в четверичную систему счисления. *80. Написать регулярную грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2.
L1={ w^ | w Î {a,b}+, w=an, где a=ab | ba, n>=1} L2={ w^ | w = bn, где b={ b, если a=ab; либо a, если a=ba} }
*81. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2. L1={ a^ | a Î {a,b}* } L2={ b^ | b = bnaR, где n - количество символов b в цепочке a, предшествующих первому вхождению символа a; aR - реверс цепочки a}
*82. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2. L1={ w^ | w Î {a,b}+, где содержится n символов a и m символов b, расположенных в произвольном порядке} L2={ w Î {a,b} * | w = a[n/2] b[m/2] }
*83. Написать грамматику для языка L1. Вставить в нее действия по переводу цепочек языка L1 в соответствующие цепочки языка L2. L1={w^ | wÎ{0,1}+, рассматривается как (bi)R, т.е. реверс двоичного числа i } L2={w Î {/} *, w = /i, т.е. количество /, равное значению i }
ЛИТЕРАТУРА 1. Д.Грис. Конструирование компиляторов для цифровых вычислительных машин. - М., Мир, 1975. 2. Ф.Льюис, Д.Розенкранц, Р.Стирнз. Теоретические основы проектирования компиляторов. - М., Мир, 1979. 3. А.Ахо, Дж.Ульман. Теория синтаксического анализа, перевода и компиляции. - Т. 1,2. - М., Мир, 1979. 4. Ф.Вайнгартен. Трансляция языков программирования. - М., Мир, 1977. 5. И.Л.Братчиков. Синтаксис языков программирования. - М., Наука, 1975. 6. С.Гинзбург. Математическая теория контекстно-свободных языков. - М., Мир, 1970. 7. Дж.Фостер. Автоматический синтаксический анализ. - М., Мир, 1975. 8. В.Н.Лебедев. Введение в системы программирования. - М., Статистика, 1975. 9. Б.Ф.Мельников. Подклассы класса контекстно-свободных языков. - М., МГУ, 1995. СОДЕРЖАНИЕ ЭЛЕ МЕ НТЫ ТЕОРИИ ФОРМАЛЬНЫХ ЯЗЫКОВ И ГРАММАТИК...... Введение........................................................................................................................ Основные понятия и определения........................................................................... Классификация грамматик и языков по Хомскому........................................... Примеры грамматик и языков................................................................................... Задача разбора.............................................................................................................. Преобразования грамматик.................................................................................... Задачи........................................................................................................................... ЭЛЕМЕНТЫ ТЕОРИИ ТРАНСЛЯЦИИ............................................................. Введение...................................................................................................................... Описание модельного языка........................................................................................
Лексический анализ.................................................................................................. О недетерминированном разборе............................................................................... Задачи лексического анализа....................................................................................... Лексический анализатор для М-языка....................................................................... Задачи............................................................................................................................ 30 Синтаксический и семантический анализ.......................................................... Метод рекурсивного спуска........................................................................................ О применимости метода рекурсивного спуска......................................................... Синтаксический анализатор для М-языка................................................................ О семантическом анализе........................................................................................... Семантический анализатор для М-языка................................................................. Задачи............................................................................................................................ Генерация внутреннего представления программ............................................ Язык внутреннего представления программы.......................................................... Синтаксически управляемый перевод........................................................................ Генератор промежуточной программы для М-языка............................................. Интерпретатор ПОЛИЗа для модельного языка.................................................... Задачи............................................................................................................................ ЛИТЕРАТУРА............................................................................................................ 61 СОДЕРЖАНИЕ.......................................................................................................... 62
|
||||||||
Последнее изменение этой страницы: 2016-12-30; просмотров: 585; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.133.144.18 (0.046 с.) |