LR-анализатор

LR-анализатор (англ. LR parser) — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин 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-анализаторами. LALR-анализатор имеют значительно большую распознавательную способность, чем SLR-анализаторы. При этом таблицы для SLR-анализа имеют такой же объём, что и для LALR-анализа, поэтому SLR-анализ уже не используется. Канонические LR-анализаторы имееют незначительно большую распознавательную способность, чем LALR-анализаторы, однако требуют намного больше памяти для таблиц, поэтому их используют очень редко.

См. также

• GLR-парсер

Отрывок, характеризующий LR-анализатор

– Мне смешно, – сказал Пьер, – что вы себя, вы себя считаете неспособным, свою жизнь – испорченною жизнью. У вас всё, всё впереди. И вы…
Он не сказал, что вы , но уже тон его показывал, как высоко ценит он друга и как много ждет от него в будущем.
«Как он может это говорить!» думал Пьер. Пьер считал князя Андрея образцом всех совершенств именно оттого, что князь Андрей в высшей степени соединял все те качества, которых не было у Пьера и которые ближе всего можно выразить понятием – силы воли. Пьер всегда удивлялся способности князя Андрея спокойного обращения со всякого рода людьми, его необыкновенной памяти, начитанности (он всё читал, всё знал, обо всем имел понятие) и больше всего его способности работать и учиться. Ежели часто Пьера поражало в Андрее отсутствие способности мечтательного философствования (к чему особенно был склонен Пьер), то и в этом он видел не недостаток, а силу.
В самых лучших, дружеских и простых отношениях лесть или похвала необходимы, как подмазка необходима для колес, чтоб они ехали.
– Je suis un homme fini, [Я человек конченный,] – сказал князь Андрей. – Что обо мне говорить? Давай говорить о тебе, – сказал он, помолчав и улыбнувшись своим утешительным мыслям.
Улыбка эта в то же мгновение отразилась на лице Пьера.
– А обо мне что говорить? – сказал Пьер, распуская свой рот в беззаботную, веселую улыбку. – Что я такое? Je suis un batard [Я незаконный сын!] – И он вдруг багрово покраснел. Видно было, что он сделал большое усилие, чтобы сказать это. – Sans nom, sans fortune… [Без имени, без состояния…] И что ж, право… – Но он не сказал, что право . – Я cвободен пока, и мне хорошо. Я только никак не знаю, что мне начать. Я хотел серьезно посоветоваться с вами.
Князь Андрей добрыми глазами смотрел на него. Но во взгляде его, дружеском, ласковом, всё таки выражалось сознание своего превосходства.
– Ты мне дорог, особенно потому, что ты один живой человек среди всего нашего света. Тебе хорошо. Выбери, что хочешь; это всё равно. Ты везде будешь хорош, но одно: перестань ты ездить к этим Курагиным, вести эту жизнь. Так это не идет тебе: все эти кутежи, и гусарство, и всё…
– Que voulez vous, mon cher, – сказал Пьер, пожимая плечами, – les femmes, mon cher, les femmes! [Что вы хотите, дорогой мой, женщины, дорогой мой, женщины!]
– Не понимаю, – отвечал Андрей. – Les femmes comme il faut, [Порядочные женщины,] это другое дело; но les femmes Курагина, les femmes et le vin, [женщины Курагина, женщины и вино,] не понимаю!
Пьер жил y князя Василия Курагина и участвовал в разгульной жизни его сына Анатоля, того самого, которого для исправления собирались женить на сестре князя Андрея.
– Знаете что, – сказал Пьер, как будто ему пришла неожиданно счастливая мысль, – серьезно, я давно это думал. С этою жизнью я ничего не могу ни решить, ни обдумать. Голова болит, денег нет. Нынче он меня звал, я не поеду.
– Дай мне честное слово, что ты не будешь ездить?
– Честное слово!


Уже был второй час ночи, когда Пьер вышел oт своего друга. Ночь была июньская, петербургская, бессумрачная ночь. Пьер сел в извозчичью коляску с намерением ехать домой. Но чем ближе он подъезжал, тем более он чувствовал невозможность заснуть в эту ночь, походившую более на вечер или на утро. Далеко было видно по пустым улицам. Дорогой Пьер вспомнил, что у Анатоля Курагина нынче вечером должно было собраться обычное игорное общество, после которого обыкновенно шла попойка, кончавшаяся одним из любимых увеселений Пьера.
«Хорошо бы было поехать к Курагину», подумал он.
Но тотчас же он вспомнил данное князю Андрею честное слово не бывать у Курагина. Но тотчас же, как это бывает с людьми, называемыми бесхарактерными, ему так страстно захотелось еще раз испытать эту столь знакомую ему беспутную жизнь, что он решился ехать. И тотчас же ему пришла в голову мысль, что данное слово ничего не значит, потому что еще прежде, чем князю Андрею, он дал также князю Анатолю слово быть у него; наконец, он подумал, что все эти честные слова – такие условные вещи, не имеющие никакого определенного смысла, особенно ежели сообразить, что, может быть, завтра же или он умрет или случится с ним что нибудь такое необыкновенное, что не будет уже ни честного, ни бесчестного. Такого рода рассуждения, уничтожая все его решения и предположения, часто приходили к Пьеру. Он поехал к Курагину.
Подъехав к крыльцу большого дома у конно гвардейских казарм, в которых жил Анатоль, он поднялся на освещенное крыльцо, на лестницу, и вошел в отворенную дверь. В передней никого не было; валялись пустые бутылки, плащи, калоши; пахло вином, слышался дальний говор и крик.