Главная Промышленная автоматика.

»

£*

Рнс. 6.2. Таблица распознавания, построенная алгоритмом 6.2.

за которым следует любое выражение, а если знака -Ь иет, то - пустую цепочку (распознаваемую К). Тогда можно так проинтерпретировать правило (1): выражение-это терм, за которыл? следует нечто, распознаваемое £ + ,3 именно либо пустая цепочка, либо цепочка из чередующихся знаков + и термов, начинающаяся с -Н и оканчивающаяся термом. Аналогично иитерпре- тируются правила (3) и (4).

Правила (5) и (6) говорят о том, что множитель (цепочка, распознаваемая F) -это либо заключенное в скобки выражение, либо символ а (если скобок нет).

Пусть (а-Ьа)*а - входная цепочка для алгоритма 6.2. Тогда он построит матрицу pfy], изображенную на рис. 6.2.

Вычислим для примера элементы последнего столбца этой матрицы. Элементы, соответствующие нетерминалам Р, М, А, L и R, принимают значение /, так как каждый из указанных нетерминалов распознает символ из S, а последний символ-это концевой маркер. К всегда дает значение /, а У-всегда 0. Применяя шаг (3) нашего алгоритма, находим, что первый проход по нетерминалам на шаге (4) дает значения для £ + , Т«, F и они равны соответственно О, О, f. После второго прохода Т получает значение /. Значения для Е я, F можно вычислить на третьем проходе.

6AJ. Реализация ОЯНРОВ-программ

На практике системы синтаксического анализа, подобные ОЯНРОВ-программам, реализуются -не в табличной форме, как это сделано в алгоритме 6.2, а обычно с помощью метода проб и ошибок. Мы построим сейчас автомат, „реализующий" распознающую часть ОЯНРОВ-программ, Читателю предоставляем самому показать, как pacшиpнт> этот автомат до преобразователя, выдающего последовательность успешных вызовов процедур, по которой можно построить „разбор" или перевод.

Автомат состоит из входной ленты с указателем, положение которого можно - восстанавливать, -управляющего устройства с тремя состояниями и магазина, в котором помещаются символы из некоторого конечного алфавита и указатели входных позиций. В работе этого автомата воплощается наше интуитивное представление о вызывающих друг друга процедурах (нетерминалах) и возвратах входного указателя, происходящих при каждой неудаче. Указатель возвращается туда, где он. находился в тот момент, когда состоялся вызов неудачной процедуры;

Определение. Анализирующей машиной назовем шестерку М - («Э, 2, Г, 6, начало, Z„), где

(1) Q -{успех, неудача, начало};

(2) 2 - конечное множество входных символов;

(3) Г-конечное множество магазинных символов;

(4) &-такое отображение множества Qx(V {е})хТ в множество QxF*, что

(а) если успех или неудача, то б(, а, Z) не определено, если а 2, и Ь(д, е, Z), имеет вид (начало. У) для некоторого У Г;

(б) если б(начало, а, Z) определено для некоторого а 2, то б(начало, 6, 2) ие определено для всех fta из 2U{e};

(в) для значением б(начало, а, Z), если оно определено, может быть только (успех, е)\

(г) б(начало, е, Z) может иметь только вид (начало, yZ) для некоторого КГ или вид (, е) для успех либо /у = неудача;

Эта ОЯНРОВ-программа предназначена для распознавания обычных арифметических выражений с операциями + и », т. е. ; языка Л (Go). Нетерминал Е распознаёт выражение, состоящее; из термов (т. е. цепочек, распознаваемых нетерминалом Т), раз-деленныхзнаками +. Нетерминал £+. распознает. выражение, в котором первый терм опупден. Таким образом, правило (2) говорит о том, что £ распознает знак + (распознаваемый Р),

Пример менее тривиального вычисления встречается в третьем столбце. Нижние семь элементов легко получаются по правилу (2). Далее, применяя (2) и учитывая, что элемент третьего столбца, соответствующий Р, равен 1, находим, что элемент четвертого столбца (4=3-f 1), соответствующий Е, тоже равен Таким образом, элемент третьего столбца, соответствующий Я., равен

2(=1 + 0- □



(5) начало - начальное состояние;

(6) ZqT - начальный магазинный символ.

Машина М похожа на автомат с магазинной памятью, но между ними есть несколько важных различий. Элементы множества Г М0Ж1Ю представлять себе как процедуры, вызывающие, друг друга или „переходящие" одна в другую. Магазин используется для записи рекурсивных вызовов и положения входной головки в момент вызова. Состояние начало обычно служит для вызова другой процедуры, это отражается в том, что если б(нач1ло, е, Z)= (начало, где КГ и Z-верхний символ магазина,

то У помещается в магазин непосредственно над Z. Состояния; успех и неудача служат для перехода к другой процедуре, а не. для вызова се. Если, например, б(успех, е, Z) = (начало, 7), то V просто заменяет Z наверху магазина. Определим формально действия машины М.

Конфигурацией машины М назовем тройку (, w\x, у), где

(1) {успех, неудача, начало};

(2) W п X принадлежат 2*, - метасимвол, указывающий положение входной головки;

(3) у - содержимое магазина, имеющее вид (Z, (\)...(Z, u). где ZjT и /у~целое число при ljm. Верх магазина расположен слева. Z- для каждого i-это вызов „процедуры", а - входной указатель.

Зададим ца множестве конфигураций отношение (или I-, когда М подразумевается):

(1) Пусть б(иачало, е, Z) = (начало, YZ) для УТ. Тогда (начало, wx,,{Z, О уЖ (начало, w]x, [У, j){Z, i)y)

где Здесь происходит „вызов" У и регистрируются поло-

жение входной головки в момент вызова и вызываемая „процедура" У.

(2) Пусть 6(, е, Z) -(начало, У), тде Уи успех, неудача}. Тогда

((?, w\x, (Z, О Т) I-(начало, w\x, {У, i)y)

Здесь Z „переходит" в К. Входная позиция, соответствующая К, та же, что и позиция, соответствующая Z.

(3) Пусть 6(начало, а, Z){q, i?) для а[}{е). Если 9-успех, то

(начало, w\ax, (Z, i)y)\- [уо-п&у,, wa\x, у) Если а не является префиксом цепочки х пли 9 = неудача, то (начало, w\x, (Z, ч) у) Р (неудача, иу, у) *

где uv=wx и \u\i. В последнем случае входной указатель возвращается на позицию, задаваемую указателем, находящимся наверху магазина.

Заметим, что при б(начало, с, Z) = (успех, е) очередным состоянием анализирующей машины будет успех, если необработанная часть входной цепочки начинается символом а, и неудача в противном случае.

Пусть f-обозначает транзитивное замыкание отношения \-. Языком, определяемым машиной М, назовем множество L(jM) = {miIS* и (начало, ]w, [Z, 0)) (успех, w], е)).

Пример 6.7. Пусть M = (Q, {а, Ь], {Z, К, Л, В, £}, б, начало, Zg), где б задается равенствами

(1) б(начало, е, Z)(начало, KZJ

(2) б(успех, е, Z) - (начало, Z„)

(3) б(иеудача; е, Za) = (начало, Е)

(4) б(начало, е. К)(начало, АУ)

(5) б(успех, е, У)= (начало, У)

(6) б(неудача, i?. У) (начало, В)

(7) б(иачало, а, Л)= (успех, е)

(8) б(начало, Ь, В) (успех, е)

(9) б(начало, е, £")--(успех, е)

М распознает цепочки, состоящие из символов а и & и окан-Ч14вающиеся символом Ь, но делает это довольно своеобразно. Л и В распознают соответственно ан Ь. Когда начинает действовать символ К, он ищет символ а и, если отыскивает его, „переходит" в себя. Таким образом, магазин не меняется, а на входе „потребляется" символ а. Если достигнут символ b или конец входной цепочки, то К в состоянии неудача стирает верхнюю ячейку магазина. Иными словами, У заменяется символом В и независимо от того, приводит В к успеху или неудаче, В в конце концов стирается.

Z„ вызывает У (и переходит в себя) так же, как У вызывает Л. Поэтому любая цепочка, состоящая из символов а и b к окан чивающаяся символом Ь, приводит к тому, что Zq сотрется и наступит успех. Действия машины yt на входной цепочке аЬаа образуют такую последовательность конфигураций:

(начало, \аЬаа, (Z,, 0)) (начало, fabaa, (К, 0){Z, 0))

[-(начало, fabaa, (Л, 0) (У, 0) (Z, 0))

Н (успех, at baa, (V, 0)(Z„ 0))

К (начало, a\baa, {У, 0){Z„ 0))

[-(начало, afbaa, (Л, 1)(У, 0) (Z, 0))

h (неудача, abaa, {У, 0) (Z„ 0))

[-(начало, ajbaa, {В, 0)(Z„ 0))



Н(успех. 1- (начало, -~ (начало, 1-(начало, К (успех, -(начало, 1-(начало, Н(успех, - (начало, \- (начало, Н(неудача, Н (начало, I-(неудача, \~ (начало, h (успех.

аЬ t аа, аЬ \аа, аЬ \ аа, аЬ \ аа, aba \ а, aba t а, aba t а, abaa f, аЬаа t, abaa], аЬаа\, abaa f, -ab t aa, ab t aa, ab t aa,

{Л. {У. (К.

0)) 0))

2)(Я„ 2) (Г, 2)(2о, 2)(Z„, 3)(К, 2) (Zo, 2)(Zo. 4) (Г, (Г, 2)(Z«, (В. 2) (Z„ (2,, 0))

(£. 0))

2)(Z„

О»

О»

2) (Zo,

2)(Zo.

Заметим, что цепочка abaa не допускается, потому что конец ее не достигается на последнем шаге. Однако цепочка ab была бы. допущена. Важно также отметить, что в четвертой сконца конфигурации В не „вызывается", а заменяет У, Поэтому наверху магазина появляется 2, а не 4, и, когда В приводит к неудаче, входная головка возвращается назад. □

Докажем теперь, что язык определяется анализирующей машиной тогда и только тогда, когда ой определяется ОЯНРОВ-программой.

ЛемМа 6.5. Если LL (М) для некоторой анализирующей-машины A1=(Q, 2, Г, 6, начало, Z), то LL{P) .для некотО рой OWOb-npoepaMMU Р.

Доказательство. Пусть P(N, 2, R, ZJ, где N = ru {X} и X - новый символ. Определим R:

(1) Для X правила нет.

(2)-Если б (начало, а, Z)(q, е), io для Z будет правило Z->а, если = успех, и правило Zf, если 9 = неудача. (3) Для других Zr зададим У, У и У так:

(а) если б (начало, е, Z) - (начало, YZ}, положим УУ*

(б) если б (9, е, Z) = (начало, К), положим YY, если q = успех, и У Y, если q = неудача,

(в) если К- не определен в (а) и (б), положим У==Х,

- Тогда для Z введем правило Z-YlY, К3].

Покажем, что для каждого Z G Г

(6.1.3)

Z="{wix,s) тогда и только тогда, когда

(начало, \wx, (Z, 0))f-(успех, w\x,e)

(6.1.4)

Докажем оба утверждения одновременно индукцией по числу шагов вывода программы Р или вычисления машины М-.

Необходимость- Базисы для (6.1.3) и (6.1.4) получаются ие-посредственно из определения отношения -•

Чтобы доказать шаг индукции для- (6.1.3), допустим, что Z="{w\x, s) и утверждения (6.1.3) й (6.1.4) верны для меньших значений п. Так как мы взяли п> 1, то для Z есть правило

Случай J: wWiW, У:" (wjwx, s) и У"(и)\х, s). Тогда п, и Пд меньше п и по предположению индукции

(6.1.5) (начало, twx, (Y, 0)) -(успех, f wx, е)

(6.1.6) (начало, f wx, (Г. 0)) Ь"*"-(успех, t х, е) Заметим, что если слева от входной головки машины М вставить какую-нибудь цепочку, в частности ш, то М выполнит те же действия. Поэтому из (6.1.6) получаем

(6.1.7) (начало, f wx, (К, 0)) + (успех, wt х,е)

Этот вывод требует, правда, доказательства, но мы.оставим

его в качестве упражнения.

Иа определения R мы знаем, что б (начало,, Z) = (начало, KjZ) и 6 (успех, Z) (начало, У). Поэтому

(6.1.8) (начало, f wx, (Z, 0)) - (начало, f wx, {У, 0) (Z, D)) -

(6.1.9) (успех, Wi f йУдХ, (Z, 0)) I- (начало, f wx, (Kj, 0)) Объединяя (6.1.9), (6.1.5), (6.1.8) и (6.1.7), получаем нужное

утверждение:

(начало, \ wx, (Z, 0)) \-- (успех, wjx, е) Случай 2: Y"i{\ WX, f) и =ф"> (ш . х, s). Доказательство аналогично доказательству в случае 1, и мы оставляем его читателю.

Теперь проведем индукцию для (6.1.4). Пусть Z:=" (\ w, f).

Случай I: =Ф"(i f ш., s) и У"{\ w, f), где WyWw. Тогда п, П2<п и из (6.1.3) и (6.1.4) получаем (6.1.10) -(начало, \w, (К, 0)) (успех, \w,e) {6ЛМ) (начало, f w,(y, 0))- (неудача, f w, е) Если в (6.1.11) слева от f вставить w, будет (6.1.12) (начало, Wj f w, (Y, 0)) (неудача, f WjW, e)

7=:"(iw f) тогда и только тогда, когда





0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 [88] 89 90 91 92 93 94 95 96 97 98 99 100 101

0.0036