quarta-feira, março 16, 2011

Minhas Aventuras com "Parsing": LR Parser (parte 1)

Embora o Earley Parser seja capaz de analisar uma gama bastante grande de gramáticas, o seu desempenho pode deixar a desejar. Minha próxima opção é o LR Parser.

Este algorítimo é bastante usado em compiladores reais, com o auxílio de pequenos truques devido às excentricidades das linguagens de programação reais.

O LR Parser recebe este nome por analisar o texto a partir da esquerda (Left) e gerar a "derivação a partir da direita" (Rightmost derivation), isto é, obter uma sequência de regras que começa substituindo o não terminal mais à direita.

Os analisadores do tipo LR costumam ser chamados de LR(k) onde k é o número de símbolos de entrada adicionalmente lidos para tomar decisões durante a análise (look ahead). LR(0) corresponde ao caso em que nenhum símbolo adicional precisa ser consultado.

Uma linguagem é considerada livre de contexto e determinística se puder ser descrita por uma gramática que possa ser analisada por um parser LR(k). Uma gramática que pode ser analisada por um parser LR(k) com k>1 pode ser transformada sempre em uma gramática que pode ser analisada por um parser LR(1) mas nem sempre em uma gramática que pode ser analisada por um parser LR(0). A transformação de LR(k) em LR(1) tem o custo de complicar a gramática, introduzindo uma grande quantidade de regras adicionais e, portanto, nem sempre é vantajosa.

Enquanto que o Earley Parser utilizava diretamente as regras da gramática, o LR Parser utiliza uma tabela de decisões montada a partir das regras (normalmente por um programa). Este pré-processamento das regras é a chave para a otimização do processo de análise. Existem diversos algorítimos para gerar esta tabela a partir das regras. O mais simples deles é o usado para gerar tabelas para um parser LR(0). Algorítimos mais sofisticados (para parsers LR(k) com k > 1) são usados com os chamados parsers SLR (Simple LR), LALR (Look Ahead LR) e LR canônico. Colocando em ordem crescente de capacidade de analisar linguagens, temos LR(0), SLR, LALR e LR canônico.

No próximo post veremos mais detalhes do algorítimo do LR parser.

Nenhum comentário: