Выводы цепочек формального языка. Деревья КСГ

 

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

Рассмотрим грамматику с аксиомой грамматики < S > и правилами вывода вида:

1. S ® a A B c 2. S ® e 3. A ® c S B

2. 4. A ® A b 5. B ® b B 6. B ® a

Если начать вывод цепочек языка, используя первое правило, то последовательность подстановок может быть следующей:

· S® a A Bc ( 1 правило )

· S® a A b B c ( 5 правило )

· S® a A b b a c ( 6 правило )

· S® a c S B b b a c ( 3 правило )

· S® a c S a b b a c ( 6 правило )

· S ® a c e a b b a c ( 2 правило )

В рассмотренном выводе присутствует семь цепочек, включая начальную и заключительную.

 

Определение. Язык, задаваемый грамматикой, есть множество терминальных цепочек, которые можно вывести из начального символа грамматики.

 

Построим дерево вывода цепочки: a c a b a c , используя выше рассмотренную грамматику.

 

S

 

aA B c

 

A b a

c S B

 

e a

 

Замечание. Для каждого дерева существует единственный левый и правый выводы, то есть вывод, когда на каждом шаге заменяется самый левый (правый) нетерминальный символ. Многие методы обработки языков рассчитаны исключительно на левый (правый) выводы. В подобных случаях пишут:

a ® _LB (L - left)

a ® _RB (R - right ).

 

Цепочке языка может соответствовать более чем одно дерево, так как она может иметь разные выводы, порождающие разные деревья. Если одна цепочка имеет несколько деревьев вывода, то говорят, что соответствующая грамматика неоднозначна.