[Caml-list] ocamlyacc help

[Caml-list] ocamlyacc help

[Jonathan Roewen]

Hi,

I'm trying to write a parser, but I've become very unstuck.

I want to parse a string of format:

(OP FLOAT*)* and generate a (char * float list) list.

The problem I have is I don't know how to generate further tuples.

Jonathan

Re: [Caml-list] ocamlyacc help

[Eric Cooper]

On Sat, Sep 10, 2005 at 10:40:28PM +1200, Jonathan Roewen wrote:
> I want to parse a string of format:
> 
> (OP FLOAT*)* and generate a (char * float list) list.
> 
> The problem I have is I don't know how to generate further tuples.

(Re)read the Dragon book on LALR parsing!

%token <char>	OP
%token <float>	FLOAT

%start expr
%type <(char * float list) list> expr

%%

expr:
	op_list				{ List.rev $1 }
;

op_list:
	/* empty */			{ [] }
  |	op_list OP float_list		{ ($2, List.rev $3) :: $1 }
;

float_list:
	/* empty */			{ [] }
|	float_list FLOAT		{ $2 :: $1 }
;

Note that it's good practice to write rules for "lists of things" in a
left-recursive style, because that allows LALR parsers to handle
arbitrarily-long lists without stack overflow.  In OCaml, where the
natural semantic action for a list is to build a list, you probably want
to build the list backwards (i.e. $2 :: $1 instead of $1 @ [$2]),
and then reverse it where it's used (if that's even necessary).

-- 
Eric Cooper             e c c @ c m u . e d u