Возможен ли генератор синтаксического анализа типа 1 Хомского?
Глядя на иерархию грамматик Хомского, я обнаружил, что для грамматик типа 2 (контекстно-свободных грамматик) существуют очень хорошие инструменты, помогающие в создании программного обеспечения для чтения их из текста в пригодную для использования структуру данных в памяти. По моему опыту Antlr4 является одним из таких инструментов, которые делают это.
Недавно я столкнулся с Markdown, который оказывается контекстно-зависимой грамматикой (т. Е. Chomsky Type 1), и поэтому не существует определения грамматики для Antlr4. Смотрите здесь и здесь.
Так что мне было интересно;
- Есть ли инструмент, который помогает в создании синтаксического анализатора для контекстно-зависимой грамматики?
- Если нет, то возможно ли такое?
2 ответа
Большинство, если не все, языки программирования реального мира чувствительны к контексту. Типичный синтаксический анализатор принимает некоторые конструкции, которые впоследствии будут отклонены как нарушающие какое-то правило или ограничение, и / или полагаются на некоторую контекстно-зависимую предварительную обработку для создания анализируемого потока токенов. Языки макросов, такие как препроцессор C, очевидно, попадают в последнюю категорию, но в гораздо более контролируемом масштабе, как и сканер Python, который вставляет INDENT а также DEDENT жетоны. Примеры первого включают общее требование, чтобы переменные объявлялись перед использованием или чтобы вызовы функций имели такое же количество аргументов, как и параметры в прототипе. Статический тип анализа также попадает в эту категорию.
Таким образом, все практические парсеры в некоторой степени отклоняются от идеализированной модели, показанной в учебниках по теории формального языка. А практические генераторы синтаксических анализаторов, такие как bison и antlr, предоставляют настраиваемые хуки, которые позволяют индивидуально реализовать эти отклонения.
Короче говоря, генераторы синтаксических анализаторов могут быть полезны и используются для языков, которые "технически" контекстно-зависимы (и я использую пугающие кавычки, потому что контекстно-зависимая является бинарным атрибутом; либо есть, либо нет).
Было бы здорово избежать идиотских взломов, но проблема кажется неразрешимой. Поскольку контекстно-зависимый язык может моделировать машину Тьюринга, детерминированный анализ должен был бы решить проблему остановки. С другой стороны, существуют детерминированные алгоритмы синтаксического анализа для определенных подмножеств множества контекстно-зависимых языков, но, похоже, они не обеспечивают всей чувствительности к контексту, которая присутствует в практических языках. Нам все еще не хватает сладкого места между слишком сильным для анализа и слишком слабым, чтобы заменить хаки.
Это все еще плодотворная область исследований, и, возможно, у вас будет, чем заняться. Но если вы ищете что-то готовое, я боюсь, вы будете разочарованы.
Я действительно столкнулся с одним. Meta-S Квинн Тейлор Джексон, кажется, делает то, что ищет OP. В этой статье Википедии обсуждается это и ряд подобных систем, но meta-S кажется более практичным, чем большинство других обсуждаемых там: https://en.wikipedia.org/wiki/Adaptive_grammar
В Quora я анализирую, как это на практике противостоит анализаторам GLR: https://www.quora.com/What-is-the-most-powerful-parser-algorithm