Re: First Order Logic (FOL) parsing

On Dec 7, 3:49 am, Erotavlas_tu...@libero.it wrote:
> Hi All,
>
> I'm new about the topic of parsing. I have to develop a parser/compiler for
> First Order Logic (FOL) clauses in C/C++ language. I have made a lot of
search
> on the web but I have found only a source codes written in ML, PROLOG,
> Haskell, Python, etc. I have also found a open source AI project that is
> written in C/C++ which has a internal FOL parser developed with Bison. The
> project is Alchemyhttp://alchemy.cs.washington.edu/. Do you know it? and
what
> do you think about it? It's better to try to use it or to rewrite a new
> parser?
>
> At the moment I'm studying Flex and Bison to understand how I can generate a
> parser. I think it's a big work for me. Do you know if exist an open source
> implementation (C/C++) from which I can start apart of Alchemy project?
>
> I would like to know if a LALR parser is able to treat a FOL grammar or if I
> need a GLR parser. What do you think?


It should certainly be easy to parse any reasonable grammar for FOL
with a LALR(1) or LL(1) parser. For example if you translate the
description at http://www.sju.edu/~jhodgson/ugai/1order.html to Bison,
you get something like this


%token PREDICATE FUNCTION CONSTANT VARIABLE
%token IMPLIES AND OR IFF THERE_EXISTS FORALL
%left '='
%left VARIABLE
%left IMPLIES
%left IFF
%left AND
%left OR
%left NOT
%%


sentence
: atomic_sentence
| sentence IMPLIES sentence
| sentence IFF sentence
| sentence AND sentence
| sentence OR sentence
| quantifier VARIABLE sentence
| '~' sentence %prec NOT
| '(' sentence ')'
;
atomic_sentence
: PREDICATE '(' term_list ')'
| term '=' term
;
term
: FUNCTION '(' term_list ')'
| CONSTANT
| VARIABLE
;
term_list
: term_list term
| term
;
quantifier
: THERE_EXISTS
| FORALL
;

Return to the comp.compilers page.
Search the comp.compilers archives again.