| dbo:abstract
|
- LR syntaktický analyzátor (anglicky LR parser) je v matematické informatice typ syntaktického analyzátoru zdola nahoru, který efektivně zpracovává deterministické bezkontextové jazyky v zaručeném lineárním čase.Jeho často používanými variantami jsou a . Pro vytváření LR syntaktických analyzátorů se často používají , které generují analyzátor mechanicky z formální gramatiky jazyka. Častěji než jiné druhy generovaných syntaktických analyzátorů se používají pro zpracování programovacích jazyků. Zkratku LR, případně LR(k) lze rozložit na jednotlivé složky: L znamená, že syntaktický analyzátor čte vstupní text v jednom směru bez návratu (tak funguje většina syntaktických analyzátorů) typicky zleva doprava. R znamená, že syntaktický analyzátor provádí syntaktickou analýzu zdola nahoru a produkuje , čímž se liší od velké skupiny analyzátorů provádějících syntaktickou analýzu shora dolů nebo ad-hoc. Zkratka LR je často následována číselným kvalifikátorem, např. LR(1) nebo LR(k). Aby se zamezilo backtrackingu nebo hádání, analyzátor se rozhoduje, jak analyzovat předchozí symboly, na základě náhledu na k dosud nezpracovaných vstupních symbolů. Nejčastěji bývá k rovno 1, a pak se neuvádí. Zkratku LR často předchází jiné kvalifikátory, jako SLR a LALR. LR syntaktické analyzátory jsou deterministické; produkují jedinou správnou syntaktickou analýzu bez hádání nebo návratu (anglicky backtracking) a pracují v lineárním čase. Díky tomu jsou ideální pro programovací jazyky. Lidské jazyky jsou naproti tomu nejednoznačné a vyžadují flexibilnější metody, které však jsou pomalejší. Příkladem je CYK algoritmus, Earleyův analyzátor a ), které provádějí návraty nebo dávají více analýz, a mohou mít časovou složitost O(n2), O(n3) nebo dokonce exponenciální, pokud provádějí špatné odhady. Výše uvedené vlastnosti L, R a k ve skutečnosti mají všechny , včetně jednoduchého . Označení LR se však používá pouze pro třídu analyzátorů, které poprvé popsal Donald Knuth, nikoli na dřívější, méně výkonné precedenční metody (například ).LR syntaktický analyzátor může zpracovávat větší obor jazyků a gramatik než precedenční syntaktický analyzátor nebo analyzátor shora dolů. Je to způsobeno tím, že syntaktický analyzátor LR má pro rozhodování, jaké pravidlo použít, k dispozici celou instanci nějakého vzorku gramatiky. LL syntaktický analyzátor se naproti tomu musí rozhodnout a odhadnout, jaké pravidlo použít, mnohem dříve, v okamžiku, kdy viděl pouze první symbol zleva v tomto vzorku. LR je také lepší v oznamování chyb. Syntaktické chyby ve vstupním proudu detekuje hned, jak je to možné. (cs)
- مجزئ يسار يمين في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. مصطلح LR(k) parser يستخدم أيضاً؛ حيث K تشير إلى عدد الغير مستهلك "look ahead" رموز المدخلات التي تستخدم في صنع القرارات التحليل. عادة ما تكون K هي 1 والعبارة LR parser عادة ما تستخدم للإشارة إلى هذه الحالة. القواعد اللغوية لكثير من لغات البرمجة يمكن تحديدها بقواعد هي LR(1) أو ما يقارب ذلك، ولهذا السبب LR parsers غالبا ما تستخدم من قبل برامج المترجم لإجراء تحليل القواعد اللغوية من شفرة المصدرsource code. LR parser يمكن إنشاءه من context-free grammar من خلال برنامج يسمى parser generator (مولد المحلل) أو مكتوب بخط اليد من قبل . قواعد السياق الحر context-free grammar يصنف كـ LR(k) إذا كان هناك محلل LR(k) له، على النحو الذي يحدده مولد المحلل parser generator. ويقال أن LR parser لإجراء تحليل من أسفل إلى أعلى لأنه يحاول أستخلاص إنتاجات أعلى مستوى نحوي عن طريق البناء من الأوراق. قواعد السياق الحر الحتمية deterministic context-free language هي لغة يوجد بها بعض قراعد LR(k) كل قواعد LR(k) k > 1 يمكن أن تحول ميكانيكيا إلى قواعد LR(1) لنفس اللغة، في حين أن قواعد LR(0) لنفس اللغة قد لا تكون موجودة، لغات LR(0) هي مجموعة فرعية مناسبة من تلك الحتمية. LR parser مبنى على خوارزمية (أو لوغرتمية) التي يقودها جدول محلل parser table، تركيبة البيانات التي تحتوي على قواعد لغة الكمبيوتر التي يتم تحليلها. حتى المصطلح LR parser في الواقع يشير لفئة من المحلل التي يمكن أن تقوم بمعالجة تقريباً أي لغة برمجة، ما دام جدول المحلل متوفر للغة البرمجة. يتم إنشاء جدول المحلل بواسطة برنامج يسمى مولد المحلل parser generator. LR parsing يمكن تعميمها كلغة سياق حر تعسفية تحلل بدون عقوبة للتشغيل، حتى لقواعد LR(k). هذا لان معظم لغات البرمجة يمكن التعبير عنها بقواعدLR(k). حيث أن K وثابت صغير (عادة يكون1). علما بأن تحليل القواعد الغير LR(k) هو أمر ضخم أبطأ (المكعب بدلا من التربيعي بالنسبة لطول الإدخال). LR parsing يمكن أن تتعامل مع أكبر مجموعة من اللغات من LL parsing، وهي أيضا أفضل في التقرير عن الخطأ، أي أنه يكشف الأخطاء النحوية عندما لاتتفق المدخل مع القواعد في أقرب وقت ممكن. هذا على النقيض مع LL(k) (أو أسوأ من ذلك، محلل LL(*) parser) والتي قد تؤجل الكشف عن الخطأ إلى فرع مختلفة من القواعد بسبب التراجع، مما يؤدى الي صعوبة تحديد موقع الخطأ عبر المفارق في البادئات المشتركة الطويلة. LR parsers صعب إنتاجها باليد، وعادة ما تنتج بمولد المحلل أو مترجم-مترجمcompiler-compiler. اعتمادا على كيفية إنشاء جدول التحليل، هذه المحللات يمكن أن تسمى محللات LR بسيطة simple LR parsers (SLR)، محللات LR النظر إلى الامام look-ahead LR parsers (LALR), أو محللات LR المقننة canonical LR parsers. محللات LALR لديها قوة أعتراف لغوي بها أكثر من SLR. بينما المحللات LR المقننة canonical LR parsers لديها قوة أعتراف بها أكثر من LALR. (ar)
- Im Compilerbau ist ein LR-Parser ein Bottom-up-Parser für LR-Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. (de)
- Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de dispositivos para manipular algunas gramáticas libres de contexto. Pertenecen a la familia de los analizadores ascendentes, ya que constituyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento de reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico. Un analizador LR consta de: 1.
* Un programa conductor 2.
* Una entrada 3.
* Una salida 4.
* Una tabla de análisis sintáctico, compuesta de dos partes (ACCIÓN y GOTO). Cabe acotar que el programa conductor es siempre igual, variando solo la tabla de análisis sintáctico para cada lenguaje. El algoritmo para reconocer cadenas es el siguiente: dado el primer carácter de la cadena y el estado inicial de la tabla, buscar qué acción corresponde en la tabla de acción. Si el estado es shiif n (n ∈ N), se coloca el carácter y el número de estado n en la pila, se lee el siguiente carácter y se repite el procedimiento, solo que esta vez buscando en el estado correspondiente. Si ACCIÓN = REDUCE n (n ∈ N), se sacan de la pila tantas tuplas (estado, símbolo) como el largo de la cola de la producción en el n-ésimo lugar y se reemplaza por la cabeza de esta producción. Se obtiene el nuevo estado al buscar en la tabla GOTO mediante el uso del número de estado que quedó en el tope de la pila, y el no terminal en la cabeza. En la tabla ACCIÓN también se encontrará ACEPTAR (que toma la cadena como válida) y se termina el análisis o ERROR (que rechaza la cadena). (es)
- Comme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine). Sur le plan de l'informatique théorique, un analyseur LR (en anglais : Left to right, Rightmost derivation ) est un analyseur pour les grammaires non contextuelles qui lit l'entrée de gauche à droite (d'où le L de Left to right) et produit une dérivation droite (d'où la dénomination Rightmost qui signifie que les motifs spécifiés par la grammaire sont recherchés parmi les suffixes de la séquence de mots lue, donc sur la partie la plus à droite de cette séquence). Cette analyse a été inventée en 1965 par Donald Knuth (l'auteur du célèbre ouvrage: The art of programming). On parle aussi d'analyseur LR(k) où k représente le nombre de symboles « anticipés » (examinés dans la chaîne analysée sans être consommés) qui sont utilisés pour prendre des décisions d'analyse syntaxique. Comme usuellement k vaut 1, il est souvent omis. Une grammaire non contextuelle est appelée LR(k) s'il existe un analyseur syntaxique LR(k) pour elle. On dit qu'un analyseur syntaxique LR réalise une analyse ascendante car il essaye de déduire les productions du niveau du haut de la grammaire en les construisant à partir des feuilles. De nombreux langages de programmation sont décrits par des grammaires LR(1), ou du même genre, et, pour cette raison, les analyseurs syntaxiques LR sont souvent utilisés par les compilateurs pour faire l'analyse syntaxique de code source. Typiquement, quand on se réfère à un analyseur syntaxique LR, on parle d'un analyseur syntaxique capable de reconnaître un langage particulier spécifié par une grammaire non contextuelle. Cependant, dans l'usage courant, on utilise le terme pour parler d'un programme pilote qui peut être appelé avec une certaine table et qui produit un large éventail d'analyseurs syntaxiques LR différents. On devrait plutôt appeler ces programmes générateurs d'analyseurs syntaxiques. L'analyse syntaxique LR a plusieurs avantages :
* de nombreux langages de programmation peuvent être analysés en utilisant une variante d'analyseur syntaxique LR. Une exception notable est C++ ;
* les analyseurs syntaxiques LR peuvent être implémentés très efficacement ;
* de tous les analyseurs syntaxiques qui parcourent leur entrée de gauche à droite, les parseurs LR détectent les erreurs de syntaxe (c'est-à-dire quand les entrées ne sont pas conformes à la grammaire) le plus tôt possible. Les analyseurs syntaxiques LR sont difficiles à produire à la main ; ils sont généralement construits par des générateurs d'analyse syntaxique ou des compilateurs de compilateurs. Suivant la manière dont la table d'analyse syntaxique est générée, ces analyseurs syntaxiques sont appelés analyseurs syntaxiques LR simples (SLR pour Simple LR parser), analyseurs syntaxiques LR avec anticipation (LALR pour Look-Ahead LR parser), et . Ces types d'analyseurs syntaxiques peuvent traiter des ensembles de grammaires de plus en plus grands ; les analyseurs syntaxiques LALR peuvent traiter plus de grammaires que les SLR. Les analyseurs syntaxiques canoniques fonctionnent sur davantage de grammaires que les analyseurs syntaxiques LALR. Le très connu Yacc produit des analyseurs syntaxiques LALR. Bien que la confusion soit fréquente, on ne doit pas confondre un analyseur LR avec un générateur d'analyseurs LR. Par exemple l'outil Yacc qui vient d'être cité n'est pas un analyseur LR à proprement parler mais bien un générateur d'analyseurs LR. Les deux notions se distinguent par leurs entrées-sorties. Un générateur d'analyseurs LR prend en entrée une grammaire et produit le code source de l'analyseur LR pour cette grammaire (et/ou des alertes/erreurs portant sur l’ambiguïté intrinsèque de la grammaire donnée en entrée). Tandis qu'un analyseur LR proprement dit prend en entrée une chaîne de caractères et produit en sortie un verdict (portant sur la conformité de cette chaîne à la grammaire ayant servi à produire cet analyseur) et éventuellement un produit de génération (un arbre d'analyse, une autre chaîne). (fr)
- In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers, and GLR parsers. LR parsers can be generated by a parser generator from a formal grammar defining the syntax of the language to be parsed. They are widely used for the processing of computer languages. An LR parser (Left-to-right, Rightmost derivation in reverse) reads input text from left to right without backing up (this is true for most parsers), and produces a rightmost derivation in reverse: it does a bottom-up parse – not a top-down LL parse or ad-hoc parse. The name LR is often followed by a numeric qualifier, as in LR(1) or sometimes LR(k). To avoid backtracking or guessing, the LR parser is allowed to peek ahead at k lookahead input symbols before deciding how to parse earlier symbols. Typically k is 1 and is not mentioned. The name LR is often preceded by other qualifiers, as in SLR and LALR. The LR(k) notation for a grammar was suggested by Knuth to stand for "translatable from left to right with bound k." LR parsers are deterministic; they produce a single correct parse without guesswork or backtracking, in linear time. This is ideal for computer languages, but LR parsers are not suited for human languages which need more flexible but inevitably slower methods. Some methods which can parse arbitrary context-free languages (e.g., Cocke–Younger–Kasami, Earley, GLR) have worst-case performance of O(n3) time. Other methods which backtrack or yield multiple parses may even take exponential time when they guess badly. The above properties of L, R, and k are actually shared by all shift-reduce parsers, including precedence parsers. But by convention, the LR name stands for the form of parsing invented by Donald Knuth, and excludes the earlier, less powerful precedence methods (for example Operator-precedence parser).LR parsers can handle a larger range of languages and grammars than precedence parsers or top-down LL parsing. This is because the LR parser waits until it has seen an entire instance of some grammar pattern before committing to what it has found. An LL parser has to decide or guess what it is seeing much sooner, when it has only seen the leftmost input symbol of that pattern. (en)
- Nell'informatica, un parser LR è un parser di tipo Bottom-up per grammatiche libere da contesto, usate molto di frequente nei compilatori dei linguaggi di programmazione (e degli altri strumenti associati). Un Parser LR legge il proprio input partendo da sinistra (Left) verso destra, producendo una derivazione destra (Rightmost Derivation). A volte questo parser viene anche indicato col nome "Parser LR(k) dove k si riferisce al numero di simboli letti (ma non "consumati") utilizzati per prendere le decisioni di parsing. Tipicamente k ha valore 1 ed è spesso omesso. Una grammatica libera da contesto è chiamata LR(k) se esiste un parser LR(k) adatto ad essa. Nell'uso tipico, quando ci si riferisce a un parser LR significa che si sta parlando di un particolare parser in grado di riconoscere un linguaggio specifico in una grammatica libera da contesto. Non è tuttavia insolito che ci si riferisca a un parser LR intendendo un programma che, fornita una tabella "ad hoc", sia in grado di produrre un ampio numero di LR distinti. Il parsing LR ha parecchi benefici:
* Parecchi linguaggi di programmazione possono essere parsificati usando varianti del parser LR. Notevoli eccezioni sono C++ e Perl.
* Il parser LR può esser implementato in modo estremamente efficiente.
* Tra tutti i tipi di parser che scandiscono il loro input da sinistra verso destra, il parser LR è quello in grado di identificare gli errori sintattici (ovvero quando l'input non è conforme alla grammatica) più rapidamente. Creare un parser LR a mano è parecchio difficile; solitamente essi sono creati usando dei generatori di parser. In base a come la tabella di parsing viene generata, questi parser possono essere anche parser SLR o . Con questi tipi di parser si ha a che fare con un'ampia varietà di grammatiche aumentate; il parser LALR ad esempio è in grado di riconoscere un numero maggiore di grammatiche rispetto ad un SLR. Il famoso Yacc produce parser di tipo LALR. (it)
- LR法またはLR構文解析器とは、文脈自由文法の構文解析手法/構文解析器である。LR法では、入力を左(Left)から右に読んでいき、右端導出(Rightmost derivation)を行う。このためLRと名づけられている。「LR(k)」といった場合、k は、消費をともなうことなく「先読み」が進められる入力記号の最大数を意味する。通常、k は 1 であり、その場合省略されることが多い。LR(k)の構文解析器が対応する文脈自由文法も LR(k) と呼ばれる。 (ja)
- Um analisador sintático LR (também chamado parser LR) é um algoritmo de análise sintática para gramáticas livres de contexto. Ele lê a entrada de texto da esquerda para a direita e produz uma derivação mais à direita (por isso LR, do termo em inglês left-right, diferente do analisador sintático LL). Outro termo usado é analisador sintático LR(x), no qual refere-se à quantidade de símbolos posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Geralmente esse valor é 1, sendo omitido. Uma gramática livre de contexto é chamada LR(x) se existe uma analisador sintático LR(x) para ela. Um analisador sintático LR é dito um analisador sintático de ascendente (bottom-up) pois ele tenta deduzir as produções da gramática a partir dos nós folha da árvore. Várias linguagens de programação são descritas por uma gramática LR(1), ou pelo menos parecida, e por isso os analisadores sintáticos LR são geralmente usados por compiladores para realizar a análise sintática do código fonte. Uma exceção notável é a linguagem de programação C++. Os analisadores sintáticos LR podem ser implementados muito eficientemente, o que é muito útil para compiladores, por exemplo. Raramente são produzidos manualmente, sendo geralmente construídos por um gerador de análise sintática ou um compilador de compiladores. Dependendo da forma como a tabela de análise sintática é gerada, o analisador é chamado SLR (simples), LALR (quando há análise de símbolos posteriores) e canônico (ou LR(1)). Os analisadores LALR podem lidar com mais tipos de gramáticas que o SLR; o canônico pode lidar com mais tipos de gramáticas que o LALR. (pt)
- 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-анализаторами. имеют значительно большую распознавательную способность, чем . При этом таблицы для SLR-анализа имеют такой же объём, что и для LALR-анализа, поэтому SLR-анализ уже не используется. Канонические LR-анализаторы имеют незначительно большую распознавающую способность, чем LALR-анализаторы, однако требуют намного больше памяти для таблиц, поэтому их используют очень редко. (ru)
- Parser LR (ang. Left to right, identifying the Rightmost production) – analizator składniowy dla gramatyk bezkontekstowych, który przetwarza wejście od lewej do prawej metodą wstępującą i produkuje prawostronne wyprowadzenie. Terminu parser LR(k), gdzie k jest liczbą naturalną lub zerem, używa się do oznaczenia analizatorów podejmujących decyzje na podstawie k podglądanych symboli na wejściu, użytych w podjęciu decyzji. Zwykle k jest równe 1 i jest często pomijane. Parser SLR i parser LALR również są typu LR, jednak pod pojęciem LR(k) zwykle mamy na myśli "kanoniczny parser LR(k)". W typowym użyciu "parser LR" oznacza konkretny parser zdolny rozpoznać konkretny język określony gramatyką bezkontekstową. Gramatyka bezkontekstowa nazywa się gramatyką LR(k), jeżeli istnieje dla niej parser LR(k). Mówimy że parser LR wykonuje analizę metodą wstępującą (ang. bottom-up), ponieważ próbuje wyprowadzić produkcję najwyższego poziomu poprzez analizowanie liści. Analizowanie typu LR przynosi następujące korzyści:
* parsery LR są często używane przez kompilatory do uprzedniej analizy składniowej (syntaktycznej) kodu źródłowego (wyjątkiem jest C++);
* parsery LR mogą być zaimplementowane bardzo wydajnie;
* parsery LR wykrywają błędy składniowe (wejście nie zgadza się z gramatyką!) tak szybko jak to możliwe. Parsery LR są trudne do ręcznego zaprogramowania, dlatego są one zwykle konstruowane przez generator parserów. W zależności od tego jak jest generowana tabela parsingu, wyróżnia się następujące parsery LR: parser SLR (Simple LR ), LALR (Look-Ahead LR) i kanoniczny parser LR. Zbiory gramatyk określone przez te rodzaje parserów mają następującą własność: . (pl)
- LR剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。LR意指由左（Left）至右處理輸入字串，並以最右邊優先衍生（Right derivation）的推導順序（相對於LL剖析器）建構語法樹。能以此方式剖析的語法稱為LR語法。而在LR(k)這樣的名稱中，k代表的是剖析時所需前瞻符號（lookahead symbol）的數量，也就是除了目前處理到的輸入符號之外，還得再向右參照幾個符號之意；省略 （k）時即視為LR(1)，而非LR(0)。 由於LR剖析器嘗試由剖析樹的葉節點開始，向上一層層透過文法規則的化簡，最後规约回到樹的根部（起始符號），所以它是一種由下而上的剖析方法。許多程式語言使用LR(1)描述文法，因此許多編譯器都使用LR剖析器分析原始碼的文法結構。LR剖析的優點如下：
* 眾多的程式語言都可以用某種LR剖析器（或其變形）分析文法。（C++是個著名的例外）
* LR剖析器可以很有效率的建置。
* 對所有「由左而右」掃描原始碼的剖析器而言，LR剖析器可以在最短的時間內偵測到文法錯誤（這是指文法無法描述的字串）。 然而LR剖析器很難以人工的方式設計，一般使用「剖析產生器（parser generator）」或「編譯器的編譯器（compiler-compiler，產生編譯器的工具）」來建構它。LR剖析器可根據剖析表（parsing table）的建構方式，分類為「簡單LR剖析器（SLR, Simple LR parser）」、「前瞻LR剖析器（LALR, Look-ahead LR parser）」以及「正統LR剖析器 (Canonical LR parser)」。這些解析器都可以處理大量的文法規則，其中LALR剖析器較SLR剖析器強大，而正統LR剖析器又比LALR剖析器能處理更多的文法。著名的Yacc即是用來產生LALR剖析器的工具。 (zh)
|
| rdfs:comment
|
- Im Compilerbau ist ein LR-Parser ein Bottom-up-Parser für LR-Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen. (de)
- LR法またはLR構文解析器とは、文脈自由文法の構文解析手法/構文解析器である。LR法では、入力を左(Left)から右に読んでいき、右端導出(Rightmost derivation)を行う。このためLRと名づけられている。「LR(k)」といった場合、k は、消費をともなうことなく「先読み」が進められる入力記号の最大数を意味する。通常、k は 1 であり、その場合省略されることが多い。LR(k)の構文解析器が対応する文脈自由文法も LR(k) と呼ばれる。 (ja)
- مجزئ يسار يمين في علوم الحاسب الآلي، هو مجزئ يقرأ الإدخال من اليسار إلى اليمين (كما ستظهر في العرض المرئي)، وتنتج استخلاص أقصى اليمين. مصطلح LR(k) parser يستخدم أيضاً؛ حيث K تشير إلى عدد الغير مستهلك "look ahead" رموز المدخلات التي تستخدم في صنع القرارات التحليل. عادة ما تكون K هي 1 والعبارة LR parser عادة ما تستخدم للإشارة إلى هذه الحالة. القواعد اللغوية لكثير من لغات البرمجة يمكن تحديدها بقواعد هي LR(1) أو ما يقارب ذلك، ولهذا السبب LR parsers غالبا ما تستخدم من قبل برامج المترجم لإجراء تحليل القواعد اللغوية من شفرة المصدرsource code. (ar)
- LR syntaktický analyzátor (anglicky LR parser) je v matematické informatice typ syntaktického analyzátoru zdola nahoru, který efektivně zpracovává deterministické bezkontextové jazyky v zaručeném lineárním čase.Jeho často používanými variantami jsou a . Pro vytváření LR syntaktických analyzátorů se často používají , které generují analyzátor mechanicky z formální gramatiky jazyka. Častěji než jiné druhy generovaných syntaktických analyzátorů se používají pro zpracování programovacích jazyků. (cs)
- Los analizadores sintácticos LR, también conocidos como Parser LR, son un tipo de dispositivos para manipular algunas gramáticas libres de contexto. Pertenecen a la familia de los analizadores ascendentes, ya que constituyen el árbol sintáctico de las hojas hacia la raíz. Utilizan la técnica de análisis por desplazamiento de reducción. Existen tres tipos de parsers LR: SLR (K), LALR (K) y LR (K) canónico. Un analizador LR consta de: 1.
* Un programa conductor 2.
* Una entrada 3.
* Una salida 4.
* Una tabla de análisis sintáctico, compuesta de dos partes (ACCIÓN y GOTO). (es)
- In computer science, LR parsers are a type of bottom-up parser that analyse deterministic context-free languages in linear time. There are several variants of LR parsers: SLR parsers, LALR parsers, Canonical LR(1) parsers, Minimal LR(1) parsers, and GLR parsers. LR parsers can be generated by a parser generator from a formal grammar defining the syntax of the language to be parsed. They are widely used for the processing of computer languages. (en)
- Comme tout analyseur grammatical (ou analyseur syntaxique), un analyseur LR vise à vérifier si une chaîne de caractères (typiquement contenue dans un fichier) possède bien la structure d'une grammaire spécifiée à l'avance. Cette vérification s'accompagne généralement d'actions. Une action typique est la génération d'une autre chaîne de caractères ou encore d'un arbre d'analyse. Ainsi l'analyse grammaticale est généralement utilisée pour la compilation (transformation d'un code source en code machine). Sur le plan de l'informatique théorique, un analyseur LR (en anglais : Left to right, Rightmost derivation ) est un analyseur pour les grammaires non contextuelles qui lit l'entrée de gauche à droite (d'où le L de Left to right) et produit une dérivation droite (d'où la dénomination Rightmost (fr)
- Nell'informatica, un parser LR è un parser di tipo Bottom-up per grammatiche libere da contesto, usate molto di frequente nei compilatori dei linguaggi di programmazione (e degli altri strumenti associati). Un Parser LR legge il proprio input partendo da sinistra (Left) verso destra, producendo una derivazione destra (Rightmost Derivation). A volte questo parser viene anche indicato col nome "Parser LR(k) dove k si riferisce al numero di simboli letti (ma non "consumati") utilizzati per prendere le decisioni di parsing. Tipicamente k ha valore 1 ed è spesso omesso. Una grammatica libera da contesto è chiamata LR(k) se esiste un parser LR(k) adatto ad essa. (it)
- Um analisador sintático LR (também chamado parser LR) é um algoritmo de análise sintática para gramáticas livres de contexto. Ele lê a entrada de texto da esquerda para a direita e produz uma derivação mais à direita (por isso LR, do termo em inglês left-right, diferente do analisador sintático LL). Outro termo usado é analisador sintático LR(x), no qual refere-se à quantidade de símbolos posteriores ao símbolo atual (ainda não consumidos da entrada) que são usados para tomar decisões na análise. Geralmente esse valor é 1, sendo omitido. Uma gramática livre de contexto é chamada LR(x) se existe uma analisador sintático LR(x) para ela. (pt)
- Parser LR (ang. Left to right, identifying the Rightmost production) – analizator składniowy dla gramatyk bezkontekstowych, który przetwarza wejście od lewej do prawej metodą wstępującą i produkuje prawostronne wyprowadzenie. Terminu parser LR(k), gdzie k jest liczbą naturalną lub zerem, używa się do oznaczenia analizatorów podejmujących decyzje na podstawie k podglądanych symboli na wejściu, użytych w podjęciu decyzji. Zwykle k jest równe 1 i jest często pomijane. Parser SLR i parser LALR również są typu LR, jednak pod pojęciem LR(k) zwykle mamy na myśli "kanoniczny parser LR(k)". W typowym użyciu "parser LR" oznacza konkretny parser zdolny rozpoznać konkretny język określony gramatyką bezkontekstową. (pl)
- LR-анализатор (англ. LR parser) — синтаксический анализатор для исходных кодов программ, написанных на некотором языке программирования, который читает входной поток слева (Left) направо и производит наиболее правую (Right) продукцию контекстно-свободной грамматики. Используется также термин LR(k)-анализатор, где k выражает количество непрочитанных символов предпросмотра во входном потоке, на основании которых принимаются решения при анализе. Обычно k равно 1 и часто опускается. (ru)
- LR剖析器是一種由下而上（bottom-up）的上下文無關語法剖析器。LR意指由左（Left）至右處理輸入字串，並以最右邊優先衍生（Right derivation）的推導順序（相對於LL剖析器）建構語法樹。能以此方式剖析的語法稱為LR語法。而在LR(k)這樣的名稱中，k代表的是剖析時所需前瞻符號（lookahead symbol）的數量，也就是除了目前處理到的輸入符號之外，還得再向右參照幾個符號之意；省略 （k）時即視為LR(1)，而非LR(0)。 由於LR剖析器嘗試由剖析樹的葉節點開始，向上一層層透過文法規則的化簡，最後规约回到樹的根部（起始符號），所以它是一種由下而上的剖析方法。許多程式語言使用LR(1)描述文法，因此許多編譯器都使用LR剖析器分析原始碼的文法結構。LR剖析的優點如下：
* 眾多的程式語言都可以用某種LR剖析器（或其變形）分析文法。（C++是個著名的例外）
* LR剖析器可以很有效率的建置。
* 對所有「由左而右」掃描原始碼的剖析器而言，LR剖析器可以在最短的時間內偵測到文法錯誤（這是指文法無法描述的字串）。 (zh)
|
