Analisador sintático LR

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.