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)


 

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

40980. ТРУДОВИЙ ДОГОВІР 233.5 KB
  Відсторонення працівника від роботи. Така угода характеризується наступними ознаками: працівник особисто виконує свої трудові функції; працівник повинен в ході виконання своєї трудової функції підпорядковуватись правилам внутрішнього трудового розпорядку; власник або уповноважений ним орган повинен організувати працю працівникастворити необхідні та належні умови праці виплачувати йому заробітну плату і т. До них слід віднести взаємне волевиявлення сторін про прийняття влаштування працівника на роботу визначення трудової функції...
40981. Медична арахноеитомологія. Членистоногі та комахи-збудники і переносники збудників захворювань людини 46.5 KB
  Клас павукоподiбнi rchnoide Медичне значення мають представники скорпіонів павуків та кліщів. Медичне значення кліщів як збудників хвороб та переносниківзбудників захворювань людини :Розміри кліщівcrinдрібні .У багатьох кліщів голово груди і черевце зливаються в єдине ціле втрачаючи сегментацію .Ротовий отвір кліщівколючосисний або гризучесисний .
40982. Взаємовідношення мови й гендера 89.5 KB
  Мовна картина світу як результат пізнання та концептуалізації об’єктивної дійсності Мові належить активна роль у культурі й пізнанні. Вона є унікальною здатністю людини що відрізняє її від будьяких інших живих істот і решти світу. Кожен народ посвоєму розчленовує фрагменти світу і посвоєму називає їх. Формується світ тих хто говорить цією мовою тобто формується концептуальна картина світу як сукупність знань про світ що є зафіксованими у лексиці граматиці фразеології.
40983. Охорона праці. Нагляд і контроль за дотриманням законодавства про працю і правил з охорони праці 218.5 KB
  Охорона праці. Нагляд і контроль за дотриманням законодавства про працю і правил з охорони праці. Поняття охорони праці за трудовим правом Загальновідомо що економічне зростання автоматично ще не веде до збалансованого економічного і соціального розвитку. Зміни що відбуваються у структурі зайнятості й попиту на робочу силу як і до становища працівника на робочому місці умов його праці ставлять підвищені вимоги до безпеки праці.
40984. Конфлікти в колективі 40.5 KB
  Тому проблема здебільшого полягає не в наявності самого факту конфлікту а в тому який характер він носить – деструктивний чи конструктивний – і яким чином розв’язується. Конструктивна та деструктивна суть конфліктів Деструктивний конфлікт переводить причини що призвели до конфлікту на “особистостіâ€. Дана установка не веде до вирішення конфлікту а навпаки його загострює зростає упередженість проти партнера напруга у взаємостосунках посилюються неприємні почуття та переживання виникають стреси та ін. Прикладом деструктивного...
40985. Трудові спори і порядок розв’язання 183.5 KB
  Поняття трудових спорів та їх класифікація При здійсненні відносин людей під час трудової діяльності між працівниками і власниками підприємств або уповноваженими ними органами можуть виникати й часто виникають різного роду непорозуміння. Перебудова виробничих і трудових відносин нові форми застосування і використання праці істотно вплинули не тільки на індивідуальні трудові відносини а й на структуру і зміст організаційноуправлінських відносин що виникають між власником підприємства або уповноваженою ним особою з одного боку і трудовим...
40986. 4-х комнатный жилой дом мансардного типа 103.5 KB
  Расширился ассортимент, и повысилось качество применяемых в отечественном строительстве отделочных материалов — всех видов керамической плитки, покрытий для пола и стен, а также керамических санитарных и санитарно-технических изделий.
40987. Мова і культура 148.5 KB
  Однак з іншого боку у самій матерії мови у ряду істотних характеристик мовної структури позначилася біологічна природа людини. Психофізіологічні можливості знакової діяльності людини зумовили багаторівневу організацію мови визначили кількісні параметри окремих рівнів наприклад обсяг фонологічної системи що коливається в різних мовах в інтервалі від 10 до 100 одиниць; обсяг словника в інтервалі від 10 тисяч до півмільйона слів; вияв надмірності в мові. Культура визначає план змісту мови. У молекулярній біології і семіотиці був виявлений...
40988. Стратегии позиционирования в маркетинге, стратегия эффективного позиционирования, проблемы разработки стратегии позиционирования 233 KB
  Целью данной работы является детальное изучение понятия позиционирования в маркетинге и рассмотрение стратегий позиционирования. Для достижения поставленной цели мною решались следующие задачи: раскрытие понятия позиционирования, выявления ключевых концепций и идей позиционирования