3
$\begingroup$

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.

$\endgroup$

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.