-трансляторов. Для СА синтаксический анализатор используется автомат с магазинной стековой

Работа добавлена: 2018-07-05






36. Транслирующие грамматики. Построение нисходящих МП-трансляторов.

Для СА (синтаксический анализатор) используется автомат с магазинной (стековой) памятью (сокращенно МП-автомат) – это кортеж из семи элементов P=(Q,T,Г,d,q0,Z0,F) , где

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

T- конечный входной алфавит;

Г - конечный алфавит магазинных символов;

d- функция переходов - отображение множества Q x (T{e}) x Г в множество конечных подмножеств Q x Г* , т.е.d:Q x (T{e}) x Г -> {Q x Г*} ;

q0 Q - начальное состояние управляющего устройства;

Z0 Г- символ, находящийся в стеке в начальный момент (начальный символ);

F Q- множество заключительных состояний

Конфигурацией (текущее состояние) МП-автомата называется тройка (q,w,u) Q x T* x Г* , где

q- текущее состояние управляющего устройства;

w- неиспользованная часть входной цепочки; первый символ цепочки w находится под входной головкой; если we, то считается, что вся вхоная лента прочитана;

u- содержимое стека; самый левый символ цепочки u считается верним символом стека; если u=e, то стек считается пустым.

Начальной конфигурацией МП-автомата P называется конфигурация вида (q0,w,Z0), где wT* , т.е. управляющее устройство находится в начальном состоянии, входная лента содержит цепочку, которую нужно распознать, а в стеке есть только начальный символ Z0 (в лекциях мы как правило использовали символS). Заключительная конфигурация - это конфигурация вида (q,e,u), где qF, uГ* .

В таком автомате определены операции:

1) Над входной цепочкой:

- сдвиг

- держать

2) Над магазином:

- втолкнуть

- вытолкнуть

- не изменять

3) Над состоянием:

- перейти в новое состояние

- не изменять

Рассмотрим работу нисходящего распознавателя: входную цепочку можно представить в виде 2 частей:ab -|, где

a - обработанная часть цепочки (изначально пустая)

b – необработанная часть

Магазин содержит цепочкуj, которая представляет собой символы языка и считается чтоj => *b (если так то считается что цепочка допускается). В начальный момент в магазине находится начальный нетерминал (S), и символ дна $.

Цепочкуb можно представить в виде:t1b’ -|

Магазин можно представить в виде:t2j’ $

Еслиt1=t2, тоt1 иt2 считаются обработанными и отбрасываются. Еслиt2 – нетерминал то его надо заменить на правую часть правила грамматики, которое определяет этот нетерминал.

Перевод с математической точки зрения перевод (что собственно и есть трансляция) представляет собой множество пар, где 1 элемент – цепочка символов входного языка, 2 – цепочка символов выходного языка. Если перевод определен с помощью некоторой грамматики, то он называется – синтаксически управляемым.

Один из способов задания транслятора – транслирующая грамматика. Транс. Грамматика содержит 2 типа терминалов:

1) из которых формируется цепочка входного языка

2) из которых формируется цепочка выходного языка (так называемые символы действия)

Пример:

E ->E+T {+}

E ->T

T ->T*P {*}

… {+} и {*} и есть символы действия. Если убрать все символы действия, то получится грамматика входного языка.

Т.о. если входная грамматика принадлежит классуLL(1) грамматик, то по ней можно построить нисходящий МП-транслятор. Магазинными символами будут являться нетерминалы, терминалы и символы действия. Входными символами: терминалы и концевой маркер.

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




Возможно эти работы будут Вам интересны.

1. - синтаксический анализатор; ЛА лексический анализатор; ГК генератор кода; СемА семантический анализат.

2. Автоматический воздушный выключатель (автомат)

3. -грамматик. Применение преобразований при проектировании трансляторов.

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

5. -трансляторов. Восходящий МП-транслятор можно построить только по грамматике польского перево

6. Слуховой анализатор играет немаловажную роль в восприятии движений собственного тела: например с его помощ.

7. шифрования (используется сложение в кольце вычетов по модулю, равному мощности алфавита):

8. функция часто используется слово назначение особенно при рассмотрении не технических объектов.

9. -Экономия материалов-Облегчение конструкций-Улучшение теплозащитных свойствДля засыпки используется керам

10. темах понятие канал используется в нескольких смыслах: Физический канал средство передачи с