LR-анализатор ( англ. LR parser ) — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования , который читает входной поток слева ( L eft) направо и производит наиболее правую ( R ight) продукцию контекстно-свободной грамматики . Используется также термин LR( k )-анализатор , где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе. Обычно k равно 1 и часто опускается.

Синтаксис многих языков программирования может быть определён грамматикой, которая является LR(1) или близкой к этому, и по этой причине LR-анализаторы часто используются компиляторами для выполнения синтаксического анализа исходных кодов.

Обычно на анализатор ссылаются в связи с именем того языка, исходный код которого он разбирает, например, «C++ анализатор» разбирает исходные коды языка C++ .

LR-анализатор может быть создан из контекстно-свободной грамматики программой, называемой , или же написан вручную программистом. Контекстно-свободная грамматика классифицируется как LR( k ), если существует LR( k )-анализатор для неё, как определено генератором анализаторов.

Говорится, что LR-анализатор выполняет , потому что он пытается вывести продукцию верхнего уровня грамматики, строя её из листьев .

— это язык, для которого существует какая-либо LR( k ) грамматика. Каждая LR( k ) грамматика может быть автоматически преобразована в грамматику LR( 1 ) для того же языка, в то время как LR( 0 ) грамматики для некоторых языков может не существовать. LR( 0 )-языки являются собственным подмножеством детерминированных.

LR-анализатор основан на алгоритме, приводимом в действие таблицей анализа , структурой данных, которая содержит синтаксис анализируемого языка. Таким образом, термин LR-анализатор на самом деле относится к классу анализаторов, которые могут разобрать почти любой язык программирования, для которого предоставлена таблица анализа. Таблица анализа создаётся генератором синтаксических анализаторов.

LR-анализ может быть обобщён как произвольный анализ контекстно-свободного языка без потери производительности, даже для LR(k) грамматик. Это происходит благодаря тому, что большинство языков программирования могут быть выражены LR( k ) грамматикой, где k — малая константа (обычно 1). Заметьте, что разбор не-LR(k) грамматик на порядок медленнее (кубический вместо квадратичного в отношении размера входного потока).

LR-анализ может применяться к большему количеству языков, чем LL-анализ , а также лучше в части сообщения об ошибках, то есть он определяет синтаксические ошибки там, где вход не соответствует грамматике, как можно раньше. В отличие от этого, LL(k) (или, что хуже, даже LL(*)) анализаторы могут задерживать определение ошибки до другой ветки грамматики из-за отката, часто затрудняя определение места ошибки в местах общих длинных префиксов.

LR-анализаторы сложно создавать вручную и обычно они создаются генератором синтаксических анализаторов или компилятором компиляторов . В зависимости от того, как была создана таблица анализа, эти анализаторы могут быть названы простыми LR-анализаторами (SLR), LR-анализаторами с предпросмотром (LALR) или каноническими LR-анализаторами . имеют значительно большую распознавательную способность, чем . При этом таблицы для SLR-анализа имеют такой же объём, что и для LALR-анализа, поэтому SLR-анализ уже не используется. Канонические LR-анализаторы имеют незначительно большую распознавающую способность, чем LALR-анализаторы, однако требуют намного больше памяти для таблиц, поэтому их используют очень редко ^{[ источник не указан 2917 дней ]} .

См. также

• GLR-парсер

Ссылки