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:

  1. Convert the grammar to Chomsky Normal Form (all productions have either a single terminal or two non-terminals).
  2. 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).
  3. 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.