Волкова И.А., Руденко Т.В. - Формальные грамматики и языки, элементы теории трансляции (1082245), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

Алгоритм разбора по диаграмме состояний:

(1) объявляем текущим состояние H;

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

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

(1) прочитана вся цепочка; на каждом шаге находилась единственная дуга, помеченная очередным символом анализируемой цепочки; в результате последнего перехода оказались в состоянии S. Это означает, что исходная цепочка принадлежит L(G).

(2) прочитана вся цепочка; на каждом шаге находилась единственная "нужная" дуга; в результате последнего шага оказались в состоянии, отличном от S. Это означает, что исходная цепочка не принадлежит L(G).

(3) на некотором шаге не нашлось дуги, выходящей из текущего состояния и помеченной очередным анализируемым символом. Это означает, что исходная цепочка не принадлежит L(G).

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

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

Определение: конечный автомат (КА) - это пятерка (K, VT, F, H, S), где

K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K  VT  K, определяющее поведение автомата; отображение F часто называют функцией переходов;

H  K - начальное состояние;

S  K - заключительное состояние (либо конечное множество заключительных состояний).

F(A, t) = B означает, что из состояния A по входному символу t происходит переход в состояние B.

Определение: конечный автомат допускает цепочку a₁a₂...a_n, если F(H,a₁) = A₁; F(A₁,a₂) = A₂; . . . ; F(A_n-2,a_n-1) = A_n-1; F(A_n-1,a_n) = S, где a_i  VT, A_j  K,
j = 1, 2 , ... ,n-1; i = 1, 2, ... ,n; H - начальное состояние, S - одно из заключительных состояний.

Определение: множество цепочек, допускаемых конечным автоматом, составляет определяемый им язык.

Для более удобной работы с диаграммами состояний введем несколько соглашений:

1. если из одного состояния в другое выходит несколько дуг, помеченных разными символами, то будем изображать одну дугу, помеченную всеми этими символами;

2. непомеченная дуга будет соответствовать переходу при любом символе, кроме тех, которыми помечены другие дуги, выходящие из этого состояния.

3. введем состояние ошибки (ER); переход в это состояние будет означать, что исходная цепочка языку не принадлежит.

По диаграмме состояний легко написать анализатор для регулярной грамматики.

Например, для грамматики G = ({a,b, }, {S,A,B,C}, P, S), где

P: S  C

С  Ab | Ba

A  a | Ca

B  b | Cb

анализатор будет таким:

#include <stdio.h>

int scan_G(){

enum state {H, A, B, C, S, ER}; /* множество состояний */

state CS; /* CS - текущее состояние */

FILE *fp;/*указатель на файл, в котором находится анализируемая цепочка */

int c;

CS=H;

fp = fopen ("data","r");

c = fgetc (fp);

do {switch (CS) {

case H: if (c == 'a') {c = fgetc(fp); CS = A;}

else if (c == 'b') {c = fgetc(fp); CS = B;}

else CS = ER;

break;

case A: if (c == 'b') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case B: if (c == 'a') {c = fgetc(fp); CS = C;}

else CS = ER;

break;

case C: if (c =='a') {c = fgetc(fp); CS = A;}

else if (c == 'b') {c = fgetc(fp); CS = B;}

else if (c == '') CS = S;

else CS = ER;

break;

}

} while (CS != S && CS != ER);

if (CS == ER) return -1; else return 0;

}

О недетерминированном разборе

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

Например, для грамматики G = ({a,b, }, {S,A,B}, P, S), где

P: S  A

A  a | Bb

B  b | Bb

разбор будет недетерминированным (т.к. у нетерминалов A и B есть одинаковые правые части - Bb).

Такой грамматике будет соответствовать недетерминированный конечный автомат.

Определение: недетерминированный конечный автомат (НКА) - это пятерка (K, VT, F, H, S), где

K - конечное множество состояний;

VT - конечное множество допустимых входных символов;

F - отображение множества K  VT в множество подмножеств K;

H  K - конечное множество начальных состояний;

S  K - конечное множество заключительных состояний.

F(A,t) = {B₁,B₂,...,B_n} означает, что из состояния A по входному символу t можно осуществить переход в любое из состояний B_i, i = 1, 2, ... ,n.

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

Один из наиболее важных результатов теории конечных автоматов состоит в том, что класс языков, определяемых недетерминированными конечными автоматами, совпадает с классом языков, определяемых детерминированными конечными автоматами.

Это означает, что для любого НКА всегда можно построить детерминированный КА, определяющий тот же язык.

Алгоритм построения детерминированного КА по НКА

Вход: M = (K, VT, F, H, S) - недетерминированный конечный автомат.

Выход: M’ = (K’, VT, F’, H’, S’) - детерминированный конечный автомат, допускающий тот же язык, что и автомат М.

Метод:

1. Множество состояний К’ состоит из всех подмножеств множества К. Каждое состояние из К’ будем обозначать [A₁A₂...A_n], где A_i  K.

2. Отображение F’ определим как F’ ([A₁A₂...A_n], t) = [B₁B₂...B_m], где для каждого 1 <= j <= m F(A_i, t) = B_j для каких-либо 1 <= i <= n.

3. Пусть H = {H₁, H₂, ..., H_k}, тогда H’ = [H₁, H₂, ..., H_k].

4. Пусть S = {S₁, S₂, ..., S_p}, тогда S’ - все состояния из K’, имеющие вид [...S_i...], .S_i  S для какого-либо 1 <= i <= p.

Замечание: в множестве K’ могут оказаться состояния, которые недостижимы из начального состояния, их можно исключить.

Проиллюстрируем работу алгоритма на примере.

Пусть задан НКА M = ({H, A, B, S}, {0, 1}, F, {H}, {S}), где

F(H, 1) = B F(B, 0) = A

F(A, 1) = B F(A, 1) = S ,

тогда соответствующий детерминированный конечный автомат будет таким:

K’ = {[H], [A], [B], [S], [HA], [HB], [HS], [AB], [AS], [BS], [HAB], [HAS], [ABS], [HBS], [HABS]}

F’([A], 1) = [BS] F’([H], 1) = [B]

F’([B], 0) = [A] F’([HA], 1) = [BS]

F’([HB], 1) = [B] F’([HB], 0) = [A]

F’([HS], 1) = [B] F’([AB], 1) = [BS]

F’([AB], 0) = [A] F’([AS], 1) = [BS]

F’([BS], 0) = [A] F’([HAB], 0) = [A]

F’([HAB], 1) = [BS] F’([HAS], 1) = [BS]

F’([ABS], 1) = [BS] F’([ABS], 0) = [A]

F’([HBS], 1) = [B] F’([HBS], 0) = [A]

F’([HABS], 1) = [BS] F’([HABS], 0) = [A]

S’ = {[S], [HS], [AS], [BS], [HAS], [ABS], [HBS], [HABS]}

Достижимыми состояниями в получившемся КА являются [H], [B], [A] и [BS], поэтому остальные состояния удаляются.

Таким образом, M’ = ({[H], [B], [A], [BS]}, {0, 1}, F’, H, {[BS]}), где

F’([A], 1) = [BS] F’([H], 1) = [B]

F’([B], 0) = [A] F’([BS], 0) = [A]

Задачи лексического анализа

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

Лексический анализ важен для процесса компиляции по нескольким причинам:

a) замена в программе идентификаторов, констант, ограничителей и служебных слов лексемами делает представление программы более удобным для дальнейшей обработки;

b) лексический анализ уменьшает длину программы, устраняя из ее исходного представления несущественные пробелы и комментарии;

c) если будет изменена кодировка в исходном представлении программы, то это отразится только на лексическом анализаторе.

Выбор конструкций, которые будут выделяться как отдельные лексемы, зависит от языка и от точки зрения разработчиков компилятора. Обычно принято выделять следующие типы лексем: идентификаторы, служебные слова, константы и ограничители. Каждой лексеме сопоставляется пара (тип_лексемы, указатель_на_информацию_о_ней).

Соглашение: эту пару тоже будем называть лексемой, если это не будет вызывать недоразумений.

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

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

Например, идентификатор (I):

I  a | b| ...| z | Ia | Ib |...| Iz | I0 | I1 |...| I9

целое без знака (N):

N 0 | 1 |...| 9 | N0 | N1 |...| N9

и т.д.

Для грамматик этого класса, как мы уже видели, существует простой и эффективный алгоритм анализа того, принадлежит ли заданная цепочка языку, порождаемому этой грамматикой. Однако перед лексическим анализатором стоит более сложная задача: он должен сам выделить в исходном тексте цепочку символов, представляющую лексему, а также преобразовать ее в пару (тип_лексемы, указатель_на_информацию_о_ней). Для того, чтобы решить эту задачу, опираясь на способ анализа с помощью диаграммы состояний, введем на дугах дополнительный вид пометок - пометки-действия. Теперь каждая дуга в ДС может выглядеть так:

Смысл t_i прежний - если в состоянии A очередной анализируемый символ совпадает с t_i для какого-либо i = 1, 2 ,... n, то осуществляется переход в состояние B; при этом необходимо выполнить действия D₁, D₂, ... ,D_m.

Лексический анализатор для М-языка

Вход лексического анализатора - символы исходной программы на М-языке; результат работы - исходная программа в виде последовательности лексем (их внутреннего представления).

Лексический анализатор для модельного языка будем писать в два этапа: сначала построим диаграмму состояний с действиями для распознавания и формирования внутреннего представления лексем, а затем по ней напишем программу анализатора.

Первый этап: разработка ДС.

Представление лексем: все лексемы М-языка разделим на несколько классов; классы перенумеруем:

• служебные слова - 1,

• ограничители - 2,

• константы (целые числа) - 3,

• идентификаторы - 4.

Внутреннее представление лексем - это пара (номер_класса, номер_в_классе). Номер_в_классе - это номер строки в таблице лексем соответствующего класса.

Характеристики

Список файлов книги