Граф автоматной грамматики

Пример: автоматная грамматика:

G= (V= {a, b, e}, N= {A, B, S}, S, R).

R:

S® aS

S® bA

A® aB

Построим цепочку a= aaabab. S® aS ® aaS® aaaS® ®aaabA® aaabaB® aaababA® ®aaabab

A® e

B® bA

B® a

 

Рассмотрим граф данной автоматной грамматики. Вершинами этого графа являются нетерминалы.

Если дуга идет из вершины А в вершину В, и помечена символом «а», то в грамматике есть правило А® аВ.

Вводится дополнительная вершина, называющаяся конечной (К). Если в эту вершину идет дуга из вершины А, помеченная символом «а», то значит в грамматике существует правило А®а.

 

 

Для записи грамматики и алгоритмов часто используется R-графы (или R-схемы), ГОСТ 19.005.85. Это тот же граф, вытянутый в сторону, использующий спец. обозначения.

 

 

Для записи алгоритмов по R-схеме используется следующее обозначение: над дугой пишется условие прохождения по дуге, под дугой – действие, которое выполняется, если это условие истинно.

 

Последовательная операция:

 

 

Параллельная операция:

 

Петля:

 

 

Вложенная структура Е, если она описана:

 

 

Действия, выполненные без условия:

 

 

Условие прохода по дуге, описывает правильность конструкции (иначе – ошибка).

 

Вопросы и упражнения

Построить R-граф лексического блока языка Милан.