Учебное пособие для студентов II курса (издание третье, переработанное и дополненное) Москва 2009 удк 519. 682. 1
 Скачать 2.2 Mb.
|
|
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}) | A A a | b Вставить в заданную грамматику действия, контролирующие соблюдение следующих усло- вий: уровень вложенности скобок не больше четырех; на каждом уровне вложенности происходит чередование скобочных и бесскобочных элементов. 12. Включить в правила вывода действия, проверяющие выполнение следующих кон- текстных условий: a) Пусть в языке L есть переменные и константы целого, вещественного и логического ти- пов, а также есть оператор цикла S for I E step E to E do S Включить в это правило вывода действия, проверяющие выполнение следующих ограниче- ний: тип I и всех вхождений Е должен быть одинаковым; переменная логического типа недопустима в качестве параметра цикла. Для каждой используемой процедуры привести ее текст на Си b) Дан фрагмент грамматики P program D; begin S {; S } end D ... | label L{,L} |... S L { , L } : S′ | S′ S′ ...| goto L |... L I где I — идентификатор. Вставить в грамматику действия, контролирующие выполнение следующих условий: каждая метка, используемая в программе, должна быть описана и только один раз; не должно быть одинаковых меток у различных операторов; если метка используется в операторе goto, то обязательно должен быть оператор, по- меченный такой меткой. Для каждой используемой процедуры привести ее текст на Си Задачи / IV. Синтаксически управляемый перевод 108 IV. Синтаксически управляемый перевод 1. Построить грамматику арифметического выражения, использующего операции , , , и круглые скобки (приоритет операций стандартный), простые аргументы операций — пере- менные a и b, например: a (b a) b a b. Предполагая, что анализ грамматики будет про- изводиться РС-методом, вставить в нее действия вида cout << ′ символ ′ по переводу таких выражений в ПОЛИЗ. 2. Дана грамматика языка L 1 , в которую вставлены действия по переводу цепочек языка L 1 в цепочки языка L 2 . Определить языки L 1 и L 2 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. Построить грамматику для языка L 1 . Вставить в нее действия по генерации цепочек языка L 2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками за- дается формальным переводом . В качестве действий можно использовать только опера- торы вида cout << ′ символ ′. a) L 1 { a n c m b n | n 0, m 1}, L 2 { 0 i 1 k | i 0, k i }, { ( a n c m b n , 0 n 1 n m ) | n 0, m 1 }; b) L 1 { c n | ∈ {a, b} * , n 1}, L 2 { a n c m | n 1, m 0 }, { ( c n , a n c m ) | ∈ {a, b} * , n 1, m a (т.е. m — количество символов а в цепочке ) }; c) L 1 {a, b} , L 2 { 1 i 0 j | i 1, j 0; i j }, { ( , 1 n m 0 n ) | ∈ {a,b} , n a , m b }; d) L 1 {a, b} , L 2 { 2 n | n 0, ∈ {a, b} }, { ( , 2 n R ) | ∈ {a,b} , n a (здесь R — реверс цепочки ) }; e) L 1 {1 n 0 m 1 m 0 n | m, n 0}, L 2 {1 i 0 k | k i 0}, { ( 1 n 0 m 1 m 0 n , 1 m 0 n m ) | m, n 0 }; f ) L 1 { 1 2 … n | n 1, i {ab, ba} для 1 i n }, L 2 { | ∈ {a, b} }, { ( 1 2 … n , 1 2 … n ) | n 1; для 1 i n i {ab, ba}, i b, если i ab, i a, если i ba }; Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ 109 4. Построить грамматику для языка L 1 . Вставить в нее действия по генерации цепочек языка L 2 в процессе анализа методом рекурсивного спуска. Соответствие между цепочками за- дается формальным переводом . В качестве действий можно использовать любые опера- торы. a) L 1 { 1 m 0 n | n, m 0}, L 2 { 1 k | k 0} { 0 i | i 0} { }, { ( 1 m 0 n , 1 m n ) | m n 0 } { ( 1 m 0 n , 0 n m ) | n m 0 } {( 1 m 0 n , ) | m n}; b) L 1 { i | i 0, i (i) 2 (т.е. i — это двоичное представление числа i без незначащих ведущих нулей) }, L 2 {( i ) R | i 1, i (i) 2 ( R — обращение цепочки ) }, { ( i , ( i 1 ) R ) | i 0, i (i) 2 , i 1 (i 1) 2 } ; c) L 1 { | {a, b} }, L 2 { b n | n 0, {a, b} }, { ( , b n R ) | ∈ {a, b} * , n a ( n — количество символов а в цепочке , R — реверс цепочки ) }; d) L 1 { | {a, b} }, L 2 { a i b k | i, k 0, i k 0 }, { ( , a [ n /2] b [ m /2] ) | ∈ {a, b} , n a , m b ( здесь [x] — ближайшее к x це- лое, например: [1/2] = 1, [1/3] = 0, [5/3] = 2) }; e) L 1 { | {a, b} }, L 2 { a i b k | i, k 0, i k 0 }, { ( , a [( n+ 1)/3] b [ | m-n | /2] ) | ∈ {a, b} , n a , m b }; f ) L 1 { | {0,1} , (i) 2 R , i 0 (т. е. — реверс двоичной записи числа i ) }, L 2 { | n | n 0 }, { ( , | i ) | {0,1} , (i) 2 R , i 0 } 5. Построить грамматику, описывающую целые двоичные числа (количество 0 и 1 четно, допускаются незначащие нули). Вставить в нее действия по переводу этих целых чисел в четверичную систему счисления. 6. Построить грамматику для выражений, содержащих переменные, знаки операций , , , , и скобки ( ) с обычным приоритетом операций и скобок. Включить в эту грамматику действия по переводу выражений в префиксную запись (операции предшествуют операн- дам). Предложить интерпретатор префиксной записи выражений. 7. В грамматику, описывающую выражения, включить действия по переводу выражений из инфиксной формы (операция между операндами) в функциональную запись. Например, а b (a, b), a b c (a, (b, c)). V. ПОЛИЗ, перевод в ПОЛИЗ 1. Представить в ПОЛИЗе следующие выражения: а) a b c b) a b c/a c) a/(b c) a d) (a b)/(c a b) Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ 110 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) 2. Для следующих выражений в ПОЛИЗе дать обычную инфиксную запись: а ) 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 3. Используя стек, вычислить следующие выражения в ПОЛИЗе: а) 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. В языке Си присваивание является операцией, а не оператором, поэтому при интерпретации ПОЛИЗа присвоенное значение сохраняется в стеке (как результат операции). Чтобы удалить ненужное значение с вершины стека (такие значения остаются в стеке, например, после испол- нения оператора-выражения), в ПОЛИЗе языка Си используется операция " ". Задачи / V. ПОЛИЗ, перевод в ПОЛИЗ 111 Чтобы отличить префиксные операции и от постфиксных, префиксные обозначают в ПОЛИЗе как +# и –#, а постфиксные как + и #– соответственно. ПОЛИЗ вызова функции представляет собой последовательность ее аргументов в ПОЛИЗе, за которыми следует имя функции. Для функций с переменным числом параметров перед именем функции в ПОЛИЗ вставляется дополнительный аргумент — количество фактических парамет- ров в данном вызове функции. При интерпретации сначала из стека извлекается этот дополни- тельный аргумент, а затем — соответствующее ему число фактических параметров. 5. По заданному ПОЛИЗу выражения записать его в инфиксной форме (на Си). a) x y z a x 5 y / z 6 8 ; b) x a x z y / z 6 a 6. Является ли запись ПОЛИЗ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 y 15 = ; x x a b c 2 / 1 + * - * a 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 - = ; y y 2 - = ; y 10 <= 5 !F правильной записью в ПОЛИЗе следующего фрагмента программы на Си (считаем, что эле- менты ПОЛИЗа нумеруются с 1): y 15; |