Analisador sintático LR

(Redirecionado de Analisador sintático SLR)

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.

Arquitetura

editar

Caso geral

editar

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

editar

O algoritmo do analisador sintático LR é definido como:

  1. A pilha é inicializada com [0]. O estado atual será sempre o estado no topo da pilha.
  2. 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
  3. O passo 2 é repetido até que a haja uma aceitação ou um erro de sintaxe.

Exemplo

editar

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

editar
ação 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

editar

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.