Курсовая работа: Конструирование модели лексического и синтаксического анализа

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

1.2 Анализ предметной области

Входящая последовательность - исходный код программы (рис. 1). В коде присутствуют массивы String Char, Int, Float, а так же указатели и ссылки “*”. Программа, работающая по исходному коду, в качестве результата выводит сначала размер массива после выводит массив рандомных чисел от 0 до 10 (рис. 2). В ходе лексического анализа должны быть выделены лексемы каждого класса, в том числе ключевых слов. Также в ходе анализа должны быть обнаружены ошибки в написании лексем, если таковые имеются. Синтаксический анализ на основе грамматики проверит правильность написания с точки зрения синтаксиса.

#include <iostream>

#include <string>

#include <ctime>

using namespace std;

void opF(int* ar, int* gogo) {

*gogo += *ar;

}

int main()

{

srand(time(NULL));

int m = 0;

int arr[5] = { 3,4,2 };

string mas ="awd";

for (int i = 0; i <2; i++)

{

opF(& arr[i], &m);

}

float *m1 = new float[m];

for (int y = 0; y < m; y++) {

m1[y] = rand() % 10;

cout <<"_"<<m1[y];

}

}

2. Конструирование модели лексического анализа

2.1 Лексический анализ

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

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

2.2 Построение конечного автомата

Граф конечного автомата представлен в п. 2.3, рис. 1

Конечный автомат (КА) демонстрирует работу лексического анализатора по считыванию входной последовательности символов. Считывание начинается в состоянии S0 и продолжается по соответствующему пути в зависимости от считанного символа. Входящим символом автомата считается последний считанный символ. При считывании определённого символа (первой буквы ключевого слова, цифры или прочего) автомат из состояния S0 переходит в соответствующее состояние.

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

А = (X, S, F, S0, д), где:

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

- S - конечное непустое множество состояний;

- F - множество выделенных заключительных состояний;

- S0 - начальное состояние;

- д - функция перехода конечного автомата (X*S > S).

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

X: ( 0..9, a..z, A..Z,

операторы - {+, -, *, /, %, =, !, ++,--,+=,-=,*=, << , >>},

сравнения - {>, <,<=,>=,==,!=,||,&&},

пунктуации - {;, (, ), [, ], {, }, “.”, “,”, “})

F: {S1, S2, S301, S305, S100, S101}

S: (S0, S1, S2, S3, S4, S5, S6, S7, S8, S9, S10, S11, S12, S13, S14, S15, S16, S17, S18, S19, S20, S21, S22, S23, S24, S25, S26, S27, S28, S29, S30, S31, S32, S33, S34, S35, S36, S37, S38, S39, S40, S41, S42, S43, S47, S48, S49, S50, S60, S61, S62, S63, S64, S65, S66, S67, S68, S69, S70, S71, S100, S101, S200, S300, S301, S302, S305, S400, S401)

д: функция переходов конечного автомата представлена в таблице (табл. 1):

Таблица 1. Функция д

2.3 Построение регулярной грамматики по конечному автомату

Грамматика - это способ описания, задания языка. Это система правил, описывающая множество последовательностей символов некоего алфавита. Регулярная грамматика (РГ) эквивалентна конечным автоматам, поэтому по конечному автомату можно получить регулярную грамматику. Алгоритм преобразования:

По конечному автомату A = (X, S, F, S0, д) можно построить регулярную грамматику G = < N, T, P, S >, где:

T = X - конечное непустое множество терминальных символов.

N = S - конечное непустое множество нетерминальных символов

S - стартовый символ грамматики;

P - конечное множество правил грамматики - продукции.

Множество правил подстановки Р строится таким образом: каждой команде автомата (Si, a) > Sj ставится в соответствие правило подстановки Si > а Sj, если Sj ? S, либо Si > а , если Sj ? F, где F- заключительное состояние.

Построение регулярной грамматики по описанному конечному автомату:

По приведённому выше конечному автомату была сформирована следующая регулярная грамматика:

G = (N, T, S, P)

T: ( 0..9, a..z, A..Z, +, -, *, /, %, =, !, ++,--,+=,-=,*=, << , >>,>, <,<=,>=,==,!=,||,&&,;, (, ), [, ], {, }, “.”, “,”, “)

N:

S0 - начало считывания лексемы

S3…S99 - посимвольное считывание ключевого слова

S400, S401 - пунктуация

S1 -проверка ключевых слов на правильность написания, добавление их в таблицу

S200 -проверка написания идентификатора и добавление его в таблицу

S300 - начало распознавания лексемы оператора

S300 - начало распознавания лексемы оператора “+,-,=,*,&,/,<,>,!”, добавление лексемы в таблицу

S301 - распознавания лексемы оператора, добавление лексемы в таблицу

“++,--,+=,-=,*=, <=,>=,==,!=,||,&&”

S302 - ошибка в написании оператора

S100 - распознавание лексемы целочисленной константы, запись её в таблицу. Ошибки в написании лексемы

S101 - распознавание лексемы константы с плавающей запятой, запись её в таблицу. Ошибки в написании лексемы

S:S0

P: Множество продукций представлено в таблице (табл. 2).

Таблица 2. Множество продукций

Таблица 3. Совмещенная таблица продукций и переходов

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

3.1 Определение лексического анализатора

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

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

* применение лексического анализатора упрощает работу с текстом исходной программы на этапе синтаксического разбора и сокращает объем обрабатываемой информации;

* для выделения и разбора лексем применяется простая и эффективная техника анализа, в то время как на этапе синтаксического анализа используются достаточно сложные алгоритмы разбора;

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

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

Таким образом, можно выделить следующие основные функции лексического анализатора:

• исключение из текста исходной программы комментариев;

• исключение из текста исходной программы незначащих пробелов, символов-табуляций и перевода строки;

• выделение лексем следующих типов: идентификаторов, строковых, символьных и числовых, констант, ключевых (служебных) слов входного языка, знаков операций и разделителей;

• выявление ошибок в написании лексем, сообщение об ошибках (с указанием позиции и типа ошибки).

3.2 Моделирование работы лексического анализатора

На вход, в текстовую область, подаётся входная последовательность - обрабатываемый код. Анализатор должен удалить из кода все комментарии - как однострочные, так и многострочные. Также анализатор должен исключить из текста программы незначащие пробелы, символы-табуляции и пустые строки (рис. 1). Параллельно с этим производится выделение лексем с последующим распределением по таблицам соответствующих классов.