40

Estou construindo um parser para uma linguagem de programação. A gramática não precisa atender todas as complexidades de uma linguagem como C++ ou Lisp.

Tenho um conhecimento moderado sobre construção de linguagens mas pouca experiência com as ferramentas e metodologias para implementá-las. Tenho uma noção como funciona um parser e quais os algoritmos mais utilizados para isso. Entre eles, pude selecionar dois, o LL e o LR. Já estudei o básico sobre eles mas por ter só conhecimento teórico ainda não estou confortável em dizer as vantagens de cada um.

Se você tem experiência com ambos algoritmos construindo um compilador na situação citada acima, poderá me ajudar.

  1. O que eu ganho e o que eu perco quando escolho o parser com algoritmo LL ou com algoritmo LR?

  2. Deixei de olhar outros algoritmos importantes que podem ser mais indicados em alguma situação do que os dois citados?

  3. Como se comportam perante a complexidade da gramática, facilidade de implementação e manutenção e velocidade de execução?

Não quero saber qual o melhor, até porque se um fosse claramente melhor que o outro, o último seria citado apenas historicamente. Isso só eu poderei determinar. Preciso de subsídios para tomar a minha decisão.

0

5 Respostas 5

29

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.


5
  • 5
    É sempre bom ver que não temos só web developers aqui :) Você já deu respostas que achei que ninguém responderia e até não tinha conseguido coisa boa em inglês.
    – Maniero
    Commented 17/01/2014 às 22:26
  • nas produções Expr → Expr '+' Expr parece-me que o texto ficaria melhor se não usasses uma gramática ambígua (Expr → Expr '+' Num). A ambiguidade vai dar conflitos desnecessários e semanticamente perigosos. Parece-me que poderias rever linha que explica o LR.
    – JJoao
    Commented 23/02/2015 às 14:04
  • @JJoao De fato o exemplo da LL estava incorreto. Corrigido. Quanto ao LR, foi intencional exibir uma gramatica ambigua, justamente para demonstar que isso é possível. Commented 23/02/2015 às 16:46
  • 1
    @GuilhermeBernal, desculpa se insisto. A ideia do R do LR não é bem essa. É mais espera pelo canto direito da árvore de derivação para tomar decisões. Em gramáticas ambíguas como essa todos as ferramentas que tenho usado (nao havendo definição extra de associatividade) se queixam de conflitos reduce-reduce e avisam que a semântica vai correr mal
    – JJoao
    Commented 24/02/2015 às 9:49
  • 1
    @JJoao eu vou rever isso com calma e ler melhor sobre o assunto. Mais para frente faço as devidas edições. Muito obrigado por apontar o erro, estudarei. Commented 24/02/2015 às 13:35
18

Primeiro você precisa determinar se uma gramática formal é mesmo a melhor maneira de representar sua linguagem. Se for, se essa gramática é implementavel por um ou outro algoritmo (pois como apontado por Guilherme Bernal, há diferenças sutis nas gramáticas aceitas por LL, LR e suas variantes) - ou se alguma outra técnica será necessária. Também é importante determinar o quanto a eficiência de compilação é necessária (já que nos dias de hoje, não há tanta necessidade de se "espremer cada ciclo da CPU").

Um "compilador de compiladores" pode ser interessante, embora existam linguagens - de sintaxe até simples - que não podem ser implementadas dessa forma. Um exemplo é Prolog, que possui instruções para definir novos operadores e, na linha de código seguinte, já permite ao programador utilizá-los como parte do programa:

:-op(500, yfx, mais).
dobro(X, Y) :-
    Y is X mais X. /* Naturalmente, 'mais/3' tem de ser definido (antes ou depois)... */

Ou seja, apesar de ser possível definir a sintaxe de Prolog com uma gramática livre de contexto, seria necessário modificar suas regras de derivação durante a própria compilação. Os compiladores de compiladores em geral não são tão flexíveis... (outra linguagem que também dá muita flexibilidade na compilação é Lisp, com suas macros de leitura)

Linguagens com essas características seriam melhor expressas de uma outra forma (por exemplo, a técnica top down operator precedence), mas vamos assumir que você optou por uma gramática formal. O próximo passo seria determinar se ela se encaixa nos requisitos para um desses métodos de geração automática (como os parsers LALR ou talvez o PEG, sugerido por @Victor). Muito provavelmente isso será possível, embora em alguns casos a forma de expressar suas regras de derivação fique um pouco "esquisita" (ex.: quando a sintaxe para genéricos foi intruduzida em Java e C#, uma regra especial foi necessária para tratar de Classe<Tipo1<Tipo2>> - pois os angle brackets precisavam ser balanceados, mas o símbolo >> não era reconhecido como dois > pelo "princípio do casamento mais longo").

Se um ou outro parser exigir muita alteração na expressão de suas regras, isso pode atrapalhar na manutenabilidade do seu compilador, de modo que isso deve ser evitado.

Por fim, se ainda restarem duas ou mais opções de parser, considere se há mesmo a necessidade de otimizar por performance: a vantagem de se utilizar um gerador já pronto ou, conversamente, a vantagem de se implementar manualmente um algoritmo mais simples, pode permitir que você tenha uma versão funcional mais rápido que lhe permita utilizar, testar, receber feedback - em suma, adquirir mais "experiência prática em criação de linguagens". Uma segunda versão, mais eficiente, sempre poderá ser feita depois.

1
  • Por vezes estas gramáticas são designadas por "Operator Precedence grammars" e são da família da "context-free-grammar"
    – JJoao
    Commented 23/02/2015 às 14:08
14

Em vez de utilizar LR ou LL, use PEGs (Parsing Expression Grammars, veja aqui e aqui).

Uma PEG é definida de forma similar a uma GLC (Gramática Livre do Contexto), apenas com as seguintes diferenças:

  • Uma PEG não tem uma escolha não-determinística (regras do tipo A ← b | c da GLC). Em vez disso PEGs têm escolhas determinísticas (regras do tipo A ← b / c). Numa escolha determinística no formato A ← b / c / d, o não-terminal A tenta derivar inicialmente um b (e o parser correspondente fará isso também). Se A não derivar b, então o parser tentará derivar um c e se não conseguir isto também um d. Esta regra é definida desta forma com a finalidade de eliminar a ambiguidade na escolha (que tipicamente existem em GLCs), mas também torna alguns casos problemáticos como A ← x / xy, aonde xy nunca será derivado. Um resultado prático interessante sobre isso é que uma regra do tipo S ← 'if' C 'then' S 'else' S / 'if' C 'then' S não sofre com o problema do dangling-else.

  • Uma PEG pode ter um predicado and. Este predicado funciona da seguinte forma: Uma regra A ← b &c significa que A deriva b se, e somente se, logo após o b existir um c.

  • Uma PEG pode ter um predicado not. Este predicado funciona da seguinte forma: Uma regra A ← b !c significa que A deriva b se, e somente se, logo após o b não existir um c.

Desta forma, a primeira regra reduz o poder de reconhecimento de linguagens do PEG em relação às GLCs e as outras duas aumentam. Como resultado existem linguagens que são PEG mas não são livres de contexto, como por exemplo a linguagem {anbncn | n > 0}:

S ← &(A 'c') 'a'+ B !('a'/'b'/'c')
A ← 'a' A? 'b'
B ← 'b' B? 'c'

Por outro lado, PEGs não são capazes de reconhecer GLCs inerentemente ambíguas e também algumas que não são ambíguas.

As vantagens das PEGs são:

  • PEGs são simples de definir e de implementar. A implementação é semelhante a de um parser LL, apenas um pouco mais sofisticada em alguns aspectos: É necessário fazer-se backtracking do input ao lidar com predicados and e not e para que a implementação também seja eficiente, é necessário implementar-se memoização. Em questão de recuperação de erros, o tratamento é semelhante.
  • PEGs são livres de ambiguidades.
  • PEGs são reconhecidas (com o algoritmo packrat) em tempo linear em relação ao tamanho da entrada (se você não tiver recursão à esquerda).
  • PEGs são superconjuntos de todas as gramáticas regulares, LR-k e LL-k para qualquer valor de k.
  • Linguagens de programação implementadas com PEGs normalmente não precisam separar a análise léxica da análise sintática, tudo pode ser feita em uma única gramática baseada nos caracteres do código-fonte, eliminando a necessidade de tokenização. Não que isso seja obrigatoriamente impossível em linguagens LR ou LL, mas normalmente parsers de linguagens LR e LL separaram uma etapa de tokenização, enquanto que isso não costuma ser considerado necessário em linguagens PEG.

Uma implementação simplória de um reconhecedor de PEGs demoraria tempo exponencial no pior caso, principalmente por causa dos predicados and e not que envolveriam bastante backtracking, além de que não seria capaz de lidar com recursividade à esquerda. Utilizando memoização (que é o que o algoritmo packrat faz), o tempo pode ser reduzido para linear e os problemas de recursões à esquerda podem ser eliminados com o uso de guardas/sentinelas que os detectem.

Além disso, já existem diversas implementações de parsers de PEGs em várias linguagens de programação e uma busca rápida no google lhe trará vários resultados, inclusive para geradores de parsers.

Há uma única desvantagem importante: O consumo de memória de um parser packrat é mais alto do que o consumo de memória de um parser LL e LR. Isto ocorre por causa do uso massivo de memoização para garantir um tempo linear.

Uma observação importante a fazer sobre PEGs é que elas são uma abordagem relativamente nova. As PEGs foram inventadas por Bryan Ford em 2002, o que na área de linguagens formais é super novo. A maioria da teoria de linguagens formais foi criada nas décadas de 1960 e 1970. Por este motivo, dificilmente você vai achar alguma referência a PEGs nos seus livros sobre compiladores e é também por causa disso que você raramente verá pessoas utilizando esta abordagem.

0
14

Contraste de análise LL e LR para uma série de critérios:

Complexidade

LL ganha aqui, fácil. Você pode facilmente escrever um parser LL à mão. De fato, é comumente feito: o compilador Microsoft C# é um parser recursivo descendente escrito à mão (fonte aqui, procure um comentário feito por Patrick Kristiansen - o blog é muito interessante também).

Análise LR utiliza um método bastante contra-intuitivo para analisar um texto. Ele funciona, mas ele leva algum tempo para entender como ele funciona exatamente. Escrevendo tal analisador à mão é, portanto, difícil: você estaria mais ou menos implementando um gerador de parser LR.

Generalidade

LR ganha aqui: todas as linguagens LL são linguagens LR, mas há mais linguagens LR do que linguagens LL (é uma linguagem LL se ela pode ser analisada com um analisador LL, e uma linguagem é LR se ela pode ser analisada com um analisador LR).

LL tem alguns incômodos que irão atrapalhar ao implementar praticamente qualquer linguagem de programação. Veja o artigo da Wikipedia para uma visão geral.

Existem linguagens não ambíguas que não são linguagens LR, mas são muito raras. Você quase nunca encontrará estas linguagens. No entanto, LALR tem alguns problemas:

  • LALR é mais ou menos uma "gambiarra" para analisadores LR obterem tabelas menores. As tabelas para um analisador LR geralmente podem crescer enormemente. Analisadores LALR se abstêm da capacidade de analisar todas as linguagens LR em troca de tabelas menores. A maioria dos analisadores LR realmente usam LALR (geralmente você pode descobrir exatamente como está implementado).

LALR pode ter dificuldades com conflitos shift-reduce e reduce-reduce. Isto é causado pela gambiarra da tabela: ele 'junta' entradas semelhantes, o que funciona, porque a maioria das entradas estão vazias, mas quando elas não estão vazias, gera um conflito. Estes tipos de erros não são naturais, são difíceis de entender e as correções normalmente ficam bastante estranhas.

Erros do compilador e recuperação de erro

LL ganha aqui. Em uma análise LL, normalmente é muito fácil emitir erros úteis do compilador, principalmente em analisadores escritas à mão. Você sabe o que você está esperando em seguida, por isso, se ele completar a compilação, você geralmente sabe o que deu errado e qual o erro mais próximo estaria ocorrendo.

Além disso, em análise LL, a recuperação de erros é muito mais fácil. Se uma entrada não analisar como correta, você pode tentar pular um pouco à frente e descobrir se o resto da entrada não analisa corretamente. Se, por exemplo, alguma instrução do programa está incorreta, você pode ir à frente e analisar a próxima instrução, assim você pode pegar mais de um erro.

Usando um analisador LR isso é muito mais difícil. Você pode tentar aumentar a sua gramática para que ele aceite a entrada errônea e imprimir erros nas áreas do texto onde as coisas deram errado, mas isso geralmente é muito difícil de fazer. A chance de você acabar com uma gramática não-LR (ou não-LALR) também aumentam.

Velocidade

A velocidade não é realmente um problema que depende tanto da maneira que você analisará sua entrada (LL ou LR ), mas sim a qualidade do código resultante e do uso de tabelas (você pode usar tabelas para ambos LL e LR). LL e LR são comparáveis.

Links

Coloquei no GitHub para referência futura.

10

Alguma notas acerca desta pergunta e das repostas:

Nota 1: as técnicas top-down/LL está a ser tratadas de modo ligeiramente injusto:

Normalmente as ferramentas Top-Down aceitam gramáticas EBNF (são fáceis de implementar em TD).

Cobertura: é fácil obter cobertura semelhante às técnicas LR à custa do uso de EBNF.

Assim, as questões de factorização e recursividade à esquerda são expressas escrevendo a gramática de forma diferente (iterativa). Ex:

a --> a OPMul f
  | f

Escreve-se como

a --> f ( OPMul f)*

Ferramentas como o ANTLR usam LL(K) com K potencialmente infinito, e são usadas para escrever compiladores reais, e disponibilizam nas suas comunidades muitas gramáticas reais, e cobrem mais do que o Parser. O ANTLR4 aceita até (um bom subconjunto de) recursividade à esquerda.

Os métodos Top-Down tornam mais fácil a implementação de atributos herdados. (ok,ok, com LR tambem se consegue)

Note 2: Bottom-up não é só yacc

Relembro que mesmo o bison actualmente gera parsers LALR mas também LR1, IELR, GLR.

Muitas ferramentas Bottom-up incluem directivas ligadas às "Operator Precedence grammars" (definição de operadores, prioridades e associatividades) que ajuda bastante à escrita de certo tipo de processadores (por exemplo é excelente para expressões).

Há mais ferramentas geradoras de parser Bottom-up!

Note 3: é necessário mais que um parser (escolha da linguagem gerada)

Para além do reconhecimento sintático, temos que criar um nível semântico e pragmático: convem escolher um gerador que produza uma linguagem que seja do nosso agrado!

Por exemplo existem variantes yacc-eiras para quase tudo o que é linguagem.

Eu gosto de Perl: usando Parse::Yapp (gera LALR) posso escrever ações semânticas em Perl de modo muito mais expedito que em C ou Java. (Esta questão é crítica).

Há também ferramentas ligadas a: (1) Travessias e decoração de árvores de parsing; (2) geração / optimização de código; (3) templating;

Nota 4: é mais frequente a criação de DSL que de compiladores completos

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .