Переход от праволинейной грамматики к автоматной

Праволинейная грамматика - грамматика с правилами вида:

A ® a

A ® aВ

где A, B Î V_N, aÎ V^*_T

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

Пример:

Дана праволинейная грамматика:

1. S®aA

2. S®bc

3. S®A

4. A®abbS

5. A®cA

6. A®E

Правила 2, 3, 4 – нарушают требования к автоматным грамматикам.

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

} { 4a A®a<bbS> 4b <bbS>®b<bS> правило 4. 4c <bS>®bS

	{		}ÈÈÈ

2a S ® b<cE>

2b <cE> ® cE правило 2.

2c E ® e.

}

{

3a S ® a<bbS>

3b S ® cA правило 3

3c S ® e

LEX

lex и yacc - программы, содержащие средства для написания компилятора.

lex – программа (в терминах UNIX – команда) лексического анализа облегчает задачу выделения лексем.

yacc - программа синтаксического анализа.

Структура lex – программ:

%{ Вставка фрагмента программы на Си

%}

Раздел деклараций: имя_значение.

%%

Раздел правил: шаблон_действие.

%%

Пользовательский код.

Раздел деклараций:

%token лексемы

Раздел правил:

нетерминал: | цепочка символов { код на Си }

;

%%

start: ‘x’ lettera ‘y’ lettera ‘\n’ { (printf(“Ok\n”); }

;

lettera: ‘z’ letterb

| ‘z’

;

letterb: ‘,’ ‘z’ letterb

| ‘,’ ‘z’

;

Пример 1:

%%

yyerror(str)

char *str;

{ printf(“error: %s”,str); }

yylex()

{

int c=getchar();

return(c);

}

main()

{ yyparse();}

____________________prog.y

%token X Y Z P

%%

text: start

| text start

start: X lettera Y lettera (printf(“Ok”);)

;

lettera: Z

| Z P lettera

;

%%

yyerror(str)

char *str;

{ printf(“error: %s”,str); }

____________________prog.1

%{

#include “y.tab.h”

%}

%%

x {return(X);}

y {return(Y);}

z {return(Z);}

[,] {return(P);}

. {return(yytext[0]);}

%%

main()

{ uuparse(); }

Для выполнения необходимы следующие действия:

$ yacc -d prog.y

# генерируется y.tab.c, содержащий основную программу

# по -d создается y.tab.h, в котором описываются макросы X Y Z P

$ lex prog.1

# создается lex.yy.c с функцией yylex - распознаватель лексем

# используется в функции yyparse

$ cc -o prog y.tab.c lex.yy.c

$ prog

Пример 2:

digit [0-9]

letter [a-z A-Z]

%%

{digit}+_{printf(“const\n”);

return (const);}

{letter}({letter}|{digit})*{printf(“var\n”);return(var);}

“+” | ”-” | ”*” | ”/”{printf(“zn\n”);

return(zn);}

“=“_{printf(“eq\n”);

return(eq);}

Если ввести а1=а1+с3-13 будет var

eq

var

zn

var

zn

const