Quando é uma ambígua gramática ou regra de produção OK? (Mudança bisontes / reduzir avisos)

Question

Há certamente uma abundância de documentos e howtos na resolução de deslocamento / reduzir erros. Os docs bisonte sugerem a solução correta é geralmente apenas% esperam-los e lidar com ele.

Quando você tem coisas como esta:

S: S 'b' S | 't'

Você pode facilmente resolvê-los assim:

S: S 'b' T | T
T: 't'

A minha pergunta é: é melhor deixar a gramática um toque ambíguo e% esperam shift / reduzir os problemas ou é melhor para tentar ajustar a gramática para evitá-los? Eu suspeito que há um equilíbrio e é baseado nas necessidades do autor, mas eu realmente não sei.

Answer 1

Como eu lê-lo, sua pergunta é "Quando é uma ambígua gramática ou regra de produção OK?"

Primeiro, considere o idioma que você está descrevendo. Qual seria a implicação de permitir uma regra de produção ambígua para a língua.

O exemplo descreve uma linguagem que pode incluir uma expressão como: t b t b t b t

A expressão resolvida como no seu segundo exemplo seria (((( t ) b t) b t ) b t ) mas em uma gramática ambígua que também poderia tornar-se ( t b ( t b ( t b ( t)))) ou mesmo ( t b t ) b ( t b t ). Que poderia ser válida pode dependem do idioma. Se o modelo de operador b subtração, ele realmente não deve ser ambígua, mas se fosse disso, pode ser ok. Isso realmente depende do idioma.

A segunda questão a considerar é que o arquivo de origem gramática resultante acaba parecendo, após os conflitos são resolvidos. Tal como acontece com outro código-fonte, uma gramática é feito para ser lido por seres humanos, e, secundariamente, também por computadores. Prefere uma notação que dá uma explicação mais clara do que o analisador está tentando fazer da gramática. Ou seja, se o analisador está executando algum comportamento possivelmente indefinido, por exemplo, ordem de avaliação de argumentos de uma função em uma linguagem ansioso, fazer a gramática olhar ambígua.

Answer 2

You can guide the conflict resolution with operator precedence. Declare 'b' as an left- or right-associative operator and you have covered at least that case.

For more complex patterns, as long as the final parser produces the correct result in all cases, the warnings isn't much to worry about. Though if you can't get it to give the correct result using declarations you would have to rewrite the grammar.

Answer 3

In my compiler course last semester we used bison, and built a compiler for a subset of pascal.

If the language is complex enough, you will have some errors. As long as you understand why they are there, and what you'd have to do to remove them, we found it to be alright. If something was there, but due to the behaviour would work as we wanted it to, and would require much to much thought and work to make it worth while (and also complicating the grammar), we left it alone. Just make sure you fully understand the error, and document it somewhere (even for yourself), so that you always know what's going on with it.

It's a cost/benefit analysis once things get really involved, but IMHO, fixing it should be considered FIRST, then actually figure out what the work would be (and if that work breaks something else, or makes something else harder), and go from there. Never pass them off as commonplace.

Answer 4

When I need to prove that a grammar is unambiguous, I tend to write it first as a Parsing Expression Grammar, and then convert it by hand to whatever grammar type the tool set I'm using for the project needs. In my experience, the need for this level of proof is very rare, though, since most shift/reduce conflicts I have come across have been fairly trivial ones to show the correctness of (on the order of your example).