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)


 

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

85994. ВНЕШНЕПОЛИТИЧЕСКИЙ ПРОЦЕСС 60.01 KB
  Ответы на этот вопрос призваны дать социологический и политический анализы внешней политики. Втретьих существует четкое осознание противоречия между с одной стороны требованиями максимально высокого профессионализма во внешней патетике а с другой императивами сохранения и укрепления и в этой сфере демократических начал. Оно ведет к поиску путей и средств оптимального преодоления названного противоречия какими оказываются многочисленные общественные организации по проблемам внешней политики как внутри социальной и политической элит так...
85995. МЕСТО И РОЛЬ КОНФЛИКТОВ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 123.4 KB
  Понятие конфликта Проблема конфликта является одной из сложнейших в теории международных отношений. Оставаясь важнейшим элементом международных отношений она переходит в качественно иное состояние наполняя внутреннюю жизнь любого субъекта напряженностью и возможной взрывоопасностью. Хотя среди аналитиков нет единого мнения в вопросе определения конфликта они в общем соглашаются что под конфликтом в международных отношениях понимается особый вид внешнеполитического взаимодействия субъектов прежде всего государств который выражается в...
85996. ПОНЯТИЕ И СУЩНОСТЬ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 155.5 KB
  В русском языке понятие «международные отношения» существенно расходится с вроде бы родственным ему «international relations» в английском языке, на котором почти исключительно создавалась эта наука. В нашем понимании «международные отношения» в изначальном и прямом...
85997. ОСОБЕННОСТИ СОВРЕМЕННОГО МИРА И ИХ ВЛИЯНИЕ НА МЕЖДУНАРОДНЫЕ ОТНОШЕНИЯ И ВНЕШНЮЮ ПОЛИТИКУ РЕСПУБЛИКИ БЕЛАРУСЬ 56.64 KB
  В современных условиях глобализация как важнейшая особенность международных отношений вызывает неоднозначную оценку. Сущность глобализации Сам термин глобализация по своей внутренней определенности предполагает формирование подлинного мира в котором по мнению некоторых аналитиков стираются географические границы социальных и культурных систем и сами люди во все большей степени осознают исчезновение подобных границ. Тем не менее глобализация имеет объективные источники и следовательно является естественным ходом истории. Таким образом...
85998. МЕТОДОЛОГИЧЕСКИЕ ПРИНЦИПЫ И ОСНОВНЫЕ КАТЕГОРИИ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 72.11 KB
  Поскольку в нашем пособии рассматривается интеллектуальная карта дисциплины международных отношений ни одно представление в этой академической области не будет приниматься само по себе. Кукулка выработать же объективистский взгляд на проблему международных отношений очень и очень трудно если вообще возможно. Так в основе историкоописательного метода лежат представления о дипломатических отношениях между государствами в тот или иной период развития истории; Он только описывает взаимодействие между основными субъектами международных...
85999. ОСНОВНЫЕ НАУЧНЫЕ НАПРАВЛЕНИЯ ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 193.5 KB
  Поэтому в современной науке о международных отношениях все чаще обнаруживается стремление к переходу от теоретического к методологическому и нормативному модусу рассмотрения этих отношений, в границах которых она нередко воспринимается как форма делегитимизации
86000. ИНТЕГРАЦИОННЫЕ И ДЕЗИНТЕГРАЦИОННЫЕ ФАКТОРЫ В ТЕОРИИ МЕЖДУНАРОДНЫХ ОТНОШЕНИЙ 76.4 KB
  Развитие интеграционных процессов стало закономерным результатом роста производительных сил что потребовало создания более надежных связей и отношений между странами и устранения многочисленных препятствий на пути сотрудничества. В интеграции необходимо выделить несколько элементов: Первый предпосылки к которым необходимо отнести близость уровней развития и степень зрелости интегрирующихся стран; наличие исторических связей общность проблем стоящих перед странами в области развития и сотрудничества; демонстративный эффект когда в...
86001. РАЗРАБОТКА И ЭКОНОМИЧЕСКОЕ ОБОСНОВАНИЕ МЕРОПРИЯТИЙ ПО ПОВЫШЕНИЮ ЭФФЕКТИВНОСТИ ДЕЯТЕЛЬНОСТИ ТРАНСПОРТНОГО ЦЕХА ОАО «ТВЕРСКОЙ ВАНОГОСТРОИТЕЛЬНЫЙ ЗАВОД» 346.5 KB
  Характеристика альтернативных видов моторного топлива; обзор инновационных технологий и оборудования в сфере использования газа как моторного топлива; исследование социально-экономических аспектов использования газомоторного топлива; характеристика ОАО «Тверской вагоностроительный завод»...
86002. ПРОБЛЕМЫ СЕМЕЙ БЕЗРАБОТНЫХ 33.57 KB
  Россия столкнулась со все более обостряющейся проблемой занятости населения при переходе к рыночным отношениям. Безработица незанятость в производстве трудоспособного желающего работать населения. В соответствии с Законом РФ О внесении изменений и дополнений в Закон РСФСР О занятости населения в РСФСР от 15 июля 1982 г. Основные группы населения составляющие безработных.