Главная  Терминология Хоора 

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 102 103 104 105 106 107 108 109 110 111 [ 112 ] 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133

(правило) (выражение) (терм) (фактор)

Заметим, что в порождающих правилах входного языка используются иные метасимволы, чем в БНФ. Это делается по двум причинам:

1. Б (5.12) нужно отличать символы языка от метасимволов.

нужно каким-то образом строить структуру данных, упп-ляющих программой. В этом смысле представление гра^ тик в БНФ оказывается идеальным в качестве исход^ данных для универсальной программы грамматического пя бора. Поэтому следующий раздел посвящен разработке пп граммы, которая читает правила БНФ и по правилам В1-.gt преобразует их во внутреннюю структуру данных, с которо может работать программа грамматического разбора (5 in [5.8].

5.6. ПРЕОБРАЗОВАНИЕ БНФ В СТРУКТУРЫ ДАННЫХ, УПРАВЛЯЮЩИЕ ГРАММАТИЧЕСКИМ РАЗБОРОМ

Транслятор, распознающий порождающие правила БНф и11реобразующий их в какое-то другое представление, как раз служит примером программы, входные данные которой можно рассматривать как предложения, принадлежащие некоторому языку. Действительно, саму БНФ можно считать некоторым языком, имеющим свой собственный синтаксис, который, разумеется, также можно описать с помощью порождающих правил БНФ. Следовательно, его транслятор может служить примером распознавателя, который помимо этого преобразует входные данные, т. е., вообще говоря, является процессором. Поэтому мы будем действовать следующим образом:

Шаг J. Определим синтаксис метаязыка, называемого РБНФ (расщиренной БНФ).

Шаг 2. Построим распознающую программу для РБНФ в соответствии с правилами, приведенными в разд. 5.4.

Шаг 3. Расширив эту программу, превратим ее в транслятор и объединим с таблично-управляемой программой грамматического разбора.

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

;=(сим10л) = (выражение) := (терм){.(терм)} 5 j2)

:=(фактор) { (фактор)}

:= (символ)! [(терм)]



5.6. Преобразование БНФ в структуры данных 341

f, Желательно использовать более привычные символы печатающего устройства, в частности использовать один знак ( = ) вместо (:: = ). Соответствие между обычной БНФ и нащей входной версией Л^казано в табл. 5.1. Кроме того, каждое наше порождающее

Таблица 5.1. Метасимволы и символы языка

БНФ РБНФ

Лравило должно заканчиваться точкой. При использовании этого входного языка для описания синтаксиса примера 5

Sf) мы получаем ....... А^х,{В). В = АС. (5.13) С==[+А]. Чтобы упростить построение транслятора, мы будем считать, что терминальные символы - это отдельные буквы и каждое порождающее правило пишется в отдельной строке. Это позволяет использовать во входном тексте пробелы (чтобы его было удобнее читать), которые транслятор игнорирует. Но тогда оператор read{ch) в правиле В7 нужно заменить вызовом процедуры, которая определяет очередной учитываемый символ. Эта процедура - простейшая разновидность лексического сканера, или просто сканера. Задача сканера - Выделить из входной последовательности обычных символов очередной символ языка*). Это не всегда бывает так легко как в нашем примере, поскольку мы до сих пор предполагали. Что символы языка - это отдельные буквы, а на самом Деле - это особый и на практике редко встречающийся случай.

Наконец, мы постулируем, что в нашем входном языке БНФ нетерминальные символы представляются буквами А - Я, а терминальные символы - буквами / - Z. Это чистая Условность, не связанная ни с какими серьезными причинами. Но она избавляет от необходимости задавать словари терминальных и нетерминальных символов перед списком порождающих правил.

*), Напомним, что символы языка суть множество терминальных и не-fepMHHaflbHHX символов, построенных из обычно вводимых символов системы. - Прим. ред.



Убедившись, что (5.12) удовлетворяет ограничениям 1 ц 9 и действуя строго по правилам В1 - 87, мы получаем п^т грамму 5.2, которая распознает язык, определенный в (5.12)* Заметим, что сканер называется getsym.

На третьем шаге разработки транслятора нужно прочитан-ные порождающие правила БНФ преобразовать в структуру данных, которая может интерпретироваться процедурой грам, матического разбора (5.11). К сожалению, этот этап не под' дается формализации в отличие от этапа, связанного с по-строением программы распознавания. Поэтому мы просто нарисуем структуры, соответствующие каждой конструкции

множители: iTtsymbot) ~

2.erm)

Слагаемым

term

empty

ч *

(factor-l>

(factor-n)

fac-1

fac-1

fac-2

fac-n

Выражения:

(,term-1>

(term-2>

<term-n>

p-*-

term-1

term-2


term-n




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 102 103 104 105 106 107 108 109 110 111 [ 112 ] 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133