Need algorithm for parser for Context-Free Grammar

This is a discussion on Need algorithm for parser for Context-Free Grammar within the C++ Programming forums, part of the General Programming Boards category; Hi all I am doing a project for my B.Sc(Honns). The project is to make a simulator for a programmable ...

  1. #1
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35

    Question Need algorithm for parser for Context-Free Grammar

    Hi all

    I am doing a project for my B.Sc(Honns). The project is to make a simulator for a programmable robot. Sounds easy, right? Right.

    Anyway, my biggest problem right now is that I need to write a parser for the simulator's language. The language is a small subset of C - nothing complicated, just three pages of context-free grammar...

    This has had me stumped for a week now - I tried using up to about four nested loops to do the job - it clearly doesn't work. Loops are not the way to go. So instead of wasting another week on trying to use recursion in five different ways, I decided to ask if anyone here has an algorithm for parsing context-free grammars?
    I code.
    I think.
    Ergo, I think in code.

  2. #2
    Registered User
    Join Date
    Sep 2004
    Posts
    719
    try:
    http://www.programmersheaven.com/zone3/cat486/index.htm

    or search for regular expression packages for c/c++ (if you're allowed to)
    i seem to have GCC 3.3.4
    But how do i start it?
    I dont have a menu for it or anything.

  3. #3
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35
    Thanks, I think I've found what I'm looking for on

    http://downloads.openwatcom.org/

    I'm downloading the sources now (>40MB... ) so that I can look through them.

    -K
    I code.
    I think.
    Ergo, I think in code.

  4. #4
    Crazy Fool Perspective's Avatar
    Join Date
    Jan 2003
    Location
    Canada
    Posts
    2,640
    Wouldnt you want a lexical analyser? An arbitrary CFG parser sounds like overkill if your language is a sub-set of C.

  5. #5
    Registered User
    Join Date
    Mar 2002
    Location
    South Africa
    Posts
    35
    Wouldnt you want a lexical analyser? An arbitrary CFG parser sounds like overkill if your language is a sub-set of C.
    The truth is that I'm dipping into compiler construction for the first time - so I wouldn't know.

    As a first step I want to be able to tell if the given program is syntactically legal. I thought you needed a parser to be able to do this? Anyways, I've been reading one of the books that my professor lent me - it seems a Finite State Automaton is the way to go.

    After that (once I'm sure that the syntax is o.k.), I want the program to be interpreted. It's a really small subset of C that I want to use - here is my grammar, in case you're interested. I thought interpreting (as opposed to compiling) would make it easier for me.

    If I may hazard a guess, I would say that you're going to reply that I need both a lexical analyser and a parser - the lexer for the syntax checker, and the parser for the interpreter?

    Code:
    PROG		  -> #include <cord.h> FUNC_DEFS MAIN_FUNC
    MAIN_FUNC	  -> void main ( ) COMPOUND_STMT
    FUNC_DEFS	  -> FUNC_DEFS FUNC_DEF
    FUNC_DEFS	  -> FUNC_DEF
    FUNC_DEFS	  -> 
    FUNC_DEF	  -> FUNC_HDR COMPOUND_STMT
    FUNC_HDR	  -> TYPE ID ( PARAM_LIST )
    TYPE		  -> void
    TYPE		  -> CALC_TYPE
    CALC_TYPE	  -> int
    CALC_TYPE	  -> bool
    PARAM_LIST	  -> PARAM_LIST , PARAM
    PARAM_LIST	  -> PARAM
    PARAM_LIST	  -> 
    PARAM		  -> CALC_TYPE ID
    COMPOUND_STMT	  -> { STMT_LIST }
    STMT_LIST	  -> STMT_LIST STMT
    STMT_LIST	  -> STMT
    STMT		  -> FLOW_CONTROL_STMT
    STMT		  -> CALC_STMT ;
    STMT		  -> DECL_STMT ;
    FLOW_CONTROL_STMT -> for ( ID = ARITH_EXPR ; LOGIC_EXPR ; CALC_STMT ) COMPOUND_STMT
    FLOW_CONTROL_STMT -> while  ( LOGIC_EXPR ) COMPOUND_STMT
    FLOW_CONTROL_STMT -> if ( LOGIC_EXPR ) COMPOUND_STMT
    FLOW_CONTROL_STMT -> if ( LOGIC_EXPR ) COMPOUND_STMT else COMPOUND_STMT
    DECL_STMT	  -> CALC_TYPE ID = ARITH_EXPR
    DECL_STMT	  -> const CALC_TYPE ID = ARITH_EXPR
    CALC_STMT	  -> ID = ARITH_EXPR
    CALC_STMT	  -> ARITH_EXPR
    LOGIC_EXPR	  -> ( LOGIC_EXPR )
    LOGIC_EXPR	  -> ! LOGIC_EXPR
    LOGIC_EXPR	  -> ARITH_EXPR REL_OP ARITH_EXPR
    LOGIC_EXPR	  -> LOGIC_EXPR BIN_LOGIC_OP LOGIC_EXPR
    LOGIC_EXPR	  -> ID ( PARAMETER_LIST ) 
    BIN_LOGIC_OP	  -> &&
    BIN_LOGIC_OP	  -> ||
    PARAMETER_LIST	  -> PARAMETER_LIST , ARITH_EXPR
    PARAMETER_LIST	  -> ARITH_EXPR
    ARITH_EXPR	  -> ( ARITH_EXPR )
    ARITH_EXPR	  -> ~ ARITH_EXPR
    ARITH_EXPR	  -> ARITH_EXPR BIN_MATH_OP ARITH_EXPR
    ARITH_EXPR	  -> ID
    ARITH_EXPR	  -> INT_LITERAL
    ARITH_EXPR	  -> ID ( PARAMETER_LIST )
    REL_OP		  -> >
    REL_OP		  -> <
    REL_OP		  -> ==
    BIN_MATH_OP	  -> +
    BIN_MATH_OP	  -> -
    BIN_MATH_OP	  -> *
    BIN_MATH_OP	  -> /
    BIN_MATH_OP	  -> &
    BIN_MATH_OP	  -> |
    ID		  -> [a-Z][a-Z0-9]*
    INT_LITERAL	  -> [0-9]*
    I code.
    I think.
    Ergo, I think in code.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Help needed with backtracking
    By sjalesho in forum C Programming
    Replies: 1
    Last Post: 11-09-2003, 06:28 PM
  2. "if you love someone" :D
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 12
    Last Post: 10-02-2003, 02:10 AM
  3. Question about atheists
    By gcn_zelda in forum A Brief History of Cprogramming.com
    Replies: 160
    Last Post: 08-11-2003, 12:50 PM
  4. SIGABRT upon free()
    By registering in forum C Programming
    Replies: 2
    Last Post: 07-19-2003, 08:52 AM
  5. How can I free what strtok returns?
    By registering in forum C Programming
    Replies: 3
    Last Post: 06-24-2003, 05:56 PM

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