Задачи - Формальные грамматики и языки. Элементы теории трансляции (1115026), страница 3
Текст из файла (страница 3)
количество /, равное значению i }5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно,допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел вчетверичную систему счисления.6. Написать грамматику для выражений, содержащих переменные, знаки операций +, -, *,/, ** и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматикудействия по переводу этих выражений в префиксную запись (операции предшествуютоперандам).
Предложить интерпретатор префиксной записи выражений.7. В грамматику, описывающую выражения, включить действия по переводу выраженийиз инфиксной формы (операция между операндами) в функциональную запись.Например,а+b==> + (a, b)a+b*c==> + (a, * (b, c))V. ПОЛИЗ, перевод в ПОЛИЗ1. Представить в ПОЛИЗе следующие выражения:а)c)e)g)a+b-ca/(b+c)*aa and b or cx+y=x/yb)d)f)h)a*b+c/a(a+b)/(c+a*b)not a or b and a(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:case 2:case 3:}a = not a; break;b = a or not b ;a=b;5.
Bыражение на ПОЛИЗе записать в инфиксной форме ( на С )a) x y z a x 5 y / + ∗ z 6 + 8 ∗ − = ==b) x a x z y / + ∗ z 6 a − * + =6. Является ли записьy, 15, =, x, x, a, b, c, 2, / , 1, +, *, −, *, a, −, =, y, y, 2, -, =, y, 10, <=, 4, !Fправильной записью в ПОЛИЗе следующего фрагмента программы на С (считаем, чтоэлементы ПОЛИЗа нумеруются с 1):y = 15; do {x = x*(a−b*(c/2+1)) −a; y = y−2;} while y>10;Если не является, то объясните почему и предложите свой вариант ПОЛИЗа для этогофрагмента программы.7. Является ли записьi, 1, =, i, n, <, 33 ,!F, a, a, b,+,1, -, x, y, y, 2, +, /, −, *, 5 ,+ ,=, i, i, 2, + ,=, 4, !правильной записью в ПОЛИЗе следующего фрагмента программы на С (считаем, чтоэлементы ПОЛИЗа нумеруются с 1):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; };b) выражение на ПОЛИЗеxyzax5y/+∗z6+8∗−===записать в инфиксной форме ( на С ).9. а) записать на ПОЛИЗе фрагмент программы на С:if (z<x*y+5) a = x<y, z = (x+6)/(a-y); else z = y<<2;b) выражение на ПОЛИЗеxaxzy/+∗z6a−*+=записать в инфиксной форме ( на С ).10.
Предложить ПОЛИЗ для следующих операторов:a) if ( E ) S1; S2; S3семантика этого оператора такова: вычисляется значение выражения Е; если его значениеменьше 0, то выполняется оператор S1 ; если равно 0 — оператор S2 , иначе — операторS3f) 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).11. Написать грамматику для выражений, содержащих переменные, знаки операций +, −,*, / и скобки ( ), где операции должны выполняться строго слева направо, но приоритетскобок сохраняется. Определить действия по переводу таких выражений в ПОЛИЗ.12. Изменить приоритет операций отношения в М-языке ( сделать его наивысшим).Построить соответствующую грамматику, отражающую этот приоритет. Написатьсинтаксический анализатор, обеспечить контроль типов, задать перевод в ПОЛИЗ.13.
Написать КС-грамматику, аналогичную данной,E → T {+T}T → F {*F}F → (E) | iс той лишь разницей, что в новом языке будет допускаться унарный минус передидентификатором, имеющий наивысший приоритет (например, a * − b + − c допускаетсяи означает a*(−b) + (−c).В созданную грамматику вставить действия по переводу такого выражения в ПОЛИЗ.Для каждой используемой процедуры привести ее текст на Cи.14.
Дана грамматика, описывающая выражения:E → TE′T → FT′F → PF′P → (E) | iE′ → +TE′ | εT′ → *FT′ | εF′ → ^PF′ | εВключить в эту грамматику действия по переводу этих выражений в ПОЛИЗ. Для каждойиспользуемой процедуры привести ее текст на Си.СОДЕРЖАНИЕЗадачи (Приложение к учебному пособию"Формальные грамматики и языки.Элементы теории трансляции") ...........................................................................................1I. Порождающие грамматики. Языки, порождаемые грамматиками.
Классификацияграмматик и языков по Хомскому .......................................................................................1II. Регулярные грамматики, ДС, анализаторы по ДС. Преобразование НКА к ДКА .....6III. Метод рекурсивного спуска (РС-метод). Применимость РС-метода. КСграмматики с действиями ...................................................................................................10IV. Синтаксически управляемый перевод.........................................................................15V. ПОЛИЗ, перевод в ПОЛИЗ ............................................................................................18.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
