Recursive Descent (LL) Parsing

• This is a nonsense grammar from a programming contest: the lowercase words are non-terminals, the uppercase characters are the terminals of this language.

    slurpy -> slimp slump
    slimp -> A rest_slimp 
    rest_slimp  -> H
    rest_slimp -> B slimp C
  
    rest_slimp -> slump C
    slump -> d_or_e F f_string end 
    d_or_e -> D
    d_or_e -> E
    f_string -> F f_string | lambda
    end -> slump
    end -> G 
   
  
  Some strings in the language: AHDFG, ADFGCDFFFFFG, ABAEFGCCDFEFFFFFFG
  Some strings NOT in the lanuage: AHDFGA, DFGAH, ABABCC

  1. Write out the First sets for each of the non-terminals in the "slurpy" grammar
  2. In class we will go over writing a pseudo-code for a recursive descent parse of this grammar.
     • Each non-terminal in the grammar is represented by a function in your code.
     • Each terminal is checked with the char in "lookahead", then call "match",
     • match() checks the char in lookahead and updates lookahead to the next char in
       the input stream.
  3. Write a recursive descent parser to ACCEPT or REJECT strings in this grammar.
  4. Example: parse.c, a recursive descent solution to the grammar L --> ( L )L | [ L ]L | lambda
  5. You can use any language to write this parser

  With this program, we can accept or reject the individual inputs. An example input might be:

  AHDFG
  DFGAH
  ADFGCDFFFFG
  

  with output: ACCEPT, REJECT, ACCEPT