I am building a parser generator, not for any project in particular, just for fun to improve my understanding of parsing, grammars, languages, etc.
I am at the point where I have lexer generation down pat. That is, I have defined a way to specify token definitions from regexes and split an input string into tokens based on those definitions.
Now I am to the point of building a parser by specifying BNF productions for a grammar. Based on my initial research, I need to convert the grammar to a pushdown automaton. What I've read has told me that I need to do so in 3 steps:
- Convert the grammar to Chomsky Normal Form (all productions have either a single terminal or two non-terminals).
- Convert from Chomsky Normal Form to Greibach Normal Form (all productions have either a single terminal or a terminal followed by a sequence of non-terminals).
- Convert from Greibach Normal Form to a Pushdown Automaton.
There are clear enough algorithms for doing these three steps. However, I am not sure how to go about the actual running of the PDA once I have it. My problem is not with how a PDA works, but with ambiguity.
Basically, I have the following questions:
- Should I account for the fact that a grammar may be ambiguous, or is it a reasonable constraint on the grammar writer to enforce that the grammar be unambiguous?
- If I allow ambiguous grammars, will this add significant overhead to the process of running the PDA? Is there a performant way of running a non-deterministic PDA?
- While on the topic of determinism, can an ambiguous grammar generate a deterministic PDA?
- Will an unambiguous grammar always generate a deterministic PDA?
- I know that determining whether a grammar is ambiguous or not is undecidable, but is there a heuristic that works in most cases?
Basically, in my work on the lexer portion of this parser, I was able to transform non-deterministic finite automata to deterministic finite automata, which allowed me to run the lexer in basically linear time, but I understand that this is not possible to do with pushdown automata, so I'm curious what implications this has on the parsing process, and how I might go about doing this.