РГЗ построение компилятора (стр. 2 )

Q – конечное множество состояний автомата;

V – конечное множество допустимых входных символов;

δ  – функция переходов автомата;

q0 – начальное состояние автомата;

F – непустое множество конечных состояний автомата.

Множество состояний автомата:

Q = {q0, q1, …, q44, q50, q100, q200, q1000}.

Множество допустимых входных символов:

V = {A..Z, a..z,  ( , ) , { , } , ; , : , 0..9}

Множество конечных состояний автомата:

F = { q2001, q100, q 24, q 25, q50, q2002, q2004, q2005, q2003, q2011, q1000}

q2001 – ключевые слова; q100 – идентификаторы; q 24, q 25  – операторы сравнения; q2002 – операторы; q2004 – арифметические операции; q2005 – оператор присваивания =; q2003 – целые числа; q2011 – вещественные числа; q1000 – ошибочное состояние.

Лексический анализатор выделяет следующие классы лексем:

ключевые слова: public, private, protected, published, class, int, char; идентификаторы – последовательность букв латинского алфавита, цифр, начинающаяся с буквы; знаки и разделители: пробел ; : ( ) { }; константы.

В ходе выполнения разбора, автомат каждую лексему представляет в виде дескриптора – пары вида (<тип лексемы>, <указатель>), где тип лексемы – это символьный код класса лексемы, а указатель – номер записи в соответствующей таблице.

В данной работе при выполнении лексического анализа также происходит замена имен всех идентификаторов кодом (key – для ключевых  слов, op – операторы, num – целые числа, ar – арифметические операции, real – вещественные числа, id – для идентификаторов, razd – для знаков и разделителей).

9. Построение синтаксического анализатора

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

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

9.1. Грамматика

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

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

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

Грамматика, моделирующая работу синтаксического анализатора в данной курсовой работе, содержит классы языка Си.

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

Работа с классами языка Си.

Class  <название>
{

private:
{Описанные в этой секции элементы не доступны извне (за пределами класса) ; }
{Здесь находятся поля класса.}
protected:
{Описанные в этой секции элементы доступны только классу и всем его потомкам ;}
public:
{Описанные в этой секции элементы доступны всем ;}
published:
{Описанные в этой секции элементы доступны всем и отображаются в Object Inspector'e ;}
};

9.1.1. Представление грамматики в виде правил КС-грамматики

Грамматика определяется как четверка следующего вида:        G(VN, VT, P, S), где:

VT – множество терминальных символов; VN – множество нетерминальных символов; P – Множество продукций грамматики вида б →в, где б ∈ (VT U VN)+, в ∈ (VT U VN)*; S – стартовый символ грамматики, S ∈ VN.

Алфавиты терминальных и нетерминальных символов грамматики не пересекаются: VT∩VN = Ш. Это значит, что каждый символ в грамматике либо терминальный, либо нетерминальный, т. е. нет символов и терминальных и нетерминальных одновременно. Множество V = VT U VN называют полным алфавитом грамматики G.

Стартовый символ грамматики – это обязательно нетерминальный символ. В данной грамматике это символ S.

VN={ S, A, B, C, D} - множество нетерминальных символов; VT={ { , },  ; , ( , ) , : , private, protected, public, published, class, char,  int, real } - множество терминальных символов;

G({ { , },  ; , ( , ) , : , private, protected, public, published, class, char, int, real}, { S, A, B, C, D}, P, S),

Первоначальная грамматика:

Множество продукций:

P:

S-->K K-->class M {D}; M-->id D-->T | T T | T T T | T T T T T--> private: P | protected: P | public: P | published: P P-->C( ); P-->O; O--> char id; | int id; | real id;

В результате синтаксического анализа в первоначальной грамматике были выявлены ошибки, например: 
продукция
P-->C( );  - конструктор по умолчанию;

P-->O; - операнды.

Конструкторы бывают по умолчанию и с параметрами, и могут включать в себя несколько переменных с разными типами данных, в связи с этим продукция была изменена следующим образом:
P->M ( ) W | M ( O ) W | M ( O O ) W | M ( O O O ) W

P->O | O O | O O O

В результате всех доработок и изменений грамматика выглядит следующим образом:

Множество продукций:

P:

S->class M { D } W D->T | T T | T T T | T T T T T->private Q P | protected Q P | public Q P | published Q P P->M ( ) W | M ( O ) W | M ( O O ) W | M ( O O O ) W P->O | O O | O O O O->char M W | int M W | real M W Q->: W->; M->id

9.1.2. Описание грамматики в форме Бекуса-Наура

Форма Бэкуса—Наура (БНФ) — формальная система описания синтаксиса, в которой одни синтаксические категории последовательно определяются через другие категории.

Запись правил осуществляется построчно – в одной строке одно правило. В первой строке описывается главное понятие языка (аксиома грамматики). Левая часть правила от правой разделяется символами ::=. Металингвистические переменные (нетерминальные символы грамматики) заключаются в угловые скобки <>, основные символы языка (терминальные символы) записываются без скобок.

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

Металингвистическая переменная и основной символ с одинаковыми именами считаются эквивалентными, такие ситуации недопустимы. Для обозначения лямбда-правил (пустых подстановок) необходимо использовать символ &. Альтернативные подстановки для правила  отделяются  друг  от  друга  вертикальной  чертой  |.  Допускается  запись альтернативных вариантов подстановок правила, при этом правила с одинаковыми правыми частями группируются в блок, т. е. должны находиться рядом. При использовании леворекурсивных определений первой альтернативой правила должна описываться альтернатива без рекурсии.

Основное назначение форм Бэкуса состоит в представлении в сжатом и компактном виде строго формальных и однозначных правил написания основных конструкций описываемого языка.

Грамматика представлена в виде четверки следующего вида:

G(VT, VN, P, <СТАРТ>), где

Множество терминальных символов:

VT={ { , },  ;  , : , private, protected, public, published, class, char, int, ansistring, real, string }

Множество нетерминальных символов:

VN={ <СТАРТ>, <КЛАСС>, <НАЗВАНИЕ КЛАССА>, <ОПИСАНИЕ КЛАССА >, <ОБЛАСТЬ ДОСТУПА>, <ОПИСАНИЕ СЕКЦИИ>, <ОПЕРАНДЫ>,<ТИП НАСЛЕДОВАНИЯ>, <КОНСТРУКТОРЫ> }

Исходная грамматика в форме Бекуса-Наура:

G({ { , },  ;  , : , private, protected, public, published, class, char, int, ansistring, real, string },{<СТАРТ>, <КЛАСС>, <НАЗВАНИЕ КЛАССА>, <ОПИСАНИЕ КЛАССА >, <ОБЛАСТЬ ДОСТУПА>, <ОПИСАНИЕ СЕКЦИИ>, <ОПЕРАНДЫ>,<ТИП НАСЛЕДОВАНИЯ>, <КОНСТРУКТОРЫ>}

, P, <СТАРТ>)

Множество продукций:

<СТАРТ>::= class <НАЗВАНИЕ КЛАССА> {<ОПИСАНИЕ КЛАССА >}; <ОПИСАНИЕ КЛАССА > ::=  <ОБЛАСТЬ ДОСТУПА> <ОБЛАСТЬ ДОСТУПА> ::=  private: <ОПИСАНИЕ СЕКЦИИ> | protected: <ОПИСАНИЕ СЕКЦИИ> | public: <ОПИСАНИЕ СЕКЦИИ> | published: <ОПИСАНИЕ СЕКЦИИ> <ОПИСАНИЕ СЕКЦИИ> ::=  <КОНСТРУКТОРЫ> (  ); <ОПИСАНИЕ СЕКЦИИ> ::= <ОПЕРАНДЫ>; <ОПЕРАНДЫ>::= char id; | int id; | real id. <НАЗВАНИЕ КЛАССА>::= id

9.1.3. Описание грамматики на языке синтаксических диаграмм

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

Синтаксические диаграммы КС-языка могут быть построены по соответствующей формальной грамматике по следующему алгоритму:

1) Для каждого нетерминала грамматики строится отдельная диаграмма, обозначенная названием этого нетерминала.

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

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

4) Ветви, соответствующие альтернативным правым частям правил для одного нетерминала, соединяются параллельно и образуют диаграмму для данного нетерминала.