Грамматика с фразовой структурой — формальная грамматика , алгебраическая структура, состоящая из упорядоченной четвёрки G=(N, T, P, S) и определённой на ней неявно операцией конкатенации.

• N — конечное множество нетерминальных символов
• T — не пересекающееся с N конечное множество терминальных символов
• P — набор ограничивающих правил (продукций)
• S — стартовый (начальный символ)

Пример Грамматикой, порождающей язык {0 ⁿ 1 ⁿ | 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

Ссылки