Интернет магазин китайских планшетных компьютеров

Компьютеры - Грамматика ван Вейнгаардена - История

В-грамматики основаны на идее дополнения нетерминальных символов КС-грамматик атрибутами, которые передают информацию между узлами дерева разбора, и используются для ограничения синтаксиса и указания семантики. Эта идея была хорошо известна в то время, в частности Дональд Кнут посетил комитет по разработке ALGOL 68 во время разработки собственной его версии. Интересной особенностью В-грамматик является их строгое отношение к атрибутам к строкам, задаваемым КС-грамматикой, в которой конкатенация является единственной возможной операцией. В грамматиках атрибутов атрибуты могут быть любого типа и к ним можно применить любую операцию.

После введения в отчёт об Algol 68, В-грамматики были сочтены слишком мощными и неограниченными для практического использования. Частично на это повлияло то, как они были применены, отредактированный отчёт об Algol 68 содержал намного более читаемую грамматику при неизменном собственно формализме В-грамматики.

В это время стало понятно, что В-грамматики действительно слишком мощны. Они являются полными по Тьюрингу, что делает невозможным их синтаксический анализ вообще: задача проверки, может ли данная строка быть порождена данной В-грамматикой, алгоритмически неразрешима. Использование их должно быть серьёзно ограничено для применения в автоматическом анализе или трансляции. Были разработаны ограниченные и модифицированные варианты В-грамматик для решения этой проблемы, в частности

• расширенный аффиксные грамматики, применяемые для описания грамматик естественных языков,
• Q-системы, также используемые для обработки естественных языков,
• серия языков Compiler Description Language, применяемых в качестве языков конструирования компиляторов языков программирования.