Файл: Теория автоматов и формальных языков.pdf

Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования
«Оренбургский государственный университет»
Кафедра программного обеспечения вычислительной техники и автоматизированных систем
Е.Н. Ишакова
ТЕОРИЯ АВТОМАТОВ
И ФОРМАЛЬНЫХ ЯЗЫКОВ
Рекомендовано к изданию Редакционно-издательским советом федерального государственного бюджетного образовательного учреждения высшего профессионального образования “Оренбургский государственный университет” в качестве методических указаний для студентов, обучающихся по программам высшего профессионального образования по направлению подготовки 231000.62
Программная инженерия
Оренбург
2014

2
УДК 004.4

422(075.8)
ББК 32.973.26-018.1я73
И 97
Рецензент - кандидат технических наук, доцент М.А. Токарева
Ишакова, Е.Н.
И 97
Теория автоматов и формальных языков: методические указания к вы- полнению курсовой работы / Е. Н. Ишакова, Оренбургский гос. ун-т. -
Оренбург: ОГУ, 2014. – 63с.
В методических указаниях содержатся материалы, необходимые для са- мостоятельной подготовки студентов к выполнению курсовой работы по тео- рии автоматов и формальных языков. В описание курсовой работы включены цель и задачи работы, порядок ее выполнения, рассмотрены теоретические вопросы, связанные с реализацией поставленных задач, приведена необходи- мая литература, контрольные вопросы и тесты для самопроверки. В приложе- ниях представлены правила оформления результатов курсовой работы.
Методические указания предназначены для выполнения курсовой рабо- ты по дисциплине «Теория автоматов и формальных языков» для бакалавров, обучающихся по направлению подготовки 231000.62 «Программная инжене- рия» всех форм обучения.
© Ишакова Е.Н., 2014
© ОГУ, 2014
УДК 004.4

422(075.8)
ББК 32.937.26-018.1я73

3
Содержание
Введение ....................................................................................................................... 4 1 Тема и цель курсовой работы .................................................................................. 5 2 Основы теории автоматов и формальных языков ................................................. 5 2.1 Методы описания синтаксиса языка программирования .................................. 5 2.2 Общая схема работы распознавателя ................................................................ 13 2.3 Лексический анализатор программы ................................................................ 17 2.4 Синтаксический анализатор программы ......................................................... 28 2.5 Семантический анализатор программы ............................................................ 33 3 Постановка задачи к курсовой работе .................................................................. 40 4 Требования к содержанию курсовой работы ...................................................... 41 5 Варианты индивидуальных заданий .................................................................... 43 6 Контрольные вопросы для самопроверки............................................................ 49 7 Тесты для самопроверки ........................................................................................ 50
Список использованных источников ...................................................................... 56
Приложение А Укрупненная схема алгоритма программного средства ............. 58
Приложение Б Контрольный пример ...................................................................... 59
Приложение В Сообщения об ошибках .................................................................. 61
Приложение Г Фрагмент текста программы .......................................................... 62

4
Введение
Предлагаемый материал посвящен основам классической теории автоматов и формальных языков – одной из важнейших составных частей системного программ- ного обеспечения.
Несмотря на более чем полувековую историю вычислительной техники, годом рождения теории формальных языков и автоматов можно считать 1957, когда по- явился первый компилятор языка Фортран, созданный Бэкусом и дающий достаточ- но эффективный объектный код. До этого времени создание распознавателей было
«творческим» процессом. Появление теории формальных языков и строгих матема- тических моделей позволило перейти от «творчества» к «науке». Именно благодаря этому, стало возможным появление сотен новых языков программирования.
Несмотря на то, что к настоящему времени разработаны тысячи различных языков и их компиляторов, процесс создания новых приложений в этой области не прекращается. Это связно как с необходимостью решения все более сложных при- кладных задач. Поэтому основы теории автоматов и формальных языков, а также практические методы разработки распознавателей лежат в фундаменте высшего об- разования по направлению «Программная инженерия».
Предлагаемый материал затрагивает основы методов разработки распознава- телей формальных языков и содержит сведения, необходимые для изучения логики их функционирования, используемого математического аппарата (теории автоматов, формальных языков и формальных грамматик, метаязыков). В методических указа- ниях содержатся материалы, необходимые для самостоятельной подготовки студен- тов к выполнению курсовой работы. В описание курсовой работы включены цель работы, порядок ее выполнения, рассмотрены теоретические вопросы, связанные с реализацией поставленных задач, приведена необходимая литература.

5
1 Тема и цель курсовой работы
Тема курсовой работы: «Разработка распознавателя модельного языка про- граммирования».
Цель курсовой работы:
- закрепление теоретических знаний в области теории формальных языков, грамматик и автоматов;
- формирование практических умений и навыков разработки собственного распознавателя модельного языка программирования;
- закрепление практических навыков самостоятельного решения инженерных задач, развитие творческих способностей студентов и умений пользоваться техниче- ской, нормативной и справочной литературой.
2 Основы теории автоматов и формальных языков
2.1 Описание синтаксиса языка программирования
Существуют три основных метода описания синтаксиса языков программиро- вания: формальные грамматики, формы Бэкуса-Наура и диаграммы Вирта.
Формальные грамматики
Определение 2.1. Формальной грамматикой называется четверка вида:
)
,
,
,
(
S
P
V
V
G
N
T

, (1.1) где V
N
- конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);
V
T
- множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V
T

V
N
=

;

6
Р – множество правил вывода грамматики, являющееся конечным под- множеством множества (V
T

V
N
)
+

(V
T

V
N
)
*
; элемент (

,

) множе- ства Р называется правилом вывода и записывается в виде



(читается: «из цепочки

выводится цепочка

»);
S – начальный символ грамматики, S

V
N
Для записи правил вывода с одинаковыми левыми частями вида
n









,
,
,
2 1

используется сокращенная форма записи
n




|
|
|
2 1


Пример 2.1. Опишем с помощью формальных грамматик синтаксис паскале- подобного модельного языка М. Грамматика будет иметь правила вывода вида:
PR

{BODY}
BODY

DESCR | OPER | BODY; OPER | BODY; DESCR
DESCR

% ID
1
| # ID
1
| $ ID
1
ID
1

ID | ID
1
, ID
OPER
1

OPER | OPER
1
: OPER
OPER

[ OPER
1
] | if COMPARE then OPER |
if COMPARE then OPER else OPER | while COMPARE do OPER |
for ID as COMPARE to COMPARE do OPER | read(ID
1
) |
write(EXPR) | ID as COMPARE
EXPR

COMPARE | EXPR, COMPARE
COMPARE

ADD | COMPARE=ADD | COMPARE>ADD |
COMPARE<ADD | COMPARE>=ADD | COMPARE<=ADD |
COMPARE<>ADD
ADD

MULT | ADD + MULT | ADD - MULT | ADD or MULT
MULT

FACT | MULT/FACT | MULT*FACT | MULT and FACT
FACT

ID | NUM | LOG | not FACT | (COMPARE)
LOG

true | false
ID

CH | ID CH | ID DIGIT

7
DIGIT
1

DIGIT | DIGIT
1
DIGIT
DIGIT

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
CH

a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z |
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U |
V | W | X | Y | Z
NUM

INT | REAL
INT

BIN | OCT | DEC | HEX
BIN

BIN
1
B | BIN
1
b | BIN
1
BIN
BIN
1

0 | 1
OCT

OCT
1
O | OCT
1
o | OCT
1
OCT
OCT
1

0 | 1 | 2 | 3 | 4 | 5 | 6 | 7
DEC

DIGIT
1
D | DIGIT
1
d | DIGIT
1
HEX

HEX
1
H | HEX
1
h
HEX
1

DIGIT | HEX
1
DIGIT | HEX
1
CH
1
CH
1

a | b | c | d | e | f | A | B | C | D | E | F
REAL

DIGIT
1
POR | DIGIT
1
.DIGIT
1
POR | .DIGIT
1
POR | .DIGIT
1
|
DIGIT
1
.DIGIT
1
POR

E+DIGIT
1
| E-DIGIT
1
| e+DIGIT
1
| e-DIGIT
1
| E DIGIT
1
| e DIGIT
1
Формы Бэкуса-Наура (БНФ)
Метаязык, предложенный Бэкусом и Науром, использует следующие обозна- чения:
- символ «::=» отделяет левую часть правила от правой (читается: «опреде- ляется как»);
- нетерминалы обозначаются произвольной символьной строкой, заключен- ной в угловые скобки «<» и «>»;
- терминалы - это символы, используемые в описываемом языке;

8
- правило может определять порождение нескольких альтернативных цепо- чек, отделяемых друг от друга символом вертикальной черты «|» (читается: «или»).
Пример 2.2. Определение понятия «идентификатор» с использованием БНФ имеет вид:
<идентификатор> ::= <буква> | <идентификатор> <буква>
| <идентификатор> <цифра>
<буква> :: = a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x |
y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R |
S | T | U | V | W | X | Y | Z
<цифра> :: = 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Расширенные формы Бэкуса-Наура (РБНФ)
Для повышения удобства и компактности описаний в РБНФ вводятся следу- ющие дополнительные конструкции (метасимволы):
- квадратные скобки «[» и «]» означают, что заключенная в них синтаксиче- ская конструкция может отсутствовать;
- фигурные скобки «{» и «}» означают повторение заключенной в них син- таксической конструкции ноль или более раз;
- сочетание фигурных скобок и косой черты «{/» и «/}» используется для обозначения повторения один и более раз;
- круглые скобки «(» и «)» используются для ограничения альтернативных конструкций.
Пример 2.3. В соответствии с данными правилами синтаксис модельного язы- ка М будет выглядеть следующим образом:
<буква> :: = a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x |
y | z | A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R |
S | T | U | V | W | X | Y | Z

9
<цифра> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<идентификатор> ::= <буква> { <буква> | <цифра> }
<число> ::= {/< цифра> /}
<ключевое_слово> ::= read | write | if | then | else | for | to | while | do | true |
false | or | and | not | as
<разделитель> ::= { | } | % | ! | $ | , | ; | [ | ] | : | ( | ) | + | - | * | / | = | <> | < | <= |
> | >= | /* | */
<программа> ::= «{» <тело> «}»
<тело> ::= (<описание> | <оператор> ) {; (<описание> | <оператор>)}
<описание> ::= <тип> <идентификатор> { , <идентификатор> }
<тип>::= % | # | $
<оператор> ::= <присваивания> | <условный> |
<фиксированного_цикла> | <условного_цикла> |
<составной> | <ввода> | <вывода>
<присваивания> ::= <идентификатор> as <выражение>
<условный> ::= if <выражение> then <оператор> [ else <оператор>]
<фиксированного_цикла>::= for <присваивания> to <выражение> do
<оператор>
<условного_цикла>::= while <выражение> do <оператор>
<составной>:: = «[» <оператор> { : <оператор> } «]»
<ввода>:: = read «(»<идентификатор> {, <идентификатор> } «)»
<вывода>:: = write «(»<выражение> {, <выражение> } «)»
<выражение>:: = <сумма> | <выражение> (
< > | = | < | <= | > | >=
) <сумма>
<сумма> ::= <произведение> { (+ | - | or) <произведение>}
<произведение>:: = <множитель> { ( * | / | and) <множитель>}
<множитель>:: = <идентификатор> | <число> | <логическая_константа> |
not <множитель> | «(»<выражение>«)»
<логическая_константа>:: = true | false
<целое>::= <двоичное> | <восьмеричное> | <десятичное> |
<шестнадцатеричное>

10
<двоичное>::= {/ 0 | 1 /} (B | b)
<восьмеричное>::= {/ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 /} (O | o)
<десятичное>::= {/ <цифра> /} [D | d]
<шестнадцатеричное>::= <цифра> {<цифра> | A | B | C | D | E | F | a |
b | c | d | e | f} (H | h)
<действительное>::= <числовая_строка> <порядок> |
[<числовая_строка>] . <числовая_строка> [порядок]
<числовая_строка>::= {/ <цифра> /}
<порядок>::= ( E | e )[+ | -] <числовая_строка>
Диаграммы Вирта
В метаязыке диаграмм Вирта используются графические примитивы, пред- ставленные на рисунке 2.1.
При построении диаграмм учитывают следующие правила:
- каждый графический элемент, соответствующий терминалу или нетерми- налу, имеет по одному входу и выходу, которые обычно изображаются на противо- положных сторонах;
- каждому правилу соответствует своя графическая диаграмма, на которой терминалы и нетерминалы соединяются посредством дуг;
- альтернативы в правилах задаются ветвлением дуг, а итерации - их слияни- ем;
- должна быть одна входная дуга (располагается обычно слева или сверху), задающая начало правила и помеченная именем определяемого нетерминала, и одна выходная, задающая его конец (обычно располагается справа и снизу);
- стрелки на дугах диаграмм обычно не ставятся, а направления связей от- слеживаются движением от начальной дуги в соответствии с плавными изгибами промежуточных дуг и ветвлений.

11
Пример 1.4. Описание синтаксиса модельного языка М с помощью диа
Описание синтаксиса модельного языка М с помощью диаграмм Вирта пред- ставлено на рисунке 2.2.
Цифра
0 1
2 3
4 5
6 7
8 9
Буква
A
B
C
D
E
F
O
P
Q
R
S
N
G
H
I
J
K
L
b c
d e
f a
U
V
W
X
Y
T
M
Z
h i
j k
l g
o p
q r
s n
u v
w x
y t
m z
Рисунок 2.2 – Синтаксические правила модельного языка М
1)
2)
3)
1) – терминальный символ, принадлежащий алфавиту языка;
2) – постоянная группа терминальных символов, определяющая название лексемы, ключевое слово и т.д.;
3) – нетерминальный символ, определяющий название правила;
4) – входная дуга с именем правила, определяющая его название;
5) – соединительные линии, обеспечивающие связь между терминальными и нетерминальными символами в правилах.
Рисунок 2.1 – Графические примитивы диаграмм Вирта