formal_languages_translation_theory (852748), страница 19

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

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

КС-грамматики с действиями10. Дана грамматика с семантическими действиями:S   A  0; B  0  L {L}  if (A  5) ERROR( )  L  a  A  A1  | b  B  B1; if (B  2) ERROR( )  |c  if (B  1) ERROR( ) Какой язык описывает эта грамматика? (см. замечание к задаче 4)11. Дана грамматика:S  EE  ( ) | (E {, E}) | AAa|bВставить в заданную грамматику действия, контролирующие соблюдение следующих условий:уровень вложенности скобок не больше четырех;на каждом уровне вложенности происходит чередование скобочных и бесскобочныхэлементов.12. Включить в правила вывода действия, проверяющие выполнение следующих контекстных условий:a) Пусть в языке L есть переменные и константы целого, вещественного и логического типов, а также есть оператор циклаS  for I  E step E to E do SВключить в это правило вывода действия, проверяющие выполнение следующих ограничений: тип I и всех вхождений Е должен быть одинаковым; переменная логического типа недопустима в качестве параметра цикла.Для каждой используемой процедуры привести ее текст на Си.Дан фрагмент грамматикиP  program D; begin S {; S } endD  ...

| label L{,L} |...S  L { , L } : S′ | S′S′  ...| goto L |...LIгде I — идентификатор.Вставить в грамматику действия, контролирующие выполнение следующих условий: каждая метка, используемая в программе, должна быть описана и только один раз; не должно быть одинаковых меток у различных операторов; если метка используется в операторе goto, то обязательно должен быть оператор, помеченный такой меткой.Для каждой используемой процедуры привести ее текст на Си.b)107Задачи / IV. Синтаксически управляемый переводIV. Синтаксически управляемый перевод1.

Построить грамматику арифметического выражения, использующего операции , , ,  икруглые скобки (приоритет операций стандартный), простые аргументы операций — переменные a и b, например: a(ba) bab. Предполагая, что анализ грамматики будет производиться РС-методом, вставить в нее действия вида cout << ′символ′ по переводу такихвыражений в ПОЛИЗ.2. Дана грамматика языка L1, в которую вставлены действия по переводу цепочек языка L1 вцепочки языка L2. Определить языки L1 и L2.a)S  a  a  1; b  0;  A A  a  if ( a ) { cout << ′a′; a  0; } else a;  A |bA  if ( b ) { cout << ′b′; b  0; } else b;  | εb)S   a  0;  E  cout << ′′ ; E  a  a  1; E  cout << ′a′ ;  |b  if (a  0) cout << ′b′; E  cout << ′b′ ;  | ε3.

Построить грамматику для языка L1. Вставить в нее действия по генерации цепочек языкаL2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками задается формальным переводом . В качестве действий можно использовать только операторы вида cout << ′символ′.a)n m nn nmn m n { ( a c b , 0 1b)i kL1 { a c b | n0, m1},L2 { 0 1 | i 0, k  i },) | n  0, m1 };L1 { c |  ∈ {a, b} , n1},n*n mL2 { a c | n1, m  0 }, { (c , a c ) |  ∈ {a, b} , n  1, m a (т.е. m — количество символов а вцепочке  )};nc)n mL1  {a, b},*i jL2  { 1 0 | i  1, j  0; ij },nm n0 ) |  ∈ {a,b}, n a, m b }; { (, 1d)L1  {a, b}, L2  { 2  | n  0,  ∈ {a, b} },n { ( , 2 R ) |  ∈ {a,b}, n a (здесь R — реверс цепочки ) };ne)n m m ni kL1  {1 0 1 0 | m, n  0}, L2  {1 0 | k  i  0},n m m nm nm { ( 1 0 1 0 , 1 0f)) | m, n 0 };L1  { 1  2 …n  | n 1, i  {ab, ba} для 1  i  n },L2  { | ∈ {a, b} }, { (  1 2 … n ,  1  2 … n  ) | n 1; для 1  i  nесли i  ab,  i  a, если i ba };108i  {ab, ba},  i  b,Задачи / V.

ПОЛИЗ, перевод в ПОЛИЗ4. Построить грамматику для языка L1. Вставить в нее действия по генерации цепочек языкаL2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками задается формальным переводом . В качестве действий можно использовать любые операторы.m nkia)L1  { 1 0 | n, m 0}, L2  { 1 | k 0}  { 0 | i 0}  {},m nmn { ( 1 0 , 1b)m n) | m  n 0 } { ( 1 0 , 0nmL1  {i | i  0, i (i)2(т.е.

i —незначащих ведущих нулей) },m n) | n  m  0 }  {( 1 0 ,  ) | m  n};это двоичное представление числа i   безL2  {(i)R | i 1, i(i)2 (R — обращение цепочки ) },  { ( i, (i1)R ) | i  0, i (i)2, i1(i1)2 } ;c)L1  {  |   {a, b} },nL2{ b  | n  0,   {a, b} }, { ( , b R) |  ∈ {a, b} , n a ( n — количество символовцепочке , R — реверс цепочки )};nd)*L1{  |   {a, b} }, { ( , a[n/2]b[m/2]i k) |  ∈ {a, b}, n a, m b ( здесь [x] — ближайшее к x це-L1{  |   {a, b} }, { ( , a[f)(n+1)/3]b[вL2{ a b | i, k  0, ik  0 },лое, например: [1/2] = 1, [1/3] = 0, [5/3] = 2)e)а|m-n |/2]};i kL2{ a b | i, k  0, ik  0 },) |  ∈ {a, b}, n a, m b };L1 { | {0,1},   (i)2 R, i  0 (т.

е.  — реверс двоичной записи числа i ) },nL2 { | | n  0 }, { ( , | ) | {0,1},   (i)2 R, i  0 }.i5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно,допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел вчетверичную систему счисления.6. Построить грамматику для выражений, содержащих переменные, знаки операций , , ,,  и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматикудействия по переводу выражений в префиксную запись (операции предшествуют операндам). Предложить интерпретатор префиксной записи выражений.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;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.

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

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