Детерминированная контекстно-свободная грамматика против контекстно-свободной грамматики?
Я читаю свои заметки для моего класса сравнительных языков, и я немного запутался...
В чем разница между контекстно-свободной грамматикой и детерминированной контекстно-свободной грамматикой? Я специально читаю о том, как парсеры O(n^3) для CFG и компиляторы O(n) для DCFG, и не очень понимаю, как разница во временных сложностях может быть настолько велика (не говоря уже о том, что я до сих пор не уверен, какие характеристики делают CFG DCFG).
Огромное спасибо заранее!
1 ответ
Концептуально они довольно просты для понимания. Контекстные грамматики - это те, которые могут быть выражены в BNF. DCFG - это подмножество, для которого можно написать работающий парсер.
При написании компиляторов нас интересуют только DCFG. Причина в том, что "детерминистический" означает примерно, что следующее правило, которое будет применено в любой точке анализа, определяется входными данными и конечным количеством ожидающих результатов. Кнут изобрел LR() компилятор еще в 1960-х и доказал, что он может обрабатывать любые DCFG. С тех пор некоторые уточнения, особенно LALR(1) и LL(1), определили грамматики, которые можно анализировать в ограниченной памяти, и методы, с помощью которых мы можем их записать.
У нас также есть методы для автоматического получения парсеров из BNF, если мы знаем, что это одна из этих грамматик. Yacc, Bison и ANTLR являются знакомыми примерами.
Я никогда не видел парсера для NDCFG, но в любой момент разбора ему потенциально нужно было бы рассмотреть всю входную строку и каждый возможный разбор, который мог бы быть применен. Нетрудно понять, почему это будет довольно большим и медленным.
Я должен отметить, что многие настоящие языки несовершенны, так как они не полностью свободны от контекста, не являются однозначными и не отличаются от идеальной DCFG. C/C++ хороший пример, но есть много других. Эти языки обычно обрабатываются специальными правилами, такими как семантические или синтаксические предикаты, обратный отслеживание в особых случаях или другие "уловки", не влияющие на производительность.
В комментариях отмечается, что некоторые виды NDCFG распространены, и многие инструменты предоставляют способ справиться с ними. Одной из распространенных проблем является двусмысленность. Разобрать неоднозначную грамматику относительно просто, введя простое локальное семантическое правило, но, конечно, это может когда-либо генерировать только одно из возможных деревьев разбора. Обобщенный синтаксический анализатор для NDCFG потенциально может создать все деревья синтаксического анализа и, возможно, разрешить фильтрацию этих деревьев при некоторых произвольных условиях. Я не знаю ни одного из них.
Левая рекурсия не является особенностью NDCFG. Это создает особую проблему при разработке парсеров LL(), но не создает проблем для парсеров LR().