ФЭНДОМ


Определение Править

Грамматика — способ описания некоторого формального языка. Более точно, грамматика - это упорядоченная тройка вида $ (A, S_0, F) $, где:

  • $ A $ - алфавит (множество символов), причём $ A = A_N \bigcup A_T $, $ A_N \bigcap A_T = \O $
    • $ A_N $ - множество нетерминальных символов
    • $ A_T $ - множество терминальных символов
    • $ W(A) $ - множество всех слов из $ A $, $ W(A) = \{ (a_1, a_2, \dots, a_n) \mid n \in {\mathbb N}, \forall i \in \overline {1, n}\ a_i \in A\} $
  • $ S_0 $ - начальное слово, $ S_0 \in W(A) $
  • $ F $ - множество записей вида $ X ::= Y $, где $ X, Y \in W(A) $

Таким образом, грамматика однозначно определяет некоторое множество слов, $ L \subseteq W(A) $.

Контекстно-свободная (бесконтекстная, context-free) грамматика - это такая грамматика, где $ F = \{"a ::= x" \mid a \in A_N, x \in W(A)\} $

Семантика Править

Так как грамматика описывает некоторый язык, с её помощью можно получить любое слово этого языка следующим образом. Рассмотрим слово $ S_0 $. Будем искать в нём такие подстроки, которые принадлежат первой компоненте $ X $ записей из $ F $. Иными словами, найдём следующее пересечение:

$ F_x = \{X \mid X \in W(A), \exists Y \in W(A) "X ::= Y" \in F\} $ - все первые компоненты записей из $ F $

$ \mbox {Substr}(s) = \{(z_1, z_2, \dots, z_n) \mid \exists l \in {\mathbb N_0} \forall k \in \overline {1, n}\ z_k = s_{l+k}\} $ - множество всех подстрок данной строки

$ P = F_x \bigcap \mbox {Substr}(S_0) $ - то, что мы ищем

Теперь распараллелим алгоритм на $ |P| $ веток и выполним его заново, заменив в $ S_0 $ каждую найденную подстроку на соответствующую ей по записи из $ F $. Любая строка, полученная на любой итерации алгоритма и состоящая только из терминальных символов, считается принадлежащей описываемому языку. Уточнение: алгоритм не обязан останавливаться, достигнув строки, принадлежащей языку - он может продолжать работу с этой строкой.

Примеры грамматикПравить

Терминальный алфавит:

Σ={'0','1','2','3','4','5','6','7','8','9','+','-','*','/','(',')'}.

Нетерминальный алфавит:

{ ФОРМУЛА, ЗНАК, ЧИСЛО, ЦИФРА }

Правила:

1. ФОРМУЛА ::= ФОРМУЛА ЗНАК ФОРМУЛА  (формула есть две формулы, соединенные знаком)
2. ФОРМУЛА ::= ЧИСЛО                 (формула есть число)
3. ФОРМУЛА ::= ( ФОРМУЛА )           (формула есть формула в скобках)
4. ЗНАК ::= + | - | * | /            (знак есть плюс или минус или умножить или разделить)
5. ЧИСЛО ::= ЦИФРА                   (число есть цифра)
6. ЧИСЛО ::= ЧИСЛО ЦИФРА             (число есть число и цифра)
7. ЦИФРА ::= 0 | 1 | 2 | 3 | 4 |
             5 | 6 | 7 | 8 | 9       (цифра есть 0 или 1 или ... 9 )

Начальный нетерминал:

ФОРМУЛА

Вывод:

Выведем формулу (12+5) с помощью перечисленных правил вывода. Для наглядности, стороны каждой замены показаны попарно, в каждой паре заменяемая часть подчеркнута.

ФОРМУЛА (ФОРМУЛА)
(ФОРМУЛА) (ФОРМУЛА ЗНАК ФОРМУЛА)
(ФОРМУЛА ЗНАК ФОРМУЛА) (ФОРМУЛА + ФОРМУЛА)
(ФОРМУЛА + ФОРМУЛА) (ФОРМУЛА + ЧИСЛО)
(ФОРМУЛА + ЧИСЛО) (ФОРМУЛА + ЦИФРА)
(ФОРМУЛА + ЦИФРА) (ФОРМУЛА + 5)
(ФОРМУЛА + 5) (ЧИСЛО + 5)
(ЧИСЛО + 5) (ЧИСЛО ЦИФРА + 5)
(ЧИСЛО ЦИФРА + 5) (ЦИФРА ЦИФРА + 5)
(ЦИФРА ЦИФРА + 5) (1 ЦИФРА + 5)
(1 ЦИФРА + 5) (1 2 + 5)$ [[Категория:Программирование]] $