spotting an Ambiguous BNF
I have an assignment to correct an ambiguous BNF, but I am completely lost. I know this not a true programming question, and I will gladly delete it if it is not an appropriate question for these boa开发者_开发问答rds. Are there any good sites where I could learn more about BNF's? The one I am dealing with seems rather simple, but I can't find any examples or good explanations regarding BNF's. I have had some experience spotting ambiguous parse trees and other sorts of grammars, but I am completely lost on this one.
Since it is a school assignment, I am not sure I should post the BNF in question, but if anyone knows of a good site that I could look over to perhaps gain a better understanding of how to attack my question. I really just don't know where to start.
Some BNF describing a context-free grammar is also describing a state machine (in this case a Pushdown automata). The best way to do this is probably by inspection of the state machine.
As a starting point, you could look into what a conflict is within parsers that make use of such automata.
If there are two or more of the same nonterminals at the right side of a sentence it's ambiguous. For example: < expr > -> < expr > + < expr > | < facto >. The right side expr's can be exported in different ways in the tree, so different trees can be drawn and it's ambiguous.
精彩评论