Непейвода Н.Н. Программирование. Раздел 4

Непейвода Н.Н. Программирование. Страница 463

Если автомат снабжается стековой памятью, то говорят об автоматах со стековой памятью, вычислительная мощность которых больше обыч­ных конечных автоматов, но меньше мощности машины Тьюринга. Именно такие автоматы служат теоретической основой разработок синтаксических анализаторов контекстносвободных языков. По существу, все анализаторы, основанные на автоматах со стековой памятью, отличаются друг от друга лишь стратегиями работы со стеком.

Мы рассмотрим только одну из этих стратегий, которая допускает интер­претацию, сохраняющую прежний смысл конечного автомата. Вместо явной дополнительной памяти в системе одновременно действует несколько про­цессов, рассматриваемых как экземпляры различных автоматов. Экземпляры подчиняются стековой дисциплине: активизация нового экземпляра автомата приводит к приостановке предыдущего автомата (запоминанию его состоя­ния), а окончание работы автомата — к возобновлению приостановленного автомата с передачей ему сведений о том, как отработал завершающийся процесс. Внимательный читатель тут же заметит, что эта трактовка повто­ряет то, что ранее мы называли процедурным механизмом, но только для процедур специального вида, которые реализуют конечные автоматы.

Эти сведения (значение True,если вызванный автомат распознал строку успешно, и Falseв противном случае) используются для выбора очеред­ного состояния, в которое переходит автомат. Использование автоматов со стековой памятью частично нарушает инвариант стиля программирования от состояний: Действия глобальны, условия локальны, поскольку пере­даваемая через стек информация, которая управляет поведением автомата, делается локальной. Конечно же, регламентированный отход от стиля не является крамолой, и именно на этом пути появляются различные стили программирования как варианты базовых стилей. Но в настоящей главе нас, в первую очередь, интересует направление, в максимальной степени соот­ветствующее стилю программирования от состояний. По этой причине мы и рассматриваем системы конечных автоматов, связанных стеком.

Новости

  • 1
  • 2
Prev Next

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

24.01.2016

Ракета "Ангара-А5В" в ближайшее десятилетие не полетит

Роскосмос не планирует в течение ближайшего десятилетия осуществлять пуск тяжёлой ракеты-носителя А...

Ученые РФ опровергли выводы исследований о вреде ГМО

24.01.2016

Ученые РФ опровергли выводы исследований о вреде ГМО

Исследователи из Института проблем передачи информации (ИППИ РАН) проанализировали несколько самых п...

Летающие "Крокодилы"

24.01.2016

Летающие "Крокодилы"

20 удивительных фактов о боевом вертолете Ми-24.Этот вертолет стал таким же узнаваемым символом сове...

В Аргентине описали новый вид динозавра-гиганта

24.01.2016

О ранее неизвестном виде динозавра, относящемуся к инфраотряду зауроподов, рассказали аргентинские п...

Реклама