Re: Parsing implicit operators with recursive descent?

"Johann 'Myrkraverk' Oskarsson" <johann@myrkraverk.com> writes:




> Is it possible to parse implicit operators, like the regular
> expression concatenation operator, with a recursive descent parser?


Yes, you can do it mostly by standard grammar-rewriting techniques.


Let us take regular expressions as an example. We start with the
grammar:




    R -> R | R
    R -> R R
    R -> R *
    R -> a


Note that the | above is a terminal. a stands for any alphabet symbol.


We start by eliminating ambiguity. We choose (as normal) | to bind
weaker than concatenation which binds weaker than Kleene-star. We
also choose | and concatenation to be right-associative. They are
semantically fully associative, so we could choose any. But we get
less left-recursion to eliminate later by choosing them to be
right-assciative.


    R -> C | R
    R -> C
    C -> S C
    C -> S
    S -> S *
    S -> a


We now do left factorisation and left-recursion elimination:


    R -> C R'
    R' -> | R
    R' ->
    C -> S C'
    C' -> C
    C' ->
    S -> a S'
    S' -> * S'
    S' ->


To see if this is LL(1), we need to calculate FIRST and FOLLOW.
Below, I have for each production added the FIRST set:




    R -> C R' {a}
    R' -> | R {|}
    R' -> {}
    C -> S C' {a}
    C' -> C {a}
    C' -> {}
    S -> a S' {a}
    S' -> * S' {*}
    S' -> {}


The FOLLOW sets are:


  FOLLOW(R) = {$}
  FOLLOW(R') = {$}
  FOLLOW(C) = {$,|}
  FOLLOW(C') = {$,|}
  FOLLOW(S) = {$,|,a}
  FOLLOW(S') = {$,|,a}


This leads to the following parse table:


      | a * | $
  --+------------------------------
  R | R->CR'
  R'| R'->|R R'->
  C | C->SC'
  C'| C'->C C'-> C'->
  S | S->aS'
  S'| S'-> S'->*S' S'-> S'->


which has no conflicts, so the grammar is LL(1).


The parse table can easily be rewritten to a recursive descent parser.


Torben

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