Re: [Caml-list] yacc question

[Brian Hurt <bhurt@spnz.org>]

On Mon, 5 Dec 2005, skaller wrote:

> I have the 'usual' kind of parser for expressions, with two
> nonterminals 'expr' and 'atom', the latter including ( expr )
> and INTEGER of course.
>
> When I have input like
>
> 1;
> 1 + 2 ;
> (1 + 2) ;
>
> none of the case parse as expressions, the first and
> last do parse as atoms (leaving the ; in the buffer).
>
> What I want is to parse the longest possible match.
> The only way I can think of doing this is:
>
> top_expr:
>  | expr token_not_allowed_in_expressions
>
> and then 'put back' the trailing token into the buffer.
> Is there another way?
>

The standard way to implement this is:

statement:
 	expression SEMICOLON

expression:
 	| mul_expression
 	| expression PLUS mul_expression
 	| expression MINUS mul_expression

mul_expression:
 	atom_expression
 	| mul_expression TIMES atom_expression
 	| mul_expression DIVIDE atom_expression
 	| mul_expression MODULO atom_expression

atom_expression:
 	ATOM
 	| OPEN_PAREN expression CLOSE_PAREN

Notice that precedence is taken care of immediately- 3 + 4 * 5 is parsed 
as 3 + (4 * 5).  Also notice that the semicolon is what terminates us- we 
keep collecting up an expression until we see a semicolon- only then do we 
complete the statement.

Hope this helps.

Brian