Формальные грамматики

Определение 2.1. Формальной грамматикой называется четверка вида:

, (1.1)

где V_N - конечное множество нетерминальных символов грамматики (обычно прописные латинские буквы);

V_T - множество терминальных символов грамматики (обычно строчные латинские буквы, цифры, и т.п.), V_T Ç V_N =Æ;

Р – множество правил вывода грамматики, являющееся конечным подмножеством множества (V_TÈ V_N) ⁺ ´ (V_TÈ V_N) ^*; элемент (a, b) множества Р называется правилом вывода и записывается в виде a ® b (читается: «из цепочки a выводится цепочка b»);

S – начальный символ грамматики, S Î V_N.

Для записи правил вывода с одинаковыми левыми частями вида используется сокращенная форма записи .

Пример 2.1. Опишем с помощью формальных грамматик синтаксис паскалеподобного модельного языка М. Грамматика будет иметь правила вывода вида:

P ® program D 2 B.

D 2 ® var D 1

D 1 ® D | D 1; D

D ® I 1: int | I 1: bool

I 1 ® I | I 1, I

B ® begin S 1 end

S 1 ® S | S 1; S

S ® begin S 1 end | if E then S else S | while E do S | read (I) | write (E)

E ® E 1 | E 1= E 1 | E 1> E 1 | E 1< E 1

E l ® T | T + E 1 | T - E 1 | T Ú E l

T ® F | F * T | F / T | F Ù T

F ® I | N | L | Ø F | (E)

L ® true | false

I ® C | IC | IR

N ® R | NR

C ® a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | w | x | y | z

R ® 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

Дата добавления: 2015-11-14