Теория языков программирования

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

Государственное образовательное  учреждение высшего профессионального  образования

«САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ  
АЭРОКОСМИЧЕСКОГО ПРИБОРОСТРОЕНИЯ»

43 КАФЕДРА

КУРСОВАЯ РАБОТА (ПРОЕКТ)  
ЗАЩИЩЕНА С ОЦЕНКОЙ

РУКОВОДИТЕЛЬ

Доцент, к.т.н.				Т.М. Максимова
должность, уч. степень, звание		подпись, дата		инициалы, фамилия

 

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА  К КУРСОВОМУ ПРОЕКТУ

РАЗРАБОТКА СИСТЕМЫ ПРОГРАММИРОВАНИЯ ДЛЯ ОБРАБОТКИ ДАННЫХ СТРОКОВОГО ТИПА

по дисциплине: ТЕОРИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ

РАБОТУ ВЫПОЛНИЛ(А)

СТУДЕНТ(КА) ГР.	Z6431				Ю.В. Зинина
			подпись, дата		инициалы, фамилия

 

 

 

Санкт-Петербург 
2011

Содержание

 

 

1. Введение

В качестве вводной части к курсовому  проекту рассмотрим теоретические  аспекты лексического и синтаксического  анализов.

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

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

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

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

 

2. Постановка задачи

Разработать программный продукт для обработки данных строкового типа.

В разработку программного продукта входят:

• построение сканера текстов с использованием утилиты flex;
• построение синтаксического анализатора с использованием утилиты bison.

 

Система программирования должна печатать таблицу сопоставления DN (Directory Numbers) именам пользователя (NAME). В качестве обрабатываемого файла система должна принимает файлы соответствующие указанному примеру.

Пример обрабатываемого файла:

DN   1002

     CPND

       NAME BRIAN WALSH

       XPLN 27

       DISPLAY_FMT FIRST,LAST

     VMB

       VMB_COS 4

       SECOND_DN

       THIRD_DN

       VMB_STATE CONFIGURED

TYPE SL1

TN   004 0 00 02 KEY 00 H MARP  DES BRIAN      1 JUN 2001

     (2008)

 

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

 

DN      First name      Last name

=================================

 

1002    BRIAN           WALSH

--------------------------------------------------------

 

3. Грамматика языка программирования обработки строк

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

Файл включает в себя 4 секции: Определения, Настройки bison, Правила и Пользовательский код (не обязательная секция).  Для разделения секций используется строка с символами %%

Описание используемого  синтаксического анализатора:

%{

#include <stdlib.h>

#include <stdio.h>

int yylex();

void yyerror(char const *msg);

%}

 

%union

{

char* string; 

}

 

%token <string> AP_DN_KW AP_NUMBER AP_CPND_KW AP_NAME_KW AP_XPLN_KW AP_DISPLAYFMT_KW AP_FIRSTLAST_KW AP_VMB_KW AP_VMBCOS_KW AP_SECONDDN_KW AP_THIRDDN_KW AP_VMBSTATE_KW AP_CONFIGURED_KW AP_TYPE_KW AP_SL AP_TN_KW AP_TN AP_KEY AP_KEY_KW AP_H_KW AP_MARP_KW AP_DES_KW AP_NAME AP_DATE AP_YEAR

 

%type <string> list record userinfo dopinfo type summary

 

%%

list  : record | list record;

record  : userinfo dopinfo type summary;   

userinfo  : AP_DN_KW AP_NUMBER AP_CPND_KW AP_NAME_KW AP_NAME AP_NAME AP_XPLN_KW AP_NUMBER AP_DISPLAYFMT_KW AP_FIRSTLAST_KW

{    

printf("%s\t", $2);

printf("%s\t", $5);

printf("\t%s", $6);

printf("\n---------------------------------");

printf("\n");

};

dopinfo  : AP_VMB_KW AP_VMBCOS_KW AP_NUMBER AP_SECONDDN_KW AP_THIRDDN_KW AP_VMBSTATE_KW AP_CONFIGURED_KW

{};

type  : AP_TYPE_KW

{};

summary  : AP_TN_KW AP_TN AP_KEY_KW AP_KEY AP_H_KW AP_MARP_KW AP_DES_KW AP_DATE AP_YEAR

{};

%%  
3. Описание детерминированной автоматной модели синтаксического анализатора

 

Основная задача синтаксического анализа - разбор структуры программы. Как правило, под структурой понимается дерево, соответствующее разбору в контекстно-свободной грамматике языка. В настоящее время чаще всего используется либо LL(1)–анализ (и его вариант – рекурсивный спуск), либо LR(1)–анализ и его варианты (LR(0), SLR(1), LALR(1) и др.). Рекурсивный спуск чаще используется при ручном программировании синтаксического анализатора, LR(1) - при использовании систем автоматизации построения синтаксических анализаторов. Результатом синтаксического анализа является синтаксическое дерево со ссылками на таблицу имен. В процессе синтаксического анализа также обнаруживаются ошибки, связанные со структурой программы.

Синтаксический анализатор, генерируемый программой Bison строится на основе LR(1)-грамматики

Алгоритм синтаксического анализа на основе LR(k)-грамматики относится к классу алгоритмов восходящего разбора.

Строкам управляющей  таблицы  М (LR-таблица разбора)  ставятся в соответствие состояния, в которых может находиться анализатор, столбцам – элементы множества {VÈTÈ$}. Каждая запись рабочего стека представляет собой пару: (символ, номер состояния). Перед началом  работы  алгоритма в рабочий стек заносится пара (Λ,1), где 1 – символ начального состояния анализатора. Возможные значения элементов таблицы и их интерпретация алгоритмом разбора приведены в таблице.

Таблица возможных значений элементов  управляющей таблицы

Значение элемента управляющей  таблицы	Интерпретация алгоритмом разбора
Номер n порождающего правила грамматики	Удаление из рабочего стека  k записей (k - количество символов в правой части правила номер n); имитация считывания в качестве следующего входного символа нетерминала левой части правила номер n; запись n  в выходную ленту
(«сдвиг», номер  j состояния)	Запись текущего входного символа  в выходной стек и в паре с номером j – в рабочий  стек; если этот символ нетерминал, установка указателей  на него в ближайших к нему n  записях выходного стека с пустыми указателями
«допуск»	Входная строка разобрана. Конец работы
«ошибка»	Входная строка ошибочна. Конец работы

 

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

После  разметки грамматики выполняется построение таблицы М  по следующему  алгоритму.

1. Если символ А в правой части правила имеет непосредственно слева от себя метку m, а непосредственно справа от себя – метку j, то M(m,A) = («сдвиг»,j).
2. Если метка j размещается за  последним  символом  правой части правила номер n, то определяется  множество Q символов, которые в какой-либо сентенциальной форме могут следовать за нетерминалом левой части правила номер n, и M(j,q)=n для всех qÎ Q.
3. M(1,<S>)= «допуск», где 1 – символ начального состояния.
4. Оставшиеся незаполненными элементы таблицы  M  получают значение «ошибка».

 

 

 

 

4. Описание структуры системы программирования

Структура системы программирования представлена представляет собой общую  схему взаимодействия файлов проекта.

 

5. Руководство пользователя
1. Перед запуском исполняемого файла программы необходимо убедиться, что в папке с программой присутствует обрабатываемый файл. Обрабатываемый файл должен называться data.txt.
2. Для запуска программы запустите исполняемый файл KP.exe.
3. В случае, если обрабатываемый файл корректен, то после запуска программы на экране отобразиться таблица соответствия DN именам пользователей. См. Приложение 2. Тестовые случаи, Тест 1.

Корректный обрабатываемый файл, должен быть выполнен по следующему примеру:

DN   <DN_Number>

     CPND

       NAME <First_Name> <Last_Name>

       XPLN 27

       DISPLAY_FMT FIRST,LAST

     VMB

       VMB_COS 4

       SECOND_DN

       THIRD_DN

       VMB_STATE CONFIGURED

TYPE SL1

TN   024 0 06 14 KEY 00 H MARP  DES LAM       29 JUN 2000

     (2008)

 

<DN_Number> - номер, который будет выбираться для соответствия с именем пользователя;

<First_Name> и <Last_Name> - Имя и Фамилия пользователя соответственно.

 

4. В случае, если обрабатываемый файл некорректен, программа выдаст сообщение об ошибке. См. Приложение 2. Тестовые случаи, Тест 2.
5. В случае, если обрабатываемый файл отсутствует в директории программы или неправильно поименован, в результате запуска программы отобразиться корректное сообщение об ошибке. См. Приложение 2. Тестовые случаи, Тест 3.

 

 

 

 

6. Заключение

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

 

7. Список использованной литературы
1. Т.М. Максимова – Теория языков программирования и методы трансляции. Методические указания к выполнению лабораторных работ № 1-4, ГОУ ВПО СПбГУАП, СПб, 2007
2. А.В.Бржезовский, Т.М.Максимова, А.А.Янкелевич – Теория языков программирования и методы трансляции. Средства автоматизации построения синтаксических анализаторов. Методические указания к выполнению лабораторных работ № 1-2, ГОУ ВПО СПбГУАП, СПб, 2006
3. Автономно-лингвистические и алгоритмические основы разработки и програмной реализации трансляторов, компиляторов и интерпритаторов, А.Б.Мартемьянов: