В последнее время мне было весело исследовать разработку синтаксических анализаторов языка в контексте того, как они вписываются в иерархию Хомского.
Что является хорошим реальным (то есть не теоретическим) примером контекстно-зависимой грамматики?
language-design
parsing
grammar
Эван Плейс
источник
источник
Ответы:
Хороший вопрос. Хотя, как упоминалось в комментариях, очень многие языки программирования являются контекстно-зависимыми, эта контекстно-зависимая часто решается не на этапе синтаксического анализа, а на более поздних этапах, то есть надмножество языка анализируется с использованием контекстно-свободной грамматики, и некоторые из этих деревьев разбора позже отфильтровываются.
Однако это не означает, что эти языки не зависят от контекста , поэтому вот несколько примеров:
Haskell позволяет вам определять функции, которые используются в качестве операторов, а также определять приоритет и ассоциативность этих операторов. Другими словами, вы не можете построить правильное дерево разбора для выражения оператора, такого как:
если вы уже не анализировали объявления приоритета / ассоциативности для
@@
и##
:Вторым примером является Bencode , язык данных, который ставит контент перед префиксом:
Проблема с этим форматом заключается в том, что практически невозможно проанализировать без чего-либо контекстно-зависимого, потому что единственный способ выяснить размеры «поля» - это ... проанализировать строку.
Третий пример - XML, при условии, что допускаются произвольные имена тегов: имена открывающих тегов должны иметь совпадающие закрытые теги:
источник
До тех пор , как я знаю, контекстно-зависимые грамматики используются при обработке естественного языка, только . Интерпретаторы и компиляторы языков программирования не пытаются анализировать грамматику без контекста из-за сложности (даже если в прошлом была предпринята некоторая попытка).
Возможно, вы можете найти пример реального использования в одной из этих библиотек:
http://en.wikipedia.org/wiki/List_of_natural_language_processing_toolkits
http://opennlp.sourceforge.net/projects.html
http://nltk.org/
http://nlp.stanford.edu/nlp/javadoc/javanlp/
источник
Контекстно-зависимые грамматики иногда используются в описаниях семантики языка программирования. Возможно, наиболее всесторонним использованием контекстно-зависимых грамматик было определение языка Algol68. Он использовал контекстную два уровня бесплатно грамматику (см http://en.wikipedia.org/wiki/Two-level_grammar ) для описания как синтаксиса и семантики программ Algol68.
Несколько моих коллег использовали ван Вейнгаарденом грамматику , чтобы направить их реализацию Algol68 (см http://en.wikipedia.org/wiki/FLACC ).
источник