Thread: 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?

try:
http://www.programmersheaven.com/zone3/cat486/index.htm

or search for regular expression packages for c/c++ (if you're allowed to)

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

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]*