20617

Магазинные автоматы

Лекция

Коммуникация, связь, радиоэлектроника и цифровые приборы

I – входная строка I – текущий символ входной строки M – стек M – символ в вершине стека pushM – операция записи в стек popM – операция выталкивания из стека M=0 – проверка стека на пустоту I=0 – проверка на пустоту входной строки nextI – переход к следующему символу в строке {Si} – множество состояний конечного автомата Текущее состояние автомата описывается тремя системами: Si M I При переводе автомата в новое состояние получим Si M ISj . Если текущий символ строки совпадает с символом в вершине...

Русский

2013-07-31

86.5 KB

3 чел.

Лекция № 3.

Магазинные автоматы.

Если детерминированный конечный автомат дополнить стеком, то становиться возможным синтаксический анализ вложенных и рекурсивных цепочек. Такой конечный автомат называется магазинным автоматом.

Iвходная строка

(I) – текущий символ входной строки

Mстек

(M) – символ в вершине стека

push(M, «…») – операция записи в стек

pop(M, «…») – операция выталкивания из стека

M=0 – проверка стека на пустоту

I=0 – проверка на пустоту входной строки

next(I) – переход к следующему символу в строке

{Si} – множество состояний конечного автомата

Текущее состояние автомата описывается тремя системами:

(Si, (M), (I))

При переводе автомата в новое состояние получим

(Si, (M), (I))(Sj, ?, ?). где ? – зависит от конкретной операции

S – грамматики:

Является одним из типов контекстно-свободных грамматик.

  1.  Характеризуется тем, что правая часть каждой продукции должна начинаться с терминального символа.
  2.  Для двух продукций, имеющих одинаковую левую часть, начальные терминалы в правой части должны быть разными.
  3.  Не допускаются продукции с пустой правой частью.

Пример:

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

Алгоритм использования магазинного автомата для S – грамматики.

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

.

  1.  Если текущий символ строки не совпадает с символом вершины стека, то это приводит к синтаксической ошибке, если вершина стека принадлежит множеству терминальных символов

и при этом    Ошибка.

  1.  Если вершина стека принадлежит множеству нетерминальных символов, то ищется правило, которое имеет в левой части этот не терминал, а его правая часть начинается с терминала совпадающего с очередным символом рассматриваемой строки. Тогда в стеке левая часть заменяется на правую.

  1.  Распознавание считается успешным, если стек и строка опустошаются одновременно.
  2.  В начальный момент времени в стек записывается стартовый символ грамматики.

Произвести синтаксический разбор 5+(2-1)

1 slist

2 listlist+block

3 listlist-block

4 listblock

5 dig0…9

6 blockdig

7 block(list)


 

А также другие работы, которые могут Вас заинтересовать

11146. Англо-американська модель корпоративного управління 111.16 KB
  Англоамериканська модель корпоративного управління Особливості англоамериканської системи корпоративного управління безпосередньо повязані з особливостями акціонерної форми власності головним чином з відсутністю в англійських і американських корпораціях зна
11147. Внутрішнє середовище корпоративного управління 72.5 KB
  ТЕМА 7. Внутрішнє середовище корпоративного управління 7.1. Органи управління акціонерним товариством Реалізація корпоративних прав акціонерів здійснюється через їхню участь в управлінні товариством. Органами управління акціонерного товариства виступають: 
11148. Господарські товариства корпоративного типу 108 KB
  Господарські товариства корпоративного типу Значного поширення в процесі реформування власності корпоратизації та акціонування підприємств набули господарські товариства. Закон України Про господарські товариства визначає поняття й види господар...
11149. Господарські товариства як обєкт управління 57.5 KB
  Господарські товариства як обєкт управління План Суть господарських товариств. Порядок створення господарського товариства. Господарські товариства корпоративного типу Товариство з обмеженою відповідальністю ...
11150. Захист прав акціонерів при зміні статутного капіталу акціонерного товариства 40.5 KB
  Захист прав акціонерів при зміні статутного капіталу акціонерного товариства Зміна розміру статутного капіталу в бік збільшення або зменшення завжди істотно зачіпає майнові інтереси акціонерів товариства. Тому законодавством встановлено обовязок товариства інформ
11151. Про порядок збільшення (зменшення) розміру статутного капіталу акціонерного товариства 55.5 KB
  Про порядок збільшення зменшення розміру статутного капіталу акціонерного товариства При збільшенні розміру статутного капіталу відкритого акціонерного товариства акції які передбачені до розміщення можуть розповсюджуватися шляхом відкр...
11152. Інститути спільного інвестування 54.5 KB
  Інститути спільного інвестування Інститути спільного інвестування фінансові установи які обслуговують сферу спільного інвестування шляхом забезпечення гарантій прав власності на цінні папери та захист прав учасників фондового ринку. Основним призначенням інстит
11153. Конфлікт інтересів 31 KB
  Конфлікт інтересів Конфлікт інтересів це ситуація зіткнення інтересів різних заінтересованих у діяльності АТ осіб груп осіб у питаннях стратегічного бачення майбутнього товариства а також формування використання розподілу та управління матеріальними та нематер
11154. Корпоративна власність. Економічна роль статутного капіталу 97.5 KB
  Корпоративна власність. Економічна роль статутного капіталу. 1. КОРПОРАТИВНА ВЛАСНІСТЬ. Корпоративна власність це привласнення засобів умов та результатів праці групою акціонерів. Корпоративна власність поділяється на такі види: 1Проста корпоративна власніст