И.А. Волкова, А.А. Вылиток, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции (1119400), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

ПОЛИЗ, перевод в ПОЛИЗ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;c)a b not and a or notпри a  b  true;d)x y0  y 2 x   andпри x  y  1.4.

Перевести в ПОЛИЗ фрагмент программы на Си: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  ! a; break;case 2: b  a || ! 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      ;x a x z y /   z 6 a    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<36!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  10; s  0; while ( i  0 && s  40 ) { p + f(i+s) ? i : s++ ; };b) выражение в ПОЛИЗе записать в инфиксной форме (на Си).x y z a x 5 y /   z 6  8     9. а) перевести в ПОЛИЗ фрагмент программы на Си:if (z  xy5) a  xy? (z  x6): (z=ay); else z + y ;b) выражение в ПОЛИЗе записать в инфиксной форме (на Си).x a x z y /   z 6 a    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СодержаниеМГУ им. М. В. Ломоносова ...................................................................................... 2Рецензенты: .............................................................................................................. 2Элементы теории формальных языков и грамматик .............................................

3Введение .................................................................................................................................... 3Основные понятия и определения ......................................................................................... 3Классификация грамматик и языков по Хомскому ................................................................. 7Грамматики с ограничениями на вид правил вывода .......................................................... 7Иерархия Хомского ...............................................................................................................

9Примеры грамматик и языков ................................................................................................ 11Регулярные .......................................................................................................................... 12Контекстно-свободные........................................................................................................ 12Неукорачивающие и контекстно-зависимые ..................................................................... 13Без ограничений на вид правил (тип 0) .............................................................................. 13Замечание о связи между языком и грамматикой .............................................................. 14Разбор цепочек ........................................................................................................................

15Преобразования грамматик .................................................................................................... 19Алгоритм удаления недостижимых символов ................................................................... 19Алгоритм удаления бесплодных символов ........................................................................

Характеристики

Список файлов книги