2003 вариант 1 ответы (Экзамен. Варианты заданий и ответы)

Вариант 1 2003 Ф.И.О 34 группы 1 '2 3 4 5 б 7 8 9 10 1. Определить тип по Хомскому заданной грамматики О=(УТ, УЬ1, Р, Б). Определить порождаемый язык и тип языка по Хамскому. Р: Б-?аАс аА -? ааВЬС ! аЬ ВЬ вЂ” ? ЬЬ ! аЬЬЬс ~ аОЬЬЬсс С вЂ” ?с О -? аЬ 2 Достаточные условия применимости РС-метода.

-! П!?цвести с'»с.'!у !?аооть! ко?!Пилято!?а» 5. Основные зала !и се?!антического анализа. Привести примеры ситуаций, когла семантический анализатор выласт ошиоку. б. Построить»ТС. соответствуюшую заланной Р-грамматике 6=( т»Т. 1 .~, Р. л), Р. б -? ВО',СΠ — ? ВО!О С-?С! !Л! Л вЂ” ?О Если ДС залает НКА, то по алгоритму преооразоваиия 1!КА в КЛ построить КЛ и написать соответствуюшую ему грамматику, иначе иаииса!ь анализатор по заланиой ! рамматике, 7.

Основные машиино-независимые оптимизируюшие преобразования 3, Задана КС-грамматика О=(УТ, т'!'1, Р, Ь). Если к ней применим РС-к!стол, написать РС-процедуру для любого иетерм!шала, иначе, если возможно, преооразовать грамматику так, чтобы РС-метод стал к ней применим. Б — ?ЬБ!аАВ А ? ЬсА ! ссА ! в В-?сЬВ!с 9.

Основные критерии проектирования стандартных библиотек. 10. Написать грамматику арифметического выражения, используюшего операции +, l и круглые скобки (приоритет стандартный!), аргументы операций переменные а и Ь,, например: в+(Ь+а)/Ыа+Ь. Предполагая, что анализ грамматики будет производиться РС-методом, вставить в нес действия (в виде соц! « ...) по переводу таких выражений в ПОЛИ3. 3 б ' На;и!сагь функцию, которая добавляет в конец заданного списка !в!<!и!> злементы зтого списка, расположенные в ооратном порялке, и печатает пол' чившийся список.

Ответы на вОпросы:::: вариант 1 2003 (первый поток) 1. Тип гр.. — 1, (неукорачивающий), 1 (б)=(а"Ь"с" ~ п=1,2,3,4). Тип языка 3 (регулярный). 2. Метод рекурсивного спуска применим в том случае если каждое правило грамматик1 рамматики имеет вид. а) либо А -+ а, где а е (ЧТ ~ ~ ЧН) и это единственное правило выво а ~ло вывода для этого нетерминала; Ь) ли, А + а,сс, ~ а сг ! ... ! а„а„где а, е Ъ'Т для всех 1 = 1, 2,..., и; а; к: а1 для 1 ~ 3; а; е (УТ ~.з УЖ), т.е. если для нетерминала А правил вывода несколько, то они должны начинаться с терминалов. причем все эти терминалы должны быть различными 4 1псЫе < 1озггеагп > я'1псЫе < !151 > ц51пд папзезрасе 5М; ~оЫ В(!151 <1и1> сч!51) ( й5! < 1п1 >:: гесегзе йега1ог гр = 15цгбе(»п (); ъя1е ( гр!= !5кгеп4)) ( !5! риз!1 Ьас(;(":(гр++)), 1~5! < ш! >:: соп51 иепиог р .= !5! Ьсгпп (); и !1йе ( р! =!51 епб ()) ', со1и « "р « ' ', р++, соц! «епб1; йи шаго () 1 !!5! <!и! > 151; ин к Гог (1 = О; 1 < 1О; 1+-) 15к рц511 Ьас!'(1); В (!5!); 5гегцгп О, ! ч.

Фаза анализа (исходная программа на 51П) => лексический анализ =-> (послеловазсльность лексем) => синтаксический анализ => (промежуточное представление программга) =-> семаиз ичсский аналиНконтроль контекстных условий. Фаза синтеза: подготовка к генерации объектного модуля => генерация объектного модуля ~ (объектный модуль) 5. Проверку контекстных условий часто называют семантическим анализом.

Примеры наиболее часто встр чаюшихся контекстных условий: а) каждый используемый в программе идентификатор должен быть описан, но нс более одного раза в одной зоне описания; Ь) при вызове функции число фактических параметров и их типы должны соответствовать числу и типам формальных параметров; с) обычно в языке накладываются ограничения иа типы операндов любой операции, определенной в этом языке; на типы левой и правой частей в операторе присваивания; на тип параметра цикла; на тип условия в операторах цикла и условном операторе и т и Г(Н,О) = АВ Г(АВ,О) = Вб Г(ЛВ,1) = С Г(Вб,О) = Вб Г(С,О) = Я АВ => А ВБ =>В б=> Гз Два заключительных состояшгя ВБ и Я сводим Б-+ В.Е!Ш. В-+ ВО!АО Л-+ 0. О- СО С-~ С1! А1 Г(С,)) = С в одно б' =э 5 с исп..1. а.

Удаление недостижимого кода. Ь. Оптимизация линейных участков программок а) удаление бесполезных присваиваний, б) -.;,",'; исключение изоыточных вычислений, в) свертка объектного кода, г) перестановка операций, д) арифметические преобразования (на основе алгебраических и логических тождеств) оптимизация вычисления логических выражений. с, Оптимизация передачи параметров в процедуры и функции: а) передача параметров через::-.-:, . "гй регистры процессора, б) подстановка кода функции вместо ее вызова в объектный код.

о, Оптимизация циклов: а) вынесение инвариантных вычислений из циклов, б) замена операций с индуктивными (образу«ошами арифметическую прогрессию) переменными (как правило умножения на сложение), в) слияние и развертывание циклов. Б — «Ьб,'аАВ Л -«ЬсЛ1 ссЛ ~ с В --«сЬБ с Г!(сБТ(А)=,'Ьс,' («О(.(.ОЛ( А)= (с ,'. = ! с ге Й ГИВ«Т(В)= , 'с). ГОП ОЮ(В)=З Б — «ЬБ аА' Л' — «ЬсА' ссЛ': В -«ЬсЛ'(ссА'(сЬВ.;с Л вЂ” «ЬсА' ссА': с - недостижимые правила, и; мо«кно убрать  — «сЬВ 5 -«ЬБ аА' Л' — «ЬсА'. сЛ" (с Л"-«сА' ЬВ В -+сЬВ:.с а. с«бшезна и1мость содержимого, Ь зффсктивность, с безопасность.

д. завершенность, е сочетаемость с базовыми типами данных, Г должна служить фундаментом для создания других библиотек !О , Е -+ Т (+Т <сои( « '+';>) Т вЂ” «Г (/Г <сои( «У;>) à — «а <соц( « 'а',> ( Ь<соц( « 'Ь';> 1 (Е) .