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)


 

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

2961. Техническая эксплуатация перекрытий зданий 70.5 KB
  Техническая эксплуатация перекрытий зданий. Эксплуатационные качества междуэтажных, чердачных и других видов перекрытий. Факторы и причины влияющие на них. Оценка технического состояния перекрытий. Обеспечение несущих и ограждающих функций крыш в процессе эксплуатации.
2962. Ограждающие конструкции с применением древесины 454.5 KB
  Ограждающие конструкции с применением древесины Деревянные и светопрозрачные настилы. Прогоны. Сборные ограждающие конструкции с использованием древесины. Основные положения расчета клеефанерных плит покрытия. Настилы являются несущими элементами ог...
2963. Магнитные датчики и приборы курсовых систем 623 KB
  Магнитные датчики и приборы курсовых систем  Общие сведения о курсе летательного аппарата Магнитное поле Земли  Магнитные компасы Девиации и погрешности магнитных компасов Индукционные компасы Контрольные вопросы Общие ...
2964. Крыши, покрытия и эксплуатационные требования к ним 117.5 KB
  Крыши, покрытия и эксплуатационные требования к ним По своему назначению любая крыша должна удовлетворять ряду важных эксплуатационных требований, так как ее состояние сказывается на техническом состоянии и эксплуатационных качествах нижележащих...
2965. Определение плотности твердого тела 171.02 KB
  Цель работы – определение плотности твердого тела и освоение методов определения погрешностей измерений и их расчёта. Задание: - определить плотность твердого тела. Оценить погрешность проведенных измерений.
2966. Курсовые системы ЛА 749 KB
  Курсовые системы ЛА. Состав курсовых систем. Гироскопические приборы, их погрешности и математическая модель. Гироскопические датчики. Математическая модель гироскопического датчика. Авиагоризонты. Центральные гировертикали...
2967. Средства отражения информации 352.5 KB
  Средства отражения информации. Виды представления пилотажной и навигационной аппаратуры Психофизиологическая деятельность человека. Особенности деятельности человека-оператора с учетом СОИ Основные этапы переработки информации оператором...
2968. Измерение фазового сдвига 446.5 KB
  Цель работы: ознакомление с осциллографическими методами измерения фазового сдвига между двумя синхронными гармоническими напряжениями и получения практического навыка проверки шкалы фазометра с помощью калибратора фазы.
2969. Создание документации к проекту по созданию и внедрению интернет магазина 121.29 KB
  Создание документации к проекту по созданию и внедрению интернет магазина  Задача лабораторной работы: формирование основной документации по проекту в соответствии со стандартом PMI (8 заданий). Название: Создание документации к проекту по соз...