Русская Википедия:Грамматика с фразовой структурой
Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определённой на ней неявно операцией конкатенации.
- N — конечное множество нетерминальных символов
- T — не пересекающееся с N конечное множество терминальных символов
- P — набор ограничивающих правил (продукций)
- S — стартовый (начальный символ)
Пример Грамматикой, порождающей язык {0n1n | n≥0}, является G: G= ({S}, {0,1}, P, S), где P = {S→0S1, S→ε}.
Понятие выводимости: Если αβγ последовательный набор символов языка G, а β→δ правило этого языка, то αβγ=>αδγ (αδγ непосредственно выводима из αβγ в G).
Цепь — последовательное присваивание нетерминальных символов. Цикл — замкнутая цепь
x (x ∈ N) — недоступный символ, если x неэквивалентен стартовому символу S (x ≠ S) и не существует выводов типа S+→αxβ. Символ называется непродуктивным, если не существует строки γ, такой, что нетерминальный символ не будет присвоен γ (x→γ) Символ называется бесполезным, если он непродуктивен или недоступен.
Литература
- Ахо, Дж. Ульман «Теория синтаксического анализа, перевода и компиляции», Т.1 «Синтаксический анализ», М.: Мир, 1978
- Р. Хантер «Проектирование и конструирование компиляторов», ФиС, 1984
Ссылки
Шаблон:Нет иллюстрации Шаблон:Нет ссылок
