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)


 

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

50488. Анализ плана с помощью инструментария Microsoft Project 508.5 KB
  Основные пункты плана внедрения Типовой план внедрения ИСУ: предварительное обследование бизнеспроцессов; Мы обследуем следующие бизнеспроцессы: контроль качества реализация подбор персонала закупки. подготовка новых бизнеспроцессов с учетом перехода на ИСУ: а выработка предложений по реинжинирингу; б формирование новых бизнеспроцессов; в согласование бизнеспроцессов. Подготавливаются следующие бизнеспроцессы: оптимизация и реализация контроля качества оптимизация реализации оптимизация подбора персонала оптимизация...
50489. ПОСТРОЕНИЕ ПЛАНА ВНЕДРЕНИЯ ИНФОРМАЦИОННОЙ СИСТЕМЫ УПРАВЛЕНИЯ ПРЕДПРИЯТИЕМ С ПРИМЕНЕНИЕМ ПРОГРАММНОГО ПРОДУКТА MICROSOFT PROJECT 602 KB
  Цель работы Сформировать план внедрения информационной системы управления завода по производству резинотехнических изделий. Порядок выполнения работы Исходной информацией для выполнения задания является выбранная функциональная подсистема в рамках которой внедряется ИСУ. подготовка новых бизнеспроцессов с учетом перехода на ИСУ: а выработка предложений по реинжинирингу; б формирование новых бизнеспроцессов; в согласование бизнеспроцессов.
50490. Физиология слухового анализатора. Слуховая сенсорная система 3.19 MB
  Слуховая сенсорная система – второй по значению дистантный анализатор человека, играет важную роль именно у человека в связи с возникновением членораздельной речи. Структурно-функциональная характеристика слухового анализатора
50491. Перемещение товаров через таможенную границу 162.5 KB
  В целом по результатам сравнительного анализа названных разделов можно сказать, что по определенным позициям законодатель оставил прежний подход в правовой регламентации основных положений перемещения товаров через таможенную границу, в то же время внес и определенные коррективы.
50492. Электрические и электронные аппараты. Лабораторные работы 1.32 MB
  Не включать установку без разрешения преподавателя ведущего занятия В случае обнаружения внештатной ситуации появление напряжения на стенде запах горения появление дыма искрение и др. Стенд имеет источники регулируемого постоянного и переменного напряжения а так же оперативное питание 15 В 30 В 5 В 15 В для питания всех устройств блока лабораторной работы микросхем систем управления обмоток реле и др. Справа от ряда предохранителей находится розетка однофазного напряжения 220 В 50 Гц для подключения осциллографа и другого...
50493. Изучение принципов работы бесконтактных датчиков и датчиков температуры 1.65 MB
  Бесконтактным выключателем (ВБ) называется выключатель, приводимый в действие внешним объектом без механического контакта выключателя и объекта. Коммутация нагрузки производится полупроводниковыми элементами. Все это обеспечивает высокую надёжность работы бесконтактных выключателей. В системах управления они, как правило, выполняют функцию датчиков обратной связи, сигнализируя о завершении выполнения конкретным элементом оборудования команды на перемещение. Но этим их применение не ограничивается.
50494. Проектирование 4-разрядного сумматора 116 KB
  Открыть VHDL файл и записать в него прогр. Сохранить файл под именем dd1 и установить его старшим в иерархии проекта. Список файлов открывается средней клавишей Files. VHDL файлы относятся файлам образующим проект.
50495. Процеси та потоки 134.5 KB
  Крім адресного простору процесу належать такі ресурси як файли динамічні області пам’яті і потоки. Ресурси створювані за життя процесу обов’язково знищуються при його завершенні. Потік thred описує послідовність виконання коду усередині процесу. Первинний потік процесу створюється системою автоматично під час створення процесу.