Математическая теория формальных языков
Неоднозначность в контекстно-свободных грамматиках
Перейдем к более богатому классу языков - к контекстно-свободным языкам. Они находят применение в разнообразных программных продуктах, таких как компиляторы, средства форматирования исходного кода, средства статического анализа программ, синтаксические редакторы, системы верстки, программы просмотра форматированного текста поисковые системы.
Начнем рассмотрение контекстно-свободных языков с введения понятия деревьев вывода, что позволит определить важное для компьютерных приложений понятие однозначности контекстно-свободной грамматики. Чтобы не вдаваться в детали определения изоморфизма ориентированных деревьев, будем использовать в определении однозначности понятие левостороннего вывода (раздел 7.2). Соответствие деревьев вывода и левосторонних (а также правосторонних) выводов понадобится также в лекции 13.
Из класса всех контекстно-свободных языков можно выделить подкласс тех языков, для которых существует хотя бы одна однозначная грамматика. В разделе 7.3* доказывается, что все праволинейные (то есть автоматные) языки принадлежат этому подклассу.
В последнем разделе этой лекции приводятся важные конкретные примеры однозначных контекстно-свободных грамматик, моделирующих системы правильно вложенных скобок и польскую (префиксную) запись выражений.
