Existe alguma maneira de distinguir entre gramática LL (k) e LR (k)?

12

Estou estudando recentemente sobre o design de compiladores. Eu vim a conhecer dois tipos de gramática, a gramática LL e a gramática LR.

Também sabemos os fatos de que toda gramática LL é LR que é gramática LL é um subconjunto adequado da gramática LR. O primeiro é usado na análise de cima para baixo e o segundo é usado na análise de baixo para cima.

Mas existe alguma maneira de dizer que uma dada gramática é LL ou LR?

Deb
fonte
3
Que tal usar as técnicas canônicas para gerar as tabelas e L R ( k ) e verificar se elas contêm conflitos? L L ( 1 ) e L R ( 1 ) são geralmente tratados em qualquer livro-texto padrão sobre análise; as técnicas L L ( k ) e L R ( k ) são um pouco mais difíceis de encontrar, mas também são bem conhecidas. LL(k)LR(k)LL(1)LR(1)LL(k)LR(k)
Alex10 Brink
@AlextenBrink Parece que você poderia dar uma resposta! (Back Bem-vindo, você estava perdido!)
Raphael
Usando a técnica canônica para verificar se uma gramática é LL ou LR é correta, mas de maneira demorada. Estou tentando encontrar uma maneira pequena de encontrar isso que encontrei no livro de compiladores de Aho-Lam-Sethi-Ullman.
dez

Respostas:

11

gramáticas L L ( k ) e L R ( k ) são boas não apenas porque podem ser analisadas com eficiência, mas também porque podemos verificar se uma gramática é L L ( k ) ou L R ( k )LL(k)LR(k)LL(k)LR(k)e porque podemos gerar tabelas para eles (as tabelas de análise são usadas para analisar as seqüências de entrada). Observe que, para essas duas classes, ter a tabela de análise imediatamente permite verificar se as gramáticas estão nas classes, porque é assim se e somente se as tabelas não contiverem erros. Além disso, sim, existem classes de gramáticas que podemos analisar com eficiência se tivermos uma tabela de análise, mas para a qual não podemos gerar a tabela se ela existir.

Qualquer livro sobre métodos de análise ensinará como gerar as tabelas para os métodos e, possivelmente, também para L R ( 1 ) (embora S L R ( 1 ) seja mais comum). Livros didáticos como Parsing Theory, de Sippu e Soisalon-Soininen, também tratam a geração de tabelas de análise para gramáticas L L ( k ) e L R ( k ) .LL(1)LR(1)SLR(1)LL(k)LR(k)

Infelizmente, para gramáticas realmente estranhas, as tabelas de análise para e L R ( k ) (embora não para L L ( 1 ) ) podem explodir e se tornar enormes; eles farão isso mesmo para gramáticas normais se k for alto o suficiente. Existem testes disponíveis que podem verificar se uma gramática é L L ( k ) ou L R ( k )LL(k)LR(k)LL(1)kLL(k)LR(k)ou não executado no tempo polinomial (a geração da tabela é exponencial). Para detalhes, leia o livro acima. Observe que, em muitos casos, a tabela é de tamanho razoável, portanto, o teste não é necessário.

kkLL(k)LR(k)LR(k)kLL(c)ck(veja aqui para detalhes).

Alex ten Brink
fonte
Você sabe onde posso encontrar os detalhes do algoritmo de tempo polinomial para testar se um idioma é LR (k) (além de comprar o livro)?
User541686
2

Temos que verificar apenas se uma gramática é LL ou não, porque toda gramática LL é LR que é LL, é um subconjunto adequado de LR. Portanto, se uma gramática é LL, deve ser LR, mas todo LR não é LL.

Uma gramática G está em LL se, sempre que A-> C | D, a seguinte condição deve ser válida:

  1. Primeiro (C) e Primeiro (D) são conjuntos disjuntos.
  2. Se vazio estiver em Primeiro (D), o Primeiro (C) e o Seguido (A) são conjuntos separados, assim como vazio está em Primeiro (C).
Deb
fonte