Реферат: Проектирование трансляторов

                            ЛЕКЦИЯ 5

               АНАЛИЗ КОНТЕКСТНО-ЗАВИСИМЫХ ЯЗЫКОВ

                С ПОМОЩЬЮ МАТРИЦ ПРЕДШЕСТВОВАНИЯ

     Наиболее  распространенные  грамматики,  описывающие   языки

программирования, - это КС-грамматики (грамматики типа 2 в  клас-

сификации  Хомского).  Однако  описание  языков  программирования

грамматиками типа 1, т.е. контекстно-зависимыми (КЗ)  грамматика-

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

сания языка, так и построение транслятора.

     Рассмотрим алгоритм анализа программы, если  алгоритмический

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

грамматик совпадает с классом КЗ-грамматик (грамматики типа 1  по

Хомскому).

     Грамматика G является неукорачивающей, если для каждого

правила x ::= y С Ф выполняется  условие │ x │<=│ y │, где │ x │

         i     i                            i      i          i

и  │ y │  -  число  символов, входящих в строки x  и y  соответ-

      i                                          i    i

ственно.

     Множества самых левых Л(В) и самых правых П(В) символов сим-

вола В:

     L(В) = { U/ ] (Be ::= Ux) С Ф \/ ] (Be ::= B1x) С Ф /\

                        /\ U С L(В1) };

     R(В) = { U/ ] (eB ::= xU) С Ф \/ ] (eB ::= xB1) С Ф /\

                        /\ U С R(В1) };

где e, x - строки, возможно, пустые; В, В1, U С Vt U Vn.

     Из этих определений следует, что терминальные символы  также

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

при условии, что они использовались как начальные (конечные) сим-

волы в строках грамматических правил (x i ::= y i) С Ф.

     Из определения L(В)   непосредственно следует, что если a ->

b, т. е. a = f1 -> f2 -> ... -> fk = b (k>1) и a  =  Bx,  то  на-

чальные символы строк f i = Ux i (1<i<=k),  в  которых  начальный

символ U участвовал в строках y правил вывода,  принадлежат  мно-

жеству L(В).

     Аналогично из определения R(В) непосредственно следует,  что

если a -> b, a = xB и, кроме того, a = f1 -> f2 -> ... -> fk =

= b (k>1), то конечные символы строк f i = x i U (1<i<=k),  в кото-

рых конечный символ U участвовал в правилах вывода,  принадлежат

множеству R(В).

     Определим  отношения  предшествования  для   неукорачивающих

грамматик:

     В  = В  <--> ] ф (ф: g ::= xB B y) С Ф;

      i    j                      i j

     B  < B  <--> ] ф (ф: g ::= xB Ny) С Ф /\ B  С Л(N);

      i    j                      i            j

     B  > B  <--> ] ф (ф: g ::= xNB y) С Ф /\ B  С П(N) \/

      i    j                       j           i

     \/ ] ф (ф: g ::= xNN y) С Ф /\ B  С П(N) /\ B  С Л(N );

                         1           i            i      1

     где x и y - строки, возможно, пустые, N, N , С V  U V .

                                            1      t    n

     Описание языка программирования неукорачивающими грамматика-

ми позволяет вводить символы языка типа IF, BEGIN,  ELSE,  FOR  и

идентификаторы стандартных функций типа SIN, COS, EXP и т.  п.  в

виде нетерминальных символов в грамматические правила, что облег-

чает анализ этих символов и ускоряет процесс трансляции.

     Теперь рассмотрим алгоритм анализа входного текста, написан-

ного на языке, порожденном неукорачивающей  грамматикой предшест-

вования типа 1 по классификации  Хомского.  Блок-схема  алгоритма

показана на рис. 4.

                        ┌─────┐

                        │  1  │

                        └──┬──┘

    ┌──────────────────────┼───────────────────┐

    │                      │                   │ нет

    │   ┌────┐      пусто / \  =  ┌─────┐     / \

    │   │ 15 ├───┬───────< 2 >────┤  3  ├────< 4 >

    │   └─┬─┬┘   │        \ /  <  └─────┘     \ /

    │     │ │    │         ├─────────┐         │ да

    │     │ │    │         │         │         │

    │     │ │    │  пусто / \  =  ┌──┴──┐     / \     ┌────┐

    │     │ │    └───────< 5 >────┤  6  │    < 13>─1──┤ 14 │

    │     │ │             \ /     └─────┘     \ /  да └────┘

    │     │ │              │<               нет│

    │     │ └──────────────┼───────────────────┘

    │     │               / \

    │     └──────────────< 7 >

    │                нет  \ /

    │                      │ да

    │                   ┌──┴──┐

    │                   │  8  │

    │                   └──┬──┘

    │                   ┌──┴──┐

    │                   │  9  │

    │                   └──┬──┘

    │                      ├────────┐

    │ ┌────┐              / \     ┌─┴───┐

    └─┤ 11 ├─────────────<10 >────┤ 12  │

      └────┘          =   \ / =/= └─────┘

                             Рис.2

    1. k,i=1                        8. q := │Xn│

       Мi=1                         9. ГП

    2. Ri ? Lk2                     10. q=1

    3. i=i+1   Ri=Lk3               11. i::=j

       k=k+1                        12. k=k-1

       j=i                              Lk=n(q)

    4. Ri=4                             q=q-1

    5. Rj=Ri                        13. Y=R1...Ri

    6. j=j-1                        14. выход

    7. Сущ. правило Y =Rj...Ri      15. обработка ошибки

     При анализе входного текста используется стек R,  работающий

по правилу FILO (first in, last  out),  чтение  исходного  текста

производится слева направо, а дерево сворачивания строится  снизу

вверх.

     Алгоритм в каждом текущем предложении Si выделяет самую  ле-

вую строку, заключенную между отношениями > и <, и заменяет ее по

соответствующему правилу грамматики. Если грамматика  предшество-

вания не имеет двух правил с одинаковыми строками y i, то  данный

алгоритм для каждого предложения S L(G) всегда порождает  одну  и

ту же последовательность правил  сворачивания.  Для  того,  чтобы

строки сворачивания всегда были заключены между отношениями  >  и

<, в грамматиках анализируемых языков, как и в случае  КС-грамма-

тик, вводятся ограничители начала и конца текста @.

     В начале  анализа строки в верхнюю ячейку стека R записыва-

ется первый символ программы,  т. е. символ @. Индексам i (номер

символов  стека R) и k (номер смвола входного текста) присваива-

ются начальные значения 1.

     Блок 2. Проверяется отношение предшествования между  верхним

символом стека Ri и очередным символом входного текста Lk .  Если

между ними отношение вида _ (пусто), значит во входном тексте до-

пущена ошибка.

     Блок 3 записывает в стек R очередной символ входного текста.

     Блок 4 выделяет признак окончания текста Ri = @.

     Блоки 5  и 6 определяют левую границу сворачиваемой строки.

Для этого проверяется отношение предшествования между каждой па-

рой символов R    и R  до выполнения условия  R   < R . В блоке

              j-1    j                         j-1   j

5 не предусмотрен выход при выполнении условия R    > R , так как

                                                j-1    j

такое условие не может иметь место; вообще в процессе работы  ал-

горитма в стеке R не может появиться пара символов  с  отношением

>, так как это исключает сам алгоритм.

     Блок 7 производит поиск правила y=Rj,...,Ri по таблице грам-

матических правил и запоминает номер правила n, если оно найдено.

     Блок 8 записывает в счетчик q число символов строки

Xn (q:=│Xn│).

     Блок 9 производит переход на генерирующую подпрограмму.

     Блок 10 проверяет длину строки Xn.

     Блок 11 "выталкивает" символы Rj,..., Ri из стека R и  запи-

сывает в него первый символ строки Xn, обозначенный на  блок-схе-

ме Xn(1).

     Блок 12 записывает все символы строки Xn, кроме первого, пе-

ред первым непрочитанным символом входного текста. Это не вы-

зовет переполнения массива L,  так как по условию  │Xn│ <= │Yn│.

Следовательно, число символов строки x не может быть больше чис-

ла символов строки y.

     Блок 13 проверяет, выполняется ли  правило  R1,...,Ri.  Если

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

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

чит данный текст из-за допущенной ошибки не может быть свернут.

     Описания языков программирования КС- и даже неукорачивающи-

ми грамматиками вынуждает переносить определение части  формаль-

ных условий из синтаксиса в семантику.  Например, в ФОРТРАНе при

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

ли его описание явным или неявным. Если описание явное, то опре-

деляется тип идентификатора.

     Пример:

     Имеется грамматика:

     Vт = { А, B },  Vn = { S, D, H, B`, A` }

     1: S -> A`SD

     2: S -> A`B`A

     3: AD -> HA

     4: H -> D

     5: B` -> B

     6: BD -> BB`A

     7: A` -> A

     Эта грамматика порождает язык следующего вида:

     (А**n)(B**n)(А**n)       ; n - степень

     L(S) =A`,A,H,D           R(S)=A, D

     L(B`)=B                  R(B`)=B

     L(A`)=A,H,D              R(A`)=A

     L(H) =D                  R(H)=D, A

     L(D) ="                  R(D)=A

     L(B) =B                  R(B)="  (неопределено)

     L(A) =H,D                R(A)="

     Матрица предшествования:

      │

    S │             =        =

    B`│          <  <  =

    A`│    =  =  <  <  <  <

    H │          <  <  =

    D │          >  >  >     >

    A │    >  >  >  >  >  >  >

    B │    =     >  >  >  <

    @ │ =     <  <  <  <

   ───┼────────────────────────

      │ S  B` A` H  D  A  B  @

      Дерево вывода на основе матрицы и правил:

       ┌──────────────────────────┐

      S+──┐    ┌─────────────А+   +D

       │  │    │               \ /

       │ S+─── +─────+B` H +────+3

       │       │     │     │    │

       │       │     +5   4+    │

       │       │     │     │    │

       │       │     +B   D+    │

       │       │     │     │    │

       +А`     +А`   └──+──┘    │

       │       │    ┌──/│\──┐   │

       │       │    │   │   │   │

       +1      +1   │   +B` │   │

       │       │    │   │   │   │

       │       │    │   +5  │   │

       │       │    │   │   │   │

       А       А    B   В   А   А

     Ф : BA ─> BDA         B.   .A

                             \./

                            ./│\.

                           B  D  A

       ЭКВИВАЛЕНТНЫЕ ПРЕОБРАЗОВАНИЯ ПОРОЖДАЮЩИХ ГРАММАТИК

                  В ГРАММАТИКИ ПРЕДШЕСТВОВАНИЯ

     Грамматики называются эквивалентными,  если  порождающие  их

языки совпадают.

     Теорема 1.  Пусть в порожденной грамматике имеется одно  или

несколько вхождений строки y в правые части  порождающих  правил.

Преобразование грамматики путем введения  нового  нетерминала  Ф,

нового правила вывода Ф::=y и замена  всех  или  части  вхождений

строк y на вхождения нового символа порождает  новую  грамматику,

эквивалентную исходной.

     G - грамматика.

     Строка АВ, которая входит хотя бы в одну часть  грамматичес-

кого правила, называется парой. Если А С R(А), В С L(В), то  пара

рекурсивно-неоднозначна.

     Грамматика, не содержащая рекурсивно-неоднозначных пар  сим-

волов, называется рекурсивно-приведенной. Любая приведенная грам-

матика - рекурсивно-приведенная.

   АЛГОРИТМ ПРЕОБРАЗОВАНИЯ РЕКУРСИВНО-НЕОДНОЗНАЧНОЙ ГРАММАТИКИ

                  В ГРАММАТИКУ ПРЕДШЕСТВОВАНИЯ

     1. Находим множество правых символов. Выбираем все рекурсив-

ные символы грамматики (А  R(А)).  Грамматические  правила  имеют

вид: Ф::=(psi). Выделяем все вхождения  этих  символов  в  строки

psi, при условии, что они являются левыми частями пар. Для каждо-

го выбранного символа, имеющего такое вхождение, введем новый не-

терминальный символ А, новое правило вывода и заменим  все  выде-

ленные вхождения А на вхождения А`.

     2. Для каждого нового правила А`::= А  ищем  другое  правило

вида Ф ::= А, и если R(А) не содержит последнего символа  строки,

то заменяем правило Ф ::= А на Ф ::= А`.

     3. Находим множество левых символов. Выбираем все леворекур-

сивные символы В L(B), при условии, что В - правый  член  некото-

рой пары. Выделим все вхождения этих символов в строку (psi), при

условии, что эти вхождения являются правыми членами пар. Для каж-

дого В, имеющего такое вхождение, вводим В`, В`::=  В  и  заменим

все вхождения В на вхождения В`.

     4. Для каждого нового правила В` ::= В ищем в G другие  пра-

вила вида Ф ::= В, при условии, что правые части этих правил сов-

падают. Если L(B) не содержит первого символа строки Ф, то  заме-

няем правило Ф ::= В на Ф ::= В`.

     5. Находим множество левых и правых символов для  полученной

грамматики, находим матрицу отношений предшествования, если  мат-

рица однозначна выход.

     6. Перебирая все вхождения пар во всех строках (psi),  отли-

чаем вхождения таких пар АiDi, где неоднозначность типа >< или >=

имеется либо между Аi и В L(Di). Для каждого отличного  вхождения

пары АiDi в строку (psi)m выделяем подстроку хАi, для нее  вводим

нетерминал Nj и новое грамматическое правило вида Nj ::=  xАi.  В

правых строках грамматических правил выделенные вхождения  цепоч-

ки xАi заменяем новым символом Nj. Если в одной строке  в  правой

части выделено несколько вхождений таких цепочек, то надо  после-

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

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

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

самых коротких.

     7. Потом повторяется п. 5.

     8. Перебирая все вхождения пар в правых частях  грамматичес-

ких правил, выбираем (отмечаем) пары АiDi, где  имеется  неодноз-

начность. Для каждого отмеченного вхождения вычисляем строку Di y.

     Для каждой выделенной подстроки, отличной от других, вводит-

ся новый нетерминал вида Nj ::= Di y. Для  всех  выделенных  под-

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

     Грамматики предшествования.

     L(U)={S/Эz(U=>Sz)}

     R(U)={S/Эz(U=>zS)}

     Si = Sj ::= Э F (F: U::=xSiSjy)

     Si < Sj ::= Э F ((F: U::=xSiUly) & Si{-L(Ul))

     Si > Sj ::= Э F ((F: U::=xUkSjy) & Si{-R(Uk)) v

        Э F ((F: U::=xUkUly) & Si{-R(Uk) & Sj {- L(Ul))

     Алгоритм.

     Обозначения:

     L    - строка анализируемого текста;

     L(k) - к-й символ L;

     S    - стек реализации процесса свертывания;

     S(i) - i-й элемент стека S

     u(l),w(l),fi(l),psi(l) - соответственно цепочки  u,w,fi,psi

правила P(l);

     │u(l)│,│w(l)│,│fi(l)│,│psi(l)│ - длины цепочек  u,w,fi,psi;

     n    -  индекс  самого  нижнего  символа  S(n),  такого что

S(n).x.S(n+1);

     m    - указатель существования в S пропущенной основы;

     │p│  - число правил в грамматике.

     Блок 1. Инициирует работу алгоритма.

     i=k=1; n=max; m=0; Si=1;

     Блок 2. Обработка ошибок.

     Блоки 3,4. Нахождение правой границы основы свертывания.

     3: S(i) ? L(k)  =< - 4, >,>< - 6

     4:   j=i=i+1;

          S(i)=L(k);

          k=k+1;

     Блоки 5,6. Запоминают n.

     5: n=i;

     6: S(i).><. L(k) & n>i да - 5, нет - 8.

     Блоки 8,9. Нахождение левой границы основы свертывания.

     8: S(j-1) >< S(j), < - 7,  = - 9

     9: j=j-1;

     Блок 7. Начальное значение номеру грамматического правила Р

          l=0

     Блок 10. Анализ завершения просмотра всех правил.

          l=│p│  да - 12, нет - 11.

     Блок 11. Переход на просмотр следующего правила.

          l=l+1;

     Блок 12 проверяет возможность анализа при отсутствии правил

вида (u fi, u psi) для свертывания выделенной основы.

          m=0;

     Блок 14 проверяет возможность запоминания выделенной основы

в S.

          n=i;

     Блок 16 - возврат на первую из пропущенных основ.

          L(k-n+j)...L(k+1)=S(n)...S(i)

          i=j=n;

          m=0;

          k=k-n+1;

     Блоки 13,15,17 проверяют соответствие строк u(l),  w(l),  fi

(l) выделенной основе и контекстным строкам, ее окружающим.

                            ЛЕКЦИЯ 6

          LR(k)-ГРАММАТИКИ И СООТВЕТСТВУЮЩИЙ АНАЛИЗАТОР

     Анализ  для  LR(k) - грамматики  называется  методом  Кнута.

     LR(k)-анализатор - устройство из неограниченных вправо вход-

ной ленты, верхнего и нижнего магазинов.

     На входной ленте помещается еще не обработанная правая  под-

цепочка анализируемой цепочки.  К  анализируемой  цепочке  справа

приписано k маркеров.

     В верхнем магазине - цепочки-символы состояний  анализатора.

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

вариантам дерева вывода на различных тактах анализа.

     В нижнем магазине  -  частично  свернутые  левые  подцепочки

входной цепочки (обработанные анализатором).

     На каждом такте работы анализатора может выполняться одно из

действий: сдвиг или свертка. После выполнения определенного коли-

чества тактов анализатор допускает  или  отвергает  анализируемую

цепочку.

     Выполнение каждого такта можно разбить на 2 этапа.  На  1  -

преобразование информации нижнего (и, возможно, верхнего) магази-

нов. Информация для выполнения 1 этапа - правое состояние  цепоч-

ки состояний (верхний магазин) и к левых символов  не  обработан-

ной части входной цепочки. Если действие - сдвиг, в нижний  мага-

зин записывается терминал из левого символа входной цепочки. Вер-

хний магазин остается без изменений. Если действие - свертка,  то

из нижнего и верхнего магазинов исключается по одинаковому  числу

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

гр.правила). Входная цепочка  -  без  изменений.  Информация  для

свертки - правые состояние и символ из верхнего и нижнего магази-

нов соответственно (после выполнения 1 этапа). Запись  в  верхний

магазин "переходного состояния".

     Свертка соответствует случаю использования некоторого прави-

ла вывода порождающей грамматики. Символы, исключаемые из  нижне-

го магазина, соответствуют правой, а символ, записываемый в мага-

зин - левой части грамматического правила.

     ОПРЕДЕЛЕНИЕ: LR(k)-анализатор, соответствующий G=(Vt,Vn,P,S)

- LR(k)=(U,X,H,T,b1,b2,S0,Z0,Sr), где:

     U - конечное множество состояний анализатора;

     X - конечное множество входных символов, Х=Vt U # -маркер;

     H - конечное множество H=(Vt U Vn U Z0),

         Х=Vt U # - маркер;

     T - {Q U (p,A)},  A C Vn,

          p - положительное целое,

          Q - сдвиг,

          пара  (p,A)  -  cвертка,  с  исключением p символов из

                          магазинов  и записью в  нижний магазин

                          символа А

              k         k

     b1 - (UxX ) -> T, X - цепочки длины k  над алфавитом X;

     b1 - частично определенная функция,  задающая  первые  этапы

тактов анализа b2 - (UxH) -> U;

     b2 -  частично определенная функция, задающая  вторые  этапы

тактов анализа;

     S0 - S0 C U - начальное состояние;

     Z0 - граничный маркер;

     Sr - Sr C U, заключительное состояние.

     Для любой LR(k) - грамматики можно построить LR(1) - грамма-

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16