И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1114891), страница 19
Текст из файла (страница 19)
Включить в эту грамматикудействия по переводу выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.7. В грамматику, описывающую выражения, включить действия по переводу выражений изинфиксной формы (операция между операндами) в функциональную запись.Например,а+b⇒ +(a, b),a+b∗c⇒ +(a, ∗(b, c)).V. ПОЛИЗ, перевод в ПОЛИЗ1. Представить в ПОЛИЗе следующие выражения:а) a+b−cc) a/(b+c)∗ab) a∗b+c/ad) (a+b)/(c+a∗b)109Задачи / V.
ПОЛИЗ, перевод в ПОЛИЗe) a and b or cg) x+y=x/yf ) not a or b and ah) (x∗x+y∗y<1) and (x>0)2. Для следующих выражений в ПОЛИЗе дать обычную инфиксную запись:а ) ab∗c+d) ab+bc−/a+g ) 2x+2x∗<b) abc∗/e) a not b and notc) ab+c∗f) abca and or and3. Используя стек, вычислить следующие выражения в ПОЛИЗе:а)x y∗x y / +при x = 8, y = 2;b)a 2+b / b 4∗+при a = 4, b = 3;при a = b = true;c)a b not and a or notпри x = y = 1.d)x y∗0 > y 2 x − < and4. Перевести в ПОЛИЗ фрагмент программы на Си:a)S = 0; i =1; while ( i < 10) { S = S∗(i+i); i + +; }b)if ( (x+1) > (2∗y) ) x = y ; else y = (x+y)∗2;c)i = 1; S = 0; while ( i < 10 && S < 40 ) { S = S + f(i); + + i; }d)if (z<x∗y+5) a = x<y, z = (x+6)/(a−y); else z = y << 2;e)a = x + y < z∗(t + x) ? − (a + b)/(c−d)∗2 : ++x+5;f)S = x + y; i = 1; for (j = 0; j < n; j++) { S = S + i∗j∗S; i = i∗x; }g)i = 1; S = 0; while ( i < 10 && S < 40 ) { S = S + f(i); ++i; }h)if (z<x∗y+5) a = x<y, z = (x+6)/(a−y); else z = y << 2;i)do {x = y; y = 2∗y;} while (x < k);j)S = 0; for (i = 1; i <= k; i = i + 1) S + = i∗i;k)switch (k) {case 1: a = not a; break;case 2: b = a or not b;case 3: a = b ;}ЗамечаниеПОЛИЗ управляющих операторов языка Си составляется аналогично ПОЛИЗу операторов Мязыка и Паскаля.
При переводе в ПОЛИЗ сложных операторов порядок внутренних конструкций (операторов и выражений) относительно друг друга сохраняется. Например, в ПОЛИЗе дляоператора цикла вида for (expr1; expr2; expr3) {body} ПОЛИЗ expr3 должен предшествоватьПОЛИЗу body.В языке Си присваивание является операцией, а не оператором, поэтому при интерпретацииПОЛИЗа присвоенное значение сохраняется в стеке (как результат операции). Чтобы удалитьненужное значение с вершины стека (такие значения остаются в стеке, например, после исполнения оператора-выражения), в ПОЛИЗе языка Си используется операция ";".110Задачи / V. ПОЛИЗ, перевод в ПОЛИЗЧтобы отличить префиксные операции ++ и −− от постфиксных, префиксные обозначают вПОЛИЗе как +# и –#, а постфиксные как #+ и #– соответственно.ПОЛИЗ вызова функции представляет собой последовательность ее аргументов в ПОЛИЗе, закоторыми следует имя функции.
Для функций с переменным числом параметров перед именемфункции в ПОЛИЗ вставляется дополнительный аргумент — количество фактических параметров в данном вызове функции. При интерпретации сначала из стека извлекается этот дополнительный аргумент, а затем — соответствующее ему число фактических параметров.5.
По заданному ПОЛИЗу выражения записать его в инфиксной форме (на Си).a) x y z a x 5 y / + ∗ z 6 + 8 ∗ − = = = ;xaxzy/+∗z6a−∗+=b)6. Является ли запись1234567891011121314151617y15=;xxabc2/1+*-*a1819202122232425262728293031-=;yy2-=;y10<=5!FПОЛИЗ32333435правильной записью в ПОЛИЗе следующего фрагмента программы на Си (считаем, что элементы ПОЛИЗа нумеруются с 1): y = 15; do {x = x∗(a−b∗(c/2+1))−a; y = y−2;} while (y >10);Если не является, объясните почему, и предложите свой вариант ПОЛИЗа для этого фрагмента программы.7. Является ли запись1234567891011121314151617i1=;in<33!Faab+1-xy181920212223242526272829303132333435y2+/-*5+=;ii2+=;5!ПОЛИЗ36правильной записью в ПОЛИЗе следующего фрагмента программы на Си:for ( i = 1; i < n; i = i +2 ) a = (a+b−1)∗(x−y /(y+2))+5;Если не является, объясните почему и предложите свой вариант ПОЛИЗа для этого фрагмента программы.8.
а) перевести в ПОЛИЗ фрагмент программы на Си:i = 1; s = 0; while ( i < 10 && s < 40 ) { s = s + f(i); ++i; };c) выражение в ПОЛИЗе записать в инфиксной форме (на Си).xyzax5y/+∗z6+8∗−===9. а) перевести в ПОЛИЗ фрагмент программы на Си:if (z < x∗y+5) a = x<y, z = (x+6)/(a−y); else z = y << 2;b) выражение в ПОЛИЗе записать в инфиксной форме (на Си).xaxzy/+∗z6a−∗+=111Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ10. Предложить ПОЛИЗ для следующих операторов:a) if ( E ) S1; S2; S3Семантика этого оператора такова: вычисляется значение выражения Е; если его значениеменьше 0, то выполняется оператор S1 ; если равно 0 — оператор S2, иначе — оператор S3 .b) choice ( S1; S2; S3), EСемантика: вычисляется значение выражения Е; если его значение равно i, то выполняетсяоператор Si для i = 1, 2, 3; иначе оператор choice эквивалентен пустому оператору.c) cycle ( E1; E2; E3), SСемантика этого оператора отличается от семантики оператора for в языке Си только тем,что оператор S выполняется, по крайней мере, один раз (т.е.
после вычисления выраженияЕ1 сразу выполняется оператор S, затем вычисляется значение Е3, потом — значение Е2, которое используется для контроля за количеством повторений цикла также, как и в циклеfor).11. Построить грамматику для выражений, содержащих переменные, знаки операций +, −, ∗,/ и скобки ( ). Грамматика должна отражать одинаковый приоритет и лево-ассоциативностьвсех четырех операций. Определить действия по переводу таких выражений в ПОЛИЗ.12.
Изменить приоритет операций отношения в М-языке — сделать его наивысшим. Построить соответствующую грамматику, отражающую этот приоритет. Написать синтаксический анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ.13. Построить КС-грамматику, аналогичную данной,E → T {+T}T → F {∗F}F → (E) | iс той лишь разницей, что в новом языке перед идентификатором будет допускаться унарный минус, имеющий наивысший приоритет (например, a ∗ −b+−c допускается и означаетa ∗ (−b)+(−c).
В созданную грамматику вставить действия по переводу такого выражения вПОЛИЗ. Для каждой используемой процедуры привести ее текст на Си + +.14. Дана грамматика, описывающая выражения:E → TE ′E ′ → + TE ′ | εT ′ → ∗ FT ′ | εT → FT ′F ′ → ^ PF ′ | εF → PF ′P → (E) | iВключить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждойиспользуемой процедуры привести ее текст на Си++.112Литература[1]. Д. Грис. Конструирование компиляторов для цифровых вычислительных машин. — М.:Мир, 1975.[2].
Ф. Льюис, Д. Розенкранц, Р. Стирнз. Теоретические основы проектирования компиляторов. — М.: Мир, 1979.[3]. А. Ахо, Дж. Ульман. Теория синтаксического анализа, перевода и компиляции. — Т.1,2. — М.: Мир, 1979.[4]. Ф. Вайнгартен. Трансляция языков программирования. — М.: Мир, 1977.[5]. И. Л. Братчиков. Синтаксис языков программирования. — М.: Наука, 1975.[6]. С.
Гинзбург. Математическая теория контекстно-свободных языков. — М.: Мир, 1970.[7]. Дж. Фостер. Автоматический синтаксический анализ. — М.: Мир, 1975.[8]. В. Н. Лебедев. Введение в системы программирования. — М.: Статистика, 1975.[9]. Б. Ф. Мельников. Подклассы класса контекстно-свободных языков. — М.: МГУ, 1995.[10]. В. Н. Пильщиков, В. Г. Абрамов, А. А. Вылиток, И. В.
Горячая. Машины Тьюринга иалгоритмы Маркова. Решение задач. — М.:МГУ, 2006.[11]. А. Ахо., Р. Сети, Дж. Ульман. Компиляторы: принципы, технологии, инструменты. —М.: «Вильямс», 2001.[12]. А. Ахо, М. Лам, Р.Сети, Дж. Ульман. Компиляторы: принципы, технологии и инструментарий. — М.: «Вильямс», 2008.113Содержание Элементы теории формальных языков и грамматик ............................................... 3 Введение .........................................................................................................................................
3 Основные понятия и определения............................................................................................. 3 Классификация грамматик и языков по Хомскому .................................................................... 7 Грамматики с ограничениями на вид правил вывода ............................................................ 7 Иерархия Хомского ................................................................................................................... 9 Примеры грамматик и языков .................................................................................................... 11 Регулярные................................................................................................................................ 12 Контекстно-свободные ............................................................................................................
12 Неукорачивающие и контекстно-зависимые ........................................................................ 13 Без ограничений на вид правил (тип 0) ................................................................................. 13 Замечание о связи между языком и грамматикой ................................................................ 14 Разбор цепочек ............................................................................................................................. 15 Преобразования грамматик.........................................................................................................
19 Алгоритм удаления недостижимых символов ...................................................................... 19 Алгоритм удаления бесплодных символов ........................................................................... 19 Алгоритм приведения грамматики......................................................................................... 20 Алгоритм устранения правил с пустой правой частью........................................................ 20 Элементы теории трансляции ................................................................................... 21 Введение .......................................................................................................................................
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
