Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
GOS.pdf
Скачиваний:
172
Добавлен:
11.03.2015
Размер:
6.59 Mб
Скачать

 

Выбор

 

 

1

a,l,c,b

 

 

2

d

 

 

3

a,l

 

 

4

c,b

 

 

5

c

 

 

6

-|,d,b

 

 

7

a

 

 

8

l

 

 

7 Грамматики польского перевода. Построение восходящих МП-трансляторов.

Восходящий МП-транслятор можно построить только по грамматике польского перевода. Это транслирующая грамматика, в которой символы действия самые правые в правой части.

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

В→<ß{x}>γ

<ß{x}>→ ß{x}

Транслятор строить также, как и распознаватель. Символьные действия выполняются при свертке правила, которому он принадлежит.

Обратная польская нотация (ОПН) (Обратная польская запись, Постфиксная нотация, Бесcкобочная символика Лукашевича, Польская инверсная запись, Полиз) — форма записи математических выражений, в которой операнды расположены перед операторами.

Описание

Отличительной особенностью обратной польской нотации является то, что все аргументы (или операнды) расположены перед знаком операциии. В общем виде запись выглядит следующим образом:

Запись набора операций состоит из последовательности операндов и знаков операций. Операнды в выражении при письменной записи разделяются пробелами.

Выражение читается слева направо. Когда в выражении встречается знак операции, выполняется соответствующая операция над двумя последними встретившимися перед ним операндами в порядке их записи. Результат операции заменяет в выражении последовательность еѐ операндов и еѐ знак, после чего выражение вычисляется дальше по тому же правилу.

Результатом вычисления выражения становится результат последней вычисленной операции.

yao.png

8. Восходящие методы обработки языков.

Распознаватель типа «перенос-свѐртка»

Такой распознаватель задаѐтся таблицей.Строка –магазинный символ,столбец-вх символ.

Множество магазинных символов –все симв грамматики(терминалы и нетерминалы).Вх символытерминалы.В клетках записывается перенос или опознание.В строке,которой соответсвует символ «+» добавляется операция «опознать».

Нужно определить,если в магазине,S-допустить.Процедура опознания включает процедуру свѐртки.

В зависимости от ситуации один и тот же симв может иметь разный код,и код верх магазина симв конкретного опред правила ,по кот. нужно выполнить свертку,поэтому проц.опознания нету,строиться граф ситуацию.

По последней свѐртке можно определить,доп-ся цепочка или нет.

Распознаватель типа «перенос-опознание»

T(табл)[m(машинный символ),x]=П(перенос)

Перенос нужно выполнять,если есть правила A→αmβ,x ПЕРВ(β)

Рассмотрим начальную ситуацию.Переносить можно только те символы,которые принадлежат множеству первых для начального нетерминала.

T[m,x]=ОП,если A→αm,x СЛЕД(А)

ОП-опозн.допускает конечное множество цепочек(предст.собой регулярный язык)Введѐм S‘→S – будет концевом маркере.Такая грамматика называется пополненной.

Самый простой класс грамматик,для которых строится расп «перенос-опознание»без конфликтов:- в одной клетке и П и ОП,нет2х правил А→αβ,В→β

Группа,в которой нет такой ситуации,называется безсуффикснойПО грамматикой.Особенность нет ε-правил.

Грамматики предшествования позволяют описывать более широкий класс языков чем ЛЛ1грамматики, однако менее чем SLR-грамматики. Алгоритм разбора грамматик предшествования относится к восходящим методам разбора, т.е. дерево разбора строится снизу вверх (листья и "ветки" соединяются в более крупные "ветки"). Работает алгоритм по принципу "переноссвертка".

Центральное место во всем, что касается грамматик предшествования занимают отношения предшествования (бинарные отношения между символами полного словаря грамматики и допустимыми символами магазина). Фактически это три отношения: < = > (сворачивается раньше, сворачивается вместе, сворачивается после).

Класс простого предшествования определяется очень просто: грамматика является грамматикой простого предшествования, если для любых двух символов полного словаря существует не более одного отношения предшествования. Неформально, это значит, что в каждой клетке матрицы предшествования должно находится не более одного отношения.

Если ПОД(s) ПОД(с)=(не пересекаются),то можно определить какое правило может применяться.

Такие грамматики наз-ся простыми грамматиками стратегии предшествования.

Самый широкий класс,для которого можно построить распознаватель «переносопознание».Порядка преобразования произвольной грамматики в грамматику смешанной стратегии предшественников нет.Любую гр. можно преобразовать в группу,которая не допускает конфликтов типа «перенос-опознание.

Конфликт возможен,если А→αx;B→βx>γ

Множество следующих за А пересекается с множеством первых для γ.Можно сделать x в конце <βx>→βx.Процедуру опознания не всегда можно построить.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]