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)


 

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

65342. ВПЛИВ ГУМОРАЛЬНИХ ФАКТОРІВ Т-ЛІМФОЦИТІВ НА ОСОБЛИВОСТІ ФУНКЦІОНУВАННЯ КЛІТИН РАКУ МОЛОЧНОЇ ЗАЛОЗИ ЗА УМОВ СФЕРОЇДНОГО ТА МОНОШАРОВОГО РОСТУ 208.5 KB
  Розуміння особливостей клітинної взаємодії при пухлинному процесі залишається актуальною медико-біологічною проблемою. З огляду на це, розроблення та впровадження простих та доступних клітинних систем для діагностики та дослідження...
65343. Удосконалення динамічної діагностики структурно-неоднорідних деталей ДТЗ 940.5 KB
  Інтересом до розробки достовірної методики динамічних розрахунків деталей нової техніки обєднаних в загальний клас структурно неоднорідних обєктів в міцністних розрахунках яких необхідно враховувати як природу...
65344. Адміністративно-правові засади формування системи та правового статусу антимонопольних органів в Україні 178 KB
  В останні десятиріччя дедалі більшого значення в Україні набуває захист і підтримка добросовісної економічної конкуренції, яка є головним рушієм розвитку ринку. Ефективність такого захисту залежить, у першу чергу, від діяльності компетентних...
65345. ПІДВИЩЕННЯ ТЕХНІКО-ЕКСПЛУАТАЦІЙНИХ ПОКАЗНИКІВ СТРІЛОВИХ САМОХІДНИХ КРАНІВ ЗАСТОСУВАННЯМ ГІДРАВЛІЧНИХ ГАСИТЕЛІВ КОЛИВАНЬ 2.1 MB
  Одним з напрямків вирішення цієї задачі є динамічне гасіння коливань суть якого полягає в приєднанні до силових ланцюгів механізмів допоміжних гасителів коливань з метою зниження коливального стану крана.
65346. КОНСТИТУЦІЙНЕ ПРАВО ГРОМАДЯН БРАТИ УЧАСТЬ У ВСЕУКРАЇНСЬКИХ ТА МІСЦЕВИХ РЕФЕРЕНДУМАХ І ЙОГО ЗАБЕЗПЕЧЕННЯ В УКРАЇНІ 157.5 KB
  Процес становлення громадянського суспільства в Україні та розбудова української демократичної правової держави передбачає перетворення українського народу з об’єкта державного управління в пріоритетний суб’єкт влади.
65347. Методичні засади підготовки фахівців спеціального зв’язку Державної прикордонної служби України у процесі навчання військово-спеціальних дисциплін 162 KB
  Результати аналізу підготовки фахівців СПЗ ДПСУ із військово-спеціальної дисципліни «Зв’язок в органах охорони кордону» свідчать, що вимогам нормативних документів підготовка цих фахівців з середнім балом успішності 3,34 задовольняє, але не забезпечує підготовку професійно компетентного фахівця.
65348. ФІНАНСОВО-ЕКОНОМІЧНИЙ МЕХАНІЗМ САНАЦІЇ АГРАРНИХ ПІДПРИЄМСТВ В РИНКОВИХ УМОВАХ 360.5 KB
  З метою збереження виробничої структури підприємства в регіональному господарстві стає впровадження санації головної процедури в системі антикризового управління. Тому на сучасному етапі в умовах зростання кількості аграрних підприємств-банкрутів...
65349. УДОСКОНАЛЕННЯ ПРОТИРАЛЬНОГО ОБЛАДНАННЯ ПІДПРИЄМСТВ ХАРЧУВАННЯ 195 KB
  Дотепер не досліджені зусилля що виникають на робочих органах протиральних машин підприємств харчування в процесі обробки різних харчових продуктів і не визначено комплексний вплив на технічні характеристики протиральних машин...
65350. ВИКОРИСТАННЯ ПОЖИВНИХ РЕЧОВИН ТА ПРОДУКТИВНІ ЯКОСТІ МОЛОДНЯКУ КРОЛІВ ЗА РІЗНИХ РІВНІВ ПРОТЕЇНУ ТА ЛІЗИНУ В КОМБІКОРМАХ 277.5 KB
  Співвідношення поголівя самців і самок у кожній з груп становило 1:1 10 самців і 10 самок яких утримували окремо. При формуванні групаналогів враховували вік стать живу масу і походження тварин.