Recursive Descent Parser

This is a discussion on Recursive Descent Parser within the C Programming forums, part of the General Programming Boards category; I'm writing a program in C for my programming languages class which must implement a RDP using a certain EBNF ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    2

    Recursive Descent Parser

    I'm writing a program in C for my programming languages class which must implement a RDP using a certain EBNF grammar for legal C statements. I have never programmed in C, so I have been having a tough time formulating the steps that can do this without being ugly, so I would like some advice on writing the parser if anyone can help.

    Here is the EBNF grammar
    Code:
    <statement> ::= ; | <assignment> | <ifStatement> | <whileStatement>
    
    <assignment> ::= <identifier> = <expression> ;
    
    <ifStatement> ::= if ( <expression> ) <statement> [ else <statement> ]
    
    <whileStatment> ::= while ( <expression> ) <statement>
    
    <expression> ::= <conjunction> { | | <conjunction> }*
    
    <conjunction> ::= <relation> { && <relation> }*
    
    <relation> ::= <addition> { (< | <= | > | >= | == | !=) <addition> }*
    
    <addition> ::= <term> { (+ | -) <term> }*
    
    <term> ::= <negation> { (* | /) <negation> }*
    
    <negation> ::= [ ! ] <factor>
    
    <factor> ::= <identifier> | <literal> | ( <expression> )
    
    <identifier> ::= <letter> | <identifier> <letter> | <identifier> <digit>
    
    <letter> ::= a | b | ... | z | A | B | ... | Z
    
    <digit> ::= 0 | 1 | 2 | ... | 9
    
    <literal> ::= <boolean> | <integer>
    
    <boolean> ::= true | false
    
    <integer> ::= <digit> | <integer> <digit>
    right now, my program is reading input from a sample text file which contains single lines of sample code. It saves each line in a character array, so that is how I am planning on working with each line of text.

    I am thinking of making a statement function, that will parse through the string until it finds either a ";" or "=" or a "(" and then depending on what it finds, passing the string down into the appropriate function for that character, ie. if I find the equal sign, it will be an assignment, so I jump into an assignment function.

    Does this seem feasible?

  2. #2
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,546
    > I have never programmed in C
    But are you an experienced programmer in some other language?

    If not, this seems a tough first assignment.

    A separate function for each BNF production is one way to go.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    2
    yeah I've programmed in Java before, but never C.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. recursive function
    By technosavvy in forum C Programming
    Replies: 1
    Last Post: 02-29-2008, 04:42 AM
  2. Problem with a file parser.
    By Hulag in forum C++ Programming
    Replies: 7
    Last Post: 03-17-2005, 08:54 AM
  3. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21