парсер LR
В компьютерных науках парсеры LR — это тип восходящего парсера , который анализирует детерминированные контекстно-свободные языки за линейное время. [1] Существует несколько вариантов парсеров LR: парсеры SLR , парсеры LALR , парсеры Canonical LR(1) , парсеры Minimal LR(1) и парсеры GLR . Парсеры LR могут быть сгенерированы генератором парсеров из формальной грамматики , определяющей синтаксис анализируемого языка. Они широко используются для обработки компьютерных языков ..
Синтаксический анализатор LR ( слева направо, крайний правый вывод в обратном порядке) читает входной текст слева направо без резервного копирования (это справедливо для большинства парсеров) и производит самый правый вывод в обратном порядке: он выполняет восходящее преобразование . синтаксический анализ — не синтаксический анализ LL сверху вниз или специальный синтаксический анализ. За именем LR часто следует числовой определитель, например, LR(1) или иногда LR( k ) . Чтобы избежать обратного отслеживания или угадывания, синтаксическому анализатору LR разрешено предварительно просматривать k входных символов , прежде чем принимать решение о том, как анализировать более ранние символы. Обычноk равно 1 и не упоминается. Имени LR часто предшествуют другие квалификаторы, например SLR и LALR . Обозначение LR( k ) для грамматики было предложено Кнутом для обозначения «переводимой слева направо с привязкой k ». [1]
Парсеры LR детерминированы; они производят один правильный анализ без догадок или возвратов за линейное время. Это идеально для компьютерных языков, но синтаксические анализаторы LR не подходят для человеческих языков, которым нужны более гибкие, но неизбежно более медленные методы. Некоторые методы, которые могут анализировать произвольные контекстно-свободные языки (например, Кока-Янгера-Касами , Эрли , GLR ), в худшем случае имеют производительность O( n 3 ) времени. Другие методы, которые возвращаются назад или дают несколько синтаксических анализов, могут даже занимать экспоненциальное время, когда они плохо угадывают. [2]
Вышеупомянутые свойства L , R и k на самом деле являются общими для всех синтаксических анализаторов сдвиг-свертка , включая синтаксические анализаторы приоритета . Но по соглашению имя LR обозначает форму синтаксического анализа, изобретенную Дональдом Кнутом , и исключает более ранние, менее мощные методы приоритета (например , анализатор приоритета оператора ). [1] Синтаксические анализаторы LR могут обрабатывать более широкий спектр языков и грамматик, чем синтаксические анализаторы приоритета или нисходящий синтаксический анализ LL . [3]Это связано с тем, что синтаксический анализатор LR ждет, пока он не увидит весь экземпляр некоторого грамматического шаблона, прежде чем фиксировать то, что он нашел. Синтаксический анализатор LL должен решить или угадать, что он видит, намного раньше, когда он увидит только самый левый входной символ этого шаблона.
Синтаксический анализатор LR сканирует и анализирует входной текст за один прямой проход по тексту. Синтаксический анализатор строит дерево синтаксического анализа постепенно, снизу вверх и слева направо, без угадывания или возврата. В каждой точке этого прохода синтаксический анализатор накапливает список поддеревьев или фраз входного текста, которые уже были проанализированы. Эти поддеревья еще не объединены, поскольку синтаксический анализатор еще не достиг правого конца шаблона синтаксиса, который будет их объединять.
На шаге 6 в примере синтаксического анализа только "A*2" был проанализирован не полностью. Существует только заштрихованный нижний левый угол дерева синтаксического анализа. Ни один из узлов дерева синтаксического анализа с номером 7 и выше еще не существует. Вершины 3, 4 и 6 являются корнями изолированных поддеревьев для переменной A, оператора * и числа 2 соответственно. Эти три корневых узла временно хранятся в стеке синтаксического анализа. Оставшаяся не проанализированная часть входного потока равна «+ 1».
