LL
O LL funciona tentando prever qual será a próxima regra de produção, e então aplicando essa regra aos próximos símbolos lidos do input. Se a previsão falhar, é necessário retornar para o estado antes da previsão, devolver os símbolos lidos ao input (backtracking) e fazer uma nova previsão. O parser falha no momento que todas as possíveis previsões tiverem sido testadas (ou seja, a previsão inicial de que ali tem um input válido para a linguagem se provar falsa).
É um tipo de parser bastante fácil de ser escrito manualmente por conta da sua característica recursiva. Se torna trivial se a linguagem for regular ou nunca necessitar de backtracking (nesse caso é um LL(1)). O código do parser é também muito similar à gramática que o produziu e pode ser lido com facilidade.
No entanto o tempo de execução é difícil de prever (embora não seja tão diferente de linear sobre o tamanho do input na maioria dos casos práticos) e nem todas as gramáticas podem ser processadas por um parser LL. Um exemplo clássico é a recursão de esquerda:
Num → [0-9]+
Base → Num | '(' Sum ')'
Prod → (Prod '*')? Base
Sum → (Sum '+')? Prod
Essa gramática não pode ser processada diretamente, pois o parser LL entende que ao ler um Sum
, deve assumir que logo em seguida vem um Sum
e checar essa possibilidade, gerando um loop infinito. Para isso funcionar você deve primeiro transformar a gramática para que ela seja aceitável para o algorítmo do LL, assim:
Num → [0-9]+
Base → Num | '(' Sum ')'
Prod → (Base '*')* Base
Sum → (Prod '+')* Prod
Ela continua aceitando exatamente a mesma linguagem, no entanto não produzirá a mesma árvore de sintaxe (Sum
e Prod
viram operações n-dimencionais no lugar de binárias) e precisa de processamento adicional para a ajustar.
LR
O LR opera em uma lista no qual a cada estágio uma das seguintes operações será executada:
- Shift: Um símbolo será lido do input e adicionado ao fim da lista como um terminal.
- Reduce: Uma regra de produção será aplicada nos últimos N símbolos terminais ou não-terminais presentes na lista, transformando-os em um não-terminal.
A operação se repete até que o input esteja vazio e a lista contenha apenas um não-terminal, o que representa a linguagem. Se não for possível chegar a esse estado (o input acabar e não existir regras para aplicar e reduzir a lista) o parser falha.
O interessante aqui é que um símbolo do input nunca é lido mais de uma vez e que o tempo de processamento é claramente linear no tamanho do input (assumindo que o número de regras de produção não seja absurdamente grande, casos práticos). Esse mecanismo pode lidar com recursão sem problemas. Algumas variantes são o LALR e o SLR.
O parser LR aceita um conjunto maior de gramáticas, não tendo problemas com recursão. A gramática a seguir, por exemplo, é perfeitamente aceitável.
Num → [0-9]+
Expr → Expr '+' Expr | Num
Sendo uma gramática ambigua, a derivação mais à direita será dada (dai o R de LR). 1+2+3
é processado como 1+(2+3)
.
É um tipo de parser difícil de ser escrito na mão pois sua lógica é na maior parte escrita na forma de tabelas de transformação, não de código. Por outro lado, é simples para ser produzido por outro algoritmo a partir da gramática, um compilador de compiladores. Alguns exemplos são o bison e o yacc que produzem um parser LALR.
Conclusão
Se você pretende escrever o parser você mesmo, sem a ajuda de nenhuma ferramenta, tenda imediatamente a escolher um LL, especialmente se a linguagem for regular ou simples o suficiente para o LL(1). É um modelo fácil de programar e na maioria dos casos a diferença de performance é muito pequena para ser relevante. (existem gramáticas que podem fazer um LL requerer tempo exponencial no tamanho do input, mas estou assumindo casos reais e práticos). É uma boa escolha para quem está iniciando no assunto por permitir realmente entender o que está acontecendo no código com facilidade.
Mas se você planeja um parser de maior complexidade ou que eficiência é importante, o ideal é confiar em uma ferramenta para gerar o parser para você. Na maioria dos casos ela será capaz de fazer simplificações na gramática que a tornam ilegível no código final do parser, mas mais rápida. Quase todas as ferramentas desse tipo produzem parsers LALR, embora algumas usem o LL (como o ANTLR). Nesse caso você descreve a gramática, geralmente em notação de PEG. O diagnóstigo para erros de sintaxe tende a ser melhor também.
No entanto se você precisa de ajustes finos no seu parser, como lidar com algum elemento de sintaxe que não seja convencional e que não seja possível escrever uma gramática diretamente. Um exemplo disso é o preprocessador do C/C++. Você pode fazer o processo em dois estágios, submetendo o código processado para o parser. Mas se o fizer perderá informações importantes de diagnóstico e a mensagem de erro pode nada ter haver com o código originalmente escrito. A opção é integrar o preprocessador no parser. Mas nesse caso não há como escrever gramática, você precisa escrever o parser em código.
Eu particularmente escolho escrever um parser (em LL) apenas quando a linguagem é extremamente simples. Para qualquer projeto real utilizo alguma ferramenta para gerar o parser.