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)


 

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

58114. Общество и общественные отношения 226 KB
  ОБЩЕСТВО - обособившееся от природы, но тесно с ней связанная часть мира, которая включает в себя способы взаимодействия людей и формы их объединений.
58115. Значение здоровья для человека 41 KB
  Цель: ознакомить с задачами и содержанием курса Основы здоровья; формировать представление о значении здоровья для обучения труда общения с родными; развивать память мотивацию основ сохранения и укрепления здоровья; воспитывать любовь к жизни к людям.
58116. Військові звання і знаки розрізнення. Начальники та підлеглі, старші та молодші, їх права і обовязки 182.5 KB
  Мета: Вивчити поняття щодо суті і значення військової дисципліни; Назвати статути Збройних сил України основні їх вимоги. Статути Збройних Сил України це зведення законів військової служби на основі яких проходять повсякденне життя виховання навчання бойова діяльність військ...
58118. Функции финансов, как экономической категории 15.22 KB
  Именно через эту функцию реализуется общественное назначение финансов – обеспечение каждого субъекта хозяйствования и государства необходимыми ресурсами, использ. в форме денежных фондов целевого назначения.
58119. Финансы как экономическая категория в системе социально-экономических категорий 15.17 KB
  Каждая наука оперирует определенным кругом понятий, имеет особые, специфические категории, которые являются концентрированным выражением общих, наиболее существенных признаков, качеств, закономерностей и взаимосвязей объектов той сферы
58120. Создание Интернет-страниц 32 KB
  Он требует терпения и знания основ «программирования» на языке html, который, по сути, языком программирования не является. Итак. Для работы нам будет достаточно программы Блокнот. И даже более того, достаточно будет использовать только меню FILE.
58121. СУСПІЛЬНО-ІСТОРИЧНІ УМОВИ РОЗВИТКУ УКРАЇНСЬКОЇ ЛІТЕРАТУРИ ХХ ст., ОСНОВНІ СТИЛЬОВІ НАПРЯМИ 120.5 KB
  Цi хронологiчнi межi визначаються не тiльки перебiгом революцiї 1905–1917 рр., а й вiдходом iз життя I. Франка (1916 р.) та М. Коцюбинського й Лесi Українки (обоє померли в 1913 р.). Формування пiсля 1905 р. Києва як лiтературної столицi України, поширення загальноукраїнської лiтературної перiодики
58122. ВВЕДЕНИЕ. МИР В XVI – XVIII ВВ 46 KB
  В более узком смысле история — это наука, изучающая всевозможные источники о прошлом для того, чтобы установить последовательность событий, исторический процесс, объективность описанных фактов и сделать выводы о причинах событий.