Курсовая работа на тему: Лексический анализатор программ на языке Perl

Заказ 381

Цена полной версии курсовой работы: 900 рублей

 

Оглавление

Введение. 4

1.Анализ технического задания. 5

1.1.Лексический анализ в программировании. 5

1.2.Лексический анализатор. 6

1.3.Описание языка. 7

1.4. Лексемы.. 7

1.4.1. Что такое лексемы.. 7

1.4.2.Типичные классы лексем.. 8

1.4.2.Таблица лексем.. 8

1.5.Регулярные выражения. 14

1.6.Инструменты для создания лексических анализаторов. 18

1.6.1. Генератор лексических анализаторов Lex. 18

1.6.2. Структура Lex-программы.. 19

1.6.3.Способы записи регулярных выражений в Lex-программе. 20

1.6.4.Пример Lex-программы.. 20

  1. Описание исходных данных, порядок лексического анализа. 22

2.1 Исходные данные. 22

Общая схема работы лексического анализатора. 22

Как работают регулярные выражения. 24

Обзор аналогов (систем- аналогов). 24

Обзор методов решения поставленной задачи. 25

Построение расширяемого лексического анализатора, на базе регулярных выражений. 25

Альтернативный способ построения расширяемого лексического анализатора. 27

Работа анализатора по регулярным выражениям в Perl 29

  1. Программная реализация разработанной структуры и алгоритмов. 30

3.1 Проектирование структуры программы и базовых алгоритмов. 30

3.2 Выполнение действий, связанных с лексемами. 31

3.3 Работа с регулярными выражениями. 32

3.4 Генератор лексических анализаторов. 32

3.5 Конечный автомат. 33

3.5 Принцип работы.. 34

3.5 Преобразование регулярного выражения в недетерминированный автомат. 34

4.Руководство программиста. 40

  1. Руководство пользователя. 41
  2. Результататы тестирования. 41

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

Литература. 43

Введение

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

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

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

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

1.Анализ технического задания

1.1.Лексический анализ в программировании

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

В информатике лексический анализ это процесс аналитического разбора входной последовательности символов (например, такой как исходный код на одном из языков программирования) с целью получения на выходе последовательности символов, называемых «токенами» (подобно группировке букв в словах). Группа символов входной последовательности, идентифицируемая на выходе процесса как токен, называется лексемой. В процессе лексического анализа производится распознавание и выделение лексем из входной последовательности символов.

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

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

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

Но есть несколько причин, по которым в состав практически всех компиляторов включают лексический анализ:

  • -применение лексического анализатора сокращает объем информации, обрабатываемой на этапе синтаксического разбора;
  • -некоторые задачи, требующие использования сложных вычислительных методов на этапе синтаксического анализа, могут быть решены более простыми методами на этапе лексического анализа (например, задача различения унарного минуса и бинарной операции вычитания, обозначаемых одним и тем же знаком «–»);
  • -лексический анализатор отделяет сложный по конструкции синтаксический анализатор от работы непосредственно с текстом исходной программы, структура которого может варьироваться в зависимости от архитектуры вычислительной системы, где выполняется компиляция, — при такой конструкции компилятора для перехода на другую вычислительную систему достаточно только перестроить относительно простой лексический анализатор;
  • -в современных системах программирования лексический анализатор может выполнять обработку текста исходной программы параллельно с его подготовкой пользователем — это дает системе программирования принципиально новые возможности, которые позволяют снизить трудоемкость разработки программ (более подробно об этом сказано в главе «Современные системы программирования»).

 

1.2.Лексический анализатор

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

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

Токен — это последовательности символов в лексическом анализе, соответствующий определенной лексеме.

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

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

Токен с типом и соответственно подготовленным значением передаётся на вход синтаксического анализатора.

 

1.3.Описание языка

Для любого компилятора можно выделить три языка:

  1. входной — язык, который анализируется компилятором.
  2. рабочий — язык, на котором написан сам компилятор.
  3. выходной — язык, который появляется в результате работы компилятора.
  4. ……………………….

………………………………..

…………………………………

1.6.3.Способы записи регулярных выражений в Lex-программе

Рассмотрим способы записи регулярных выражений во входном языке Lex’а. Символ из входного алфавита, естественно, представляет регулярное выражение из одного символа. Специальные символы (в том числе +-*?()[]{}|/\^$.<>) записываются после префикса \. Символы и цепочки можно брать в кавычки, например допустимы следующие три способа кодирования символа а: а, «а» и .

Имеется возможность задания класса символов:

[0-9] или [0123456789] – любая цифра

[A-Za-z] – любая буква

[^0-7] – любая литера, кроме цифр от 0 до 7

. – любая литера, кроме \n

Грамматика для записи регулярных выражений (в порядке убывания

приоритета):

<р>* – повторение 0 или более раз

<р>+ – повторение 1 или более раз

<р>? – необязательный фрагмент

<р><р> – конкатенация

<р>{m,n} – повторение от m до n раз

<р>{m} – повторение m раз

<р>{m,} – повторение m или более раз

^<р> – фрагмент в начале строки

<р>$ – фрагмент в конце строки

<р>|<р> – любое из выражений

………………………..

………………………….

…………………………

3.3 Работа с регулярными выражениями

Назовем регулярными следующие языки:

  • пустой язык (не содержащий в себе слов), язык, содержащий единственное слово – ε, а

также языки, содержащие единственное слово, являющееся символом алфавита;

  • языки, являющиеся конкатенациями регулярных языков;
  • языки, являющиеся объединениями регулярных языков;
  • языки, являющиеся замыканиями Клини регулярных языков.

Для задания и описания регулярных языков используются регулярные выражения:

  • для пустого языка регулярным выражением является O;
  • для языка, содержащего единственное слово – ε, регулярным выражением является ε;
  • для языка, содержащего единственное слово – символ алфавита, регулярным

выражением является данный символ алфавита;

  • для конкатенации регулярных языков, имеющих регулярные выражения α и β –

(α)(β);

  • для объединения регулярных языков, имеющих регулярные выражения α и β – (α) | (β);
  • для замыкания Клини регулярного языка, имеющего регулярное выражение α – (α)*.

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

  • наивысший приоритет присвоим операции замыкания Клини,
  • меньший приоритет – операции конкатенации
  • и наименьший приоритет – операции объединения.

Для удобства записи регулярных выражений введем дополнительные

……………………………

…………………………..

…………………………

Заключение

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

Реализовано описанные в методических

указаниях типы данных, процедуры и функции лексического анализатора в

виде отдельного модуля (модуль назвать PerlScan);

Создан в среде Lazarus отдельный проект и подключен к нему

созданный модуль PerlScan;

Реализована в проекте возможность открытия файлов с

программами на языке Perl, с использованием компоненты

TMemo;

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

программах на языке Perl;

Одновременно с подсчетом числа лексем организован их вывод в

порядке встречаемости в тексте программы на языке Perl с указанием

типа лексемы, номера строки и номера позиции начала лексемы в строке.

 

Литература

  • Хопкрофт Д., Мотвани Р., Ульман Д. Введение в теорию автоматов, языков и вычислений.
  • М.: Вильямс, 2002.
  • Поликарпова Н. И., Шалыто А. А. Автоматное программирование. СПб.: Питер, 2009.
  • Свердлов С.З.,Языки программирования и методы трансляции;Учебное пособие.-СПб.;Питер 2007,-638 с.;ил.
  • Ахо Ф.В.,Лам М.С.,Сети Р.,Ульман Д.Д., Компиляторы;принципы, технологии и инструментарий, 2-е изд..; пер. с фнгл.-М.;Издательский дом «Вильямс»,2008.=1184 с.;ил.
  • Мансуров К.Т., основы программирования в среде Lazaurus/2010/-772 с.;ил.
  • Алексеев Е.Р., Чеснокова О.В., Кучер Т.В., самоучитель по программированию на Free Pascal и Lazaurus.-Донецк.;ДонНТУ,
  • Технопарк ДонНТУ УНИТЕХ. 2009.-503 с.