Мартыненко Б.К. Синтаксически управляемая обработка данных. Изд. 2-е, дополн
Подождите немного. Документ загружается.
151
Грамматика CALC. Последовательные эквивалентные версии регулярных
выражений в правых частях правил будем разделять знаком '='. Начнем
преобразования с правила (2), поскольку в нем имеются две леворекурсивные
альтернативы: (2.2) и (2.3). Итак, имеем:
EXPRESSION = TERM ;
EXPRESSION , Push Priority 1 Plus , '+' ,TERM;
EXPRESSION , Push Priority 1 Minus , '–' ,TERM
= TERM, ((Push Priority 1 Plus , '+' ;
Push Priority 1 Minus , '–' ) , TERM)
*
= TERM # (Push Priority 1 Plus , '+' ;
Push Priority 1 Minus , '–' )
= TERM # (Push Priority 1 Operation , ( '+' ; '–' )).
Здесь на последнем шаге преобразований вместо двух различных семантик
Push Priority 1 Plus и Push Priority 1 Minus, каждая из которых специализирована
на обработку соответствующей бинарной операции '+' или '−', введена новая
унифицированная семантика Push Priority 1 Operation, которая обрабатывает
любую из этих двух бинарных операций. Однако платой за такую унификацию
является явная зависимость реализации этой новой семантики от текущего
входного символа ('+' или '−').
Другими словами, если в исходной версии грамматики в зависимости от
текущего входного символа было запланировано выполнение соответствующей
семантики, предназначенной для обработки именно этого символа, то в новой
версии в обоих случаях выполняется одна и та же семантика, которая, однако,
вынуждена сама анализировать (повторно) текущий входной символ.
Новая семантика имеет следующую реализацию:
procedure PushPriority1Operation; { Обработка бинарного '+' или '–' }
begin Unload(1); { Разгружает из магазина и выполняет операции
приоритета 1 и выше}
Inc ( OperationStackTop); { Помещает в магазин текущую операцию на входе}
with OperationStack [ OperationStackTop ] do
begin case CurrentSymbol of
'+' : Operation := Plus;
'–' : Operation := Minus
end;
Priority := 1
end
end;
Предполагается, что CurrentSymbol — вспомогательная функция, выдающая
текущий входной символ.
Вполне аналогичные преобразования правила (3) дают следующий
результат:
TERM : FACTOR # (Push Priority 2 Operation , ( '
*
' ; '/' )) .
152
Новая семантика Push Priority2 Operation имеет следующую реализацию:
procedure PushPriority2Operation; { Обработка бинарного '
*
'
или '/' }
begin
Unload ( 2 ); { Разгружает из магазина и выполняет операции приоритета 2 и выше}
Inc ( OperationStackTop ); { Помещает в магазин текущую операцию на входе}
with OperationStack [ OperationStackTop ] do
begin
case CurrentSymbol of
'
*
' : Operation := Mult;
'/' : Operation := Division
end; Priority := 2
end
end;
Подставляя в новое правило для нетерминала EXPRESSION только что
полученное выражение для нетерминала TERM и вводя вспомогательное
понятие DYADIC OPERATION при помощи правила
DYADIC OPERATION : Push Priority 1 Operation, ( '+' ; '−' ) ;
Push Priority 2 Operation, ( '
*
' ; '/' ) .
получаем следующее правило для нетерминала EXPRESSION:
EXPRESSION : FACTOR # DYADIC OPERATION .
Обработку бинарных операций разного старшинства в правиле для
вспомогательного понятия DYADIC OPERATION также можно
унифицировать при помощи новой семантики:
procedure PushDyadicOperation; { Обработка бинарных операций}
var Prio : TPrio; CS : Char;
begin
CS := CurrentSymbol;
case CS of
'+', '–' : Prio := 1;
'
*
' , '/' : Prio := 2
end;
Unload (Prio); Inc(OperationStackTop);
with OperationStack [ OperationStackTop ] do
begin
case CS of
'+' : Operation := Plus;
'–' : Operation := Minus;
'
*
' : Operation := Mult;
'/ ' : Operation := Division
end; Priority := Prio
end
end;
И тогда окончательно получаем:
DYADIC OPERATION : Push Dyadic Operation, ( '+' ; '–' ; '
*
' ; '/') .
153
В свою очередь, правило (4) для нетерминала FACTOR можно преобразо-
вать следующим образом:
FACTOR = NUMBER, Push Operand;
Push Open Par,
'(', EXPRESSION , Unload And Discard Open Par, ')';
Push Monadic Plus , '+' , FACTOR ;
Push Monadic Minus , '–' , FACTOR
= ( Push Monadic Plus , '+' ; Push Monadic Minus , '–' )
*
,
( NUMBER , Push Operand ;
Push Open Par,
'(', EXPRESSION , Unload And Discard Open Par, ')' )
= ( MONADIC OPERATION )
*
, OPERAND.
Здесь введены вспомогательные понятия: OPERAND и MONADIC
OPERATION при помощи следующих правил:
MONADIC OPERATION : Push Monadic Operation , ( '+' ; '–' ) .
OPERAND : NUMBER , Push Operand ;
Push Open Par,
'(', EXPRESSION , Unload And Discard Open Par, ')'.
Новая унифицированная семантика обработки унарных операций Push
Monadic Operation имеет следующую реализацию:
procedure PushMonadicOperation; { Помещает унарную операцию
в магазин операций}
begin Inc ( OperationStackTop );
with OperationStack[OperationStackTop ] do
begin
case CurrentSymbol of
'+' : Operation := MonadicPlus;
'–' : Operation := MonadicMinus
end;
Priority := 3
end
end;
Подставляя в правило для нетерминала EXPRESSION вместо нетерминала
FACTOR только что полученное выражение, получаем следующее правило:
EXPRESSION : ((MONADIC OPERATION)
*
, OPERAND) # DYADIC OPERATION .
Обратимся теперь к группе правил, определяющих числа:
NUMBER = INTEGER NUMBER , Set Integer Number ;
REAL NUMBER , Set Real Number
= INTEGER NUMBER , Set Integer Number ;
( FRACTION , Init Real with Fraction ;
154
FRACTION , Init Real with Fraction ,
EXPONENT PART , Append Exponent Part ;
INTEGER NUMBER , Init Real with Integer ,
EXPONENT PART, Append Exponent Part ) , SetRealNumber
= INTEGER NUMBER , Set Integer Number ;
(FRACTION, Init Real with Fraction ,
[ EXPONENT PART, Append Exponent Part ];
INTEGER NUMBER , Init Real with Integer ,
EXPONENT PART , Append Exponent Part ) , SetRealNumber
= INTEGER NUMBER ,
( Set Integer Number ;
Init Real with Integer, EXPONENT PART ,
Append Exponent Part, Set Real Number ) ;
FRACTION, Init Real with Fraction ,
[ EXPONENT PART , Append Exponent Part ] , SetRealNumber
= INTEGER NUMBER ,
(Set Integer Number ;
(Init Real with Integer, EXPONENT PART,
Append Exponent Part ;
INTEGER NUMBER, InitFraction ,
FRACTIONAL PART , AppendFractionalPart ,
Init Real with Fraction, [ EXPONENT PART ,
Append Exponent Part ] ) , SetRealNumber )
= INTEGER NUMBER,
(Set Integer Number ;
(Init Real with Integer, EXPONENT PART , Append Exponent Part ;
InitFraction, FRACTIONAL PART , AppendFractionalPart ,
Init Real with Fraction , [ EXPONENT PART ,
Append Exponent Part ] ) , SetRealNumber ) .
На этом шаге преобразований становится ясно, что если бы семантики были
ориентированы непосредственно на сборку вещественного числа (т.е. элемента
операционной среды Number), а не промежуточных значений (RealNumber,
IntegerNumber, Fraction), то выражение для понятия NUMBER можно было бы
значительно упростить. Действительно, последнее выражение для понятия
NUMBER с учетом переориентации семантик эквивалентно следующему:
NUMBER = INTEGER NUMBER ,
( Init Number with Integer ;
Init Number with Integer , EXPONENT PART ,
Append Exponent Part ;
Init Number with Integer , FRACTIONAL PART ,
AppendFractionalPart ,
[ EXPONENT PART , Append Exponent Part ] )
= INTEGER NUMBER , Init Number with Integer,
[ EXPONENT PART , Append Exponent Part ;
FRACTIONAL PART , AppendFractionalPart,
[ EXPONENT PART , Append Exponent Part]]
= INTEGER NUMBER , Init Number with Integer ,
[ FRACTIONAL PART , AppendFractionalPart ] ,
[ EXPONENT PART , Append Exponent Part ] .
155
Окончательно получаем правило
NUMBER : INTEGER NUMBER , Init Number with Integer ,
[ FRACTIONAL PART , AppendFractionalPart ] ,
[ EXPONENT PART , Append Exponent Part ] .
Семантические символы, используемые в нем, имеют следующую интер-
претацию:
procedure Init Number with Integer ;
begin Number := IntegerNumber end ;
procedure AppendFractionalPart ;
begin Number := Number + FractionalPart end;
procedure AppendExponentPart;
begin Number := Number
*
ExponentPart end;
Преобразуем теперь правило для INTEGER NUMBER:
INTEGER NUMBER = DIGIT, Init Integer Number;
= INTEGER NUMBER , DIGIT , Append Digit
= DIGIT , Init Integer Number, ( DIGIT , Append Digit )
*
= Init Integer , ( DIGIT , Append Digit )
+
= Init Integer , ( Set Digit , 'd', Append Digit )
+
.
В результате получаем правило
INTEGER NUMBER : Init Integer , ( Set Digit, 'd', Append Digit )
+.
Здесь
новые семантики Init Integer и Set Digit имеют следующую реализацию:
procedure InitInteger;
begin IntegerNumber := 0; DigitsNmb := 0 end;
procedure SetDigit;
begin Digit := Ord ( CurrentSymbol) – Ord ('0') end;
Правило для
FRACTIONAL PART не нуждается в преобразованиях.
Остается преобразовать лишь правило для EXPONENT PART:
EXPONENT PART = 'E' , EXPONENT , Set Exponent Part
= 'E' , ( INTEGER NUMBER , Set UnsignedExponent ;
SIGN, INTEGER NUMBER, Set Signed Exponent ) ,
Set Exponent Part
= 'E' , [ SIGN ] , INTEGER NUMBER,
Set Exponent , Set Exponent Part
= 'E' , [ Set Positive, '+' ; Set Negative , '–' ] ,
INTEGER NUMBER , Set Exponent ,
Set Exponent Part
= 'E' , Set Sign , ( [ '+' ] ; '–' ) , INTEGER NUMBER,
Set Exponent , Set Exponent Part .
Заметим, что при обработке порядка можно обойтись без переменной
ExponentPart и обслуживающей ее семантики SetExponentPart, если выражение
для нее из этой семантики подставить в последнее определение семантики
AppendExponentPart.
156
Тогда получим:
EXPONENT PART : 'E' , Set Sign , ( [ '+' ]; '–' ) , INTEGER NUMBER , SetExponent .
в предположении, что в правиле для понятия NUMBER используется
следующая интерпретация семантического символа Append Exponent Part:
procedure AppendExponentPart ;
begin
if Exponent >= 0
then Number := Number
*
Power (10, Exponent )
else Number := Number
/
Power (10, – Exponent )
end;
Семантики же Set Sign и Set Exponent имеют следующую реализацию:
procedure SetSign;
begin if CurrentSymbol = '–' then Sign := –1 else Sign := +1 end;
procedure SetExponent; begin Exponent := IntegerNumber
*
Sign end;
Заметим, что из правой части правила для нетерминала NUMBER
посредством подстановок можно исключить нетерминалы INTEGER
NUMBER, FRACTIONAL PART, EXPONENT PART, как и сам нетерминал
NUMBER исключить из правой части правила, определяющего нетерминал
OPERAND, а OPERAND, в свою очередь, — из правой части правила для
конструкции EXPRESSION. Однако эти подстановки можно не производить
вручную
110
. Они будут выполнены системой SYNTAX, если перевести эти
символы из словаря нетерминалов в словарь вспомогательных понятий,
сохраняя для них полученные правила.
Окончательная версия грамматики калькулятора, пригодная для построения
процессора, реализующего интерпретацию арифметических выражений,
приведена в разд.1.3. Она отличается от грамматики, полученной в данном
разделе, лишь тем, что в ней слегка сокращены семантические символы путем
заключения части обозначений в скобки комментариев '{' и '}', и вместо
семантического символа Init Number with Integer используется символ Set
Integer Part. Кроме того, в реализацию семантики Set Digit внесены небольшие
усовершенствования.
6.3. ГЕНЕРАЦИЯ
ДИАГНОСТИЧЕСКИХ СООБЩЕНИЙ ОБ ОШИБКАХ
Использование вспомогательных понятий, кроме упомянутой автоматизации
подстановок, способствует сохранению информации о первоначальной
синтаксической структуре входного языка. Это позволяет генерировать
диагностические сообщения об ошибках в терминах исходной структуры,
более понятных пользователям программы синтаксически управляемой
обработки данных, чем терминология рабочей грамматики.
110
Их и не следует производить вручную, так как в этом случае будет потеряна структурная
информация об исчезающих в результате этих подстановок конструкциях, а она могла бы
использоваться в диагностических сообщениях об ошибках на входе. При автоматических
подстановках эта информация сохраняется. Этот вопрос подробно обсуждается в разд. 6.3.
157
В самом деле, основной целью эквивалентных преобразований грамматики
является ее максимальная регуляризация, фактически сводящаяся к
исключению из грамматики как можно большего числа нетерминалов. Но
именно нетерминалы несут всю структурную информацию о входном языке.
Исключая нетерминалы, мы теряем возможность формулировать диагности-
ческие сообщения об ошибках в терминах первоначальной структуры входного
языка. Например, из грамматики CALC могли бы быть исключены все
нетерминалы, кроме двух: PROGRAM и EXPRESSION. Однако сохранение в
качестве вспомогательных понятий символов NUMBER (ЧИСЛО), INTEGER
NUMBER (ЦЕЛОЕ), FRACTIONAL PART (ДРОБНАЯ ЧАСТЬ), EXPONENT
PART (ПОРЯДОК), DIGIT (ЦИФРА), MONADIC OPERATION (УНАРНАЯ
ОПЕРАЦИЯ), DYADIC OPERATION (БИНАРНАЯ ОПЕРАЦИЯ) и OPERAND
(ОПЕРАНД) с соответствующими синонимами (терминами, указанными в
скобках) обеспечивает достаточный термино-логический базис для формиро-
вания диагностических сообщений об ошибках. Это достигается тем, что при
построении управляющей граф-схемы производятся своего рода макро-
подстановки графов, представляющих правила для вспомогательных понятий
вместо их использующих вхождений. При этом такие вставки маркируются
именами соответствующих вспомогательных понятий. По маркам однозначно
восстанавливается первоначальная синтакси-ческая структура конструкций,
используемая в диагностических сообщениях
111
.
В том, что подбор синонимов вспомогательных понятий грамматики CALC
действительно удачен, можно убедиться, если сопоставить приводимые далее
тексты диагностических сообщений, сгенерированных системой SYNTAX с
управляющей таблицей калькулятора из разд.1.5.
Диагностические сообщения CALC.
В состоянии 1:
В конструкции ПРОГРАММА ожидается ВЫРАЖЕНИЕ
В состоянии 2:
В конструкции ОПЕРАНД после компоненты '('
ожидается ВЫРАЖЕНИЕ
В состоянии 3:
В конструкции ВЫРАЖЕНИЕ после компоненты УНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 4:
В конструкции ВЫРАЖЕНИЕ после компоненты УНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 5:
В конструкции ВЫРАЖЕНИЕ после компоненты ОПЕРАНД
ожидается БИНАРНАЯ ОПЕРАЦИЯ
В конструкции ЦЕЛОЕ после компоненты ЦИФРА ожидается ЦИФРА
В конструкции ЧИСЛО после компоненты ЦЕЛОЕ
ожидается ДРОБНАЯ ЧАСТЬ или ПОРЯДОК
111
Разумеется, леворекурсивная структура, исключаемая посредством ее замены
итеративной, не поддается восстановлению.
158
В состоянии 6:
В конструкции ДРОБНАЯ ЧАСТЬ после компоненты '.'
ожидается ЦЕЛОЕ
В состоянии 7:
В конструкции ПОРЯДОК после компоненты 'E'
ожидается '+' или ЦЕЛОЕ или '–'
В состоянии 8:
В конструкции ВЫРАЖЕНИЕ после компоненты БИНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 9:
В конструкции ВЫРАЖЕНИЕ после компоненты БИНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 10:
В конструкции ВЫРАЖЕНИЕ после компоненты БИНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 11:
В конструкции ВЫРАЖЕНИЕ после компоненты БИНАРНАЯ ОПЕРАЦИЯ
ожидается УНАРНАЯ ОПЕРАЦИЯ или ОПЕРАНД
В состоянии 12:
В конструкции ВЫРАЖЕНИЕ после компоненты ОПЕРАНД
ожидается БИНАРНАЯ ОПЕРАЦИЯ
В конструкции ЦЕЛОЕ после компоненты ЦИФРА
ожидается ЦИФРА
В конструкции ЧИСЛО после компоненты ДРОБНАЯ ЧАСТЬ
ожидается ПОРЯДОК
В состоянии 13:
В конструкции ПОРЯДОК после компоненты '+'
ожидается ЦЕЛОЕ
В состоянии 14:
В конструкции ПОРЯДОК после компоненты '–'
ожидается ЦЕЛОЕ
В состоянии 15:
В конструкции ВЫРАЖЕНИЕ после компоненты ОПЕРАНД
ожидается БИНАРНАЯ ОПЕРАЦИЯ
В конструкции ЦЕЛОЕ после компоненты ЦИФРА ожидается ЦИФРА
В состоянии 16:
В конструкции ПРОГРАММА после компоненты ВЫРАЖЕНИЕ
ожидается 'EOF'
В состоянии 17:
В конструкции ОПЕРАНД после компоненты ВЫРАЖЕНИЕ ожидается ')'
В состоянии 18: {Никаких диагностик}
В состоянии 19:
В конструкции ВЫРАЖЕНИЕ после компоненты ОПЕРАНД
ожидается БИНАРНАЯ ОПЕРАЦИЯ
159
Диагностические сообщения соотнесены с состояниями, в которых
обнаруживаются ошибки
112
. Заметим, что для состояния 18, являющегося
конечным, никакой диагностики не указано. Но это не означает, что всегда так:
просто в данной конкретной ситуации для конечного состояния не существует
никакой диагностической информации.
6.4. ИСПОЛЬЗОВАНИЕ РЕЗОЛЬВЕРОВ
В ТРАНСЛЯЦИОННЫХ ГРАММАТИКАХ
До сих пор рассматривались примеры трансляционных грамматик, в
которых резольверы не использовались. Но часто бывает необходимо
определять трансляцию в зависимости от контекста. Такая ситуация возникает,
например, при обработке описателей в языке программирования Алгол 68.
Описатели входят в состав некоторых конструкций и используются для
спецификации видов. При этом одни конструкции используют фактические
описатели (например, описания переменных, генераторы), другие —
виртуальные (например, описатели имен), а третьи — формальные описатели
(например, описания тождеств). Различие в описателях разного типа
текстуально заметным образом сказывается лишь в описателях массивов. Во-
первых, в фактических описателях массивов требуется указывать строгие
границы индексов, в качестве которых можно использовать любые основы
целого вида. Во-вторых, символ flex может быть первым символом лишь в
фактических и виртуальных описателях. Например, в качестве фактических
описателей массивов могли бы использоваться описатели [5,10]int или
flex [1:0]char; как виртуальные: [,]int и flex []char; в роли формальных:
[,]int или []char. С другой стороны, описатель может входить в состав
другого описателя и при этом его тип, в общем случае, зависит от типа
описателя, его объемлющего. Общие правила этой зависимости таковы:
• Описатели видов полей структуры и элементов массива имеют тот же
тип, что и сам описатель структуры или массива.
• В описателе имени за символом ref всегда следует виртуальный
описатель.
• Описатели параметров процедуры и ее результата, а также описатели
объединенных видов — всегда формальные.
Например, локальный генератор
loc [5]struct ([2][4,4]int
a, ref flex []char b, proc []real c)
имеет следующий состав описателей:
112
Строго говоря, ошибки обнаруживаются только в неподавляемых состояниях. Но
подавляемые состояния, проходимые при процессировании, запоминаются в специальном
магазине. В момент обнаружения ошибки выдаются диагностические сообщения,
соотнесенные с состоянием, в котором эта ошибка обнаружена, а также с подавляемыми
состояниями из магазина.
160
фактические: [5]struct([2][4,4]int a, ref flex[]char b, proc[]real c)
struct([2][4,4]int a, ref flex[]char b, proc[]real c)
[2][4,4]int
[4,4]int
int
ref flex[]char
виртуальные : flex[]char
char
фактический: proc[]real
формальные: []real
real
Как видно из приведенной далее грамматики Gener, описывающей
генераторы Алгола 68, структура описателей рекурсивна. Поэтому для
запоминания типа текущего описателя на время анализа составляющего
подописателя потребуется использование магазина с тем, чтобы после
завершения разбора этого подописателя можно было восстановить тип
текущего описателя, извлекая его из магазина.
Таким образом, при синтаксическом анализе только что приведенного
генератора после того, как просканирован символ loc, должен быть установлен
фактический тип ожидаемого далее описателя. Затем при получении символа
ref текущий тип описателя (фактический) должен быть помещен в магазин, а в
качестве нового текущего типа установлен виртуальный.
После завершения анализа описателя поля ‘b’ из магазина извлекается
значение фактический, которое становится текущим типом до момента
получения символа proc, с которого начинается описатель вида поля ‘c’
структуры. С этого момента текущим типом становится формальный, а
прежний
(фактический) попадает в магазин. После завершения анализа
описателя вида поля ‘
c’ из магазина извлекается значение фактический,
которое далее используется в качестве текущего типа. Эти изменения текущего
типа описателей обеспечиваются семантиками Set Actual, Set Formal, Set
Virtual, а также Init и Reset.
С другой стороны, текущий тип описателя должен тестироваться при
поступлении символа flex — он должен быть фактическим или виртуальным, и
при получении основы в качестве строгой границы — он должен быть
фактическим. Именно с этой целью в соответствующих позициях правил
грамматики, определяющих понятия ROWS OF MODE DECLARATOR и
ROWER, используются резольверы Is VirAct и Is Actual.
Приведем пример трансляционной грамматики, определяющей генераторы
Алгола 68, с тем упрощением, что границы индексов будут представлены
основами, в качестве которых могут использоваться лишь целые числа.
Применяемая в ней лексика определяется грамматикой GenerLex. Она будет
описана в следующей главе.