Детерминированные автоматы с магазинной памятью

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

(МП-автоматы)

Есть «промежуточная» математическая модель между автоматами и контекстно-свободными грамматиками – автомат с магазинной памятью. (МП-автомат).

Существует достаточно распространенная задача – задача определения парности скобок. Однако ее нельзя представить автоматной грамматикой.

Соответсвующая грамматика может выглядеть следующим образом:

S®(S)

S®SS

S®e

МП-автомат состоит из входной ленты, в ячейках которой записывается анализируемая строка (┤-конец строки), устройства управления и разбитого на ячейки магазина (стека). Ñ - символ пустого магазина. Устройство управления автомата может )."помнить" состояние (S1…).

Требуется распознать: ( ( ) ( ) )

( ( ) ( ) ) ┤

Ñ

Работу автомата можно описать программой.

Здесь и далее используются обозначения:

¯a - поместить строку a в вершину магазина.

a - заменить верхний символ магазина на строку a.

­a - убрать символ из вершины магазина.

® - сдвинуться на шаг вправо по входной строке.

> < - стоять на месте.

¾ - отвергнуть.

+ - принять.

S - State - состояние МП-автомата (на каждое состояние своя таблица, здесь одно состояние S1).

Ñ [S1] ( ( ) ( ) ) ┤

­

xÑ [S1] ( ( ) ( ) ) ┤

­

xxÑ [S1] ( ( ) ( ) ) ┤

­

xÑ [S1] ( ( ) ( ) ) ┤

­

xxÑ [S1] ( ( ) ( ) ) ┤

­

xÑ [S1] ( ( ) ( ) ) ┤

­

Ñ [S1] ( ( ) ( ) ) ┤

­

Задача распознавания вложенных скобок "типа матрешка" сложнее и для ее распознавания требуется МП-автомат с двумя состояниями:

( ( ( ) ) )

При встрече первой закрывающей скобки МП автомат меняет состояние S₁ на состояние S₂.