# 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 $x$ 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.

## Arquitetura
### Caso geral

O analisador sintático é uma máquina de estado finito que consiste de:
* um buffer de entrada;
* uma pilha no qual é armazenada uma lista de estados anteriores;
* uma tabela de próximo estado que indica para onde o novo estado deve se mover;
* uma tabela de ação que indica uma regra gramatical a aplicar no estado e símbolo atual na entrada de dados.

#### Algoritmo

O algoritmo do analisador sintático LR é definido como:
* A pilha é inicializada com [0]. O estado atual será sempre o estado no topo da pilha.
* Dado o estado atual e o símbolo atual na entrada, uma ação é procurada na tabela de ação:
** uma mudança de estado sn:
*** o símbolo terminal atual é removido da entrada
*** o estado n é inserido na pilha (tornando-se o estado atual)
** uma redução rm:
*** o número m é escrito no fluxo de saída
*** para cada símbolo à direita da regra m, um estado é removido da pilha
*** dado o então estado atual no topo da pilha e a regra m, um novo estado é procurado na tabela de próximo estado, tornando-se o estado atual ao ser inserido na pilha
** uma aceitação: a cadeia de caracteres é aceita
** sem ação: um erro de sintaxe é retornado
* O passo 2 é repetido até que a haja uma aceitação ou um erro de sintaxe.

### Exemplo

A gramática abaixo será usada para o exemplo a seguir. Ela trata expressões matemáticas, no qual é aceito somas e multiplicações entre uns e zeros.
    (1) E → E * B
    (2) E → E + B
    (3) E → B
    (4) B → 0
    (5) B → 1
deve-se analisar sintaticamente a seguinte entrada:
    1 + 1

#### Tabelas de ação e próximo estado

| | ação | ação | ação | ação | ação | próximo estado | próximo estado |
| estado | * | + | 0 | 1 | $ | E | B |
| 0 | | | s1 | s2 | | 3 | 4 |
| 1 | r4 | r4 | r4 | r4 | r4 | | |
| 2 | r5 | r5 | r5 | r5 | r5 | | |
| 3 | s5 | s6 | | | acc | | |
| 4 | r3 | r3 | r3 | r3 | r3 | | |
| 5 | | | s1 | s2 | | | 7 |
| 6 | | | s1 | s2 | | | 8 |
| 7 | r1 | r1 | r1 | r1 | r1 | | |
| 8 | r2 | r2 | r2 | r2 | r2 | | |
A tabela de ação é classificada por um estado do analisador sintático e um símbolo terminal (incluindo o terminal especial $ que indica o final da entrada de dados) e contém três tipos de ações:
* mudança de estado (shift), escrito sn e indicando que o próximo estado é n
* redução (reduce), escrito rm e indicado que a redução com a regra gramatical m deve ser feita
* aceitação (accept), escrito acc e indicando que o analisador sintático aceita a entrada de dados
A tabela de próximo passo é classificada por um estado do analisador sintático e por um símbolo não terminal. Ela indica qual o próximo estado do analisado se um símbolo não-terminal foi reconhecido.

#### Procedimento de análise

A tabela abaixo ilustra cada passo do processo. Aqui o estado refere-se ao elemento no todo da pilha (mais à direita), e a próxima ação é determinada referindo-se à tabela de ação acima. Notar que um $ é adicionado no final da entrada de dados para indicar o fim do texto.
| Estado | Entrada de dados | Saída de dados | Pilha | Próxima ação |
| 0 | 1+1$ | | [0] | mudança de estado para 2 |
| 2 | +1$ | | [0,2] | reduz 5 |
| 4 | +1$ | 5 | [0,4] | reduz 3 |
| 3 | +1$ | 5,3 | [0,3] | mudança de estado para 6 |
| 6 | 1$ | 5,3 | [0,3,6] | mudança de estado para 2 |
| 2 | $ | 5,3 | [0,3,6,2] | reduz 5 |
| 8 | $ | 5,3,5 | [0,3,6,8] | reduz 2 |
| 3 | $ | 5,3,5,2 | [0 3] | aceita |
O estado inicial do analisador é sempre 0, armazenado na pilha. O primeiro valor terminal encontrado pelo parser é 1, e de acordo com a tabela de ação deve haver uma mudança de estado para 2. No estado 2 a tabela de ação indica que qualquer terminal que apareça, deve-se realizar uma redução com a regra gramatical 5. Por isso escreve-se 5 da saída de dados, retira-se um estado da pilha e adiciona-se na pilha o estado da tabela de próximo estado (que no caso é 4).
Apesar disso a tabela de ação do estado 4 indica que deve-se realizar uma redução com a regra 3. Então escreve-se 3 na saída de dados, retira-se um estado da pilha, encontra-se um novo estado na tabela de próximo estado (que no caso é 3).
O próximo terminal no parser é +, e de acordo com a tabela de ação deve-se ir para o estado 6. O próximo terminal é 1, significando que deve-se realizar uma mudança para o estado 2. Assim como o 1 anterior, é feita uma redução para B, indo-se para o estado 8. Nesse estado sempre é feita uma redução pela regra 2.
Finalmente é lido o terminal $ da entrada de dados, o que significa que, de acordo com a tabela de ação (o estado atual é 3), o analisador sintático aceita a entrada de dados.