Пример: автоматная грамматика:
G= (V= {a, b, e}, N= {A, B, S}, S, R).
R:
S® aS
S® bA
A® aB
|
B® bA
B® a
Рассмотрим граф данной автоматной грамматики. Вершинами этого графа являются нетерминалы.
Если дуга идет из вершины А в вершину В, и помечена символом «а», то в грамматике есть правило А® аВ.
Вводится дополнительная вершина, называющаяся конечной (К). Если в эту вершину идет дуга из вершины А, помеченная символом «а», то значит в грамматике существует правило А®а.
Для записи грамматики и алгоритмов часто используется R-графы (или R-схемы), ГОСТ 19.005.85. Это тот же граф, вытянутый в сторону, использующий спец. обозначения.
Для записи алгоритмов по R-схеме используется следующее обозначение: над дугой пишется условие прохождения по дуге, под дугой – действие, которое выполняется, если это условие истинно.
Последовательная операция:
Параллельная операция:
Петля:
|
|
Вложенная структура Е, если она описана:
Действия, выполненные без условия:
Условие прохода по дуге, описывает правильность конструкции (иначе – ошибка).
Вопросы и упражнения
Построить R-граф лексического блока языка Милан.