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

void is_dlm (void); - если символ в буфере buf является разделителем, то формирует соответствующую лексему, иначе вызывает функцию обработки ошибок error();

void error(void); - функция обработки ошибок, которая выдает диагностическое сообщение и прекращает анализ входного текста.

Диаграмма состояний для лексического анализатора приведена на следующей странице.

Второй этап: по ДС пишем программу

#include <stdio.h>

#include <ctype.h>

#define BUFSIZE 80

extern ptabl TW, TID, TD, TNUM;

char buf[BUFSIZE]; /* для накопления символов лексемы */

int c; /* очередной символ */

int d; /* для формирования числового значения константы */

void clear(void); /* очистка буфера buf */

void add(void); /* добавление символа с в конец буфера buf*/

int look(ptabl); /* поиск в таблице лексемы из buf; результат: номер строки таблицы либо 0 */

int putl(ptabl); /* запись в таблицу лексемы из buf, если ее там не было; результат: номер строки таблицы */

int putnum(); /* запись в TNUM константы из d, если ее там не было; результат: номер строки таблицы TNUM */

int j; /* номер строки в таблице, где находится лексема, найденная функцией look */

void makelex(int,int); /* формирование и вывод внутреннего представления лексемы */

void id_or_word(void) { if (j=look(TW)) makelex(1,j);

else { j=putl(TID); makelex(4,j);}

}

void is_dlm(void) { if (j=look(TD)) {makelex(2,j); gc();}

else error();}

Замечание: символом N_x в диаграмме (и в тексте программы) обозначен номер лексемы x в ее классе.

void scan (void)

{enum state {H, ID, NUM, COM, ASS, DLM, ER, FIN};

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

FILE* fp;

TC = H;

fp = fopen("prog","r"); /* в файле "prog" находится текст исходной программы */

c = fgetc(fp);

do {switch (TC) {

case H:

if (c == ' ') c = fgetc(fp);

else if (isalpha(c))

{clear(); add(); c = fgetc(fp); TC = ID;}

else if (isdigit (c))

{d = c - '0'; c = fgetc(fp); TC = NUM;}

else if (c=='{') {c=fgetc(fp); TC = COM;}

else if (c == ':')

{c = fgetc(fp); TC = ASS;}

else if (c == '')

{makelex(2, N_); TC = FIN;}

else TC = DLM;

break;

case ID:

if (isalpha(c) || isdigit(c)) {add(); c=fgetc(fp);}

else {if (j = look (TW)) makelex (1,j);

else {j = putl (TID); makelex (4,j);};

TC = H;};

break;

case NUM:

if (isdigit(c)) {d=d*10+(c - '0'); c=fgetc (fp);}

else {makelex (3, putnum()); TC = H;}

break;

/* ........... */

} /* конец switch */

} /* конец тела цикла */

while (TC != FIN && TC != ER);

if (TC == ER) printf("ERROR !!!\n");

else printf("O.K.!!!\n");

}

Задачи.

33. Дана регулярная грамматика с правилами:

S  S0 | S1 | P0 | P1

P  N.

N  0 | 1 | N0 | N1 .

Построить по ней диаграмму состояний и использовать ДС для разбора цепочек : 11.010 , 0.1 , 01. , 100 . Какой язык порождает эта грамматика ?

34. Дана ДС.

1. Осуществить разбор цепочек 1011 , 10+011 и 0-101+1 .

2. Восстановить регулярную грамматику, по которой была построена данная ДС.

3. Какой язык порождает полученная грамматика ?

35. Пусть имеется переменная c и функция gc(), считывающая в с очередной символ анализируемой цепочки. Дана ДС с действиями:

1. Определить, что будет выдано на печать при разборе цепочки 1+101//p11+++1000/5?

2. Написать на Си анализатор по этой ДС.

36. Построить регулярную грамматику, порождающую язык

L = {(abb)^k| k >= 1},

по ней построить ДС, а затем по ДС написать на Си анализатор для этого языка.

37. Построить ДС, по которой в заданном тексте, оканчивающемся на , выявляются все парные комбинации <>, <= и >= и подсчитывается их общее количество.

38. Дана регулярная грамматика:

S  A

A  Ab | Bb | b

B  Aa

Определить язык, который она порождает; построить ДС; написать на Си анализатор.

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

*40. Даны две грамматики G1 и G2.

G1: S  0C | 1B G2: S  0D | 1B

B  0B | 1C |  B  0C | 1C

C  0C | 1C C  0D | 1D | 

D  0D | 1D

L1 = L(G1); L2 = L(G2).

Построить регулярную грамматику для:

1. L1L2

2. L1L2

3. L1^* \ {}

4. L2^* \ {}

5. L1L2

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

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

a) S  0S | 0B b) S  aA | aB | bA

B  1B | 1C A  bS

C  1C |  B  aS | bB | 

c) S  aB d) S  0B

B  aC | aD | dB B  1C | 1S

C  aB C  

D  

42. Для данной грамматики

1. определить ее тип;

2. какой язык она порождает;

3. написать Р-грамматику, почти эквивалентную данной;

4. построить ДС и анализатор на Си.

S  0S | S0 | D

D  DD | 1A | 

A  0B | 

B  0A | 0

43. Преобразовать грамматику к виду, допускающему детерминированный разбор (использовать алгоритм преобразования НКА к детерминированному КА). Какой язык порождает грамматика? Написать анализатор.

a) S  C b) S  C

B  B1 | 0 | D0 C  B1

C  B1 | C1 B  0 | D0

D  D0 | 0 D  B1

c) S  A0 *d) S  B0 | 0

A  A0 | S1 | 0 B  B0 | C1 | 0 | 1

C  B0

*e) S  A0 | A1 | B1 | 0 | 1 *f) S  S0 | A1 | 0 | 1

A  A1 | B1 | 1 A  A1 | B0 | 0 | 1

B A0 B  A0

*g) S  Sb | Aa | a | b

A  Aa | Sb | a

44. Грамматика G определяет язык L=L1L2, причем L1 L2 =. Написать регулярную грамматику G1, которая порождает язык L1*L2 (см. задачу 20). Для нее построить ДС и анализатор.

S  A

A  A0 | A1 | B1

B  B0 | C0 | 0

C  C1 | 1

*45. Даны две грамматики G1 и G2, порождающие языки L1 и L2. Построить регулярные грамматики для

1. L1  L2

2. L1  L2

3. L1 * L2 (см. задачу 20)

G1: S  S1 | A0 G2: S  A1 | B0 | E1

A  A1 | 0 A  S1

B  C1 | D1

C  0

D  B1

E  E0 | 1

Для полученной грамматики построить ДС и анализатор.

46. По данной грамматике G1 построить регулярную грамматику G2 для языка L1*L1 (см. задачу 20), где L1 = L(G1); по грамматике G2 - ДС и анализатор.

G1: S  S1 | A1

A  A0 | 0

47. Написать регулярную грамматику, порождающую язык:

1. L = { |   {0,1}^* , где за каждой 1 непосредственно следует 0};

2. L = {11 |   {0,1}⁺ , где все подряд идущие 0 – подцепочки нечетной длины};

по грамматике построить ДС, а по ДС написать на Си анализатор.

48. Построить лексический блок (преобразователь) для кода Морзе. Входом служит последовательность "точек", "тире" и "пауз" (например, ..--. .- ...- ). Выходом являются соответствующие буквы, цифры и знаки пунктуации. Особое внимание обратить на организацию таблицы.

Синтаксический и семантический анализ

На этапе синтаксического анализа нужно установить, имеет ли цепочка лексем структуру, заданную синтаксисом языка, и зафиксировать эту структуру. Следовательно, снова надо решать задачу разбора: дана цепочка лексем, и надо определить, выводима ли она в грамматике, определяющей синтаксис языка. Однако структура таких конструкций как выражение, описание, оператор и т.п., более сложная, чем структура идентификаторов и чисел. Поэтому для описания синтаксиса языков программирования нужны более мощные грамматики, чем регулярные. Обычно для этого используют укорачивающие контекстно-свободные грамматики (УКС-грамматики), правила которых имеют вид A  , где A  VN,
  (VT  VN)^*. Грамматики этого класса, с одной стороны, позволяют достаточно полно описать синтаксическую структуру реальных языков программирования; с другой стороны, для разных подклассов УКС-грамматик существуют достаточно эффективные алгоритмы разбора.

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

Существуют табличные методы анализа ([3]), применимые ко всему классу КС-грамматик и требующие для разбора цепочек длины n времени cn³ (алгоритм Кока-Янгера-Касами) либо cn² (алгоритм Эрли). Их разумно применять только в том случае, если для интересующего нас языка не существует грамматики, по которой можно построить анализатор с линейной временной зависимостью.

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

Метод рекурсивного спуска

Пример: пусть дана грамматика G =({a,b,c, }, {S,A,B}, P, S), где

P: S  AB

A  a | cA

B  bA

и надо определить, принадлежит ли цепочка caba языку L(G).

Построим вывод этой цепочки:

S  AB  cAB  caB  cabA  caba

Следовательно, цепочка принадлежит языку L(G).

Последовательность применений правил вывода эквивалентна построению дерева разбора методом "сверху вниз":

Метод рекурсивного спуска (РС-метод) реализует этот способ практически "в лоб": для каждого нетерминала грамматики создается своя процедура, носящая его имя; ее задача - начиная с указанного места исходной цепочки найти подцепочку, которая выводится из этого нетерминала. Если такую подцепочку считать не удается, то процедура завершает свою работу вызовом процедуры обработки ошибки, которая выдает сообщение о том, что цепочка не принадлежит языку, и останавливает разбор. Если подцепочку удалось найти, то работа процедуры считается нормально завершенной и осуществляется возврат в точку вызова. Тело каждой такой процедуры пишется непосредственно по правилам вывода соответствующего нетерминала: для правой части каждого правила осуществляется поиск подцепочки, выводимой из этой правой части. При этом терминалы распознаются самой процедурой, а нетерминалы соответствуют вызовам процедур, носящих их имена.

Пример: совокупность процедур рекурсивного спуска для грамматики
G = ({a,b,c,}, {S,A,B}, P, S), где

P: S  AB

A  a | cA

B  bA

будет такой: