Re: Generating parse-table for table-driven EBNF parser.

djast@my-deja.com wrote:


>I've written a recursive-descent EBNF parser to read in language-
>definitions, with the goal of generating parsers for these languages.
>So as the recursive-descent parser is processing the definition, I
>need to build up some appropriate internal-representation of it which
>I can then process in order to create the parse-table for a
>table-driven parser for that language. I know this should be pretty
>straight- forward but the books I've got don't have information on
>_generating the table for a table-driven EBNF parser_.


A simple solution is to rewrite the EBNF to BNF and use the standard
LL(1) construction. This can be found in, e.g., the Dragon book.


The advantage of this approach is that you get the benefit of EBNF
when specifying your grammars and the simplicity of BNF when running
the parsers.


It isn't difficult to translate EBNF to BNF:




      N ::= ... (E1|E2) ...
  |
  V
      N -> ... N1 ...
      N1 -> E1
      N1 -> E2




      N ::= ... {E} ...
  |
  V
      N -> ... N1 ...
      N1 -> \epsilon
      N1 -> E N1




      N ::= ... [E] ...
  |
  V
      N -> ... N1 ...
      N1 -> \epsilon
      N1 -> E




Torben Mogensen (torbenm@diku.dk)

Return to the comp.compilers page.
Search the comp.compilers archives again.