Грамматика без контекста (CFG) G - это четверка (V, Σ, R, S), где
- V: набор нетерминальных символов
- Σ: набор клемм (V ∩ Σ = Ǿ)
- R: набор правил (R: V → (VU Σ) *)
- S: начальный символ
Пример CFG:
- V = {q, f,}
- Σ = {0, 1}
- R = {q → 11q, q → 00f, f → 11f, f → ε}
- S = q
- (R = {q → 11q | 00f, f → 11f | ε})
Насколько я понимаю, форма Бэкуса-Наура (BNF) - это еще один способ представления вещей, показанных в контекстно-свободной грамматике (CFG)
Пример BNF:
[число] :: = [цифра] |[число] [цифра]
[цифра] :: = 0 |1 |2 |3 |4 |5 |6 |7 |8 |9
, который можно прочитать как что-то вроде: «число - это цифра или любое число, за которым следует дополнительная цифра» (что является искаженным, но точным способом сказать, что число состоит из одной или нескольких цифр) "цифра - это любой из символов 0, 1, 2, ... 9"
Разница:
Обозначения этихдва представления немного отличаются, то есть
-> равно :: =
|равно или
должны быть и другие различия, но, если честно, я не знаю ничего другого:)
Вывод строки:
Пусть S будет символом начала
- S -> A, начальное состояние
- A -> 0A
- A -> 1B
- A ->?
- B -> 1B
- B ->?
Пример строкиВывод:
Генерирует ли эта грамматика строку 000111?
да, да!
- S -> A
- A-> 0A
- 0A -> 00A
- 00A -> 000A
- 000A -> 0001B
- 0001B -> 00011B
- 00011B -> 000111
Это все со моей стороны, я тоже над этим работаю и обязательно поделюсь, если узнаю больше подробностей об определении синтаксиса языка.
ура!