Реферат: Проектирование трансляторов
│ │ │ │ │ │ │
│ │ │ │ пусто / \ = ┌──┴──┐ / \ ┌────┐
│ │ │ └───────< 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, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
