少于 1 分钟阅读

Serving Order

When preparing a Context-Free Grammar (CFG) for parsing, especially for top-down parsers like LL parsers, the following 4 CFG preprocessing procedures are better to be performed in this order:

  1. Simplification
  2. Disambiguation
  3. Eliminate left recursion
  4. Left factoring

Some may argue that procedure #3 and #4 can be done in reversed order.

If you’re writing a bottom-up parser (e.g., LR parser), left recursion is not a problem, so you might skip procedure #3.

More on $\varepsilon$-production elimination in procedure #1

In real-world compiler design, grammars are not always simplified to eliminate $\varepsilon$-productions for the following reasons:

  1. $\varepsilon$-productions can model “optional” constructs like optional else after if, empty parameter list in functions, etc.
  2. Eliminating $\varepsilon$-productions can make grammars ugly

So eliminating $\varepsilon$-productions best works for theoretical proofs.

Scenario Eliminate $\varepsilon$-productions? Reason
Real-world languages ❌ No (and often) Readability, maintainability, and intuitive grammar design.
Theoretical proofs ✅ Yes Required for formalisms like CNF or to prove grammar properties.
Parser optimizations ✅ Yes (but rare) Modern tools handle ε efficiently; elimination is no longer needed.

分类:

更新时间:

留下评论