Грамматика - это набор структурных правил для строк в формальных языках, который семантически описывает не строки, а их форму. Все мы знаем, что к разным языкам применяются разные правила грамматики. Применяются ли эти грамматики только к строкам? Можем ли мы приложить усилия, чтобы применить эти грамматики для формирования и понимания различных типов диаграмм? Да, в этом блоге мы рассмотрим, как грамматики могут использоваться для определения простых диаграмм.

Формальная грамматика состоит из конечного набора производственных правил в следующей форме.
Левая часть → Правая часть.
Производство позволяет взять строку, содержащую переменные в LHS, и заменить их справа от продукции, где каждая сторона состоит из конечной последовательности символов.
* Начальный символ
* Набор нетерминальных символов
* Набор нетерминальных символов

Пример - Правила производства:
S → AB
S → ε (ε - пустая строка)
A → aS
B → b
где, S - начало символ, {a, b} - терминальный набор, а {S, A, B} - нетерминальный набор.

Типы грамматик

Обычно существует четыре типа грамматики, как указано ниже.
1. Тип 0: неограниченная грамматика
2. Тип 1: контекстно-зависимая грамматика
3. Тип 2: контекстно-зависимая грамматика
4 Тип 4: Обычная грамматика

В нашем блоге мы собираемся больше сосредоточиться на грамматике типа 2, которая является контекстно-свободной грамматикой для определения простых диаграмм.

Контекстно-свободная грамматика: введение
Формальное определение контекстно-свободной грамматики - это 4-кортеж (V, Σ, S, P), где:
• V - конечное набор переменных
• Σ - конечный алфавит терминалов
• S - начальная переменная
• P - конечный набор продукций, каждое производство имеет вид V → (V ∪ Σ) *

пример:
S → 0S1
S → ε
Производным может быть:
S ⇒ 0S1 ⇒ 00S11 ⇒ 0011, а строка 0011 находится на языке, созданном с помощью правил грамматики.

Индивидуальное правило подстановки может быть рекурсивным, так что один и тот же нетерминал может существовать как в правой, так и в левой части уравнения. Пример правила, обладающего этим свойством, - B → BC.

В нашем контексте грамматики представлены в форме, называемой нормальной формой Хомского. Это
накладывает несколько дополнительных ограничений на формат правил замены. Грамматика находится в нормальной форме Хомского, если все правила подстановки имеют вид:
A → BC, A → d или A → ε. Здесь A, B, C - нетерминалы, d - терминал, а
ε - пустая строка.
Начальный нетерминал не может существовать справа от любого правила подстановки. Это означает, что B и C не могут быть начальным символом.

Использование контекстно-свободной грамматики для определения диаграмм

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

1. S → S | SF | FF | ε
2. F → CC | CL | FL
3. C → LL
4. L → l

Без терминалов
S - Начальный график
F - Рисунок (замкнутая или открытая структура из более чем двух линий)
C - Две линии, которые касаются друг друга в один конец.
L - Линия
Терминал
l - это представление прямых линий, образующих структуру.

Все приведенные выше правила производства должны удовлетворять некоторым пространственным отношениям, таким как отношения касания или перекрытия между каждым элементом. Третье правило подразумевает образование соединения с двумя линиями, когда они соприкасаются друг с другом. Второе правило подразумевает, что фигура может быть образована комбинацией двух соединений, соединения и линии или фигуры и линии, когда они имеют прикоснуться к соединению друг с другом.
Первое правило подразумевает начальную диаграмму (полную диаграмму) посредством соединения более чем фигуры посредством рекурсивности.

Это простой способ определения тригонометрических диаграмм с помощью контекстно-свободной грамматики. Теперь я надеюсь, что вы также сможете начать писать грамматики для простых типов диаграмм. Вы также можете проверить правильность своей грамматики с помощью этого инструмента.

Ссылки

Https://en.wikipedia.org/wiki/Chomsky_hierarchy
https://www.tutorialspoint.com/automata_theory/chomsky_classification_of_grammars.htm