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

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

На первый взгляд может показаться, что такие системы еще дальше уво­дят от программирования от состояний, чем автоматы со стековой памятью. Однако требование корректно определять вычисления системы неизбежно приводит к тому, что потоки, которые перерабатываются вызываемыми в од­ном состоянии экземплярами автоматов, должны быть строго локальными для них. В самом деле, если допустить, что передаваемый поток является общим, то чтение из него должно быть независимым для каждого из экзем­пляров, а это противоречит дисциплине обработки потока. При успешном окончании работы экземпляра очередной читаемый символ должен следо­вать за подстрокой, которая распознана отработавшим экземпляром, т. г. для продолжения действий используется тот поток, который был передан этому экземпляру. Что же касается неуспешно завершившихся экземпляров, то их локальные потоки ликвидируются. Обычным способом реализации такого расщепления потока и локализации его потомков по вызываемым экземпля­рам автоматов является организация возвратов по обрабатываемой строке.

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

Новости

  • 1
  • 2
Prev Next

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

Реклама