Теория и реализация языков программирования


         

где P1 состоит из правил


(4) Положить G1 = ((N
Ne)
{S}, T, P1, S), где P1 состоит из правил множества P, содержащих только символы из Ne
T,

Чтобы устранить все бесполезные символы, необходимо применить к исходной грамматике сначала Алгоритм 4.2, а затем Алгоритм 4.1.

Пример. Все символы следующей грамматики

S
AS | b

A
AB

B
a

являются достижимыми. Поэтому нарушение предложенного порядка применения к ней алгоритмов приведет лишь к частичному решению задачи.

КС-грамматика без бесполезных символов называется приведенной. Легко видеть, что для любой КС-грамматики существует эквивалентная приведенная. В дальнейшем будем предполагать, что все рассматривамые грамматики - приведенные.


Содержание  Назад  Вперед