repérer une BNF ambiguë

Question

J'ai un devoir de corriger un BNF ambigu, mais je suis complètement perdu. Je sais que ce n'est pas une vraie question de programmation, et je vais la supprimer avec plaisir si ce n'est pas une question appropriée pour ces conseils. Y a-t-il de bons sites où je pourrais en apprendre plus sur les BNF? Celui auquel j'ai affaire semble plutôt simple, mais je ne trouve pas d'exemples ou de bonnes explications concernant BNF. J'ai eu de l'expérience en repérant des arbres d'analyse ambigus et d'autres sortes de grammaires, mais je suis complètement perdu sur celui-ci. Puisqu'il s'agit d'une tâche d'école, je ne suis pas sûr que je devrais publier la BNF en question, mais si quelqu'un connaît un bon site que je pourrais examiner pour peut-être mieux comprendre comment attaquer ma question. Je ne sais vraiment pas par où commencer.

Answer 1

Certains BNF décrivant une grammaire sans contexte décrivent également une machine d'état (dans ce cas un Pushdown automata). La meilleure façon de le faire est probablement par l'inspection de la machine d'état. Pour commencer, vous pouvez regarder ce qu'est un conflict dans parsers that make use of such automata.

Answer 2

S'il y a deux ou plusieurs des mêmes non-terminales du côté droit d'une phrase, c'est ambigu. Par exemple: < expr> -> < expr> + < expr> | < facto>. Le côté droit expr peut être exporté de différentes manières dans l'arbre, ce qui permet de tracer des arbres différents et c'est ambigu.