Appetizers Before Parsing: Serving Order
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:
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:
- $\varepsilon$-productions can model “optional” constructs like optional
else
afterif
, empty parameter list in functions, etc. - 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. |
留下评论