Информатика и выч. техника \ Информационно-безопасные системы

Информационно-безопасные системы. Анализ проблемы: Учебное пособие, страница 34

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

Если язык определяется 1Х(1)-грамматикой, то его можно распознать с помощью МП-автомата с одним состоянием, использующего расширенную магазинную операцию ЗАМЕНИТЬ.

Для данной LL(1) - грамматики МП-распознаватель с одним состоянием задается следующим образом:


1.  Множество входных символов - это множество терминальных символов грамма­тики, расширенное концевым маркером;

2.  Множество магазинных символов состоит из маркера дна, нетерминальных сим­волов грамматики и терминалов, которые входят в правые части правил, за исключени­ем тех, что занимают крайнюю левую позицию;

3.  Вначале магазин содержит маркер дна и начальный нетерминал;

4.  МП - автомат описывается управляющей таблицей, строки которой помечены магазинными символами, столбцы - входными символами, а элементы описываются ниже;

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

<А>® bа;

где b - терминальный символ, а - цепочка терминальных и нетерминальных символов, тогда используется переход

ЗАМЕНИТЬ(ar) , СДВИГ.

Для того, чтобы применить правило вида

<А>® а,

где  а - цепочка терминальных и нетерминальных символов, не начинающаяся с терминала, используется переход

ЗАМЕНИТЬ(аr) , ДЕРЖАТЬ.

Здесь можно воспользоваться тем фактом, что при а=е

ЗАМЕНИТЬ(ar)=ВЫТОЛКНУТЬ

6. Если для нетерминала <А> имеется аннулирующее правило и по правилу 5 н было создано элемента таблицы, соответствующего магазинному символу <А> и вход­ному символу b, то можно или применить аннулирующее правило, или отвергнуть входную цепочку;

7. Если магазинным символом является терминал b, то элементом таблицы в стро­ке b и столбце b будет

ВЫТОЛКНУТЬ, СДВИГ;

8. Элементом таблицы, который находится в строке маркера дна и столбце конце­вого маркера, является

ДОПУСТИТЬ;

9. Элементы таблицы, не описанные ни в одном из пунктов 5-8, заполняются опе­рацией

ОТВЕРГНУТЬ.

Построение синтаксического блока как МП-автомата является очень трудоемким процессом, поэтому далее рассмотрим еще один метод построения синтаксического блока - метод рекурсивного спуска.

Построение синтаксического блока методом рекурсивного спуска

Введем ряд определений, которые понадобятся для дальнейшего изложения [З].

Определение 8.1: Транслирующей грамматикой или грамматикой перевода называется КС-грамматика, множество терминальных символов которой разбито на множе­ство входных и множество символов действия. Если дана транслирующая грамматика, то грамматика полученная путем вычеркивания всех символов действия из правил этой грамматики, называется входной грамматикой.

Определение 8.2: Для данной КС-грамматики и нетерминала <Х>

СЛЕД(<Х>)

это множество терминальных символов, которые могут следовать непосредственно за <Х> в какой-либо промежуточной цепочке, выводимой из начального нетерминала <S>.

Определение 8.3: По данным КС-грамматике и промежуточной цепочке а, со­стоящей из символов этой грамматики, определим

ПЕРВ(а )

как множество терминальных символов, которые стоят в начале промежуточных цепочек, выводимых из а, т.е. являются их первыми символами.

Определение 8.4: Определим ВЫБОР(Р) как множество выбора правила Р сле­дующим образом:

1.  ВЫБОР(<А>®ba) = {b}, где b - терминальный символ, а - цепочка терми­нальных и нетерминальных символов,

2.  ВЫБОР(<А>®e) = СЛЕД( <А> ),

3.  ВЫБОР(<А>®a) = ПЕРВ(а), где а не аннулирующая,

Скачать файл