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)


 

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

59557. Виховуємо на традиціях рідного народу 46 KB
  Для мене особисто стало доброю традицією розповідати кожному поколінню моїх вихованців про рушники. І вже на конкретних прикладах можна показати різні за призначенням рушники: утирачі стирки покутники плечові подарункові весільні.
59558. Голодомор. Сценарій уроку 79.5 KB
  То ж помянемо хоч сьогодні із запізненням у декілька довгих десятиліть мовчання тих великомучеників нашої тяжкої історії мільйони українських селян жертв небаченого в історії людської цивілізації голодомору. Та забути жахи голодомору люди не могли.
59559. Інтегрований урок з основ економіки. Гроші, їх види та функції 71 KB
  Механізми що приводять у дію економіку досить складні але один з найдавніших і важливих гроші. Як економічний механізм гроші відомі нам з раннього дитинства з першої монетки чи банкноти. Рольова гра учні класу виступають у ролі представників наукових і фінансових структур.
59560. Гурток англійської мови 75 KB
  People of different countries celebrate Christmas in various ways. But some traditions of celebrating it are common for all the countries. Two of them should be mentioned here. They are to decorate Christmas tree and to light candles.
59561. Засоби масової інформації 39 KB
  Мета та завдання: познайомити учнів із поняттям засобів масової інформації її інформаційними функціями розвивати вміння знаходити інформацію та користуватись нею аналізувати її розвивати критичне ставлення до подачі інформації.
59562. Здоров’я — мудрих гонорар день здоров’я для вчителів 70.5 KB
  Учителям пропонується пройти стежиною здоровя. Маршрут стежки здоровя Перша зупинка Канони здоровя знайомство з основними заповідями Салернського кодексу здоровя медичного трактату XIV століття. Друга зупинка Сонячна вибір із палітри фарб кольору здоровя відбиття власного настрою у виборі вираження обличчя.
59563. Здрастуй, рідна школо! 76.5 KB
  Обладнання: прапори країн; карта світу; стенд присвячений організації ЮНЕСКО; стенди із символікою школи гімн герб прапор з історією виникнення розвитку й досягнень школи; на партах література книги журнали країн світу магнітофон музичні записи; різні сувеніри на яких написано...
59564. Знайомство з історією 38.5 KB
  Знаряддя праці зброя місце поховань храми фундаменти будівель це: а речові історичні джерела; б писемні історичні джерела; в усні історичні джерела. Які історичні джерела допомагають відтворити побачити минуле...
59565. Діагностика ПК за допомогою програм та утиліт 55 KB
  Програми подібного роду дуже часто працюють під управлінням операційної системи MS-DOS, оскільки вона для своєї роботи вимагає дуже мало системних ресурсів, що дозволяє звести до мінімуму вплив на результати тестів. Звично при запуску файлу, при спробі викачування його з Інтернету, пропонується створити завантажувальну дискету...