Главная » Просмотр файлов » И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции.

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

Файл №1114901 И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (И.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции.) 6 страницаИ.А. Волкова, Т.В. Руденко - Формальные грамматики и языки. Элементы теории трансляции. (1114901) страница 62019-05-08СтудИзба
Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 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.Генератор внутреннего представления программы на М-языкеКаждый элемент в ПОЛИЗе - это лексема, т.е.

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

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

Свежие статьи
Популярно сейчас
Зачем заказывать выполнение своего задания, если оно уже было выполнено много много раз? Его можно просто купить или даже скачать бесплатно на СтудИзбе. Найдите нужный учебный материал у нас!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
6430
Авторов
на СтудИзбе
306
Средний доход
с одного платного файла
Обучение Подробнее