Limitações de gramática e analisador geradores PEG?

Question

Eu estava gostando usando YARD muito:

http://www.ootl.org/yard/

http://code.google.com/p/yardparser/

http://www.codeproject.com/KB/recipes/yard- tokenizer.aspx

Eu era capaz de construir calculadora totalmente funcional. Estou avaliando YARD fazer parser PHP. Por favor, informe sobre as limitações de gramática e analisador geradores de PEG. Muito obrigado!

Answer 1

Eu acho que o "problema" grande com PEG é que eles não se encaixam na taxonomia normal das gramáticas como eles operam de uma forma fundamentalmente diferente. gramáticas normais são "para trás" no sentido de que eles descrevem todas as possíveis sentenças (programas) que podem ser gerados. PEGs descrever como analisar - eles vêm para o problema da outra extremidade

.

Na minha opinião, esta é uma maneira mais natural de pensar sobre o problema, e certamente para qualquer (recursiva-descida) parser escrito à mão que eu não faria qualquer outra coisa.

Answer 2

A principal limitação do PEG gramáticas é que eles não lidar com a ambiguidade em tudo.

Para ter certeza, esta é também a sua força desde lidar com ambiguidades é uma das partes mais frustrantes de usar uma ferramenta CFG (contexto livre gramática).

Com PEGs lo a lidar com ambiguidades explicitamente ao ordenar a regra que deseja corresponder antes de uma outra regra que iria corresponder de forma ambígua, mas que você não quer.

O problema é que nem sempre você sabe mesmo sobre alguns ou mesmo qualquer uma das ambigüidades em um idioma ou uma gramática e geradores de PEG, pelo menos os que eu tentei, não analisar a gramática para a ambigüidade de ajudá-lo a encontrá-los e, em seguida, projetar e encomendar o seu regras para lidar com eles da maneira certa.

geradores de analisador CFG como yacc e Bison analisar a sua gramática e relatar todas as ambiguidades. Infelizmente, eles frequentemente relatam eles de uma maneira bastante enigmática que pode ser difícil de fazer sentido. E é claro que é muitas vezes difícil de corrigir a gramática para lidar com eles. Mas pelo menos você vai estar ciente de que eles existem.

Com uma gramática PEG pode ser alegremente ignorante das ambiguidades na sua gramática conceitual porque uma vez que você faz um PEG que não tem ambigüidades mais, ele só tem regras e normas talvez silenciosamente inacessíveis que também correspondem se combinando eles tinham maior precedência. Estes podem não aparecer em seu teste, mas pode aparecer após o lançamento.

Com CFG gramáticas você é forçado a lidar com ambiguidades durante o desenvolvimento, mas não vai ser fácil.

---

No caso eu não estou deixando claro, aqui está uma discussão de seis anos de idade, por Joshua Haberman mais no Lambda the Ultimate linguagens de programação no blog: PEGs e Packrat de análise não são a resposta .