Главная страница
Навигация по странице:

  • 8.3. Грамматики рекурсивного спуска

    		•

    Карпов. СодержаниеПредислови Конечные автоматы


    Скачать 1.07 Mb.
    НазваниеСодержаниеПредислови Конечные автоматы
    АнкорКарпов.pdf
    Дата18.03.2019
    Размер1.07 Mb.
    Формат файлаpdf
    Имя файлаКарпов.pdf
    ТипДокументы
    #26044
    страница6 из 7
    1   2   3   4   5   6   7
    8.2. LL(k)-грамматики
    8.2.1. Существуют ли грамматики класса LL(0)? Если да, то постройте пример такой грамматики.
    8.2.2. Постройте множества FIRST и FOLLOW для каждого нетерминала следующих КС- грамматик:
    S

    aAB| BA
    A

    BB | a
    B

    AS | b
    S

    ABC
    A

    BB | ε
    B

    CC | a
    B

    CC | b
    S

    S+T| T
    T

    S(S) | a
    S

    aAB| B
    A

    aA | a
    B

    BS | A | b
    S

    begin D; R end | s
    D

    D;d | d
    R

    R; S | S
    8.2.3. Постройте KC-грамматику, порождающую язык L={abbabb, abbb}. При каком k эта грамматика является LL(k)-грамматикой?
    8.2.4. Известно, что проблема однозначности КС-грамматик алгоритмически неразрешима.
    Можно ли утверждать, что КС-грамматика:
    S

    aSRd | RA
    R

    bA | cRA |

    A

    fAb | d является однозначной? Почему?
    8.2.5. При каком значении k следующая грамматика является LL(k)-грамматикой?
    S

    aAaa | bAba
    A

    b |

    8.2.6. Является ли нижеследующая грамматика s-грамматикой? Является ли она LL(1)- грамматикой? Постройте управляющую таблицу LL-анализатора и проведите синтаксический анализ цепочки abbab в этой грамматике.
    S

    aBS | b
    A

    a
    B

    A | bSB

    50 8.2.7. Постройте LL(1) грамматику и синтаксический анализатор для языка, включающего строки (программы) такого вида:
    for x:= m to n do
    begin
    x := 3 + x; y :=5
    end;
    8.2.8. Для грамматики:
    S‟

    S $
    S

    AaS | b
    A

    CAb | B
    B

    cSa |

    C

    c | ab
    постройте множества выбора для альтернатив каждого нетерминала.
    8.2.9. Проверьте, является ли следующая грамматика LL(1)-грамматикой:
    G = { S‟ → S$, S → B A, A → +B A | ε, B → DC, C → *DC | ε, D → ( S ) | a } построив множества выбора для альтернатив каждого нетерминала.
    8.2.10. Грамматику:
    G = { S

    aT | TbS, T

    bT | ba } приведите к виду LL(1), проведя факторизацию. Проведите анализ цепочки bbababba в построенной грамматике.
    8.2.11. Проверьте, является ли следующая грамматика LL(1)-грамматикой:
    S‟ → S$
    S → AbB | d
    A → Cab | B
    B → cSd | ε
    C → a | ed построив множества выбора для альтернатив каждого нетерминала.
    8.2.12. Можно ли привести грамматику G к эквивалентной LL(1)-грамматике?
    G = {S

    BAb, A

    aABC | bB | a, B

    b, C

    cA }.
    Проведите в этой LL(1)-грамматике распознавание цепочки babccaab.
    8.2.13. Покажите, что следующая грамматика c начальным символом <программа> является
    LL(1)-грамматикой:
    <программа>

    <оператор>
    <оператор>

    begin <описание> : <список операторов> end
    <описание>

    d | d ; <описание>
    <список операторов>

    s ; <список операторов> |

    Постройте таблицу принятия решений для этой грамматики. Выполните синтаксический анализ цепочки:

    51 begin d; d : s ; s; s; end
    8.2.14. Покажите, что следующая грамматика является LL(1)-грамматикой:
    {S

    BA, A

    BS | d, B

    aA | bS | c}.
    Постройте таблицу для принятия решений при синтаксическом анализе цепочек, порождаемых этой грамматикой. Выполните синтаксический анализ цепочки bcdcadd.
    8.3. Грамматики рекурсивного спуска
    8.3.1. Постройте программу, которая вводит поток телеграмм, и для каждой телеграммы подсчитывает и печатает число слов, стоимость телеграммы (при известной стоимости слова), число телеграмм в потоке и общую стоимость телеграмм. Слово определяется, как последовательность букв, заканчивающаяся пробелом, телеграмма – как последовательность слов, заканчивающаяся маркером конца „#‟, поток телеграмм – как последовательность телеграмм, заканчивающаяся символом конца текста eot.
    8.3.2. Постройте синтаксическую диаграмму и семантические действия для генерации команд стековой машины для расширения языка Милан условным оператором присваивания вида
    a:= if b>c then e*f else a+b fi.
    8.3.3. Постройте синтаксическую диаграмму и семантические действия для генерации команд стековой машины для расширения языка Милан оператором цикла языка Java вида do
    { <список операторов> } while (<условие>). При необходимости введите дополнительные команды стековой машины.
    8.3.4. Постройте синтаксическую диаграмму и семантические действия для генерации команд стековой машины для расширения языка Милан оператором цикла языка Java вида for
    ( <инициализация>; <условие>; <итерация> ) { < список операторов > }. При необходимости введите дополнительные команды стековой машины.
    8.3.5. По синтаксической диаграмме для нетерминала <Список_параметров> языка Паскаль постройте процедуру на С, распознающую все цепочки подъязыка, порождаемого этим нетерминалом.
    8.3.6. По КС-грамматике:

    52
    S

    aSRd | RA
    R

    bA | cRA |

    A

    aAb | d постройте синтаксические диаграммы. Является ли эта грамматика грамматикой рекурсивного спуска? Почему? Постройте по синтаксическим диаграммам распознающие процедуры входного языка.
    8.3.7. Преобразуйте следующую КС-грамматику:
    S‟

    #S#
    S

    abARd | abb
    R

    R ; A | b
    A

    aAb | d к грамматике рекурсивного спуска. Постройте синтаксические диаграммы этой новой грамматики и по ним соответствующие распознающие процедуры. Выполните по построенным синтаксическим диаграммам разбор цепочки #abddb;d#.
    8.3.8. Покажите, что следующая КС-грамматика с начальным нетерминалом 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‟ является двусмысленной. Постройте эквивалентную недвусмысленную грамматику, в которой выполнение операций „

    ‟ и „

    ‟ определено слева направо без учета приоритетов.
    8.3.9. Преобразуйте следующую грамматику с начальным нетерминалом
    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‟ к грамматике рекурсивного спуска, в которой операции „

    ‟ и „

    ‟ выполняются слева направо без учета приоритета. Постройте синтаксические диаграммы этой новой грамматики и по ним соответствующие распознающие процедуры. Выполните по построенным синтаксическим диаграммам разбор цепочки:
    М={a , b}; N=M

    {d , a, b}

    M.
    8.3.10. Для грамматики
    G={S‟→begin S end, S→if E then S else S | begin SL | print E,L → end | ;SL, E→i= i} постройте распознаватель методом рекурсивного спуска.

    53 8.3.11. Постройте распознаватель методом рекурсивного спуска для грамматики
    G = { S‟

    S$, S → (B)B, B → (B)B |

    }.
    8.3.12. Для грамматики, представленной синтаксическими диаграммами с включенными семантическими действиями, постройте компилятор: процедуры распознавания, дополненные семантическими операциями:
    8.3.13. На языке Милан++ построена программа суммирования чисел из входного потока: begin i,s := 0,0; n := read; loop i < n -> s,i := s+read,i+1 endloop; write (s) end а) Постройте программу стековой машины для выполнения этой программы. б) Постройте синтаксические диаграммы и семантические операции языка Милан ++ для транслятора рекурсивного спуска.
    8.3.14. На языке Милан++ построена программа подсчета факториала: begin read x; if x>0 then fact := 1; repeat fact *= x; x – until x = 0; write (fact) end а) Постройте программу стековой машины для выполнения этой программы. б) Постройте синтаксические диаграммы и семантические операции языка Милан ++ для транслятора рекурсивного спуска.
    8.3.15. Существует мнение, что формулы линейной темпоральной логики LTL, используемые в верификации ПО и аппаратуры, не очень понятны разработчикам программ. В некоторых системах верификации спецификация требований к поведению программ задается на ограниченном естественном английском языке PSL (Property Specification Language).
    Примеры таких спецификаций на упрощенном языке PSL:

    54
    Цепочка языка PSL
    Соответствующая формула LTL
    assert always ! (a

    next b)
    G

    (a

    Xb)
    assert never (a & b)
    G

    (a&b)
    assert always (req

    next (busy until done ) ) G(req

    X(busy U done) )
    assert always (a

    next b)
    G(a

    Xb)
    assert eventually (b

    next (always ! b) )
    F(b

    X (G

    b) )
    Постройте грамматику упрощенного языка PSL и транслятор с него в язык формул линейной темпоральной логики.
    8.3.16. Для грамматики простого языка спецификации свойств программ:
    G: S → assert Ф
    Ф → P | (Ф) | not Ф | (Ф or Ф) | ( Ф and Ф ) | ( if Ф then Ф ) |
    always Ф | next Ф | eventually Ф | Ф until Ф
    Р → a | b | c | ... | x | y | z постройте транслятор рекурсивного спуска (синтаксические диаграммы и семантические операции) для перевода фраз ограниченного естественного языка в формулы темпоральной логики LTL. Например, по тексту:
    assert always ( if not a then eventually (b until (c or next d)) должна быть выдана следующая формула темпоральной логики LTL:
    assert G(

    a

    F (b U (c

    Xd) ) ),
    8.4. Грамматики простого предшествования
    8.4.1. Постройте матрицу отношений предшествования для грамматики:
    0. S‟

    #S#
    3. S

    [S]
    1. S

    aST
    4. T

    b
    2. S

    a
    5. T

    cT
    Восстановите правый вывод цепочки #[a a [a] cbb]# в этой грамматике.
    8.4.2. Выполните синтаксический анализ цепочки #aababdcdccc# в грамматике:
    S‟

    #S#
    S

    aSс | bBc
    B

    baSd|d методом простого предшествования.
    8.4.3. Выполните синтаксический анализ цепочки #abadaccac# в грамматике:
    S‟

    #S#
    S

    aBSc | a
    B

    bSc | d методом простого предшествования.

    55 8.4.4. Выполните синтаксический анализ цепочки # [ ( ( ( a a ) a ) a ) ] # в грамматике:
    S‟

    #S#
    S

    [M]
    M

    ( L | a
    L

    Ma) методом простого предшествования.
    8.4.5. Выполните синтаксический анализ цепочки #ababacb# в грамматике:
    S‟

    #S#
    S

    aASc|ba
    A

    baSc методом простого предшествования.
    8.4.6. Выполните синтаксический анализ цепочки #((cc)c)# в грамматике:
    S‟

    #S#
    S

    (SS) | c методом простого предшествования.
    8.4.7. Выполните синтаксический анализ цепочки #(((aa)a)a)# в грамматике:
    S‟

    #S#
    S→( R | a
    R→S a )
    методом простого предшествования.
    8.4.8. Постройте матрицы отношений предшествования для грамматик:
    G1 = { S‟

    #S#, S

    aSbb | abb }
    G2 = { S‟

    #S#, S

    aSAb | aSb, A

    b }
    G3 = { S‟

    #S#, S

    if B then S else S | s, B

    B or b | b }
    G4 = { S‟

    #S#, S

    SA | A, A

    (S) | ( ) }
    G5 = { S‟

    #S#, S

    AS | A, A

    (S) | ( ) }
    G6 = { S‟

    #S#, S

    aRSd | c, R

    Rb | b }
    G7 = { S‟

    #S#, S

    SaSb | c }
    G8 = { S‟

    #S#, S

    aSSb | c }
    G9 = { S‟

    #A#, A

    (A) | a }
    8.4.9**.
    Разработайте программу-конструктор, автоматизирующую процесс синтаксического анализа цепочек языков, порождаемых грамматиками простого предшествования. Программа должна выполнять следующие функции:
    1) ввод произвольной грамматики;
    2) формирование для нее матрицы простого предшествования;
    3) проверка того, что введенная грамматика удовлетворяет требованиям грамматики простого предшествования;
    4) выполнение распознавания входных цепочек.

    56
    8.5. LR-грамматики
    8.5.1. Для грамматики:
    { S‟

    #S#, S

    aBc, B

    Bb | b } постройте LR(0) анализатор и восстановите вывод цепочки #abbbc#.
    8.5.2. Для грамматики { S

    #A#, A

    (A) | a } постройте самый простой возможный LR анализатор и восстановите вывод цепочки #((a))#. Для той же грамматики постройте нисходящий анализатор и восстановите вывод этой цепочки с помощью этого анализатора.
    8.5.3. Правильно построенные списки рекурсивно определяются так: i) любой элемент p есть список; ii) если А и В – списки, то [А] и А;В – тоже списки; iii) других списков нет. а) Постройте недвусмысленную КС-грамматику Хомского, порождающую все списки. б) Постройте LR(0)-анализатор для этой грамматики и выполните с его помощью синтаксический анализ следующих цепочек:
    1) [a;[b]; c] 2) а; [[a;b]; c];[d] 3) [[a; c];[d]
    8.5.4. Для грамматики, порождающей скобочные скелеты:
    S‟

    #S#
    S

    S (S) |

    постройте самый простой LR анализатор и восстановите правый вывод цепочки
    # ( ( ) ( ) ) ( ) #.
    8.5.5. Постройте LR(0) анализатор для грамматики:
    S‟

    #S#
    S

    aST | [Sb] | a
    T

    cT | b
    Восстановите правый вывод цепочки #[a b [abc] a]# в этой грамматике.
    8.5.6. Для грамматики:
    { S‟

    #S#, S

    dAb | Bb, B

    cd, A

    cBA|d} постройте самый простой LR анализатор и восстановите правый вывод цепочки #dccdccddb#
    8.5.7. Для грамматики:
    S‟

    #E#
    E

    (L) | i
    L

    L , E | E постройте LR(1)-распознаватель и SLR(1)-распознаватель. Выполните синтаксический анализ цепочки #( ( i ), i, ( i, i ) )# с помощью каждого из двух этих распознавателей.

    57 8.5.8. Для грамматики:
    { S‟

    #S#, S

    BSb |

    , B

    bBca | c } постройте самый простой LR анализатор и восстановите правый вывод цепочки #accaccbb#
    8.5.9. Для грамматики:
    S‟

    #S#
    S

    aSBa | [S] | a
    B

    bB| b постройте LALR(1) анализатор и восстановите правый вывод цепочки #[abb[a]]#
    8.5.10. Для грамматики:
    S

    ac | bAc | Aa
    A

    a постройте LALR(1) анализатор и восстановите правый вывод цепочки bac. Какой язык порождает эта грамматика?
    8.5.11. Для грамматики:
    S‟

    #S#
    S

    SAb | b |

    A

    Ab| b постройте SLR(1) анализатор и восстановите правый вывод цепочки #abbabbb#
    8.5.12. Для грамматики:
    S

    #Е#
    E

    E - T | T
    T

    i | (E) постройте самый простой LR анализатор и восстановите правый вывод цепочки #i-(i-i-i)-i#
    8.5.13. Для грамматики:
    S‟

    #S#
    S

    A B c
    A

    a
    B

    b |

    постройте LR(1) анализатор и восстановите правый вывод цепочки #abc#. Какой язык порождает эта грамматика?
    8.5.14. Для грамматики:
    S‟

    #S#
    S

    aAa | aBb| bAb | bBa
    A

    c
    B

    c постройте LALR(1) анализатор и восстановите вывод цепочки #acb#. Какой язык порождает эта грамматика?

    58 8.5.15. Для грамматики:
    {S‟

    #S#, S

    ac | aBbc, B

    Bb |

    } постройте LALR(1) анализатор и восстановите вывод цепочки #abbbc#.
    8.5.16. Для грамматики:
    {S

    #B#, B

    E=E, B

    i, E

    E+i, E

    E-i, E

    i} постройте простейший LR- анализатор и восстановите вывод цепочки # i+i = i - i+i #.
    8.5.17. Для грамматики:
    { S‟

    # E #, E

    E -T | T, T

    i | (E) } постройте LALR(1) анализатор и восстановите вывод цепочки # i - ( i – i ) #.
    8.5.18. Для грамматики:
    { S

    #E#, E

    ( L ) | a, L

    E L | E } постройте LALR(1) анализатор и восстановите правый вывод цепочки #( (a) а (a а) )#. Какой язык порождает эта грамматика?
    8.5.19. Покажите что грамматика:
    { S‟

    #S#, S

    aAd | bBd | aBe | bAe, A

    c, B

    c } является LR(1) грамматикой, но не LALR(1) грамматикой. Для этого постройте LALR(1)- анализатор и LR(1)-анализатор, и покажите, что первый имеет неразрешимые конфликты, а во втором конфликтов нет.
    8.5.20. Покажите, что грамматика:
    { S

    #А#, A

    aAa |

    } не является LR(k) грамматикой при любом k (покажите это построением LR(0), LR(1) и
    LR(2)-анализаторов). Является ли она двусмысленной?
    8.5.21*. Для грамматики:
    S‟

    #S#
    S

    if b then S fi | if b then S else S fi | оп постройте LR(0)-распознаватель. Существуют ли коллизии в LR(0)-автомате? Какое дерево вывода в этой грамматике будет у цепочки:
    if b then if b then if b
    1   2   3   4   5   6   7

    написать администратору сайта