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)


 

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

22657. Роздільна здатність оптичних приладів 70 KB
  Характеризує здатність давати зображення двох близько розташованих одна від одної точок об’єкта рознесених в просторі. Найменша лінійна кутова відстань між двома точками починаючи з якої їх зображення зливаються і не розрізняються наз. Релей ввів критерій згідно до якого: зображення двох точок можна розрізнити якщо дифр. Предмет знаходиться на а зображення утворюється в фокальній площині об`єктива телескопа з фокусною відстанню f .
22658. Принципы объединения сетей на основе протоколов сетевого уровня 138.5 KB
  Протоколы сетевого уровня реализуется, как правило, в виде программных модулей и выполняются на конечных узлах-компьютерах, называемых хостами, а также на промежуточных узлах-маршрутизаторах, называемых шлюзами. Функции маршрутизаторов могут выполнять как специализированные устройства, так и универсальные компьютеры с соответствующим программным обеспечением.
22659. Інтерференція поляризованих променів при проходженні через кристали 89 KB
  Світло поширюється вздовж вісі OZ. Ніколь N1 забезпечує лінійно поляризоване світло в площині XOY. На пластинку падає лінійно поляризоване світлоко де розпадається на звичайний і незвичайний промені.векторів звичайної і незвичайної хвиль на вході в пластинку у вигляді: де різниця фаз між звичайним і не звичайним променями Склавши два останні рівняння отримаємо Розглянемо два випадки: 1 еліптично поляризоване світло.
22660. Явища обертання площини поляризації падаючого світла в речовинах 359 KB
  Явища обертання площини поляризації падаючого світла в речовинах Відомо що світло – це поперечна хвиля тобто вона розповсюджується у напрямку  до площини що утворюють вектори E та H. Частковим випадком еліптичної поляризації є колова поляризація. Деякі речовини при проходженні через них світла можуть змінювати площину поляризації. Це пояснюється поворотом площини поляризації що здійснюється оптично активним зразком схема: Джерело – поляризатор – зразок – аналізатор Розглянемо явище у різних середовищах: 1 Усі одновісні оптично активні...
22661. Основні закони випромінювання. Ф-ла Планка 381 KB
  Основні закони випромінювання. Закон СтефанаБольцмана для ачт : M=σT4 де М – енергетична густина випромінення σконстанта Стеф. Закон зміщення Віна: Tλmax=b де bconst яка не залежить від темпер. Класичній підхід: ймовірність що енергія моди лежить в проміжку тоді отримуємо формулу РелеяДжинса: ; Планк: тоді: формула Планка З формули Планка можна отримати закон зміщення Віна і М Т4 при Закон Кіргофа: спектральна випромінююча здатність поглинаюча здатність Це відношення не залежить від природи...
22662. Квантування енергії лінійного гармонічного осцилятора 75 KB
  Модель гармонічного осцилятора : частинка коливається навколо положення рівноваги тоді ми можемо розкласти наш потенціал в ряд поблизу положення рівноваги x0=0. Тоді гамільтоніан для такої системи буде Щоб перейти від класичної системи до квантової необхідно від фізичних величин перейти до операторів тоді . Щоб його розв’язати необхідно перейти до безрозмірних змінних тоді Розглянемо асимтотики цього рівняння: отримуєм при . Тоді підставляючи цей вираз у рівняння для U і роблячи деякі перетворення можна отримати вираз для...
22663. Явище радіоактивності. Види радіактивного розпаду 27.5 KB
  Види радіактивного розпаду. Ядра що підлягають такому розпаду наз. В процессі розпаду у ядра може змінюватись як атомний номер Z так і масове число A. Фізичною характеристикою розпаду є середній час життя ядер.
22664. γ – випромінювання та ефект Месбауера 46 KB
  γ – випромінювання та ефект Месбауера Явище γ – випромінювання ядер полягає в тому що ядро випромінює γ – квант без зміни А кількість нуклонів та Z кількість протонів. Гама – випромінювання виникає за рахунок енергії збудження ядра. Спектр γ – випромінювання завжди дискретний через дискретність ядерних рівнів. Особливо інтенсивне γ – випромінювання з’являється коли β – розпад у високій степені заборонений в основний стан кінцевого ядра і дозволений в один із збуджених станів.
22665. Класифікація ядерних реакцій. Реакція термоядерного синтезу 69 KB
  Ядерна реакція типу: де а А частинки до реакції;b В частинки після реакції;Q – енергія що виділилась після реакції екзотермічна реакція вид енерг ендотермічна реакція погл енерг пружне розсіяння . Реакції описуються за даними диференціального перерізу розсіяння в елемент тілесного кута : і інтегрального перерізу : . Можна виділити пружні і непружні реакції Складне compound ядро коли реакція йде у дві стадії: спочатку утворюється складне ядро С – воно повинно жити досить довго по ядерним масштабам – і яке потім...