Различие между LL и Синтаксическим анализатором с рекурсивным спуском?
В чем разница
1.
public interface MyGlobalConstants {
public static final int TIMEOUT_IN_SECS = 25;
}
2.
public class MyGlobalConstants {
private MyGlobalConstants () {} // Prevents instantiation
public static final int TIMEOUT_IN_SECS = 25;
}
и используя MyGlobalConstants.TIMEOUT_IN_SECS везде, где нам нужна эта константа. Я думаю, что оба одинаковы.
1 ответ
LL обычно является более эффективным методом синтаксического анализа, чем рекурсивный спуск. Фактически, простой синтаксический анализатор с рекурсивным спуском будет на самом деле O (k ^ n) (где n - размер входных данных) в худшем случае. Некоторые методы, такие как мемоизация (которая дает синтаксический анализатор Packrat ), могут улучшить это, а также расширить класс грамматик, принимаемых синтаксическим анализатором, но всегда есть компромисс пространства. Анализаторы LL (насколько мне известно) всегда являются линейным временем.
С другой стороны, вы правы в своей интуиции, что синтаксические анализаторы с рекурсивным спуском могут обрабатывать больший класс грамматик, чем LL. Рекурсивный спуск может обрабатывать любую грамматику, которая является LL (*) (то есть неограниченный просмотр вперед), а также небольшой набор неоднозначных грамматик. Это связано с тем, что рекурсивный спуск на самом деле является реализацией PEG с прямым кодированием или грамматикой (граммами) выражения синтаксического анализатора . В частности, дизъюнктивный оператор ( a | b ) не коммутативен, что означает, что a | b не равно b | a . Парсер с рекурсивным спуском будет пробовать каждую альтернативу по порядку. Таким образом, если a соответствует вводу, он будет успешным, даже если b будет соответствовать вводу. Это позволяет обрабатывать классические неоднозначности «самого длинного совпадения», такие как проблема висячего else , просто путем правильного упорядочивания дизъюнкций.
С учетом всего вышесказанного, возможно реализовать LL (k) синтаксический анализатор, использующий рекурсивный спуск, так что он работает за линейное время. Это осуществляется путем встраивания наборов прогнозов, так что каждая процедура синтаксического анализа определяет соответствующее производство для данного ввода за постоянное время. К сожалению, такой метод исключает обработку целого класса грамматик. Как только мы перейдем к предиктивному синтаксическому анализу, такие проблемы, как dangling else , больше не будут решаться с такой легкостью.
Что касается того, почему LL предпочтительнее рекурсивного спуска, это в основном вопрос эффективности и ремонтопригодности. Синтаксические анализаторы с рекурсивным спуском значительно проще реализовать, но их обычно сложнее поддерживать, поскольку грамматика, которую они представляют, не существует ни в какой декларативной форме. В большинстве нетривиальных вариантов использования парсера используется генератор парсера, такой как ANTLR или Bison. С такими инструментами это действительно не так. Не имеет значения, является ли алгоритм алгоритмом прямого кодирования с рекурсивным спуском или алгоритмом LL (k), управляемым таблицей.
Интересно, что стоит также изучить рекурсивный спуск , который представляет собой синтаксический анализ алгоритм закодирован непосредственно по типу рекурсивного спуска, но способен обрабатывать любую грамматику LALR. Я бы также углубился в комбинаторы синтаксического анализатора , которые представляют собой функциональный способ объединения синтаксических анализаторов с рекурсивным спуском.