Приведенные грамматики

Грамматика называется приведенной, если она не содержит приведенных символов.

Символ называется бесполезным, если:

• Из него не может быть получена конечная цепочка.
• Символ не может быть получен при выводе.

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

Алгоритм определение непроизводящих символов:

• Составить множество нетерминальных символов, для которых правая часть правил содержит только терминалы или пусто.
• Если существует правило, для которого правая часть содержит терминальные символы нетерминальные символы включенные множества на предыдущем шаге, то дополнить множество левым нетерминалом.
• Пункт 2 выполнять до тех пор, пока множество не перестанет пополняться.

Символы не вошедшие в множество называются непроизводящими. Правило их содержащие должны быть исключены.

Пример 1:

I -> ABC
A -> int | char
B -> iR
R -> ,iR | i
C -> ;

Решение:

1. A,C,R
2. A,C,R,B
3. A,C,R,B,I

Так как все нетерминальные символы входят в множество допустимых нетерминалов, то грамматика не содержит непроизводящих символов.

Пример 2:

I -> aIa
I -> bAd
I -> c
A -> aBd
B -> dA

Решение:

1. I
2. I+I = I
3. Множество не пополняется, следовательно, все остальные (A,B) является непроизводящие, следовательно, их нужно исключить.

Итак,

I -> aIa
I -> c

Пример 3:

I -> i=AB
A ->iR
A ->(A)R
R ->+A
R ->$

Решение:

1. R
2. R, A
3. R, A

Правило 1 (I -> i=AB) нужно исключить.

Недостижимые символы – это символы, которые не участвуют в выводе. Правило, содержащее недостижимые символы, должны быть исключены из грамматики. Алгоритм определение недостижимых символов.

• Включить множество начальных символов грамматики I.
• Если в правой части грамматики содержатся терминальные символы и нетерминальные символы уже вошедшие в список, то дополнить множество левым нетерминалом данного правила.
• Шаг 2 повторять до тех пор, пока множество не перестанет пополняться.

Пример 1:

I -> ABC
A -> int | char
B -> iR
R -> ,iR | i
C -> ;

Решение:

1. I
2. I, A, B, C
3. I, A, B, C, R. То есть все символы являются производящими.