Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 28 стр.

UptoLike

Составители: 

S bSS bbSSbSS bbaabaa;
S bSS bbSSbSS bbbSSbSSbbSSbSS ...
Из полученных цепочек видно, что:
а) цепочки всегда начинаются с терминала b, кроме аксиомы, и заканчиваются
терминалом а;
б) количество терминалов а в любой цепочке всегда на 1 больше, чем b.
Исходя из этих выводов, определим язык, порождаемый заданными правилами,
следующим образом:
L(G) = {α | α {a, b}*}, |a| = |b| + 1, причем цепочки начинаются с терминала b и
заканчиваются терминалом а.
4.4. Грамматический разбор
В КС-грамматике может быть несколько выводов, эквивалентных в том смысле, что в
них применяются одни и те же правила к одинаковым в промежуточном выводе цепочкам,
но в различном порядке. Например, для грамматики G с правилами вывода S ScS|b|a
возможны следующие эквивалентные выводы терминальной цепочки acb: S ScS
Scb acb и S ScS acS acb.
Деревом вывода цепочки х в КС-грамматике G = (V
T
, V
N
, Р, S) называется
упорядоченное дерево, каждая вершина которого помечена символом из множества V
V
N
{ε} так, что каждому правилу А b
1
b
2
b
3
... b
k
, использующемуся при выводе цепочки х, в
дереве вывода соответствует поддерево с корнем А и прямыми потомками b
1
, b
2
, b
3
, ..., b
k
,
которое приведено на рисунке:
A
b
1
b
2
… b
k
В силу того, что цепочка х L(G) выводится из аксиомы S, корнем вывода всегда
является аксиома. Внутренние узлы вывода соответствуют нетерминальным символам.
Концевые вершины дерева вывода - листья - это вершины, не имеющие потомков. Такие
вершины соответствуют либо терминалам, либо пустым символам (ε) при условии, что среди
правил грамматики имеются правила с пустой правой частью. При чтении слева направо
концевые вершины дерева вывода образуют цепочку х.
Дерево вывода часто называют деревом грамматического разбора, или
синтаксическим деревом, а процесс построения дерева вывода - грамматическим разбором
(синтаксическим анализом). Одной цепочке языка может соответствовать больше одного
дерева, так как эта цепочка может иметь разные выводы, порождающие разные деревья.
КС-грамматика G == (V
T
, V
N
, Р, S) называется неоднозначной (неопределенной), если
существует цепочка х L(G), имеющая два или более дерева вывода.
Рассмотрим пример.
Пусть даны две КС-грамматики:
G
1
= (V
T
, V
N
, Р
1
, S), V
N
= {S},
P
1
={S S+S | S | SS | (S) | a};
G
2
= (V
T
, V
N
, Р
2
, S), V
N
= {S, A, B},
P
2
= {S S + A | A | A, A AB | A / B | B, B a| (S)}, содержащие в множестве
терминальных символов знаки операций, круглые скобки и символ а. Определить, являются