Ответы: Экзамен. Варианты заданий и ответы

Файл скачан с сайта StudIzba.com

При копировании или цитировании материалов на других сайтах обязательно используйте ссылку на источник

Распознанный текст из изображения:

ФИО

Вариант 11 2002

№группы

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

2. Привести общую схему работы компилятора. Перечислить основные функции

семантического анализатора.

3. Восстановить грамматику по функциям, реализующим синтаксический анализ методом рекурсивного спуска:

чо]г]80(А(); й(с <='з.'] ЕВВС]й();)

чек] А() ( В(); чгп]!е ( с == 'а') ( с = (де!с((р); В(); ) )

чо]с! В() ( и ( с == 'Ь' ) с = (де!с((р); )

4. Преобразовать грамматику к виду, допускающему детерминированный разбор (использовать алгоритм преобразования НКА к КА).

8-+ Ся

С -+ А ! ! В ! ! 1

А -+ А!',СО]О

В -+ СО]О

5. Дана грамматика с действиями.

Я -> а < а = 1; Ь = О; > А Э.

А-+ а < й(а)(ри!спаг(а), а=о;) е!аеа++;> А]

ЬА< й( Ь](ри!СпаГ('Ь'); Ь= 0;) Е!аЕ Ь+эч >] С

Описать перевод, который она определяет.

б. Написать грамматику. порождаюшую язык Б(О) = ( 0" 1!"'~!. п>1).

Каков тип этой грамматики? Каков тип языка?

7. а) записать на ПОЛИЗе фрагмент программы на С;

! = 1; Я = 0; тчЬ(! е ( 1 < 10 8ссс Б < 40 ) ( Б = Б '- г(1); >.>1; 1;

Ь) выражение на ПОЛИЗе

х ч й а х 5 у г' <- * к б > 8 * — = = =

записать в инфиксной форме ( ца С ).

Библиотека ЯТ1л написать функцию. которая в конец списка вещественных

чисел добавляет элемент. значение которого равно среднему арифметическому всех его

элементов.

Распознанный текст из изображения:

Вариант 12 2002

ФИО

№группы

1. Перечислить основные функции отладчика в рамках интегрированной среды

разработки программного обеспечения.

2. Привести обшую схему работы компилятора. Перечислить основные функции

лексического анализатора.

3. Восстановить грамматику по функциям, реализуюшим синтаксический анализ

методом рекурсивного спуска:

чо(О 8() ( й (с == 'а') ( с = (де1с((р); А(); )

е!ае 11 (с == 'Ь' ) ( с = (де(с((р); В(); )

е1зе ЕВНОВ0;

)

яо1О А()( и ( с == 'с') ( с = (де1с((р); 8()0 )

кок1 В() ( ъчп11е ( с ==" ,) ( с = (де1с((р); и (с! = 'Ь') ЕВРОЙ(); с = (де!с((р);) )

4, Преобразовать грамматику к виду, допускающему детерминированный разбор (использовать алгоритм преобразования НКА к КА).

8-> А)

А -+ ВЬ1а

В -> ВЬ1Ь

5. Дана грамматика с действиями:

8-+ < а = О; > Е.( < рыспаг('З.'); >

е — > а < а = 1;> е < ршсьаг('а'); > 1

Ь < й (а == О) ршспаг('Ь');> Е < ри1слаг('Ь); > 1 с

Описать перевод, который она определяет.

° б. Написать грамматику. порождаюшую язык 1.(О) = ( са"сЬ"с", пВО, т>0 ).

Каков тип этой грамматики? Каков тип языка?

7. а) записать на ПОЛИЗе фрагмент программы на С: (г" (г<х*у->5) а = х<у, х = (х+б)/(а-у); е(зе г = у«2;

Ь) выражение на ПОЛИЗе

х а х х у! -> * г б а - * + =

записать в инфиксной форме ( на С ).

8. ).нблиотека БТ)е написать функцию, которая в конец вектора вешественных чисел добавляет элемент, значение которого равно произведению всех его элементов.

Распознанный текст из изображения:

Вариант 4 2002

ФИО

№группы

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

2. Привести общую схему работы компилятора. Перечислить основные функции синтаксического анализатора.

3, Библиотека БТЬ: дать определение контейнера. Перечислить контейнеры, входящие в состав библиотеки БТ(..

4. Библиотека БТЬл написать функцию, которая по заданному списку целых чисел формирует вектор из элементов списка с четными значениями и распечатывает его содержимое.

5. К какому типу по Хомскому относится данная грамматика (указать максимально

возможный тип)? Какой язык она порождает? Каков тип языка? Выписать грамматику (в состав которой входит только один нетерминал — цель грамматики), подтверждающую Ваш ответ.

Б -э 1АО

1А — ь! !АО!01

б. Преобразовать грамматику к виду, допускающему детерминированный разбор

(использоватыпгорнтм преобразования НКА к КА).

3 — ьЗЬ|Аа(а

А -+ БЬ|а!Ь

7. Определить. применим ли метод рекурсивного спуска к данной грамматике. Ответ обосновать.

Б -+ аАЬс ! А

А -ь ЬВ ! сВс

В -+ ЬсВ ! а ! в

8. Написать грамматику для языка Е1. Вставить в нее действия по переводу цепочек языка Е1 в соответствующие цепочки языка Е2. В качестве действий можно использовать только вызовы функции рц1сйаг()п! с).

1.1=( ас", а Е (а,Ь)',п>=1)

1 2=,' а"с'", где гп — количество символов а в цепочке а)

9. Является ли запись

1, =. Ь и, <, 33,!(Е, а, а, Ь,+,1, -, х, у, у, 2, +, /, -, *, 5,+,=, Ь Ь 2, ч-,=, 4,!

правильной записью в ПОЛИЗе следующего фрагмента программы на С (считаем, что

элементы ПОЛИЗа нумеруются с 1):

Гог( ! = 1;!< и;1=)ь2) а=(а+Ь-1)'(х у/(уь2))+5;

Если не является, то обьясните почему. В этом сл> чае предложите свой вариант ПОЛИЗа

для этого фрагмента программы. Если запись верная, то проинтерпретируйте запись в

ПОЛИЗе при следующих значениях: х = ! 0; у = 2,' а = 3; Ь = 4; и = 4.

Распознанный текст из изображения:

Е(Н,О)=ВБ Е(ВБ,О)=ВСБ Р(В,О)=ВСБ Р(ВСБ,О)=ВСБ

Р(Н,!)=В Р(ВБ,$)=, " Р(В,!)= Р(ВСБ,1)= В

Пусть ВБ=Х, ВСБ=У; тогда

Сс Б->ХЛ.!Уз. Х->О У->10!ХО!ВО В->У!!1

№3 — вар.б либо №1 — вар.8

Е!КБТ(А) = (а,с); РО1Л.0%(А) = (Ь) -я пока хорошо

Е(КБТ(1)) = (Ь); Е01.ЬОЮ(Р) = (а,Ь,с) Ф РС-метод неприменим

№4 — вар.б либо №4 — вар.8

б Б->180)А С), ~(

А -> ОА ! 0 зч1)- (

Ск Б -> !БО <ри1сЬаг('0');> ! А

А -> 0 <риссЬаг('1'); ршсЬаг(') ')> А1! 0 <ршсЬаг('1'); риссЬаг(' ! ');>

у',). 1 ю~'. )~ /

№5- вар.б либо №3 — вар.8

1, О, =, Б, О, =, 1, 5, <, 34,! Р, 18, 1, 1, ®, 7, 1, Б, Б„а 1, Д; х, яп„Б, -, 2, +, ~, +, =, 14,!

— <

/, /

''7 = '-.,з -' Д'„; '~ М 1 пи~ т) 'Х'- „.~ -'".(

' /

ъ! з~ в ут'

( Ф'~ВЕТЫ::: вар.б либо №2 — вар.8 рачиваюшая грамматика Грамматика б = (ЧТ, ч'Ы, Р, Б) называется леукорачивающей грамматикой, правило из Р имеет вид а -з (3, где а,13 ('Л 1Гг1)' и ! я ! <= ! !3 !.

( а"Ь"с~", и>=! ) — язык типа ! №2 — вар,б либо №5 — вар.8

к--,о ! -) ~~,(,)<, 1,' Д

Распознанный текст из изображения:

ответы::;

вар.7

Р(Н,а)=ВБ Е(ВБ,а)=ВБ Е(С,а)= Р(Н,Ь)= Р(ВБ,Ь)=С Р(С,Ь)= Р(Н,с)= Р(ВБ,с)= Р(С,с)=Б

Р(Б,а)=ВБ

Р(Б,Ь)=

Р(Б,с)=

Пусть ВБ=Х, Б=У, Б'=Б; тогда

с г„= ~)

-б: Б->Х! (У! Х->Ха!та~а У->Сс С->ХЬ

№3 — вар.5 либо №1 — вар.7

Р1ВБТ(А) = (а,с); РОЫ.0%(А) = (Ь)

И1КБТ(1)) =. (4); РО(.ЬО%(0) = (а,б) зь РС-мегол неприменим

' 'з

(№4 — вар.5 либо №4 — вар.7

Сс 'Б-> 1БО ) А

А -> ОА1 ! е

Сс Б -> 1 <ригсЬзг(' ! ');>БО <ригсЬаг('0*)! рнгсЬаг('0');> ! А

А -> 0 <ригсЬаг('1');> А ! ! е

№5 — вар.1 либо )АЗ вЂ” вар.7

1, О, =, а а, Ь, О, !О, -, Ъ„ *, ехр, ~,-„ =, Ь ф1, а, Ь, >, 4, !Т

х

нг,( ° + ~ з! — вар.5 либо №2 — вар.7 грамматика типа 0

-о

Опр. Грамматика б = (ЧТ, ЧЫ, Р, Б) называется граммалгикой типа О, если на правила из Р не накладывается никаких ограничений, кроме тех, что заданы а определении грамматики.

ла

(.(О) = ( (аЬ)"с", п>=0) + 1.(б)-(е) — КС - язык

Распознанный текст из изображения:

ОТВЕТЫ::: Ва ианты 2 и 4::: г амматики

№1 — вар.2 либо №Б — вар.4

тип 1;-неукорачивающая„но не КЗ (из-за альтернативы О1)

(.(О) = ( 1"'010", п>=1) — КС вЂ” язык

Б -> 180 ! 010

№2 — вар.2 либо №6 — вар.4

г(Б,а)= а

г(Б,Ь)= АБ

Р(Н,а)=АБ

г(Н,Ь)=А

г(АБ,а)=Б

г(АБ,Ъ)=АБ

г(А,а)=Б

г(А,Ъ)= Я

Пусть АБ=Х, Б=У, Б'=Б; тогда

Со Б -> Х). ~ У-'

г" -> Аа ) Ха

Х -> ХЬ | 'гЬ ( а

А -> Ь

№3 — вар.2 либо №7 — вар.4

г)ВБТ(В) = (а,Ь); Р01(.ОЧ/(В) = (Ь,с) я РС-метод неприменим

(нетерминализованная альтернатива А в нетерминале Б допустима, т.к. она не является

конкурентом другой терминализованной альтернативе)

№4 — вар.2 либо №8 — вар.4

О: Б->аБ~ЬБ~сА А -> сА ~ с

О'. Б -> аБ «рщсйаг('с');> ( ЬБ ( с <рщсЬаг('а')„>А А -> с <рщсЬаг('а');> А ( с

№5 — вар.2 либо №9 — вар.4

Не является, т.к. изменен порядок операндов в исходном тексте программы в

такая запись не может быть сгенерировала автоматически в процессе синтаксического

анализа. Однако указанная запись семантически эквивалентна исходной.

ПОЛИЗом исходной конструкции является запись

1, =, Ь п, <, 37,!р, 18,! Ь ь 2, +,=, 4, Ь а, а, Ь+ 1,>х, у, у, 2+ /, ~, 5, + ~,=, 11,!

Распознанный текст из изображения:

ОТВЕТЫ::: Ва увиты 10 и 12::: СП и БТ$.

№6- вар.10 либо №1 — вар.12

° пошаговое выполнение программы (шаг=строка; с трассировкой внутри вызываемой

функции и без нее)

° выполнение программы до строки, в которой в редакторе стоит курсор

° выделение выполняемой в данный момент строки

° приостановка выполнения программы:

можно запросить значение переменной

° заказать вычисление некоторого выражения

можно изменить значения переменной н продолжить выполнение

программы (! но редко какой отладчик позволяет изменять программный

код, т.е, поддерживает частичную перекомпиляцию)

° расставитьГснять точки останова, которые визуализируются в текстовом редакторе

° вся информация должна выдаваться в терминах исходной программы

№7 — вар.10 либо №2 — вар.12

исх.пр-ма -> ЛА->посл,лексем+таблицьг->СА->внугр.предст.->КУ->ГЕН->объект,пр-ма

Функции ЛА:

° объединить литералы в лексемы — минимальные элементы программы,

обладаюшие определенным смыслом в анализируемом языке

° сформировать таблицы, которые будут использоваться и пополняться на

каждом из последуюших этапов

° удалить комментарии

№8 — вар.10 либо №8 — вар.12

я)пс)пг(е <(озггеагп>

й(пс1пг(е кчеглог>

пз(п8 паглеярасе зМ;

чогб 8(чесгогсдоцЫе> 8сч)

(чесГог<допЫе>хсопзг «егагог р=ч.Ье8(пО;

допЫе з=1;

ччЬйс (р!=ч.епдО)

з-заир. рч..~ .~

ч.рпвЬ ЬасЦз);

либо

човб Г(чесгог<йоцЫс> гач)

(допЫе з=1; (пг Ь

Гог (г=О; всч.з(аеО„( '-+) з=а*чЯ;

ч.рцзй Ьаск(з);

Распознанный текст из изображения:

ОТВЕТЫ::: Вп униты 2 и 4::: СП и ЯТЕ

№6 — вар.2 либо №1 — вар.4

° пошаговое выполнение программы (шаг=строка; с трассировкой внутри вызываемой

функции и без нее)

° выполнение программы до строки, в которой в редакторе стоит курсор

° выделение выполняемой в данный момент строки

° приостановка выполнения программы:

ьэоээгно запросить значение переменной

° заказать вычисление некоторого выражения

° можно изменить значения переменной и продолжить выполнение

программы (! но редко какой отладчик позволяет изменять программный

код, т.с. оолдерэкнвает частичную перекомпиляцию)

° расставить/снять точки осталова, которые визуализируются в текстовом редакторе

я вся информация догокна выдаваться в терминах исходной программы

№7 — вар.2 либо №2 — вар.4

исх.пр-ма -> ЛА->посл.лексем табэлицы->СА->внутр.предст.->КУ->ГЕН->объект.пр-ма

Функции СА;

° определить, нчсс э ли цепочка лексем структуру, заданную синтаксисом языка

программирования

° зафиксировать.нэ стр) ктурз во внутреннем представлении программы

№8 — вар,2 либо ээяЗ вЂ” вар.4

Контейнер — это класс. опьскты которого предназначены для хранения других объектов. В библиотеку ЯТ1. входят следуюшие контейнеры;

!ли — двчсвязный список

эс-нс — оче едь с да"мя концамн

Р— ' ".'..

пенс - очс .ль

рпопэу цесис - очередь с

п ио итегом

яэасй - стек

шар — ассоцн;пнвный ! ши1бтар — ассоциативный массив, элементы которого

массив ээог т иметь одинаковые ключи

яес - множество ~ пш!пьс! — множество, которое может содержать

, олинаковые элементы

№9 — вар.2;ибо №4 — вар.4

ээ!пс!цг)е <югпгсаэп>

(1)пс1цде <тесгог>

э))пс1цде <1(яг>

ця)пц патеярасе яий

то)я) п(тес!от<)ээг> йьт.!! я(<ш1> яь! яг)

( 1!я(<)пг>цсопяг Нега!от р=)яг.Ьеээ)иВ;

и Ьие (р1=)яг.егн1())

(11'(!(*р%2)) юрия!э Ьасй(*р); р++;)

1ог ((пг 1=0; 1<т.я!ае0; эе+)

сонг«т(э!«" "«~ ээг(1;

соп1«спи!;

)!

!и! пшш()

(эес!огдпп> эт 1ии<ш!> Ьк

(ог(эпг 1=О; !<20: э+ ) Ькрцяй Ьасй(э);

сонг«" Ья! эя сэсээссс!" ' сээь!1;

й(т.! яг);

гепэгп О:

)

Распознанный текст из изображения:

Ответы нд вопросы:::: вариант 1 2003 (первый поток)

. Тип гр.. — 1 (неукорачиваюьций),1.(б)=(а"Ь"с" ~ п=1,2,3,4). Тип языка 3 (регулярный).

2. Метод рекурсивного спуска применим в том случае, если каждое правило грамматики имеет вид

а) либо А -+ а, где о'. с (ь'Т Уг() и это единственное правило вывода для этого

нетерминала;

Ь) либО А -+ а,а~ ! атаз ! ... ! а„а„, где а; Я Ъ'Т длЯ всех ! = 1, 2,..., и; а; ~ а„- длЯ (л); сс; в (~Т ~

ЧИ), т.е. если для нетерминала А правил вывода несколько, то они должны начинаться с

терминалов, причем все эти терминалы должны быть различными,

в' !пс!цг!е < !оз!геагп >

в* !псЫе < !!з! >

цзщ пагпезрасе з!ц;

тою ~ (!!з! <ит!> Ыэ!) (

йз! < !и! >:; гетегье !!ега!ог гр =!э!.гЬей!и ();

мм!!е ( гр!= 1з! гепд()) (

Ьп рцьй Ьасй("'(грз ь))

йы < !и! >, соим !~сга~ог р = !згЬеяш (),

«1и!е ( р'=!и епс( ()) ,'

сош « 'р «'', р-'-:-,

!

соц! «епс!1,

ли ~паиз () ',

1на < 1и! > !э!, !и! ь

Гог (! = О; ! < ! О; !е-) 1ы.рцай Ьасй(!);

Я (15!),

згеинп О,

4. Фаза анализа (исходная программа на ЯП) ~ лексический анализ .=> (послеловатсльносгь лексем)

синтаксический анализ .=> (промежуточное представление программы) =-> семаит ичсский

анализ!1контроль контекстных условий.

Фаза синтеза: подготовка к генерации обьектного модуля => генерация обьелтиого модуля =>

(обьектньш молуль)

5. Проверку контекстных условий часто называют семантическим анализом. Примеры наиболее часто

астр чаюцшхся контекстных условий:

а) каждый используемый в программе идентификатор должен быть описан, но ие более одного

раза в одной зоне описания;

Ь) при вызове функции число фактических параметров и их типы должны соответствовать

числу и типам формальных параметров;

с) ооычио в языке накладываются ограничения иа типы операндов любой операции,

опрелеленной в этом языке; на типы левой и правой частей в операторе присваивания; на

тип параметра цикла; на тип условия в операторах цикла и условном операторе и т и

Г(Н,О) = АВ

Г(АВ,О) = ВЯ

Г(АВ,1) = С

Г(ВБ,О) = ВБ

Р(С,О) = Я

АВ.=» А

ВЯ=>В

б => 0

Два заключительных

состояния Вб и Я сводим

Б -> В3. ! 133. В-+ ВО!АО Л-+ О.

13-+ СО С -э С1 ! А!

Распознанный текст из изображения:

в олно с" => Ь с исп, (..

Уда.тение нелостижигиого кода*

Ь. Оптимизации линейных участков программы: а) удаление бесполезных присваиваний

исключение избыточных вычислений, в) свертка объектного кода, г) перестановка операций

арифметические преобразования ~на Основе алгебраических и логических тождеств)

оптимизация вычисления лоп!ческих выражении.

с Оптимизации передачи параметров в процедуры и функции: а) передача параметров через

регистры процессора,

ра, б) голстановка кода функции вместо ее вызова в объектный кол

д. Оптиз!Нзйпия циклов: а Вь

О, !;,, . ОВ; а) Вынесение инвариантных вычислений из циклов, б) замена операц!Ий

с инлуктивными (Образу!

разу!Ошими арифметическую прогрессию) переменными (как правило,.

умножения на сложение), В) слияние и развертывание циклОВ.

Б — ? ЬБ', аАВ

А — ~ЬсА!ССА!а

В-~сЬВ е

(!(К„"-Т(А)--,'Ь,с'!, ГО(Л 0'Л(А)=!!с,'. г- = (с'!~ О

НР5Т(В)=(с(. ГО( ( 0~0'(В)=И

Б -! ЬЬ аА'

А' — > ЬсА' ссА' В -+ ЬсА' ! ссА' ! сЬВ ' е

-> А — > ЬсА' ссА': с - нелостижих!Ые правила. Нх можно убрать

 — > сЬВ

5-~ Ь5 аА'

Л' — ~ ЬсА'. сЛ'*,(с

=-> А -Ф сА ЬВ

В-+СЬВ.'е

а. Оогцезна гимость солсржимого,

Ь зф!!)сктиВиость.

безопасность.

О. завершенность,

сочетаех!Ость с ОазОВыми типами да!! ных,

Г, должна служить фундаментом для создания других библиотек

10, Е -+ Т (+Т «сои( « '+';>)

Т -> Г (/Г «сои( « У;>)

Г-+ а «сои! «'а';> (Ь<соц! « 'Ь',> ~ (Е)

Распознанный текст из изображения:

Вариант 1 2003 Ф.И.О. Л'а группы

1 '2 3 4 5 б 7 8 9 10

1. Определить тип по Хомскому заданной грамматики б=(т/Т, %Ч, Р, 5).

Определить порождаемый язык и тип языка по Хомскому.

Р: 5-+аАс

аА — к ааВЬС ! аЬ

ВЬ -э ЬЬ ! аЬЬЬс ! аОЬЬЬсс

С -+ с

Π— ~ аЬ

2 Достаточные условия применимости РС-метода.

3. 5Т' 1гыписать функшио, котооая добавляет в конец заданного сшюка1в!<ш!> злементы зтого списка, расположенные в обратном порядке, и печатает по.и швшийся список.

4. Привести с,ему работь! компилятора

5 Основные задачи семантического анализа. Привес~и примеры ситуациГи

когда семантический анализатор выдаст ошибку.

6. Построить ДС. соответствлошую заданной Р-грамматике б=(УТ, ~ Х.!'. 5!

Р: 5-+ВО;СО

В -> ВО,' 0

С вЂ” э С1!Л!

Л вЂ” кО

Если ДС залает ИКА, то по алгоритму преобразования 1Н<Л в КЛ

построить КЛ и написать соответствуюшую ему грамматику, иначе написать

анализатор по заданной грамматике.

7. Основные машинно-независимые оптимизируюшие преобразова~и1я

8. Задана КС-грамматика б=(УТ, ЪЬ1, Р, 5). Если к ией применим ГС-метод,

написать РС-процедуру для любого нетермииала, иначе, если возможно,

преобразовать грамматику так, чтобы РС-метод стал к ией применим.

5 — >Ь5 ! аАВ

А-+ ЬсА ! ссА ! с

В -~ сЬВ!с

9. Основные кр|п ерин просктирования стандартных библиотек.

!О. Написать грамматику арифметического выражения, используюшего операц1ш +, / и круглые скобки (приоритет стандартный), аргументы операций

переменные я и Ь,. например; а+(Ь+а)/Ь/а+Ь. Предполагая, что анализ грамматики будет производить~я РС-методом, вставить в исс действия (в виде соц! « ...) по переводу таких выражений в ПОЛИ3.

Распознанный текст из изображения:

Ответы на вопросы::: вариант 2 2003 (первый поток)

2. Ф 1пс)цг)е < 1озггеагп >

Л (псЫе <» есгог >

омпй пашсарасе зМ;

»оЫ !'(»есгог <с11аг> »Ег») ,'

с!»аг апз="уев"; йи 1=0,

»ссгш < с)шг > сопи исггиог р = м Ьсвп (),

» есгог < сйаг >: гс» егзс цсгагог гр -- » гЬсй!и (),

«10!с (1<= » з)ае()»2) 1

1Г( р '.= "гр) [апз =. "по"; Ьгеа)ч»»

сои! «апз «епг)1;

Гог (1=0;1<» з(ае(),1-'-) сош «с[1],

сош «епг)1; )

ци шаш () ',

сесюг < сйаг > »(5):

[О]='а': [1]='Ь'; [2]='Ь': [2]гыь'; '[4]='а',

Г()

ге!игл О. ',

3 Гексгоаый редактор = (исходныс модули программы) — макрогсисратор и компилятор =- (обьектные модули -библиотеки ) = релакзор связей = (исполняемый файл) .— заг!гбузч»»к = "'выполнение программы> = отладчик — все с начала

5-» С',О).

С-» Сс,' Вс

А-» а

0-» 0Ь [ВЬ

В -» АЬ

ВС~В

В5~ 0

СБ~С

Два заключительных

состояния В5 и С5 сволим

водно 5'=: 5 с исп. 3'

Г(Н,а) = Л

Г(Л,Ь) = ВС

Г(ВС,Ь) = В5

Г(ВС,с) = С5

Г(ВБ,Ь) = В5

Г(С5,с) = С5

5-» аАБЬ [сГАд

А — ьЬА]с[а

ГИ5'Г(А)=»»Ь,с], ГОП0%(А)=(а,с,г)); гл = (с)~ О

5 — »аА'[с

А'-»ЬА'] с5Ь [ 5Ь -» ЬА' [с5Ь [ а А'Ь] сГАг(Ь

А-»ЬА]с[с

5 — » аА' ] СГЛАЗ

° А'-» ЬА' [а А'Ь [сл"

Библиотеки функций (опрелеляют возможности системы, различают библиотеки для языков

программирования и библиотеки для решения задач в конкретной проблемной областц

представляют собой откомпилированные объектные модули),

Библиотеки классов (все ее классы должны быть написаны на том же ЯП, на котором пишется

программа, различают конкретньш классы, абстрактные классы, шаблоны классов,

включаются в программу на агапе компиляции).

° Библиотеки компонент (это готовые откомпилированные программные модули,

предназначенные для использован»и в качестве составной части программы, и котор»иы»г

можно манипулировать во время разработки программы, компоненты б»цва»от локальные ц

распределенные).

Распознанный текст из изображения:

А" ->БЬ ! ГА!)Ь -+ аА'Ь ! сГА!)Ь ! ГА!)Ь - О,К1

А-+ ЬА(с)в

6.

а) выделить в исходном тексте цепо~ку символов, представляющую лексему,

б) удалить пробельные символы и комментарии,

в) зафиксировать в специальных таблицах для хранения разных типов лексем факт появлени~

соответствующих лексем в анализируемом тексте,

г) преобрвловать цепочку символов, представляющих лексему, в пару (тип лексемы,

указатель на >шформацшо о ней),

7 Тип гр. - О, 1 (О)---(О" 1" ! п--1,2,3,4,51. Тип языка 3 (регулярныГ!)

3 Основные свойства языка вн)треннего представления программ:

а) он позволяет фиксировать синтаксическую структуру исходной программы,

Ь») текст на нсч можно автоматически генерировать во время синтаксического анализа,

с) его конструкш!и должны относительно просто транслироваться в обьектньш кол либо

лостаточно эффективно интерпретироваться

») Š— >Т ,'-Т <соц! «'-',>!

1 — > Б,'"'Г <со!д « '"',>',

Г -> а <сош « 'а'.> ' Ь<сои! «Ь' >' ,(Е)

10, 5!виве вылелсиис блоков фиксированного рлзчсрл, которые связыва!отса в с!и!сок !шл

которым достаточно легко выполнять операции их вылсления и освобол;леиия П:носы - если

программа полностью использует блок памяти, то никаких лополнитсльиых расколов ие и»жио С

кажльп! блоком связан указатель на его начало, и надо кран!пь только иифорчацшо о том. занят'олок

или нет Свооолные блоки можно вполшивать» между сооой, используя часть блока лля хранения

указателей, с помощью которых осушествляется обьелинеиис свободной памяти в список. Когла

очерелиой блок свооолной памяти вьшеляется программе, он улаляется из списка, а иачалы!ый

указатель принимае~ значение указателя на слелПоший свооолиый блок памяп! Когда какой-то блок

памяти освобожлается, ои добавляется в список свободной памяти

11виос вылелсиис блоков псремсииогв ряз»>срл. Один из»!с!пав вылелсиия блоков

переменного размера называешься мел!о!)огл периоео по!)>лп)яще;о При вылелсиш! блока размера в

на. ол!!тся первый свооолньи! Олок раз»!ера Г>=5. Затем этот олок разоивасгся !га два " с 1>азчс)>ами 5 и !.

з Но мы можем и не наГпи такой фрагмс>гп Тогда исоо»олимо приоста!швливать выполис!шс

программы и искать все использованные фрагменты и перемешать их например иа лио кучи

Неявное выделение/освобожлсиис памяти. Неявно вылеляемыс блоки памяти также х!ог)-!

оьпь фиксированного или переменного размера. При неявном динамическом вылслеиии и

освосождснии блоков памяти, выделяемые блоки обычно имею~ следуюшу!о структ) ру.

° размер блока (д;ш блоков переменного разя!ера),

° счетчик ссылок, пометка (обычно есть либо одно, либо другое)

Счетчик ссылок подсчитывает количество указателей в программе, которые ссылаются ня

этот блок, если счетчик равен нулю, то блок ие используется и его можно освобол!пь

Существует проблема циклических ссылок, кощ)а счетчики всегда >О.

Пометка фиксирует, задействован данный блок или не задействован. Т.с у программы ест!

хотя бы один указатель, ссылаюшиГюя на этот блок. В некоторый момент иа ишает работат!

«сборщик мусора». Он помечает все блоки как недостижимыс, а потом на~пи!аст анализ текущих

указателей программы. Блоки, на которые ничего не указывает, счита!отса свободными и и»

можно перегруппировать.

указатели на блоки

° то, что досталось пользователю, заказавшему этот блок.

Распознанный текст из изображения:

Вариант 2 2003 Ф.И.О.

№ группы

1 2 3 4 5 6 7 8 9 1О

1. Каковы основные типы библиотек„их краткая характеристика.

2. БТ1.. Написать функцию, которая для заданного вектора ч <с!~аг> проверяет, является ли слово, храняшееся в векторе, патипдромом (одинаково читается с любого конца) и печатает ответ "уев" или "по" и само анализируемое ~лово

3. Привести схему функционирования системы программирования,

4. Построить !(С, соответствуюшую заданной Р-грамматике О=(УТ, Ъ'!4, Р, б)

Р. Б — ~ ВЬ ! Сг.

В -> ВЬ ! АЬ

С вЂ” к Сс , 'ЛЬ

А — >а

Если ДС задаст НКЛ, то по алгоритму прсооразоваиия НКА в КЛ построить КА и написать соотвстствуюгцую ему грамматику, ииа ~с написать анализатор по заданной грамматике.

5 Задана КС-грамматика О=(кТ, 'тХ Р, 5) Если к исй принсипи РС-метод написать РС-процедуру для люоого нетерминала. иначе, если 'возможно преооразовать грамматику так, чтобы РС-метод стал к ней применим.

б-> аЛБЬ с1.М

Л->ЬЛ'с с

6. Основные зада ш лексического анализа.

7, Определить тип по Конскому заданной грамматики О=('~"!', т.". Р. З)

ОП!!слепить по1гожгитецый язык и тип языка по,',омскоис

Р Б — >ОЛ!

ОЛ вЂ” э ОВ1;0

В1 -+ ОС!1~01

С-к 00)0001~0

(3 -+ 01

8. Свойства языка внутреннего представления программы

9. Написать грамматику арифметического выражения, используюшего операции

и круглыс скобки (приоритет стандартный), аргументы операций переменные а и Ь, например: а-Ь-аЯЬ "(а-Ь). Предполагая, по анализ грамматики будет проводиться РС-методом„вставить в нее действия (в виде соц! « ...) по переводу таких выражений в ПОЛИЗ.

10. Основныс методы дюгамичсского распределения памяти (явиого и

неявного).

Распознанный текст из изображения:

Ответы вд вопросы:.":: вариант 5(7) 2003 (первый поток)

1(4).а х,у,+,а,1,х,+,*,<,25,!г,а, Ь, +,Е, с, с(, -, I, 2, *,30,!, х++,5, +,=,

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 '1 7 18 19 20 21 22 23 24 25 26 27 28 29 30

Е - унарный минус

2(9)<Схема работы "чистого" компилятора; (исходная программа на ЯП) => лекс

лекснческии анализ+

синтаксический анализ + семантический анализбконтроль контекстных условий + генерация

объектного модуля =-> (объектный модуль)

Схема работы "чистого" интерпретатора: (исходная программа на ЯП+ входные данные) .=>

интерпретатор =.> (результаты работы исходной программы на входных данных)

Смещяшая стратегия тршгсляиии: (»сходная программа на ЯП) =э лексическшй анализ +

синтаксический анализ+ семантический анадиздконтроль контекстных условий > (промежтточнос

гредставдение программы +входные данные) => интерпретазор промежуточного прс ~ставдеиия

(результаты работы исходной программы иа в: одиых данных)

3 (10). Ф!пс!цде <юмгеат>

Й!пс(цбе <зесюг>

Ф!пс!цае <1ик>

изгой пащезрасс ад.

л Ы 8(хее!ог<пи> Аг, !на<ни> Ым) [

!шй5,

Гог (! = 05 = О, ! < з з1ае(), 1--, 1--:)

5=5 †'х[1]:

!ки<ин> йсгмог р = !м,Ьс йи1().

Р

и!и!с (р,=!м епо())

'р= р 5.

р

1((р'=!м епс)()) р++;

!

'. (2) Перечислить типы Пхамзгатик ио Хомскому и описать соотношении мс;кду ними.

Т11П 0 - любые.

Т1! П 1: неукорачивающая лиоо «онтекстно-зависимая ( КЗ )

Т11П 2: контекстно-свободная (КС ) либо укорачивающая коитекс пю-свободная ( УКС )

ТИП 3: регулярная праволинейная либо регулярная леволииейная

Соотношении !иезкду типавяи грамкаатик:

(1) любая регулярная грамматика является КС-грамматикой;

(2) любая регулярная грамматика является УКС-грамматикой;

(3) любая КС-грамматика является УКС-грамматикой;

(4) люоая КС-грамматика является КЗ-грамматикой,

(5) любая КС-грамматика является неукорачивающей грамматикой;

(6) любая КЗ-грамматика является грамматикой типа О.

(7) любая неукорачивающая грамматика является грамматикой типа О.

(8) любая УКС-грамматика является грамматикой типа О.

Заме гяиис: УКС-грамматика, содержащая правила вида А -+ в, не является К3-грамматикой и

ие является неукорачивающей грамматикой.

5 (6). Основные задачи синтаксического анализа:

° установить, имеет лн цепочка лексем, получаемая от лексического анализатора, структуру,

заданную синтаксисом лзьиса

° зи[шксировать зту структуру (на некотором языке внугрсинего представления)

Примеры ситуаций, 'когда сшггакснчсский анализатор выдаст ошибку, - л1обыс синтаксические

ошибки

Распознанный текст из изображения:

б (з). г(н,о) = с

Г(С,о) = С

Г(С,1) = А

Г(А,О) = В5

Г(В5,1) = А5

Г(А5,0) =- В5 А5 =» К 5- Р)-!0.01В.Ь

Г(Л5,1) = 5 В5 0 Р -+ Р1! Е!

Г(5,1) = 5 5 =» Р К-> 01

Три заключительных О Ао! Во

состояния А5, В5 и 5 сводим А-> С1

в о»но Б' ~ Б с исп. С->СО!О

7 (5). Основные функции текстового редгистора в рвянсях ИСР программного обеспечения,

примеры интеграции текстового редактора с другнмн компонента>ни

подготовка текста программы (ооычные действия по созданшо, редактированию, сохраненшо

файла с текстом программы),

2 многооконный интерфейс с поллержкой режима "оуксировки" фрагментов текста мышкой

(дгаЫдгор),

3. интеграция с компилятором

° визуализация текста с вызелением лексем (синтаксическая полсветка элементов языка)

лополнение кола интерактивная подсказка (а, =: получаем список все. членов класса Гг о>

контекстный список параметров метола Г).

° шаблоны кола (на "горя-иг" клав илах - ~асго использусмгкс программные ко |са рк кции)

всплывающие подсказки об атрибутах идентификаторов, если на них )стаиовить курсор

отобра>кен~ с ошибок. обнар)>ксш|ых на згапс комш:ляшш, в тексте программы,

4 интеграция с отладчиком

отображение контрольны' точе) останова и!3« отладке.

° отоора>кение текушего значения ооьекта. при навелении курсора на идентификатор

8 (7). 5 — > 5а '. 5ЬЬ ! ГЛс 5 -> ГЛс5' 5 — > ГЛс5'

Л->аВ г) (левая рекурсия) 5'-+ а5'! ЬЬ5, с 5' — > а5') ЬЬ5'; с

В -> аЬВ 5Ь => А — >аВ!д => А>аВ!г!

 — > аЬВ ! 5Ь В -+ аЬВ ! (Ась'Ь

Г!Р5Т(5')=(а,Ь), ГО~Л.О>>(5')=,'Ь); гл = (Ь)~ О

5 -+ ГАс5' 5 -> ГАс5'

5' — > а5'1ЬЬ5'! с 5'-+ а5'~ ЬЬ5'! в

— А->аВ,:д .=> А — >аВ,'г(

 — > аЬВ , ,'ГЛс5"  — > аЬВ 1 ГЛс5"

5"-> а5" ~ ЬЬ5" ! Ь 5"-> а5" ~Ь5"'

5 "' — > Ь5" ! с

Г)Р,5Т (5"')=(Ь' Г01Л Ор/(5'")=(с), - = О =» О К!

9 (!), Дать определение итерятора. к)см отличаются обратиыс итсраторы от пряча>ыху 11ривссзи

примеры использования итсраторов этих типов,дать пояснения к примерам.

Итсратор — это класс, обьекты которого по отношеншо к контейнерам играют роль указателей

Они позволяе~ получить доступ к содержимому контейнера. Прямые илераторы (при их продвижении

с помошью операции ++) проходят последовательность элементов контейнера от начала к его концу;

обратные итераторы в такой же ситуации проходят последовательность от конца к началу.

Примеры 1) Ь81лсопз! «ега1ог р = (з1.Ьея!«О, //прямой итератор, установили на начало списка

тк Ьйе (р 1= !а1.епг)О) // пока р не будет указывать «за конец» списка

( соц! « *р «" "; р++; ) // печатаем очередной элемент и переходим на

//следующий за иим

2). йз!<1п1>«сопя! гсгегзе «ега!ог р = !а!.гЬеоо!«О,//обратиьш итсратор, уста~юлили его иа

//последний элемент списка

>кййе (р 1= 1з1.епс3О) // пока р не будет указывать «за начало» списка

( соц! « *р «" *'; р++; ) // печатаем очередной элемент и переходим к

//предшествующему элементу

10 (8). 5 — > а < сог««'1',> Л < соц1 « *О*;>~ Ь < соц! «'1';> Л

Л вЂ” >, а < соц! «'1';> Л < соц! « '0';>~ Ь < со«1 «' Г;> Л ) в

Распознанный текст из изображения:

Вариант 5 2003 Ф.И.О. М группы

ф:::,".;;:..',; 2:1:Э;:.",,'!", :4 5 ''",61!';..'.!',: 7:;:Я":;.';;;,.''.' 9;::,'~'(')':::

1. Записать на ПОЛИЗс фрагмент программы на С:

а = к +) < ея(! + к) " .- (а + Ь) >(с-с!)*2; ++к+5:

2.Типы трансляторов. осооснности комшгляторов и иитсрпрстаторов, Смешанная сгра-

тсгия траисляции.

„", 5З Ь Описать ф) нкцию с лвумя парачстрами, которая в заланноч векторе цслык шссл наколит сумму его элементов. имс1ошик чстиыс Номера. Затсч в задаю>ом списке цсльг'' ~и>сел 1всличиваст Всс сго злс>1снты. Н>1сюш!ю нсчстиыс но>!сра. на эт> Всличин>, Номера злл1снтов на шн:!ются с О (и в всктОрс. и в списке. О - четное число)

4 Псрс шслить типы граччатик по Хсоюком) и описать соотношения мс>кл> Ними,

Осиовныс за зачи синтакси юского впали>а Привес>и иршыры сит) аций. кш та сиитакси'и."ский вилли.1атор выласт ОшиОкъ.

б Построи>л ДС. соотвстств) юш) 1О заланиой Р-граччатикс С=(>"Г. 'тЕ. Р. 5)

Р. 5 — >5! ,'ЛО

Л вЂ” > !!! С!

В->АО

С > СО,О

Если ДС залает НЕА. то по алгоритм) прсобразоваиия НЕА в ЕА постро1п ь ЕА

и написать соотвстствуюшую ему грачматик). иначе написать ан:пизатор по зазаиной

грамматике.

2. Перечислить Основныс ф> нкции тскстОВОГО рсдакто!и В ра>!как интсгр! 0>оваи1юи срслы разработки программного обсспсчсш1я. Привссти примеры иитсграции текстового редактора с лругиаш компонентами этой срслы

3. Залана КС-грамматика б=(УТ, УХ, Р, 5). Если к ней применим!'С-чстол. написать РС-процсл)ру лля любо!о нстсрминала, ииачс, сели возможно, прсобразовать гра>1>1атику так. чтобы РС-метод стал к ней применим.

5'- 5а!5ЬЬ!ГАС

А -> ВВ ! !)

В->аЬБ !5Ь

9. Дать опрслслсние итсратора. Чем отличаются обратныс итсраторы от прямы '? При-

вести примеры использования итсраторов этик типов, дать поясисиия к причсрам,

10. Написать грамматику для языка 1.1. Вставить в псе действия по перевозу цепочек языка 1.! в соотвстству!Ощис цепочки языка Ь2. Б качестве действий ыожио использовать только сои! << ...СУ-перевод проискод>п во время анализа методом рекурсивного спуска.

Ь1 = ( гв П (а,Ь)", где содер>китов и символов а и п> символов Ь, расположсинык в произвольном порядке; и, п1 >= 0; и+ш > 0 )

1.2 = ( 1"'"'О" (и, гп >= О;и+гп > 0)

Распознанный текст из изображения:

Ответы нд вопросы:::: вариант 6(8) 2003 (первый поток)

1 (1О), Дать определение контейнера. Перечислить контейнеры разных типов

типов, входящие в

состав библиотеки ЯТ(- Дать кратку>о характеристику каждо>ау из перечисленных

контейнеров.

Контейнер — зто класс, ооъекты которого предназначены,аля хранения других объектов.

В БТ1. определены следуюшие контейнеры:

чессог- динамический массив

Г>з1 — двунаправленныГ! список

всас(с - стек

с)иес>е - очерель

!пар — ассоциативный список (пары — ключ и значение)

зе1 — множество, где каждый злемент уникален

-' (б).

б!псЫе

е!пс!с!с)е '<кессог>

='!псЫе <1!зс>

мыпб !га!Ве>>заве з! '.

мо!о 01' ес!ог с<к, 1!5!

,'!п! !. 5.

!!>с

и Ь!1с (с!'=.)з! епс)!))

! В=Б "'Ч. 0!'':.

!Г(г! '.= В! епс)()) 0-'ч.,

!

1ог (! = 1. ! < 10; ! -= 2) > И = ф)-5,

!

5-> Х' )У Х > Ха ! '>'а 'а У-> Сс С->ХЬ

4 (7). Г(Н.а) -- ВБ

Г(ВБ.а) = В5

г(ВБ,Ь) = С

Г(С,с) = Б

Г(~, )=ВВ

Два заключительных

состояния ВБ и 5 сводим

в одно Б' ~ 5 с исп. 1.

Б -+ сЛд

Л-> ЬВЛ'

К-+ аК! а

В->аЬВ)а

Г!АКТ(В)=(а), ЕО1 ) 0%(В)=-(а,с$); г> = (а)х О

р!!" ЯТ(Л)=(а), ГО(Л ОИ(К)=(с)); г> = 1<)

5 -> сЛс) Я -> сЛс!

=> А-> ЬВ' =э Л-> ЬВ'

А'-> аЛ'! е Л'-> аЛ'(в

В' — > аЬВ' ! Л' В' -+ аЬ13' ! аЛ'! в

5 (2). б — > сМ

А -> Ла ! ЬВ (левая рекурсия)

В -> аЬВ ! е

ю~

В -+ сЛс!

Л вЂ” > ЬВ'

л — > аЛ)6

В'-+ аВ" )е

б -+ сЛс)

Л вЂ” > ЬВ' =>

Л'-> аЛ'! а

В' — > аВ" (с

3 (1). Этапы ж>сзиеииого никла программного продукта. 10раткап характеристика кя>кло!.о

зтапа.

1 Лнализ, пель — опрслслсги!е треоований к булусисму программного продукту

2 Проектирование, резус!ьтат — концепт)альпах с;сма ар>ппсктуры булугисй системы

3 1 салола!и!я ьол!!рованис тестирован!ге отладка

-1 Сопрово>кление зво.помня программного прод)кта прп с!о зксплугпаиии

Распознанный текст из изображения:

В"-> ЬВ' ( аА'1 е

В"-> ЬВ' ! А'

Г(й.8т(В')=(а), ГО "(-О«'«((В )=Ж '

г!Ют(В")=(а,Ь), ГО(-(-О® Р )=1«с() '

б (8), Основные задачи редактора связей:

он должен разрешить межмодульные связи (для ' объектных файлов, порожд

компилятором при раздельной трансляции модулей, составляющих программу)

должен связать Объектные файлы, порожденные компилятором, и библиотечные ф "

течные фаилы,

ВК1>дящие в сос~а~ системы п)зограммирования (для статически связ1,!Ваек1ых библиотек)

Пример сит)»ации, когда редактор сВЯзсЙ Выдаст Ошиоку: какая-либо из Внешних ссылок Осталас1,

нс~изрешсннОЙ.

7(б).

Бху+=!1=~ О=) и <39!р23! )++12! 88 ! ) ~ 5 ' +=- ! ! х = 19!

12345678910!1 12!3 14 15 1617 18 192021222324252627282930313233 3435363738

8 (3). Дать Опрелслсиис типа языка по Хок!Скому. Описать соотношения между Языка«и! разли !Иых

т1гпов

«»1 !'. сдс. »«';1»!»с; Язык ( 1««») ЯвлЯсУСЯ Языком типа к. ссл и с1 О «1ож11О О!11!Сать ! !>В«1«1а Г11кой 1 ииа 1,"

и нсльзЯ Описать грамматикой! Типа );+1.

Соотиои1сиия мсжлу типлзи! из!иков:

(1) кажльи1 рсгуляриьц! Язык яв:!Яется Кс-языко«1, НО су!Исс1ву!От Кс-языки, которые ис

Являются регулярными ( напри«1ср, 1.' = , 'а"Ь"! п>О',)

(2) ка>клы!! 1«С-яз!»1к Являс!Ся ЕЗ-ЯЗ!»!КО«1, ИО сушсству1от Е3-языки. Когорыс ис Являются 1;С-

языками ( например. 1 = ,'а Ь"с"!! п>О,').

(3) каждый ЕЗ-язык является языком типа 0

Зямсчанис; УЕС-язык, солсржащий1 пуст«ю испо»!к«', нс являс!Ся ЕЗ-язык«««!.

9(4). 8-+ а<сов! «'2';> Л <сощ «'а';>'ЬЛ<сощ «Ь';>

Л-> а<сои! «2';> Л<соо! «»а';>'ЬЛ<сои! «'Ь;> !е

10 (9). Осиовиыс фуикиии отлалчикя в рамках 11СР программного обеспечении;

'1. пошаговое выполнение программы (шаг = строка, с трассировкой ви«три вы1ьигасмой ф«икц!Ии и

ОСЗ НСС),

Выполнение программы ло строки, в которой в рсзакто!>с стоит к«'рсор,

3. вылсление выполнясз!ОЙ в за!И1ы!! момент строк«,

4. приостановка выполнения программы;

5. можно запрос!ггь 3!ячсиис пс!Зсх!СИИОЙ,

6. Можно заказать вы шслснис некоторого выражения,

можно изменить значение переменной и продол>кить выполнение программь1,

8. расставить/снять точки останова, которые визуализируются в текстовом редакторе,

9. Вся информация должна выдаваться В терминах исхолиоЙ програк!»«!ы.

Распознанный текст из изображения:

Вариант 6 2003 Ф.И.О.

№ группы

1. Дать опрслслснис контейнера. Перечислить контейнеры разных типов. вхсл»шис в

состав библиотеки 5Т1.. Дать кратку!о характеристику кажлому нз перечисленных

контейнеров.

2. 5ТЕ. Описать ф)нкиию с лвумя параметрами, которая в заланном списке полых чисел нахолит сумму его элементов. имсюших чстныс номера. Затем в заданном векторе исльг чисел увели кивает все его элементы. нмсюшнс нечетные ноз!с!за. на эту вели шну, Номе!за элементов нгпшнаютея с О (и в векторе. и в списке: Π— !стпос число)

3. Этапы жизненного никла программного прел) кла. (храткая характериспика ка,клоке

этапа

ч. Построить ДС. соотвстсзв) юш) ю каленной Р-гром гаи!кс О='(Л'Т Л"У Р. 5)

Р 5 -+ 5а ' Сс.:' а

С-+ЬЬ

 — ! 5а!а

Если ДС залает Н)Л. то по алгорит!г и!жооразоваии» ! !!Е Л в (х Л пое!Рени ь )хЛ

и написать соотвстств) юш) ю ему г!заюатик). иначе написать а!ш.иыа гор по залаииой

тра оштике.

3, Залана )хС-тра!!э!алика О=(Л!Т. ЛХ Р, 5). Если к нс!! прим»ч!ю! РС-,мото,!, написать

РС-пропел) ру лля любого нстсрминала. иначе, если возможно. ирсоораюкать

граюатик) так. чтобы РС-могол стал к ней применим

5 -> сЛг)

Л -+ Ла'ЬВ

В-!ЗОВ е

б Оспою!ыс зала и рслакто!га св»зсй. Г1ривссти примеры с!и) а!ии!. ког ц р. дк!ор

ск» ый вы'!аст оиигбк!

7. Записать на ПОПИЗс ф!югмснт программы иа С: 5 = х-,у; ! = 1; Го! (! = О; ! < и )- ) , '5 = 5 + !'!" 5. ! = !*х. ',

Х. Дать опрслслснис типа языка по Хоз!ско!!у. Описать еоотиоиыии» х!сж.р»з!!к!!!и!

различных типов

9. Написпь граюштик) лля языка 1.1. Вс~ави~ь в нес лсГ!етвия по псрсво.г, испочьч!

»зыка С! в еоотвстству!ошне цепочки языка Е2 В качестве лсГютвий можно

использовать только сои! « ., СУ-перевел происхолит во время анализа мстолом

рекурс!юного спуска

11 = ( ы П (а,Ь) . тле еолсржится и шышолов а, располо>ксииьг! в

произвольном порялке: и >= О)

Е2 = ( 2'в!к(и >= О, ык- реверс испо!ки в! )

!О. Перечислить основиыс функции отлалчика в рамках и!псгрироваииой срелы

раз«к

аз))лботки программного обеспечения. Привести примеры иитсграиии отлатч!и;в с

лр)тими компонентами этой срслы.

Распознанный текст из изображения:

Вариант 3 2005 Ф.И.О.

№ г1зуппы

Гг )з1з 14 1т~з 17 ~«1д т рГ1

3. Написать грамматику для языка 1!. Вставить в иее действия по переводу пеночек

языка 1.1 в соответстау1ощие цепочки языка 1.2 1в ходе анализа цепочек языка 1.1

методом рекурсивного спуска). В качестве действий допустимо только использование

оператора соФ << ., °

» „Ье

1,2 = 1 0"'1"'", где в — количество символов с в папочке ц.,

к — количество символов д в папочка Й 1

4, Дана В=грамматика б = ~7Т, ЪЪ, Р, Б). Определить, применим ли к ней метод

рекурсивного спуска. Ответ обоспонать.

8 -+ аБИ 1 ЬАГ ~ я

А -+ ЬАс ~ сЗ

В -+ сВ10

Р: 8-+Ва~Аа~БЬ~а~Ь

А -+ Ба ~ АЬ ! а

7. Дать определение недостнхгимого символа грамматики. Привести

грамматики, содержа~~й напасти®иный символ.

Распознанный текст из изображения:

2. Дана КС-Грамматика й = (УТ, ЪЪ, Р, б). Определить„применим ли к ней метол

рекурсивнОГО спуска. Ответ Обосноийть.

б-+аБВ~ЬА

А — ~йб~сА)е

В -+ ЬВ ~ д

Р: В-+Аа~АЬ~ВЬ|а

А -+ АЯ~БЬ~а~Ь

Если ДС аадает НКА, то по айторитму преобрааоийния НКА а КА построить

КА н написать соотнетстнуннпую емъ' Грамматик~, иначе написать йнйлнзйтор по

Зеленной Грамматике.

б. Библиотека БТЕ: Перечислить пать типов итераторов, Сравнить воамо~кностн, прелостйвляемые лвунйпралленным итерйтором и нтератором пронавольнОГО Доступа, Привести пример Оьнибочного использования двунаправленного

нтерйторй.

Распознанный текст из изображения:

,рзм ""

мни и"' . Л,

поззззз''С" С ес зз з,

- «з'""н рлм"""'

тоФ - „,Рмлз~м' „п~«пр

смроез«М з УДИ

М~

зл. ез"

с

,зс

«Мз««еи У

зс.

,сзс па ««Ззн

. и м "т '

КД «

; , з« л~«

МКО„К««с« '„,: он

Резо«озал «з«из«тор ззо

«зоу«з У' „«изноет

«МКД."' „ра««у. и

ео«М, ~"'"'

~«М " ' 'д ««зд Раз УФ

«и Р„«т з ««инн и с

«мтлм«м п«исае««з«нр«испи« .зв л н

Б-ззь!«5~«

.З -з л 5 ~ ЬИ Кое

В- «В,У

н н по пафалоду пм«Ф«

* н нес лсисз«н«по пафалоду

5.Мимм м ~ем

издам) В «изсстес ззедс пми до«тетин

мммимумуииювата сду

Уд"У т'У'дм 1«,Мм О1

нине««Д от ммтсузпуатп уп".з М н

Уп"~ =-"'«мм у«. е

ездиий!- н' ммпз мам«ам«ни«тор оти«з«амд от и

тмипридваю ФЯ Отде«сипи трипс«Мни«

дз -. ма ус«анни иди«еда«Ости Метод« Ре«трем«из«и «муз«ми

4'Ф~~~.,Г...„

5:-"мдммдОКеидаУ«4ффВИ«ММ идмдммм, и«ФФО«им ууумм,иумщ ~ 5 „,