И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901), страница 6
Текст из файла (страница 6)
стр. 37-38), позволяющий в некоторых случаяхполучить грамматику, к которой применим метод рекурсивного спуска.53. Какой язык порождает заданная грамматика? Провести анализцепочки (a,(b,a),(a,(b)),b)⊥.S → <k = 0> E ⊥Ε → A | (<k=k+1; if (k == 3) ERROR();> E {,E}) <k = k-1>A→a|b54. Есть грамматика, описывающая цепочки в алфавите {0, 1, 2, ⊥}:S → A⊥A → 0A | 1A | 2A | εДополнить эту грамматику действиями, исключающими из языка всецепочки, содержащие подцепочки 002.55. Дана грамматика, описывающая цепочки в алфавите {a, b, c, ⊥}:S → A⊥A → aA | bA | cA | εДополнить эту грамматику действиями, исключающими из языка всецепочки, в которых не выполняется хотя бы одно из условий:••в цепочку должно входить не менее трех букв с ;если встречаются подряд две буквы а, то за ними обязательнодолжна идти буква b.56.
Есть грамматика, описывающая цепочки в алфавите {0, 1}:S → 0S | 1S | εДополнить эту грамматику действиями, исключающими из языка любыецепочки, содержащие подцепочку 101.57. Написать КС-грамматику с действиями для порожденияL = {am bn ck | m+k = n либо m-k = n}.58. Написать КС-грамматику с действиями для порожденияL = {1n 0m 1p | n+p > m, m ≥ 0}.59. Дана грамматика с семантическими действиями: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() >Какой язык описывает эта грамматика ?60.
Дана грамматика:S → E⊥E → () | (E {, E}) | AA→a|bВставить в заданную грамматику действия, контролирующие соблюдениеследующих условий:1. уровень вложенности скобок не больше четырех;2. на каждом уровне вложенности происходит чередование скобочныхи бесскобочных элементов.61. Пусть в языке L есть переменные и константы целого, вещественногои логического типов, а также есть оператор циклаS → for I = E step E to E do SВключить в это правило вывода действия, проверяющие выполнениеследующих ограничений:1.
тип I и всех вхождений Е должен быть одинаковым;2. переменная логического типа недопустима в качестве параметрацикла.Для каждой используемой процедуры привести ее текст на Си.62. Дана грамматикаP → program D; begin S {; S} endD → var D' {; D'}D'→ I {, I}: record I: R {; I: R} end | I {, I} : RR → int | boolS → I := E | I.I := EE → T {+T}T → F {*F}F → I | (E) | I.I | N | L ,где I - идентификатор, N - целая константа, L - логическая константа.Вставить в заданную грамматику действия, контролирующие соблюдениеследующих условий:1.
все переменные, используемые в выражениях и операторахприсваивания, должны быть описаны и только один раз;2. тип левой части оператора присваивания должен совпадать стипом его правой части.Замечания: а) все записи считаются переменными различных типов(даже если они имеют одинаковую структуру);b) допускается присваивание записей.Генерация внутреннего представления программРезультатом работы синтаксического анализатора должно бытьнекоторое внутреннее представление исходной цепочки лексем, котороеотражает ее синтаксическую структуру. Программа в таком виде вдальнейшем может либо транслироваться в объектный код, либоинтерпретироваться.Язык внутреннего представления программыОсновные свойства языка внутреннего представления программ:1.
он позволяет фиксировать синтаксическую структуру исходнойпрограммы;2. текст на нем можно автоматически генерировать во времясинтаксического анализа;3. его конструкции должны относительно просто транслироваться вобъектный код либо достаточно эффективно интерпретироваться.Некоторыепрограмм:общепринятые1. постфиксная записьспособывнутреннегопредставления2.3.4.5.префиксная записьмногоадресный код с явно именуемыми результатамимногоадресный код с неявно именуемыми результатамисвязные списочные структуры, представляющие синтаксическоедерево.В основе каждого из этих способов лежит некоторый методпредставления синтаксического дерева.Замечание: чаще всего синтаксическим деревом называют деревовыводаисходнойцепочки,вкоторомудаленывершины,соответствующие цепным правилам вида A → B, где A, B ⊂ VN.Выберем в качестве языка для представления промежуточной программыпостфиксную запись (ее часто называют ПОЛИЗ - польская инверснаязапись).В ПОЛИЗе операнды выписаны слева направо в порядке ихиспользования.
Знаки операций стоят таким образом, что знакуоперации непосредственно предшествуют ее операнды.Например, обычной (инфиксной) записи выраженияa*(b+c)-(d-e)/fсоответствует такая постфиксная запись:abc+*de-f/-.Замечание: обратите внимание на то, что в ПОЛИЗе порядок операндовостался таким же, как и в инфиксной записи, учтено старшинствоопераций, а скобки исчезли.Более формально постфиксную запись выражений можно определитьтаким образом:••если Е является единственным операндом, то ПОЛИЗ выражения Е- это этот операнд;ПОЛИЗом выражения Е1 θ Е2, где θ - знак бинарной операции,Е1 и Е2 операнды для θ, является запись E1’ E2’ θ , где E1’ и E2’ ПОЛИЗ выражений Е1 и Е2 соответственно;••ПОЛИЗом выражения θ E, где θ- знак унарной операции, а Е операнд θ, является запись E’ θ, где E’ - ПОЛИЗ выражения Е;ПОЛИЗом выражения (Е) является ПОЛИЗ выражения Е.Запись выражения в такой форме очень удобна для последующейинтерпретации (т.е. вычисления значения этого выражения) с помощьюстека: выражение просматривается один раз слева направо, при этом••если очередной элемент ПОЛИЗа - это операнд, то его значениезаносится в стек;если очередной элемент ПОЛИЗа - это операция, то на "верхушке"стека сейчас находятся ее операнды (это следует из определенияПОЛИЗа и предшествующих действий алгоритма); они извлекаютсяиз стека, над ними выполняется операция, результат сновазаносится в стек;•когда выражение, записанное в ПОЛИЗе, прочитано, в стекеостанется один элемент - это значение всего выражения.Замечание: для интерпретации, кроме ПОЛИЗа выражения, необходимадополнительная информация об операндах, хранящаяся в таблицах.Замечание: может оказаться так, что знак бинарной операции понаписанию совпадает со знаком унарной; например, знак "-" вбольшинстве языков программирования означает и бинарную операциювычитания, и унарную операцию изменения знака.
В этом случае вовремя интерпретации операции "-" возникнет неоднозначность: сколькооперандов надо извлекать из стека и какую операцию выполнять.Устранить неоднозначность можно, по крайней мере, двумя способами:1. заменить унарную операцию бинарной, т.е. считать, что "-а"означает "0-а";2. либо ввести специальный знак для обозначения унарной операции;например, "-а" заменить на "&a".
Важно отметить, что этоизменение касается только внутреннего представления программыи не требует изменения входного языка.Теперь необходимо разработать ПОЛИЗ для операторов входного языка.Каждый оператор языка программирования может быть представлен какn-местная операция с семантикой, соответствующей семантике этогооператора.Оператор присваиванияI := Eв ПОЛИЗе будет записан какI E :=где ":=" - это двухместная операция, а I и Е - ее операнды; I означает,что операндом операции ":=" является адрес переменной I, а не еезначение.Оператор перехода в терминах ПОЛИЗа означает, что процессинтерпретации надо продолжить с того элемента ПОЛИЗа, которыйуказан как операнд операции перехода.Чтобы можно было ссылаться на элементы ПОЛИЗа, будем считать, чтовсе они перенумерованы, начиная с 1 (допустим, занесены впоследовательные элементы одномерного массива).Пусть ПОЛИЗ оператора, помеченного меткой L, начинается с номера p,тогда оператор перехода goto L в ПОЛИЗе можно записать какp!где ! - операция выбора элемента ПОЛИЗа, номер которого равен p.Немного сложнее окажется запись в ПОЛИЗе условных операторов иоператоров цикла.Введем вспомогательную операцию - условный переход "по лжи" ссемантикойif (not B) then goto LЭто двухместная операция в операндами B и L.
Обозначим ее !F, тогда вПОЛИЗе она будет записана какB p F!где p - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой L.Семантика условного оператораif B then S1 else S2с использованием введенной операции может быть описана так:if (not B) then goto L2; S1; goto L3; L2: S2; L3: ...Тогда ПОЛИЗ условного оператора будет таким:B p2 !F S1 p3 ! S2 ... ,где pi - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой Li, i = 2,3.Семантика оператора цикла while B do S может быть описана так:L0: if (not B) then goto L1; S; goto L0; L1: ...
.Тогда ПОЛИЗ оператора цикла while будет таким:B p1 !F S p0 ! ... ,где pi - номер элемента, с которого начинается ПОЛИЗ оператора,помеченного меткой Li, i = 0,1.Операторы ввода и вывода М-языка являются одноместнымиоперациями. Пусть R - обозначение операции ввода, W - обозначениеоперации вывода.Тогда оператор ввода read (I) в ПОЛИЗе будет записан как I R;оператор вывода write (E) - как E W.Постфиксная польская запись операторов обладает всеми свойствами,характерными для постфиксной польской записи выражений, поэтомуалгоритм интерпретации выражений пригоден для интерпретации всейпрограммы, записанной на ПОЛИЗе (нужно только расширить наборопераций; кроме того, выполнение некоторых из них не будет даватьрезультата, записываемого в стек).Постфиксная польская запись может использоваться не только дляинтерпретации промежуточной программы, но и для генерации по нейобъектной программы.
Для этого в алгоритме интерпретации вместовыполнения операции нужно генерировать соответствующие командыобъектной программы.Синтаксически управляемый переводНа практике синтаксический, семантический анализ и генерациявнутреннегопредставленияпрограммычастоосуществляютсяодновременно.Существует несколько способов построения промежуточной программы.Один из них, называемый синтаксически управляемым переводом,особенно прост и эффективен.В основе синтаксически управляемого перевода лежит уже известнаянам грамматика с действиями (см. раздел о контроле контекстныхусловий).
Теперь, параллельно с анализом исходной цепочки лексем,будем выполнять действия по генерации внутреннего представленияпрограммы. Для этого дополним грамматику вызовами соответствующихпроцедур генерации.Содержательный пример - генерация внутреннего представленияпрограммы для М-языка, приведен ниже, а здесь в качествеиллюстрации рассмотрим более простой пример.Пусть есть грамматика,выражение:E → T {+T}описывающаяпростейшееарифметическоеT → F {*F}F → a | b | (E)Тогда грамматика с действиями по переводу этого выражения в ПОЛИЗбудет такой:E → T {+T <putchar('+')>}T → F {*F <putchar('*')>}F → a <putchar('a')> | b<putchar('b')> | (E)Этот метод можно использовать для перевода цепочек одного языка вцепочки другого языка (что, собственно, мы и делали, занимаясьпереводами в ПОЛИЗ цепочек лексем).Например, с помощью грамматики с действиями выполним переводцепочек языкаL1 = {0n1m | n,m>0}в соответствующие цепочки языкаL2 = {ambn | n,m>0}:Язык L1 можно описать грамматикойS → 0S | 1AA → 1A |εВставим действия по переводу цепочек вида 0n1m в соответствующиецепочки вида ambn :S → 0S <putchar('b')> | 1 <putchar('a')> AA → 1 <putchar('a')> A |εТеперь при анализе цепочек языка L1 с помощью действий будутпорождаться соответствующие цепочки языка L2.Генератор внутреннего представления программы на М-языкеКаждый элемент в ПОЛИЗе - это лексема, т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
