Синтаксические диаграммы КС-языков - Рисунок порядка КС-языков⁠⁠

Предыдущая статья: Автомат с магазинной памятью (стог-памятью) и КС-языки в vk.com

Статья для повторения:Синтаксические диаграммы автоматных языков - рисунок порядка автоматных языков в vk.com

Чтобы построить рисунок порядка по КС-грамматике следует соблюдать:

1. Каждому неконечному строится свой отдел, помеченный именем символа.

2. Неконечные из правил вывода вписывают в прямоугольники, а конечные в круги или овалы.

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

4. Ветви образованные одним неконечным, соединяются параллельно и образуют один отдел.

Рассмотрим правила: А → БвГд | а

Простейший случай А→ а, имеем ветвь из одного конечного символа а.
Продолжим:

Тут описана ветвь А → БвГд, Б и Г неконечные символы поэтому заключены в прямоугольники, в и д конечные поэтому в круги. Обе ветви следует объединить параллельно:

Отдел А завершён. Но мы имеем ещё два неконечных Б и Г, поэтому следует отобразить и их отделы. Пусть Б описывает Б → в | дБ , а Г → eБГ | ε. Отобразим их:

Почти закончили, обратите внимание на правила Б → дБ и Г → еБГ, что между ними общего? Внутри этих правил встречается одноименный неконечный символ и он находится справа от всех символов. Такие правила называют праворекурсивными. Для этих неконечных у нас есть альтернативы Б → в , Г → ε, что нам говорит о необязательности вхождения левых символов праворекурсивных правил. Мы можем упростить отделы избегая рекурсии (перепутья), заменяя на циклы:

Отобразим полный рисунок и на этом урок завершён.

З.Ы. ε (эпсилон) - это пустая цепочка, теперь более понятно воспринимаю книгу «О дивный новый мир». Подписывайся, пройденный урок поможет нам разобраться в рекурсивном спуске.