Friday, 21 March 2008

Executable BNF parser in Prolog


% <digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
% <sign> ::= + | -
% <number> ::= [ <sign> ] <digit> { <digit> }


:- op(1120, xfx, ::=).
:- op(11, fx, <), op(13, xf, >).


<digit> ::= 0 ; 1 ; 2 ; 3 ; 4 ; 5 ; 6 ; 7 ; 8 ; 9 .
<sign> ::= (+) ; (-) .
<number> ::= [ <sign> ], <digit>, { <digit> } .

<expr> ::= <factor>, { ((+) ; (-)), <factor> } .
<factor> ::= <term>, { ((*) ; (/)), <term> } .
<term> ::= '(', <expr>, ')' ; <number> .


parse(Rule) --> { Rule ::= Body }, parse(Body).
parse(Atom) --> { atomic(Atom), atom_codes(Atom, Codes) }, Codes.

parse((X , Y)) --> parse(X), parse(Y).

parse((X ; _)) --> parse(X).
parse((_;Y;Z)) --> parse(Y ; Z).
parse((_ ; Z)) --> { Z \= (_ ; _) }, parse(Z).

parse([X]) --> parse(X).
parse([_]) --> {}.

parse({X}) --> parse(X), parse({X}).
parse({_}) --> [].


% phrase(parse(<expr>), "-5*(73+7)").



Compare with a C implementation -- http://cvs.savannah.gnu.org/viewvc/bnf/bnf/src/grio.c?view=markup

2 comments:

Vanesa said...

Thanks...

Andrew said...

Hi this system is awesome, but I can't figure out how to get it to work. Could you perhaps illustrate it's use by feeding the executable parser you have there with two files - a BNF for a language and a sample of the language? I've been trying to get it to work, and it sort of does, but I can't figure out how to do it completely correctly. Thanks!