Карпов. СодержаниеПредислови Конечные автоматы
 Скачать 1.07 Mb.
|
|
then оп fi else if b then if b then оп fi else оп fi (Указание. При построении распознавателя всю терминальную цепочку „if b then‟ удобно обозначить одним терминальным символом if). 8.5.22. Для двусмысленной грамматики: S‟ #E# E E-E | i постройте LALR(1)-распознаватель. Существуют ли в нем коллизии? а) Если при конфликте типа “перенос/свертка” всегда выполнять свертку, к чему это приведет при синтаксическом анализе? Какое дерево вывода при таком разборе будет у цепочки: # i – i – i – i # 59 б) Провести такой же анализ при условии, что при конфликте типа “перенос/свертка” всегда выполняется перенос. 8.5.23. Дана двусмысленная грамматика: S #E# E E+E | Е*Е | i а) Постройте для нее LALR(1)-распознаватель. б) Можно ли определить правила разрешения коллизий в этом распознавателе, чтобы операция „*‟ была более приоритетна, чем операция „+‟, а операции одного приоритета выполнялись бы слева неправо? в) Постройте с помощью этого анализатора анализ цепочки # i + i * i * i + i + i #. 8.5.24*. Для грамматики: S‟ #S# S if b then S | if b then S else S | оп постройте SLR(1)-распознаватель. Существуют ли коллизии в SLR(1)-автомате? а) Если при конфликте типа “перенос/свертка” всегда выполнять свертку, к чему это приведет при синтаксическом анализе? Какое дерево вывода при таком разборе будет у цепочки: if b then if b then if b then оп else if b then if b then оп else оп б) Провести такой же анализ при условии, что при конфликте типа “перенос/свертка” всегда выполняется перенос. (Указание. При построении распознавателя всю терминальную цепочку „if b then‟ удобно обозначить одним терминальным символом if). 8.5.25*. Для грамматики: S‟ #S# S if b then S | if b then S1 else S | оп S1 if b then S1 else S | оп постройте SLR(1)-распознаватель. а) Существуют ли коллизии в SLR(1)-автомате? б) Какое дерево вывода в этой грамматике будет у цепочки: if b then if b then if b then оп else if b then if b then оп else оп (Указание. При построении распознавателя всю терминальную цепочку „if b then‟ удобно обозначить одним терминальным символом if). 8.5.26. Двусмысленная грамматика: S‟ # stmt # stmt s | stmt ; stmt порождает цепочки из операторов s, разделенных точками с запятой (здесь stmt – нетерминал, от слова statement, оператор). Постройте для этой грамматики SLR(1)-распознаватель. Существуют ли коллизии? Как будет выполняться анализ цепочки # s; s; s; s; s #, если коллизии в SLR(1)- распознавателе решать в пользу свертки? Как будет выполняться анализ этой цепочки, если коллизии решать в пользу переноса? 60 8.5.27. Двусмысленная грамматика: S‟ # S # S SS | (S) | порождает скобочные формы. Постройте для этой грамматики LR(1)-распознаватель. Существуют ли коллизии? Как будет выполняться анализ цепочки # ( ( ) ) ( ) ( ( ) ) #, если коллизии в LR(1)- распознавателе решать в пользу свертки? Как будет выполняться анализ этой цепочки, если коллизии решать в пользу переноса? 8.5.28. Является ли следующая грамматика логических формул недвусмысленной? G={ S‟ S$, S p | (S S) | (S S) | (S S) | S } К какому классу она относится? Постройте для этой грамматики распознаватель. 8.6. Универсальные алгоритмы распознавания КС языков 8.6.1. Для двусмысленной грамматики: S SS| ( S ) | ( ) постройте два дерева вывода цепочки ( ) ( ( ) ) ( ) с помощью алгоритма Кока-Янгера-Касами. 8.6.2. Для двусмысленной грамматики: S S ; S| оп порождающей последовательности операторов, разделенные точками с запятой, постройте два дерева вывода цепочки оп ; оп ; оп с помощью алгоритма Эрли. 61 9. Трансляция конструкций языков программирования 9.1. Контекстно-зависимые элементы в языках программирования 9.1.1. Чему станет равна переменная b в результате выполнения следующего фрагмента кода на языке С? int b = 2 /*ptrx ; b = 3; /*** переменная b изменяет свое значение ***/ /**** ptrx объявлен ранее как указатель на переменную х, которая равна 2 ****/; 9.1.2. Постройте грамматику, порождающую описания переменных вида: integer a, b, c; real d, e; и постройте семантические атрибуты, позволяющие присвоить каждой переменной в таблице имен свой тип. Покажите семантические вычисления на дереве синтаксического анализа цепочки integer a, b, c;. 9.1.3. Целые константы без знака в языке С определяются так: десятичные: <последовательность цифр, начинающаяся не с нуля> восьмеричные: 0<последовательность цифр от 0 до 7> шестнадцатеричные: 0 {X, x} <последовательность цифр 0-9 и букв a-f или A-F> Постройте грамматику, синтаксическую диаграмму распознавателя и транслятор языка целых констант С. 9.1.4. Десятичные константы с плавающей точкой в языке С имеют следующий формат: целая часть, десятичная точка, дробная часть, экспонента, начинающаяся с e либо Е, например: 2.34Е-23, 17.344, 2Е-2, .34е3. Либо целая, либо дробная часть константы может быть опущена, но не обе сразу. Либо десятичная точка с дробной частью, либо экспонента могут быть опущены, но не обе сразу. Знаки „+‟ и „-„ после знаков е и Е могут присутствовать или отсутствовать. а) Постройте описание формата такой константы с помощью грамматики Хомского. б) Постройте описание этого формата в БНФ нотации. в) Постройте описание этого формата в виде синтаксической диаграммы. г) Постройте описание этого формата в виде конечного распознающего автомата. д) Постройте транслятор, переводящий любую константу без знака во внутреннее представление. 9.1.5. В некоторых языках программирования (например, в языке Modula-2) описание процедуры имеет следующий вид: PROCEDURE Proc; BEGIN ... 62 END Proc; Завершается процедура ключевым словом END, после которого идет имя этой процедуры. Постройте КС-грамматику, порождающую описания процедур языка Modula-2. |