Analisador sintático LR
Um analisador sintático 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. Outro termo usado é analisador sintático LR(x), no qual refere-se à quantidade de símbolos posteriores ao símbolo atual 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.
Caso geral
O analisador sintático é uma máquina de estado finito que consiste de: O algoritmo do analisador sintático LR é definido como:
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. deve-se analisar sintaticamente a seguinte entrada: 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: 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. 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.
