Построение программы грамматического разбора для заданного синтаксиса.

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

Для простоты мы будем считать, что предложение, которое нужно анализировать, представлено входным файлом input и что терминальные символы – отдельные значения типа char. Пусть символьная переменная char ch всегда содержит очередной читаемый символ. Тогда переход к следующему символу выражается оператором: ch = fgetc(input); Следует отметить, что функция char fgetc(FILE *fp)является стандартной функцией языка Си для чтения символа из файла и для ее использования необходимо в начале программы подключить соответствующий заголовочный файл директивой #include <stdio.h>Основная программа будет остоять из оператора чтения первого символа, за которым следует ператор активации основной цели грамматического разбора. Отдельные процедуры, соответствующие целям грамматического разбора или графам, получаются по следующим правилам. Пусть оператор, полученный с помощью преобразования графа S, обозначается через T (S).

Правила преобразования графа в программу:

В1. Свести систему графов к как можно меньшему числу отдельных графов с помощью соответствующих подстановок.

В2. Преобразовать каждый граф в описание процедуры в соответствии с приведенными ниже правилами В3-В7.

В3. Последовательность элементов

переводится в составной оператор

{T(S1);T(S2);...;T(Sn)}

В4. Выбор элементов

переводится в условный оператор

if(belongsTo(ch, L1)) T(S1);else if(belongsTo(ch, L2)) T(S2);else...if(belongsTo(ch, Ln)) T(Sn);else error();

где Li означает множество начальных символов конструкции Si (Li = first(Si)), а функция belongsTo(ch, Li) возвращает истинное значение, если символ ch принадлежит соответствующему множеству начальных символов Li и ложное значение в противном случае.

В5. Цикл вида

переводится в оператор

while(belongsTo(ch, L)) T(S);

где T(S) есть отображение S в соответствии с правилами В3-В7, а L есть множество L = first(S).

В6. Элемента графа, обозначающий другой граф A

переводится в оператор обращения к функции A().

В7. Элемент графа, обозначающий терминальный символ

переводится в оператор

if(ch == ’x’) ch = fgetc(input);else error();

где error() – функция, к которой обращаются при появлении неправильной конструкции.

Дополнительные правила:

if(ch == 'x1')

{ch = fgetc(input);T(S1);}else if(ch == 'x2') {ch = fgetc(input);T(S2);}else...if(ch = 'xn'){ch = fgetc(input);T(Sn);}else error();

while(ch == 'x')

{ch = fgetc(input); T(S);}