Карпов. СодержаниеПредислови Конечные автоматы
 Скачать 1.07 Mb.
|
|
X | U | G | F а) Покажите, что эта грамматика двусмысленна. б) Постройте для этой грамматики все возможные деревья вывода формулы GFp Xq. в) Постройте недвусмысленную грамматику языка формул LTL. 7.1.9. Является ли следующая грамматика недвусмысленной? S P . | P ; S P N = E E E O E | N | { L } | ( E ) O | N x | y | z | u | v | w L A | L , A 42 A a | b | c | d | e | f Постройте такую цепочку, порождаемую этой грамматикой, которая имеет два дерева вывода. 7.1.10. Для следующей КС-грамматики с начальным нетерминалом Program , записанной в БНФ: Program ::= Statement „.‟ | Statement „;‟ Program Statement ::= Name „=‟ Expression Expression ::= Expression Operator Expression | Name | „{‟ Elements „}‟ | „(„ Expression „)‟ Operator ::= „ ‟ | „ ‟ Name ::= „A‟ | „B‟ | …| „X‟ | „Y‟ | „Z‟ Elements ::= Element | Element „,‟ Elements Element ::= „a‟ | „b‟ | … | „x‟ | „y‟ | „z‟ постройте эквивалентную недвусмысленную грамматику, в которой соблюдается приоритет операций „ ‟ и „ ‟. 7.1.11. Множество формул логики предикатов представляет собой язык. Пусть х обозначает любую переменную предметной области, а обозначает любую константу предметной области, р – обозначает отношение на множестве объектов предметной области. Грамматика, порождающая все формулы логики предикатов иногда задается так: argument ::= x | a argument_list ::= argument | argument, argument_list atomic_formula ::= p | p(argument_list) formula ::= atomic_formula | formula| formula formula formula ::= x formula| x formula Является ли эта грамматика двусмысленной? Определите все источники двусмысленности. Приведите примеры двусмысленных формул. 7.2. Теория атрибутной семантики Кнута 7.2.1. Постройте грамматику, порождающую описания переменных вида: integer a, b, c; real d, e; и постройте семантические атрибуты, позволяющие присвоить каждой переменной в таблице имен свой тип. Покажите семантические вычисления на дереве синтаксического анализа цепочки integer a, b, c;. 7.2.2. Контекстно-свободную грамматику, порождающую описания переменных языка Паскаль, можно задать следующим образом (D – начальный нетерминал): D var V : T; V i | V, i T real | integer Постройте семантические атрибуты, позволяющие присвоить после трансляции описания каждой переменной в таблице имен свой тип. Покажите семантические вычисления на дереве синтаксического анализа цепочки var a, b, c : integer;. 43 Указание: Для нетерминала V следует определить два атрибута: наследуемый атрибут V.тип и синтезированный атрибут V.множ - множество имен тех переменных, которые выводятся из V. Значение атрибутаV.тип должно быть присвоено всем переменным множестваV.множ 7.2.3. Для следующей грамматики, порождающей рациональные двоичные числа, постройте атрибутную семантику для трансляции символьных цепочек в их значения: Num ::= Int „.‟ Frac | „.‟ Frac | Int „.‟ Int ::= „ц‟ | „ц‟ Int Frac ::= „ц‟ | Frac „ц‟ 7.2.4. Определите семантические атрибуты и их зависимости для вычисления значения рациональных двоичных чисел, определяемых следующими грамматиками: G1: S L . L L BL | B B 0 | 1 G2: S L . R L BL | B R RB | B B 0 | 1 G3: S R . R | R . R B | BR | RB B 0 | 1 G4: S L . L | L . | . L L B | B L B 0 | 1 G5: S L . L | . L L B | BL | LB B 0 | 1 G6: N L . L | L . L B | L B B 0 | 1 G7: N L . R L B | L B R B R | B 0 | 1 G8: N L . R L B | B N R B | R B | B 0 | 1 G9: S L . R | L . | . R L B | B L R B | R B| B 0 | 1 Для цепочки 110.011 постройте аннотированные деревья вывода в каждой грамматике с вычислением значения этой цепочки. 7.2.5. Для грамматики: S 0S11 | 1S00 | ε постройте атрибутную семантику, которая для каждой порожденной цепочки позволяет подсчитать: число единиц в цепочке и максимальную длину непрерывной цепочки единиц. 7.3.6. Язык формул логики высказываний для базиса { , } описывается следующей грамматикой в БНФ нотации: ::= р | ( ) | ( ) где - начальный символ, а p – атомарное утверждение. а) К какому классу относится эта грамматика? б) Постройте атрибутную семантику этой грамматики для вычисления истинностного значения логических формул. в) Вычислите истинностное значение формулы ((р 1 ( (р 2 р 3 ))) ( р 1 )) по синтаксическому дереву при следующих значениях семантических атрибутов терминалов: (р 1 .val = И; р 2 .val = Л; р 3 .val = И. 44 7.3. Примеры атрибутных трансляций 7.3.1. По заданной ниже атрибутной грамматике, порождающей вещественные десятичные числа, постройте дерево вывода входной цепочки 252.028 и покажите последовательность вычисления значений семантических атрибутов для этой цепочки: N Синтаксическое правило Семантическое правило 1 S A . B S.val:=A.val + B.val; B.p := -1; 2 A A.val := 0; A.p := 0; 3 A ц A 1 A.val := ц.val*10 A 1 .p + A 1 .val; A.p := A 1 .p +1; 4 B B.val :=0; 5 B ц B 1 B.val := ц.val *10 B.p + B 1 .val; B 1 .p := B.p - 1 7.3.2. Постройте атрибутную грамматику интерпретатора логических формул, представленных в базисе Буля. Примеры логических формул: not (A or not (B and C) ), A and not B and C. 7.3.3. Грамматика формул логики высказываний обычно задается следующим образом: p | | | | | Покажите, что эта грамматика двусмысленная. Постройте недвусмысленную грамматику формул логики высказываний с учетом приоритетов. Приоритеты логических операций обычны: в порядке убывания приоритетов идут операция отрицания, затем операция конъюнкции, затем операция дизъюнкции. Приоритеты всех остальных бинарных логических операций одинаковы и меньшие, чем приоритет дизъюнкции. Скобки „(„ и „)‟ имеют обычное значение: они связывают подвыражения. Постройте атрибутную семантику, позволяющую вычислять логическое значение любой правильно построенной формулы логики высказываний при известных истинностных значениях ее аргументов. 7.3.4. Схема мультиплексора (MUX), т.е. схема с тремя входами и одним выходом, реализует функцию ite(x, y, z) = if x then y else z. Эта функция может быть записана и в конъюнктивном базисе: ite(x, y, z) = xy xz. Схемно мультиплексор в некоторых технологиях очень просто реализуется. Известно, что множество функций {0, 1, ite} составляет базис, т.е. любая логическая функция может быть выражена через константы 0,1 и функцию ite. Например, х=ite(x, 0, 1); x y=ite(x, y, 0); x y=ite(x, 1, y). Постройте транслятор, который по булевой формуле, выраженной с помощью функций И, ИЛИ, НЕ, строит формулу в базисе {0, 1, ite}. Такая формула будет основой для синтеза схемы, реализующей из мультиплексоров заданную логическую функцию. 45 7.3.5. Постройте атрибутную грамматику для трансляции заданной логической формулы представленной в базисе Буля с тесными отрицаниями (отрицания только у переменных) в соответствующую переключательную релейно-контактную схему 7.3.6. Постройте атрибутную грамматику для трансляции заданной логической формулы в базисе Буля в логическую формулу в базисе {ite, 0, 1}. Примеры логических формул на входе транслятора: not (A or not(B and C) ), A and not B and C. 7.3.7. Постройте атрибутную грамматику для трансляции заданной логической формулы в базисе Буля в логическую формулу в базисе Шеффера. Примеры логических формул на входе транслятора: not (A or not(B and C) ), A and not B and C. 7.3.8. Для грамматики, порождающей двоичные формулы с операциями {И, ИЛИ, НЕТ, , }, постройте атрибутную семантику, позволяющую транслировать логическую формулу в формулу в дизъюнктивном базисе {ИЛИ, НЕТ}. Покажите, как будет выполняться трансляция на дереве вывода формулы (x y) z. 7.3.9. Для грамматики, порождающей двоичные формулы с операциями {И, ИЛИ, НЕТ}, постройте атрибутную семантику, позволяющую транслировать логическую формулу в базис Жегалкина (т.е. в базис { , И, 1}). Покажите, как будет выполняться трансляция на дереве вывода формулы (x y) z. 7.3.10. Для грамматики, порождающей двоичные формулы в базисе Жегалкина (т.е. в базисе { , И, 1}), постройте атрибутную семантику, позволяющую транслировать любую логическую формулу в базис Буля {И, НЕТ}. Покажите, как будет выполняться трансляция на дереве вывода формулы 1 x y z. 7.3.11. Постройте атрибутную грамматику для трансляции заданной логической формулы в базисе Буля в программу стековой машины, в которой определены команды AND, OR, NOT. Примеры логических формул: not (A or not(B and C) ), A and not B and C. 7.3.12. Для темпоральных формул логики линейного времени LTL постройте атрибутную семантику, которая преобразует введенную темпоральную формулу к темпоральной формуле только с темпоральными операторами Х и U, позволяя замены темпоральных операторов F и G в соответствии с правилами вывода Fφ = TrueUφ, Gφ = F φ. 7.3.13. Пара скобок в арифметическом выражении называется избыточной, если после ее удаления выражение остается эквивалентным исходному. Постройте атрибутную грамматику, которая позволяет удалять все избыточные пары скобок арифметических выражений. 7.3.14. Постройте атрибутную грамматику, которая по формуле двоичной функции в инфиксной нотации строит эквивалентную формулу: а) в префиксной нотации; б) в постфиксной нотации (ПОЛИЗ). 7.3.15. Постройте грамматику, порождающую описания переменных вида: 46 integer a, b, c; real d, e; и постройте семантические атрибуты и атрибутную семантику, позволяющие присвоить каждой переменной в таблице имен свой тип. Покажите семантические вычисления на дереве синтаксического анализа цепочек real d, e; integer a, b, c;. 7.3.16*. Для грамматики, порождающей дробные десятичные числа без знака, ниже приведено представление атрибутной грамматики. ALPHABET Num :: float V. Int :: float V; int P. Frac :: float V; int P. digit :: int Val. RULE Num ::= Int '.' Frac SEMANTICS V<0> = V<1>+V<3>; P<3>=1. RULE Int ::= e SEMANTICS V<0> = 0; P<0>=0. RULE Int ::= digit Int SEMANTICS V<0> = Val<1>*10**P<2>+V<2>; P<0> = P<2>+1. RULE Frac ::= e SEMANTICS V<0> = -1. RULE Frac ::= digit Frac SEMANTICS V<0> = Val<1>*10**P<0>+V<2>; P<2> = P<0>-1. Постройте грамматику метаязыка, на котором описана эта атрибутная грамматика. 7.4. Трансляция арифметических выражений 7.4.1. Переведите в ПОЛИЗ арифметическое выражение a+b*(c+d)/e +(f - d). 7.4.2. С помощью стека сгенерируйте последовательность команд стековой машины для вычисления значения арифметического выражения с*(c+d)/e +(f - d), предварительно представленного в ПОЛИЗ. 7.4.3. Представьте в ПОЛИЗ арифметическое выражение (a+b)*с-(c+а)/(e+f ). Сгенерируйте последовательность команд стековой машины для вычисления значения этого выражения по его представлению в ПОЛИЗ. 47 7.4.4. Синтаксическим графом арифметического выражения называется направленный граф, полученный из синтаксического дерева для арифметического выражения объединением всех вершин, соответствующих совпадающим подвыражениям. Такой граф позволяет эффективно вычислять значения арифметических выражений и строить оптимальные компиляторы. Постройте атрибутную грамматику, которая позволяет представить арифметическое выражение синтаксическим графом. 7.4.5. В функциональных языках, например, в языке LISP, арифметические выражения записываются в префиксной форме, а именно <операция> ( <операнд1> <операнд2> ) для бинарных операций. Например, выражение a – b*c в префиксной форме будет записано так: - (a ( * ( b c) )). Постройте грамматику, порождающую записи арифметических выражений в префиксной форме языка LISP, и определите семантические атрибуты, генерирующие программу для стековой машины, вычисляющую значение таких арифметических выражений. 7.4.6. Постройте атрибутную грамматику арифметических выражений, содержащих как целые, так и вещественные операнды. Семантические атрибуты должны позволить вычислить значение выражения правильного типа. Тип операнда и его значения известны (они являются семантическими атрибутами). Если типы операндов арифметической операции не совпадают, то целый операнд должен быть приведен к вещественному типу. Результатом арифметической операции, в которой тип хотя бы одного из операндов вещественный, должен быть вещественного типа. Команды для выполнения операций над целыми и вещественными различаются. 7.4.7. Грамматика, описывающая все формулы линейной темпоральной логики LTL обычно строится следующим образом: p | | | | | X | U Покажите, что эта грамматика двусмысленная. Постройте недвусмысленную грамматику формул темпоральной логики LTL с учетом приоритетов. Темпоральные операторы имеют наивысший приоритет, а приоритеты логических операций обычные. Скобки „(„ и „)‟ имеют обычное значение: они связывают подвыражения. 7.4.8. Темпоральным операторам X, U, F и G в формулах темпоральной логики ветвящегося времени CTL непосредствено предшествуют кванторы существования и всеобщности. Грамматика, порождающая формулы этой логики: p | | | | | AX | EX | A( U ) | E( U ) | AG | EG | AF | EG Покажите, что эта грамматика двусмысленная. Постройте недвусмысленную грамматику формул логики CTL с учетом приоритетов. Темпоральные операторы имеют наивысший приоритет, а приоритеты логических операций обычные. Скобки „(„ и „)‟ имеют обычное значение: они связывают подвыражения. 48 8. Распознаватели подклассов КС - языков 8.1. s-грамматики 8.1.1. Пусть задана в s-грамматика: S aSRb | bRсA R bA | aR A aAb | c в которую семантические действия добавлены так: S „(‟ aSRb „)‟ | „(‟ bRсA „)‟ R „(‟ bA „)‟ | „(‟ aR „)‟ A „(‟ aAb „)‟ | „(‟ c „)‟ здесь „(„ и „)‟ являются „семантическими‟ символами, не влияющими на ход синтаксического анализа. При синтаксическом анализе пусть каждый вытолкнутый из стека символ (нетерминалы, терминалы и семантические символы) также выводится. Покажите, какое дерево вывода в скобочной записи будет построено в результате обработки терминальной строки abccbcbb. 8.1.2. Известно, что проблема однозначности КС-грамматик алгоритмически неразрешима. Можно ли утверждать, что КС-грамматика: S aSRbcA | bRA R bA | cRAR | aRA A aAb | c является однозначной? Почему? Провести синтаксический анализ цепочки bbcabb, порожденной в этой грамматике (возможно, с синтаксическими ошибками) 8.1.3. Можно ли привести следующую грамматику к эквивалентной s-грамматике? S aS | aA A bA | aB | aC B bA | b С | bA Если можно, то проведите в этой s-грамматике распознавание цепочки aababba. Указание. Эта грамматика – автоматная. 8.1.4. Можно ли привести следующую грамматику к эквивалентной s-грамматике? S abSba | acAb A bbAa | bcB | a B bBA | c Если можно, то проведите в этой s-грамматике распознавание цепочки acbbbccab. 49 8.1.5. Для следующей s-грамматики: S‟→ begin S end S → if E then S else S | S → begin S L | S → print num L → end | ; S L E → num = num выполните синтаксический анализ цепочки: begin if num=num then print num ; else begin print num end end Указание. Здесь все терминалы – лексемы входного языка. |