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

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

Переход от автоматов с возвратами к безвозвратной схеме и условия ее реализации рассмотрены Д. Кнутом в статье [Topdownanalysis], в которой формализуется класс так называемых нисходящих методов синтаксического анализа. Примечательно, что этот подход хорошо ложится в русло стиля программирования от состояний, что будет показано в ближайших разделах.

10.3.2. Задача анализа простых выражений

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

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

Новости

  • 1
  • 2
Prev Next

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

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

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

24.01.2016

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

Реклама