Задача.
Доказать, что контекстно-свободный язык L = { a
n
b
n
| n ≥
0} нерегулярен.
Доказательство (от противного).
Предположим, что язык
L
регулярен. Тогда существует конечный автомат ( ДКА или
НКА )
)
,
,
,
,
(
F
I
K
A
, допускающий язык
L
:
L
A
L
)
(
. ( Согласно утверждению 10, лю- бой регулярный язык может быть задан конечным автоматом). Пусть число состояний авто- мата A равно k (k
0). Рассмотрим цепочку a
k
b
k
L. Так как L =L (A), a
k
b
k
L (A). Это означает, что в автомате
A
есть успешный путь
T
с пометкой a
k
b
k
:
1 2
2 2
1 2
1
k
b
k
b
b
k
b
k
a
k
a
a
a
p
p
p
p
p
p
p
, где
1 2
,
,
1
k
i
для
K
p
i
. Так как в автомате
A
всего
k состояний, среди p
1
, p
2
, …, p
k
1
найдутся хотя бы два одинаковых. Иными словами, существуют i, j, 1
i < j
k, такие что
p
i
p
j
. Таким образом, участок
j
a
a
i
p
p
пути T является циклом. Пусть длина этого цикла равна m (m
0, так как цикл — это непустой путь). Рассмотрим успешный путь
T
, который отличается от T тем, что циклический участок
j
a
a
i
p
p
присутствует в нем дважды:
1 2
1 1
)
(
k
b
k
a
j
a
a
j
i
a
a
i
a
p
p
p
p
p
p
p
Элементы теории трансляции
/
Разбор по регулярным грамматикам
34
Пометкой пути
T
является цепочка
kmkba
. Поскольку
T
— успешный путь,
)
(
ALbakmk
. Так как
Lbakmk
, получаем, что
)
(
ALL
. Это противоречит равен- ству
)
(
ALL
. Следовательно, предположение о том, что
L регулярен, неверно
Регулярные выражения
Кроме регулярных грамматик и конечных автоматов, существует еще один широко используемый в математических теориях и приложениях формализм, задающий регулярные языки. Это регулярные выражения. Они позволяют описать любой регулярный язык над за- данным алфавитом, используя три вида операций:
(объединение),
(конкатенация),
(итерация).
15)
Определение. Пусть
L,
L1
,
L2
— языки над алфавитом
. Тогда будем называть язык
L1
L2
объединением языков
L1
и
L2
; язык
L1
L2
{
|
L1
,
L2
} —
конкатена-цией (
сцеплением) языков
L1
и
L2
(содержит всевозможные цепочки, полученные сцеплени- ем цепочек из
L1 с цепочками из
L2
);
i-ой степенью языка
L назовем язык
L i
L i
1
L для
i
0,
L0
= {
}. Язык
L*
0
nnL назовем
итерацией языка
L.
Определение. Пусть
— алфавит, не содержащий символов
,
,
,
, (, ). Опреде- лим рекурсивно
регулярное выражение
над алфавитом
и регулярный язык
L(
), задавае- мый этим выражением:
1)
a
{
,
} есть
регулярное выражение;
L(
a)
{
a} для
a
{
};
L(
)
;
2)
если
и
— регулярные выражения, то: а) (
)
(
) — регулярное выражение;
L(
(
)
(
)
)
L(
)
L(
); б) (
)(
) — регулярное выражение;
L(
(
)(
)
)
L(
)
L(
); в) (
)
*
— регулярное выражение;
L(
(
)
*
)
(
L(
)
)
*
;
3)
все регулярные выражения конструируются только с помощью пунктов 1 и 2.
Если считать, что операция «
» имеет самый низкий приоритет, а операция «
» — наивысший, то в регулярных выражениях можно опускать лишние скобки.
Примеры регулярных выражений над алфавитом {
a,
b}:
a
b, (
a
b)
*
, (
aa (
ab)
*
bb)
*
Соответствующие языки:
L(
a
b )
{
a}
{
b}
{
a,
b},
15)
Операцию итерации называют также звездочкой Клини, в честь ученого, предложившего регулярные выра- жения для описания регулярных языков. «Регулярность» в названии этого класса языков означает повторя- емость некоторых фрагментов цепочек. На примере диаграмм конечных автоматов видно, что повторяе- мость фрагментов обусловлена наличием циклов в диаграмме.
Элементы теории трансляции
/
Задачи лексического анализа
35
L(
(
a
b)
*
)
{
a,
b}
*
,
L(
(
aa (
ab)
*
bb)
*
)
{
}
{
aax1
bbaax2
bb...
xkbb |
k
1,
xi
{(
ab)
n |
n
0} для
i
1, ...,
k }.
Существуют алгоритмы построения регулярного выражения по регулярной грамма- тике или конечному автомату и обратные алгоритмы, позволяющие преобразовать выраже- ние в эквивалентную грамматику или автомат [3].
Регулярные выражения используются для описания лексем языков программирова- ния, в задачах редактирования и обработки текстов; подходят для многих задач сравнения изображений и автоматического преобразования. Расширенные их спецификации (эквива- лентные по описательной силе, но более удобные для практики) входят в промышленный стандарт открытых операционных систем
POSIX и в состав базовых средств языка про- граммирования
Perl.
ЗадачилексическогоанализаЛексический анализ (ЛА) — это первый этап процесса компиляции. На
этом этапе ли- теры, составляющие исходную программу, группируются в отдельные лексические элемен- ты, называемые
лексемами.
Лексический анализ важен для процесса компиляции по нескольким причинам: а)
замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы более удобным для дальнейшей об- работки; б)
лексический анализ уменьшает длину программы, устраняя из ее исходного пред- ставления несущественные пробельные символы и комментарии; в)
если будет изменена кодировка в исходном представлении программы, то это от- разится только на лексическом анализаторе.
Выбор конструкций, которые будут выделяться как отдельные лексемы, зависит от языка и от точки зрения разработчиков компилятора. Обычно принято выделять следующие типы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексе- ме сопоставляется пара:
тип_лексемы, указатель_на_информацию_о_ней
Соглашение: эту пару тоже будем называть лексемой, если это не будет вызывать недоразумений.
Таким образом, лексический анализатор — это транслятор, входом которого служит цепочка символов, представляющих исходную программу, а выходом — последовательность лексем.
Очевидно, что лексемы перечисленных выше типов можно описать с помощью регу- лярных грамматик. Поскольку лексемы не пусты, для описания лексического состава любого языка программирования достаточно автоматных грамматик без
-правил.
Например, идентификатор (
I ) описывается так:
Элементы теории трансляции
/
Задачи лексического анализа
36
I →
a |
b| ...|
z |
Ia |
Ib |...|
Iz |
I0 |
I1 |...|
I9
Целое без знака (
N):
N → 0 | 1 |...| 9 |
N0 |
N1 |...|
N9 и т. д.
Для
грамматик этого класса, как мы уже видели, существует простой и эффективный алгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грам- матикой. Однако перед лексическим анализатором стоит более сложная задача:
он должен сам выделить в исходном тексте цепочку символов, представляющую лексему, и проверить правильность ее записи;
зафиксировать в специальных таблицах для хранения разных типов лексем факт появления соответствующих лексем в анализируемом тексте;
преобразовать цепочку символов, представляющих лексему, в пару
тип_лексемы, указатель_на_информацию_о_ней
;
удалить пробельные литеры и комментарии.
Для того чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммы состояний, введем на дугах дополнительный вид пометок — пометки-действия. Теперь каж- дая дуга в ДС может выглядеть так:
Смысл
ti прежний: если в состоянии
A очередной анализируемый символ совпадает с
tiдля какого-либо
i
1, 2, …,
n, то осуществляется переход в состояние
B, при этом необходи- мо выполнить действия
D1
,
D2
, ...,
DmЗадача. По заданной регулярной грамматке, описывющей целое число без знака, по- строить диаграмму с действиями по нахождению и печати квадрата данного числа.
S →
N
N → 0 | 1 |...| 9 |
N0 |
N1 |...|
N9
Решение Перевод числа во внутренне представление (переменная
n типа
int) будем осуществ- лять по схеме Горнера: распознав очередную цифру числа, умножаем текущее значениие
n на 10 и добавляем числовое значение текущей цифры (текущий символ хранится в перемен- ной
c типа
char). Встретив маркер конца, печатаем квадрат числа
n. A B t1
, t2
,…, tnD1
;
D2
;
…;
Dmn =
n
10
c –’0’;
cout << n*n;
0, 1,…, 9
n =
c–’0’;
0, 1,…, 9
N S H Элементы теории трансляции
/
Задачи лексического анализа
37
Лексический анализатор для
М
- языка
Описание модельного языка
P → program D1
;
B
D1
→ var D {,
D}
D → I {,
I}: [
int|
bool ]
B → begin S {;
S}
end S → I
E |
if E then S else S |
while E do S |
B |
read (
I) |
write (
E)
E → E1
[
|
|
| !
]
E1
|
E1
E1
→ T {[
|
|
or ]
T}
T → F {[
| / |
and ]
F}
F → I |
N |
L |
not F | (
E)
L → true |
false I → C |
IC |
IR N → R |
NR C → a |
b | ... |
z |
A |
B | ... |
Z R → 0 | 1 | 2 | ... | 9
Замечания к
грамматике модельного языка:
а)
запись вида {
} означает итерацию цепочки
, т. е. в порождаемой цепочке в этом месте может находиться либо
, либо
, либо
, либо
и т. д.; б)
запись вида [
|
] означает, что в порождаемой цепочке в этом месте может находиться либо
, либо
; в)
P — цель грамматики; символ
— маркер конца текста программы.
Контекстные условия:
1.
Любое имя, используемое в программе, должно быть описано и только один раз.
2.
В операторе присваивания типы переменной и выражения должны совпадать.
3.
В условном операторе и в операторе цикла в качестве условия возможно только логическое выражение.
4.
Операнды операции отношения должны быть целочисленными.
5.
Тип выражения и совместимость типов операндов в выражении определяются по обычным правилам; старшинство операций задано синтаксисом.
В любом месте программы, кроме идентификаторов,
служебных слов и чисел, может находиться произвольное число пробелов и комментариев в фигурных скобках вида {
любые символы, кроме «}» и «
»
}.
true,
false,
read и
write — служебные слова (в М-языке их нельзя переопределять в от- личие от аналогичных стандартных идентификаторов в Паскале).
Разделители между идентификаторами, числами и служебными словами употребля- ются так же, как в Паскале.
Элементы теории трансляции
/
Задачи лексического анализа
38
Перейдем к построению лексического анализатора.
Вход лексического анализатора — символы исходной программы на М-языке; резуль- тат работы — исходная программа в виде последовательности лексем (их внутреннего пред- ставления). В нашем случае лексический анализатор будет вызываться, когда потребуется очередная лексема исходной программы, поэтому результатом работы лексического анализа- тора будет очередная лексема анализируемой программы на М-языке.
Лексический анализатор для модельного языка будем создавать поэтапно: сначала опишем на языке Си
классы объектов, которые будут использоваться при ЛА, затем по- строим ДС с действиями для распознавания и формирования внутреннего представления лексем, а затем по ДС напишем программу ЛА. Отметим, что мы будем рассматривать один из возможных способов проектирования и реализации программы ЛА на Си
, быть мо- жет, не самый лучший.
Проектирование классовой структуры лексического анализатора
Представление лексем: выделим следующие типы лексем, введя следующий перечис- лимый тип данных: enum type_of_lex
{
LEX_NULL,
// 0
LEX_AND, LEX_BEGIN, … LEX_WRITE,
// 18
LEX_FIN,
// 19
LEX_SEMICOLON, LEX_COMMA, … LEX_GEQ,
// 35
LEX_NUM,
// 36
LEX_ID,
// 37
POLIZ_LABEL,
// 38
POLIZ_ADDRESS,
// 39
POLIZ_GO,
// 40
POLIZ_FGO
// 41
};
Содержательно внутреннее представление лексем — это пара (
тип_лексемы, значе-ние_лексемы). Значение лексемы — это номер строки в таблице лексем соответствующего класса, содержащей информацию о лексеме, или непосредственное значение, например, в случае целых чисел.
Соглашение об используемых таблицах лексем:
TW — таблица служебных слов М-языка;
TD — таблица ограничителей М-языка;
TID — таблица идентификаторов анализируемой программы;
Таблицы TW и TD заполняются заранее, т. к. их
содержимое не зависит от исходной программы; TID формируется в процессе анализа.
Необходимые таблицы можно представить в виде объектов, конкретный вид которых мы рассмотрим чуть позже, или в виде массивов строк, например, для служебных слов.
Класс
Lex:
Элементы теории трансляции
/
Задачи лексического анализа
39 class Lex
{ type_of_lex t_lex; int v_lex; public:
Lex ( type_of_lex t = LEX_NULL, int v = 0)
{ t_lex = t; v_lex = v;
} type_of_lex get_type () { return t_lex; } int get_value () { return v_lex; } friend ostream& operator << ( ostream &s, Lex l )
{ s << '(' << l.t_lex << ',' << l.v_lex << ");"; return s;
}
};
Класс Ident:
class Ident
{ char
* name; bool declare; type_of_lex type; bool assign; int value; public:
Ident ()
{ declare = false; assign = false;
} char *get_name ()
{ return name;
} void put_name (const char *n)
{ name = new char [ strlen(n) + 1 ]; strcpy ( name, n );
} bool get_declare ()
{ return declare;
} void put_declare ()
{ declare = true;
}
Элементы теории трансляции
/
Задачи лексического анализа
40 type_of_lex get_type ()
{ return type;
} void put_type ( kind_of_lex t )
{ type = t;
} bool get_assign ()
{ return assign;
} void put_assign ()
{ assign = true;
} int get_value ()
{ return value;
} void put_value (int v)
{ value = v;
}
};
Класс tabl_ident : class tabl_ident
{ ident
* p; int size; int top; public: tabl_ident ( int max_size )
{ p
= new ident[size=max_size]; top = 1;
}
tabl_ident ()
{ delete []p;
} ident& operator[] ( int k )
{ return p[k];
} int put ( const char *buf );
}; int tabl_ident::put ( const char *buf )
{
Элементы теории трансляции
/
Задачи лексического анализа
41 for ( int j=1; j++top; return top-1;
}
Класс Scanner : class Scanner
{ enum state { H, IDENT, NUMB, COM, ALE, DELIM, NEQ }; static char
* TW[]; static type_of_lex words[]; static char
* TD[]; static type_of_lex dlms[]; state
CS;
FILE
* fp; char c; char buf[80]; int buf_top; void clear ()
{ buf_top = 0; for ( int j = 0; j < 80; ++j ) buf[j] = '\0';
} void add ()
{ buf [ buf_top ++ ] = c;
} int look ( const char *buf, char **list )
{ int i = 0; while ( list[i] )
{ if ( !strcmp(buf, list[i]) ) return i;
++i;
} return 0;
} void gc ()
{ c = fgetc (fp);
} public:
Элементы теории трансляции
/
Задачи лексического анализа
42
Lex get_lex ();
Scanner ( const char * program )
{ fp = fopen ( program, "r" );
CS = H; clear(); gc();
}
};
Таблицы лексем М-языка можно описать на Си
, например, таким образом: char * Scanner::TW[] =
{
""
// 0 позиция 0 не используется "and",
// 1
"begin",
// 2
"bool", // 3
"do",
// 4
"else",
// 5
"end",
// 6
"if",
// 7
"false",
// 8
"int",
// 9
"not",
// 10
"or",
// 11
"program",
// 12
"read",
// 13
"then",
// 14
"true",
// 15
"var",
// 16
"while",
// 17
"write",
// 18
NULL
}; char * Scanner:: TD[] =
{
""
// 0 позиция 0 не используется "@",
// 1
";",
// 2
",",
// 3
":",
// 4
":=",
// 5
"(",
// 6
")",
// 7
"=",
// 8
"<",
// 9
">",
// 10
"+",
// 11
"-",
// 12
"*",
// 13
"/",
// 14
"<=",
// 15
Элементы теории трансляции
/
Задачи лексического анализа
43
"!=",
// 16
">=",
// 17
NULL
}; tabl_ident TID(100); type_of_lex Scanner::words[] =
{
LEX_NULL,
LEX_AND,
LEX_BEGIN,
LEX_BOOL,
LEX_DO,
LEX_ELSE,
LEX_END,
LEX_IF,
LEX_FALSE,
LEX_INT,
LEX_NOT,
LEX_OR,
LEX_PROGRAM,
LEX_READ,
LEX_THEN,
LEX_TRUE,
LEX_VAR,
LEX_WHILE,
LEX_WRITE,
LEX_NULL
}; type_of_lex Scanner::dlms[] =
{
LEX_NULL,
LEX_FIN,
LEX_SEMICOLON,
LEX_COMMA,
LEX_COLON,
LEX_ASSIGN,
LEX_LPAREN,
LEX_RPAREN,
LEX_EQ,
LEX_LSS,
LEX_GTR,
LEX_PLUS,
LEX_MINUS,
LEX_TIMES,
LEX_SLASH,
LEX_LEQ,
LEX_NEQ,
LEX_GEQ,
LEX_NULL
};
Элементы теории трансляции
/
Задачи лексического анализа
44
Рис. 9. ДС для модельного языка.
H
clear();
add();
gc();
gc();
’_’ ALE
NEQ
DELIM
add();
gc();
IDENT
буква, цифра NUMB
d
d*10
(
c –´0´);
gc();
цифра COM
gc();
gc();
}
ER
ER
буква цифра {
Скачать 2.2 Mb.