Головна

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

  1.  IV. Перехід займенників в інші частини мови
  2.  LL (1) - граматики.
  3.  LR - граматики
  4.  P-n-перехід
  5.  P-n-перехід в стані термодинамічної рівноваги
  6.  P-n-перехід під впливом зовнішнього напруги
  7.  P_ n перехід в рівноважному стані

Праволінейная граматика - Граматика з правилами виду:

A ® a

A ® aВ

де A, B I VN , AI 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

4b ®b правило 4.

4c ®bS

       
 
{
 
 } EEE


2a S ® b

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

2c E ® e.

}


{
 3a S ® a

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

 




 машини Тьюринга |  Нормальні алгорифм Маркова |  Нормальна схема преобразуемое |  рекурсивні функції |  L-числення |  Поняття формальної граматики |  дерева виведення |  Класифікація мов по Хомського |  розпізнають автомати |  поняття транслятора |

© um.co.ua - учбові матеріали та реферати