Курсовая работа по информатике (стр. 1 )

Оглавление

Оглавление

1 Структура математического обеспечения ЭВМ ………………………………………………...5

1. 1 Средства программирования…………………………5

1. 2 Средства управления …………………………………6

2 Элементы компиляции. Анализ формальных языков……………………………………………... 6

2. 1Сведения о регулярных выражениях и грамматиках .6

2. 2 Регулярные выражения……………………………… 8

2. 3 Грамматика…………………………………………… 9

2. 4 Способы получения одних цепочек символов из других……………………………………………………. 11

2. 5 Формальное определение языка…………………... 12

2. 6 Расширенные грамматики…………………………. 14

2. 7 Задачи анализа.………………………………………15

2. 8 Синтаксические диаграммы……………………….. 18

2. 9 Введение в компиляцию…………………………… 21

2. 10 Структура компилятора …………………………...23

2. 11 Проходы компилятора……………………………. 25

3 Алгоритмический язык SPL …………………26

3. 1 Символы ……………………………………………..27

3. 2 Идентификаторы…………………………………… 27

3. 3 Константы …………………………………………...28

3. 4 Переменные …………………………………………28

3. 5 Выражения …………………………………………..29

3. 6 Служебные слова ……………………………………29

3. 7 Функции ……………………………………………..29

3. 8 Оператор цикла ……………………………………...31

4 Лексический анализ …………………………..33

4. 1 Блок - схема функции void main ()…….………..…39

4. 2 Блок-схема функции void number () ………………..41

4. 3 Блок-схема функции void word ()………………….. 44

4. 4 Блок-схема функции char*add()……………..…….. 47

5 Полный синтаксис языка SPL ………………49

5. 1 Алфавит нетерминальных символов ………………50

5.2 Синтаксические диаграммы и функции распознавания цепочек для нетерминальных символов…………………………………………………..56

6 Пояснения к выполнению курс овой работы……………………………………………. 71

6. 1 Пример выполнения курсовой работы …………….76

6. 2 Варианты заданий для курсовой работы………….. 82

6. 3 Требования к оформлению курсовой работы…….. 90

7 Вопросы к экзамену …………………………...91

8 Список литературы…………………………... 94

1 Структура математического обеспечения ЭВМ

СМО

 

Системное-программное Прикладное программное обеспечение обеспечение

(операционные системы)

 

Средства Средства Программы Программы

програм-мирования

управления

пользователя

технического обслуживания (тесты)

1. 1 Средства программирования

Существуют такие средства программирования:

Текстовые редакторы (диалоговые программы);

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

Редакторы связей (компоновщики) lіnker;

Утилиты (сервисные программы, копирование, перемещение и т. д.);

1. 2 Средства управления

Средствами управления являются:

−Внутренние команды (при изготовлении ПК);

−Внешние программы (в DOS);

−Драйверы (программы, которые руководят внешними устройствами).

2 Элементы компиляции. Анализ формальных языков

2. 1Сведения о регулярных выражениях и грамматиках

Любой язык имеет свой алфавит.

Алфавит – это конечное множество I элементов, называемых символами.

Цепочка или слово в алфавите I – это конечная последовательность элементов (символов) из алфавита I. Например, если алфавит языка состоит только из заглавных и строчных букв латинского алфавита, то любые последовательности этих букв являются цепочками (словами), в том числе цепочка может состоять из одного символа.

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

§  хn. Цепочка символов х повторяется (пишется без пробелов одна за другой) n раз. Например, abba2 – это abbaabba.

§  хk. Цепочка символов х записывается в обратной последовательности. Например, portR - это trop.

§  xy. За цепочкой символов x без пробела помещается цепочка символов y.

§  х*. Цепочка символов х в цикле может повторяться нуль и более раз.

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

Например: intl iden (‘,’ iden)* ‘;’

Это означает, что за символом intl должно следовать iden. Затем через запятую может еще повторяться iden нуль и более раз. В конце должна быть точка с запятой.

·  х+. Цепочка символов х должна повторяться один и больше раз. В алгоритмическом языке Pascal это реализуется оператором repeat, а в языке Си – оператором цикла do while.

·  |х|. Определение длины цепочки символов х (количество символов в цепочке).

·  {} или l, или e - обозначение пустой цепочки символов.

·  [х]. Так обозначается необязательная цепочка символов. Например, такая запись нужна для того, чтобы обозначить, что перед числом знак может быть, а может и отсутствовать.

Кроме алфавита и цепочки символов (слов), важным понятием является язык.

Язык в алфавите I – это произвольное множество цепочек (слов).

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

Это цепочки символов, в которые входят не только символы из некоторого алфавита I, но и другие символы, которые часто носят служебный характер. Например, это могут быть запятая для разделения других символов, а также символы для обозначения каких-либо действий над цепочками. Пусть множество {,* |} из перечисленных в фигурных скобках символов не входит в алфавит I. Тогда цепочка символов из объединения IU{,* |} называется регулярным выражением. Эти выражения обычно используются для описания синтаксиса какого-либо алгоритмического языка.

2. 3 Грамматика

Грамматика G=(T, N,P, S),

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

N – алфавит т. н. нетерминальных символов. Это символы, которые обычно используются для определения каких-либо понятий. Такими понятиями в алгоритмическом языке, например, являются идентификатор, переменная, константа, выражение, оператор и, в конце концов, программа. Обычно эти понятия перечисляются и обозначаются символами. Эти символы определяются через терминальные символы или, кроме того, через другие нетерминальные символы более низкого уровня. Например, при определении нетерминального символа “программа” используются терминальные символы алгоритмического языка, а также нетерминальные символы “оператор”, “выражение”, “слагаемое” и др.

Множества T и N не пересекаются. Обычно терминальные символы обозначаются строчными буквами, а нетерминальные – заглавными. Р – множество правил вывода для нетерминальных символов. Например, это правила описания переменных, констант, написания выражений, операторов и т. д. S – стартовый (главный) нетерминальный символ. Для алгоритмических языков это обычно нетерминальный символ “программа”.

2. 4 Способы получения одних цепочек символов из других

1 Это можно сделать непосредственно, т. е. за одну операцию. Условное обозначение Þ.

Например, dÞh означает, что цепочку символов h можно получить из цепочки d за одну операцию.

Пример. Есть цепочки d=aAb и h=anb. Здесь, a,n,b - терминальные символы (обозначены строчными буквами), а А – нетерминальный символ. Пусть среди множества правил Р есть такое: A®nЄР. То есть нетерминальный символ АЄN можно заменить на терминальный n. Таким образом, за одну операцию из d можно получить цепочку h.

2 Одну цепочку из другой можно получить не за одну операцию. Условное обозначение Þ*.

Например, a0 Þ*an.

Это имеет место или если a0 = an , или существует последовательность непосредственно получаемых цепочек, таких, что a0 Þ a1 Þ a2 Þ …Þ

Þ an-1 Þ an.

2. 5 Формальное определение языка

Способы получения цепочек символов необходимы, чтобы формально дать определение языка L(G), описываемого заданной грамматикой G. Язык L(G) – это множество цепочек w терминальных (и только терминальных!) символов, выводимых из начального (стартового, главного) нетерминального символа S. L(G)={w|S Þ*w, где w – терминальные цепочки}.

Вертикальная черта после w в выражении означает, что w получены при условии, что они выводятся из S. А звездочка означает, что этот вывод может происходить за произвольное количество операций. При этом используется множество P правил, описанное в грамматике G.

Ниже приводятся примеры грамматики и описываемые ими языки.

Пример 1 G=(T,N,P,S).

T={x,y,w,z} – алфавит терминальных символов. Только эти символы можно использовать.

N={S,A,B} – множество нетерминальных символов, из которых S – главный (стартовый) нетерминальный символ. Именно с него должен начинаться вывод цепочек (слов) в соответствии с множеством правил вывода P.