Re: First Order Logic (FOL) parsing

Gene <gene.ressler@gmail.com>
Fri, 10 Dec 2010 19:27:14 -0800 (PST)

          From comp.compilers

Related articles
First Order Logic (FOL) parsing Erotavlas_turbo@libero.it (2010-12-07)
Re: First Order Logic (FOL) parsing haberg-news@telia.com (Hans Aberg) (2010-12-10)
Re: First Order Logic (FOL) parsing gene.ressler@gmail.com (Gene) (2010-12-10)
| List of all articles for this month |

From: Gene <gene.ressler@gmail.com>
Newsgroups: comp.compilers
Date: Fri, 10 Dec 2010 19:27:14 -0800 (PST)
Organization: Compilers Central
References: 10-12-016
Keywords: parse
Posted-Date: 14 Dec 2010 20:35:25 EST

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
;



Post a followup to this message

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