Search code examples
compiler-constructioncontext-free-grammar

Compiler Construction Overlapping First Sets


I am attempting to create a compiler and have calculated the first sets but have run into the following problem.

LHS -> Var
LHS -> Field

Where Var and Field are nonterminals with overlapping first sets thus making the grammer ambiguous. I was wondering if there is an way to solve this problem.


Solution

  • "Ambiguous" means there are two or more possible parses. That's probably not the case with your grammar. Overlapping FIRST sets indicates that a top-down parser isn't capable of guessing the correct parse. That doesn't mean that there isn't one. A bottom-up parser may well just work.

    If you insist on too-down parsing, you'll need to modify your grammar. There are standard heuristics, although nothing is guaranteed to work and it may simply be impossible. Often, you will find that left-factoring is sufficient. You may also need to eliminate left-recursion. You'll find algorithms for both of these in your textbook (if you have one), on Wikipedia, and all over the internet. (Of course, not all of the algorithms you'll find on the internet are correct, bug-free, and well-explained.)