В литературном смысле этого термина грамматики обозначают синтаксические правила общения на естественных языках. Лингвистика пыталась определить грамматику с момента появления естественных языков, таких как английский, санскрит, мандарин и т. Д.
Теория формальных языков находит широкое применение в области компьютерных наук. Ноам Хомский дал математическую модель грамматики в 1956 году, которая эффективна для написания компьютерных языков.
грамматика
Грамматика G может быть формально записана в виде 4-х кортежей (N, T, S, P), где —
-
N или V N — это набор переменных или нетерминальных символов.
-
T или ∑ — это набор символов терминала.
-
S — это специальная переменная, называемая символом начала, S ∈ N
-
P — Правила производства для терминалов и нетерминалов. Производственное правило имеет вид α → β, где α и β — строки на V N ∪ ∑, и хотя бы один символ α принадлежит V N.
N или V N — это набор переменных или нетерминальных символов.
T или ∑ — это набор символов терминала.
S — это специальная переменная, называемая символом начала, S ∈ N
P — Правила производства для терминалов и нетерминалов. Производственное правило имеет вид α → β, где α и β — строки на V N ∪ ∑, и хотя бы один символ α принадлежит V N.
пример
Грамматика G1 —
({S, A, B}, {a, b}, S, {S → AB, A → a, B → b})
Вот,
-
S, A и B — нетерминальные символы;
-
a и b являются терминальными символами
-
S — начальный символ, S ∈ N
-
Производства, P: S → AB, A → a, B → b
S, A и B — нетерминальные символы;
a и b являются терминальными символами
S — начальный символ, S ∈ N
Производства, P: S → AB, A → a, B → b
пример
Грамматика G2 —
(({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})
Вот,
-
S и A — нетерминальные символы.
-
a и b являются терминальными символами.
-
ε — пустая строка.
-
S — начальный символ, S ∈ N
-
Производство P: S → aAb, aA → aaAb, A → ε
S и A — нетерминальные символы.
a и b являются терминальными символами.
ε — пустая строка.
S — начальный символ, S ∈ N
Производство P: S → aAb, aA → aaAb, A → ε
Выводы из грамматики
Строки могут быть получены из других строк с использованием произведений в грамматике. Если грамматика G имеет произведение α → β , мы можем сказать, что x α y выводит x β y в G. Этот вывод записывается как —
x α y ⇒ G x β y
пример
Давайте рассмотрим грамматику —
G2 = ({S, A}, {a, b}, S, {S → aAb, aA → aaAb, A → ε})
Некоторые из строк, которые могут быть получены:
S ⇒ aA b с использованием продукции S → aAb
⇒ a aA bb с использованием продукции aA → aAb
⇒ aaa A bbb с использованием производства aA → aAb
⇒ aaabbb с использованием продукции A → ε