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)


 

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

39714. Этапы развития маркетинга 17.05 KB
  Так в это время спрос намного превышает предложение и поэтому любой производитель может продать свой товар важную роль играет количество товара а не его качество. В определенный момент монополия конкретного товара становится тормозом развития своего рынка поэтому либо вмешивается государство антимонопольная политика либо фирма вынуждена переориентировать свою деятельность препятствуя падению покупательского спроса. Задачей производителя было произвести как можно больше товара и как можно изощреннее его продать. Все это привело к...
39715. Стратегическое планирование 15.63 KB
  Не используя преимущества стратегического планирования организации в целом и отдельные люди будут лишены четкого способа оценки цели и направления корпоративного предприятия. Процесс стратегического планирования обеспечивает основу для управления членами организации.Система стратегического планирования дает возможность акционерам и менеджменту компаний определиться с направлением и темпом развития бизнеса очертить глобальные тенденции рынка понять какие организационные и структурные изменения должны произойти в компании чтобы она стала...
39716. Основные компоненты стратегического планирования 15.71 KB
  В нем также раскрываются потенциальные препятствия с которыми предстоит столкнуться компании и пути их преодоления. Каждый хороший стратегический план должен содержать заявление о миссии компании. Оно должно быть кратким лаконичным объяснять причину существования компании и того чего она пытается добиться. Цели организации представляют собой пути посредством которых вы планируете выполнить миссию компании.
39717. Процесс управления маркетингом: планирование, организация, мотивация и контроль 19.66 KB
  Разработка комплекса маркетинга разработка товаров; установление цен на товары; методы распространения товаров; стимулирование сбыта товаров 4. Стратегия маркетинга это генеральная программа маркетинговой деятельности на целевых рынках. Она включает главные направления маркетинговой деятельности фирмы и инструментарий комплекса маркетинга маркетингмикс с помощью которого разрабатывают и осуществляют маркетинговые мероприятия для достижения поставленных целей. Стратегия маркетинга показывает с каким продуктом на какие рынки с каким...
39718. Маркетинговый план 16.39 KB
  Анализ достигнутого уровня: историческая справка; ситуационный анализ; анализ продаж; анализ привлекательности отрасли; плановые ожидания прогнозы. В анализе достигнутого уровня предприятия дается историческая справка о его состоянии и деятельности и приводятся основные показатели деятельности предприятия в динамике. Дается описание рынка относительно его размера основных сегментов и потребностей покупателей проводятся анализ факторов среды обзор основных товаров приводятся перечень конкурентов и их оценка показаны каналы...
39722. Принципы сегментирования 21.29 KB
  Любую из этих переменных можно использовать в качестве сегментирования рынка.Географический принцип он предполагает разбивку рынка на различные географические единицы: государства страны регионы области города территории округа районы.Демографический принцип заключается в разбивке рынка на группы на основе демографических переменных таких как пол возраст семья уровень дохода род занятий образование религиозные убеждения и национальность.