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)


 

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

12781. ЧТО ТАКОЕ CSS 24.99 KB
  ВВЕДЕНИЕ Каскадные таблицы стилей/Cascading Style Sheets CSS это поразительное изобретение для улучшения вида ваших webсайтов. Оно поможет сэкономить уйму времени и предоставит вам совершенно новые возможности в дизайне webсайтов. CSS совершенно необходим каждому работающему с we...
12782. Шрифты. Семейство шрифта 18.13 KB
  Шрифты На этой лабораторной работе вы изучите работу со шрифтами с помощью CSS. Мы рассмотрим также вопрос о том что конкретный шрифт выбранный для webсайта может отображаться только в том случае если этот шрифт установлен на PC с которого выполняется доступ к этому webса...
12783. Цвет и фон. Цвет переднего плана: свойство color 52.81 KB
  Цвет и фон На этой лабораторной работе вы научитесь использовать цвета и фон на ваших webсайтах. Мы рассмотрим также продвинутые методы позиционирования и управления фоновым изображением. Будут разъяснены следующие CSSсвойства: color backgroundcolor backgroundimage bac...
12784. Текст. Отступы. Выравнивания текста 12.22 KB
  Текст Форматирование и установка стиля текста ключевая проблема для любого webдизайнера. На лабораторной вы увидите впечатляющие возможности CSS при отображении текста. Будут рассмотрены следующие свойства: textindent textalign textdecoration letterspacing texttransform ...
12785. Ссылки. Что такое псевдокласс 15.12 KB
  Ссылки Всё изученное в предыдущих уроках вы можете применять и для ссылок/links например изменять шрифт цвет подчёркивание и т. д. Новым будет то что в CSS эти свойства можно определять поразному в зависимости от того посетили уже ссылку активна ли она находится ли указ...
12786. Идентификация и группирование элементов (class и id) 15.12 KB
  Идентификация и группирование элементов class и id Иногда вам нужно будет применить особый стиль к определённому элементу или конкретной группе элементов. В этой лабораторной работе мы подробно разберём как можно использовать class и id для специфицирования свойств выбран
12787. Группирование элементов (span и div) 15.67 KB
  Группирование элементов span и div Элементы span и div используются для структурирования документа часто совместно с атрибутами class и id. В этом уроке мы подробно рассмотрим как использовать span и div поскольку эти элементы HTML имеют важнейшее значение в CSS. Группиро...
12788. Боксовая модель в CSS 24.21 KB
  Боксовая модель Боксовая модель в CSS описывает боксы генерируемые для HTMLэлементов. Боксовая модель также имеет детальные опции для определения полей рамок заполнения и содержимого каждого элемента. На диаграмме далее показано как построена боксовая модель: Боксов...
12789. Поля и заполнение 13.38 KB
  Поля и заполнение В предыдущем уроке мы рассмотрели боксовую модель. В этом уроке объясним как можно изменять представление элементов свойствами margin и padding. Установим поля элемента Установим заполнение элемента Установим поля элемента У элемента ест