2.2.4. Тестирование лексического анализатора

Тестирование лексического анализатора заключается в моделировании его работы. Результатом этапа лексического анализа является заполненные вручную таблицы и выходной поток токенов для контрольного примера, представляющего собой программу на входном языке

2.3. Описание этапа синтаксического анализа

На этапе синтаксического анализа выполняется проверка синтаксической корректности исходной программы, представленной в виде потока токенов и совокупности таблиц, и преобразование ее в некоторую внутреннюю форму, удобную в дальнейшем для генерации объектного кода.

Опишем порядок действий, выполняемых при разработке синтаксического анализатора.

2.3.1. Построение кс-грамматики входного языка

Для построения КС-грамматики входного языка необходимо:

1. Заменить металингвистические переменные БНФ обозначениями нетерминальных символов, используя короткие имена;

2. В качестве терминальных символов использовать токены;

3. Металингвистический символ «::=» заменить символом «»;

4. Заменить одну металингвистическую формулу с n альтернативами на n правил грамматики с одинаковым символом в левой части правила вывода;

5. Исключить металингвистические символы [ ] и { }, включив в правила грамматики -правила и рекурсивные правила.

2. Определение класса КС-грамматики входного языка

Построенная КС-грамматика входного языка должна входить в определенный в задании на курсовую работу класс грамматик. Определение класса КС-грамматики рекомендуется выполнять с помощью лабораторного практикума [2]. Если грамматика не принадлежит заданному классу, то необходимо ее преобразовать. Для преобразования можно использовать алгоритмы и рекомендации, приведенные в [3] – [6].

2. Разбиение грамматики на подграмматики

Если преобразование КС-грамматики не приведет к нужному результату, то рекомендуется найти правила грамматики, в которых нарушаются требования, предъявляемые к грамматикам заданного класса, после чего выполнить одно или несколько действий из приведенного списка:

1. Изменить (пополнить) список токенов так, чтобы терминальные символы грамматики, приводящие к конфликту, были разбиты на непересекающиеся подмножества.

2. Выделить из исходной грамматики подграмматики таким образом, чтобы каждая из полученных грамматик принадлежала заданному классу.

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

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

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

1. Совокупности выделенных из грамматики взаимосвязанных правил должна представлять собой КС-грамматику.

2. Основной символ подграмматики становится (специальным) терминальным символом исходной грамматики.

3. Если множества нетерминальных символов подграмматики и модифицированной исходной грамматики не пересекаются, то синтаксический анализ для каждой из них может быть реализован при помощи отдельного процессора с магазинной памятью (ДМП-процессора).

2. Описание промежуточного языка

Тип промежуточного языка, используемого для представления программы после синтаксического анализа, определен в задании на курсовую работу. Описание различных типов промежуточных языков приводится в [1].

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

Фрагмент описания промежуточного языка приводится в табл. 2.4.

Таблица 2.4

Описание тетрады
Синтаксис					Семантика
Коп	Оп1	Оп2	Рез
BRL	Label			Безусловный переход на метку Label
BF	Label	R		Переход на метку Label, если R = False
DEFL	Label			Определение метки Label

2. Неформальное описание перевода

При описании перевода конструкций входного языка в промежуточный язык следует руководствоваться методикой, изложенной в [1]. Рекомендуемая форма описания перевода приведена на рис. 2.3. Для возможности построения ссылок на описание в его заголовке указывается номер первого правила грамматики, описывающего конструкцию. Формы конструкции и тетрады, входящие в ее перевод, нумеруются. Например (j).1.5 – ссылка на тетраду определения метки перевода полной формы условного оператора IF.

( i ) Перевод условного оператора IF

Полная форма

Входная конструкция:

Последовательность тетрад:

IF

<Выражение>

1

Перевод выражения (R – результат)

THEN

2

BF

Lelse

R

<Операторы>

3

Перевод операторов

ELSE

4

BRL

Lend

5

DEFL

Lelse

<Операторы>

6

Перевод операторов

END

7

DEFL

Lend

Сокращенная форма:

Входная конструкция:

Последовательность тетрад:

IF

<Выражение>

1

Перевод выражения (R - результат)

THEN

2

BF

Lend

R

<Операторы>

3

Перевод операторов

END

4

DEFL

Lend

Рис. 2.3

2. Построение транслирующей грамматики

Транслирующая грамматика определяет порядок применения операционных символов (элементов перевода), строящих выходную цепочку.

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

• способ реализации заданного метода синтаксического анализа;

• интерпретация операционных символов (имя процедуры или функции, которую необходимо выполнить).

Построение транслирующей грамматики выполняется в соответствии с методикой, приведенной в [1].

2. Построение атрибутной транслирующей грамматики

При необходимости передачи данных между узлами синтаксического дерева транслирующую грамматику расширяют до атрибутной транслирующей грамматики (АТГ). Методика этого процесса описана в [1]. Рекомендуемая форма представления АТГ приведена на рис. 2.4, описание операционного символа – на рис. 2.5.

(2)	OpIf			IF Exps1, s2 THENn1 {BF}n2, n3, s3 LOp END {DEFL}n4
				n2s1 // местоположение значения выражения
				n3s2 // тип выражения
				s3 NewLabel // генерировать метку перехода
				n1 s3 // запомнить метку в магазине
				n4 n1 // передать метку перехода
Рис. 2.4
Операционный символ {BF}n2, n3, s2
if (n3 == BOOLEAN)
{ Записать на выход тетраду вида
			BF		s2	n2
}
else { Ошибка: неверный тип выражения в операторе IF
}
Рис. 2.5