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)


 

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

11714. Настройка и запуск Telnet Services 26 KB
  Лабораторная работа №14. Настройка и запуск Telnet Services. Цели работы: научиться настраивать службы Windows 7 Telnet для доступа к ним клиента Telnet; соединяться со службой Telnet при помощи клиента Microsoft Telnet Client. Выполнил: Слепцов И. А. Группа: 103ПО. Дата: 18.12.12. Проверил: Антипенко
11715. Дослідити методи завантаження програм та налаштування інтерфейсу інтегрованного середовища Borland C++ 5.02 451.5 KB
  Програма, що створюється в середовищі ВС++, називається файлом проекту і є структурою, ієрархічно звязаних між собою файлів, використовуваних в програмі (виконуваного, початкового, заголовних і так далі). Файл проекту має розширення..
11716. Основи роботи в інтегрованому середовищі програмування Borland C++ 5.02 265 KB
  Лабораторна робота №2 Тема: Основи роботи в інтегрованому середовищі програмування Borland C 5.02. Мета: Дослідити методи завантаження програм та налаштування інтерфейсу інтегрованного середовища Borland C 5.02. Послідовність виконання роботи. Ввімкнути ПК. З...
11717. Організація введення/виведення інформації. Вивчення стандартних типів даних 67.5 KB
  Лабораторна робота №3 Тема: Організація введення/виведення інформації. Вивчення стандартних типів даних. Мета: Дослідження функцій введення виведення даних мови програмування С. Порядок виконання роботи Завантажити та налаштувати систему Borland C 5.02 ...
11718. Базові типи даних і уведення-виведення 247 KB
  Лабораторна робота №4 Тема: Базові типи даних і уведеннявиведення Мета роботи: Отримання практичних навиків в роботі з типами даних мови С і використанні функцій стандартного уведеннявиведення. Теми для попереднього опрацьовування Типи даних мови С. ...
11719. Організація введення/виведення данних мови програмування С++. Вивчення стандартних типів даних 77.5 KB
  Організація введення/виведення інформації. Вивчення стандартних типів даних. Мета роботи: Дослідження функцій введення виведення даних мови програмування С. Послідовність виконання роботи Завантажити та налаштувати сис
11720. Арифметичні операції і математичні функції мови C++ 130.5 KB
  Лабораторна робота №6 Тема: Арифметичні операції і математичні функції мови C Мета роботи:Отримання практичних навиків в програмуванні алгебраічних виразів і використанні математичних функцій бібліотеки мови С. Теми для попереднього опрацьовування ...
11721. Разработка программ линейной структуры с использованием логических операций и операций отношения 61.5 KB
  Лабораторная работа №7 Тема: Разработка программ линейной структуры с использованием логических операций и операций отношения Цель работы: 1.Освоение линейной структуры программы. 2.Изучение порядка действий при вычислении выраже
11722. Умовний оператор в мові С++ 143.5 KB
  Лабораторна робота №8 Тема: Умовний оператор в мові С Мета роботи: отримання практичних навиків в роботі з умовним оператором і розгалуженими алгоритмами в мові С. Теми для попереднього опрацьовування логічні операції умовний оператор Завданн