Грамматика называется приведенной, если она не содержит приведенных символов.
Символ называется бесполезным, если:
- Из него не может быть получена конечная цепочка.
- Символ не может быть получен при выводе.
Если из символа не может быть выведена конечная цепочка, то он называется непроизводящим.
Алгоритм определение непроизводящих символов:
- Составить множество нетерминальных символов, для которых правая часть правил содержит только терминалы или пусто.
- Если существует правило, для которого правая часть содержит терминальные символы нетерминальные символы включенные множества на предыдущем шаге, то дополнить множество левым нетерминалом.
- Пункт 2 выполнять до тех пор, пока множество не перестанет пополняться.
Символы не вошедшие в множество называются непроизводящими. Правило их содержащие должны быть исключены.
Пример 1:
I -> ABC
A -> int | char
B -> iR
R -> ,iR | i
C -> ;
Решение:
- A,C,R
- A,C,R,B
- A,C,R,B,I
Так как все нетерминальные символы входят в множество допустимых нетерминалов, то грамматика не содержит непроизводящих символов.
Пример 2:
I -> aIa
I -> bAd
I -> c
A -> aBd
B -> dA
Решение:
- I
- I+I = I
- Множество не пополняется, следовательно, все остальные (A,B) является непроизводящие, следовательно, их нужно исключить.
Итак,
I -> aIa
I -> c
Пример 3:
I -> i=AB
A ->iR
A ->(A)R
R ->+A
R ->$
Решение:
- R
- R, A
- R, A
Правило 1 (I -> i=AB) нужно исключить.
Недостижимые символы – это символы, которые не участвуют в выводе. Правило, содержащее недостижимые символы, должны быть исключены из грамматики. Алгоритм определение недостижимых символов.
- Включить множество начальных символов грамматики I.
- Если в правой части грамматики содержатся терминальные символы и нетерминальные символы уже вошедшие в список, то дополнить множество левым нетерминалом данного правила.
- Шаг 2 повторять до тех пор, пока множество не перестанет пополняться.
Пример 1:
I -> ABC
A -> int | char
B -> iR
R -> ,iR | i
C -> ;
Решение:
- I
- I, A, B, C
- I, A, B, C, R. То есть все символы являются производящими.
Дата добавления: |
Просмотров: 7154 |
|