Грамматика с фразовой структурой — формальная грамматика, алгебраическая структура, состоящая из упорядоченной четвёрки 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.
Ссылки Формальные грамматики и языки. Элементы теории трансляции / И.А. Волкова, А.А. Вылиток, Т.В. Руденко // учеб. пос. ВМК МГУ. - М.: МГУ, 2009. - 115 с. ISBN 978-5-89407-395-8. Теория алгоритмов и математическая логика
Категория:Грамматика Категория:Обработка естественного языка