Author: baby-guest Date: 2008-02-29 11:42:51 +0000 (Fri, 29 Feb 2008) New Revision: 5955
Added: software/gofind/BoolExprParser.cpp software/gofind/BoolExprParser.h Modified: software/gofind/Makefile software/gofind/filter.cpp software/gofind/filter.h software/gofind/slre.h software/gofind/utf8.h Log: Added parser for boolean expressions Added: software/gofind/BoolExprParser.cpp =================================================================== --- software/gofind/BoolExprParser.cpp (rev 0) +++ software/gofind/BoolExprParser.cpp 2008-02-29 11:42:51 UTC (rev 5955) @@ -0,0 +1,180 @@ +/* $Id: BoolExprParser.cpp,v 1.11 2005/05/09 02:43:19 sarrazip Exp $ + BoolExprParser.cpp - Boolean expression parser and syntax tree builder + + boolstuff - Disjunctive Normal Form boolean expression library + Copyright (C) 2002-2005 Pierre Sarrazin <http://sarrazip.com/> + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. +*/ + +#include <boolstuff/BoolExprParser.h> + +#include <cassert> +#include <memory> + +using namespace std; +using namespace boolstuff; + + +BoolExprParser::BoolExprParser() + : curInput(), + curIndex(0) +{ +} + + +BoolExprParser::~BoolExprParser() +{ +} + + +BoolExpr<string> * +BoolExprParser::parse(const std::string &expr) throw(Error) +{ + curInput = expr; + curIndex = 0; + + auto_ptr< BoolExpr<string> > root(parseExpr()); + if (!atEnd()) + throw Error(curIndex, Error::GARBAGE_AT_END); + return root.release(); +} + + +BoolExpr<string> * +BoolExprParser::parseExpr() throw(Error) +{ + auto_ptr< BoolExpr<string> > left(parseTerm()); + + if (!tokenSeen("|")) + return left.release(); + + skipToken("|"); + BoolExpr<string> *right = parseExpr(); // may throw + return new BoolExpr<string>(BoolExpr<string>::OR, left.release(), right); +} + + +BoolExpr<string> * +BoolExprParser::parseTerm() throw(Error) +{ + auto_ptr< BoolExpr<string> > left(parseFactor()); + + if (!tokenSeen("&")) + return left.release(); + + skipToken("&"); + BoolExpr<string> *right = parseTerm(); // may throw + return new BoolExpr<string>(BoolExpr<string>::AND, left.release(), right); +} + + +BoolExpr<string> * +BoolExprParser::parseFactor() throw(Error) +{ + bool v = true; + while (tokenSeen("!")) + { + skipToken("!"); + v = !v; + } + + BoolExpr<string> *atom = parseAtom(); // may throw + if (v) + return atom; + + return new BoolExpr<string>(BoolExpr<string>::NOT, NULL, atom); +} + + +BoolExpr<string> * +BoolExprParser::parseAtom() throw(Error) +{ + skipSpaces(); + size_t startIndex = curIndex; + if (tokenSeen("(")) + { + skipToken("("); + auto_ptr< BoolExpr<string> > expr(parseExpr()); // may throw + + if (!tokenSeen(")")) + throw Error(startIndex, Error::RUNAWAY_PARENTHESIS); + skipToken(")"); + + return expr.release(); + } + + return parseString(); // may throw +} + + +BoolExpr<string> * +BoolExprParser::parseString() throw(Error) +{ + skipSpaces(); + size_t inputLen = curInput.length(); + if (curIndex == inputLen) + throw Error(curIndex, Error::STRING_EXPECTED); + size_t startIndex = curIndex; + while (curIndex < inputLen && isStringChar(curInput[curIndex])) + curIndex++; + if (curIndex == startIndex) + throw Error(startIndex, Error::STRING_EXPECTED); + string s(curInput, startIndex, curIndex - startIndex); + return new BoolExpr<string>(s); +} + + +bool +BoolExprParser::atEnd() +{ + skipSpaces(); + return curIndex == curInput.length(); +} + + +bool +BoolExprParser::tokenSeen(const char *s) +{ + if (s == NULL) + return false; + + skipSpaces(); + return strncmp(curInput.c_str() + curIndex, s, strlen(s)) == 0; +} + + +void +BoolExprParser::skipToken(const char *s) +{ + curIndex += strlen(s); +} + + +void +BoolExprParser::skipSpaces() +{ + size_t inputLen = curInput.length(); + while (curIndex < inputLen && isspace(curInput[curIndex])) + curIndex++; +} + + +bool +BoolExprParser::isStringChar(char c) const +{ + return isalnum(c) || c == '_'; +} Added: software/gofind/BoolExprParser.h =================================================================== --- software/gofind/BoolExprParser.h (rev 0) +++ software/gofind/BoolExprParser.h 2008-02-29 11:42:51 UTC (rev 5955) @@ -0,0 +1,116 @@ +/* $Id: BoolExprParser.h,v 1.12 2005/05/09 02:43:19 sarrazip Exp $ + BoolExprParser.h - Boolean expression parser and syntax tree builder + + boolstuff - Disjunctive Normal Form boolean expression library + Copyright (C) 2002-2005 Pierre Sarrazin <http://sarrazip.com/> + + This program is free software; you can redistribute it and/or + modify it under the terms of the GNU General Public License + as published by the Free Software Foundation; either version 2 + of the License, or (at your option) any later version. + + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. + + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA + 02111-1307, USA. +*/ + +#ifndef _H_BoolExprParser +#define _H_BoolExprParser + +#include <boolstuff/BoolExpr.h> + +#include <string> + + +namespace boolstuff { + + +/** + Parser for a language of boolean expressions. + The parse() method dynamically allocates a binary tree of nodes that + represents the syntactic structure of a textual boolean expression. +*/ +class BoolExprParser +{ +public: + + /** Error descriptor. */ + class Error + { + public: + /** Possible error codes returned by the parser. */ + enum Code + { + GARBAGE_AT_END, + RUNAWAY_PARENTHESIS, + STRING_EXPECTED + }; + + /** Index (>=0) in the input string where the error was detected. */ + size_t index; + /** Code that gives the type of the error */ + Code code; + + /** + Initializes an error object with the given index and error. + */ + Error(size_t i, Code c) : index(i), code(c) {} + }; + + + /** + Initializes the parser. + */ + BoolExprParser(); + + /** + Destroys the parser and frees the associated resources. + */ + ~BoolExprParser(); + + /** + Parses a textual boolean expression and creates a binary syntax tree. + Dynamically allocates a tree of nodes that represents the + syntactic structure of 'expr'. + The returned tree must eventually be destroyed with operator delete. + + @param expr text of the boolean expression to parse + @returns the root of the created tree + @throws Error describes a parsing error + */ + BoolExpr<std::string> *parse(const std::string &expr) throw(Error); + +private: + + std::string curInput; + size_t curIndex; + + // Implementation methods: + BoolExpr<std::string> *parseExpr() throw(Error); + BoolExpr<std::string> *parseTerm() throw(Error); + BoolExpr<std::string> *parseFactor() throw(Error); + BoolExpr<std::string> *parseAtom() throw(Error); + BoolExpr<std::string> *parseString() throw(Error); + + bool atEnd(); + bool tokenSeen(const char *s); + void skipToken(const char *s); + void skipSpaces(); + bool isStringChar(char c) const; + + // Forbidden operations: + BoolExprParser(const BoolExprParser &); + BoolExprParser &operator = (const BoolExprParser &); +}; + + +} // namespace boolstuff + + +#endif /* _H_BoolExprParser */ Modified: software/gofind/Makefile =================================================================== --- software/gofind/Makefile 2008-02-29 03:46:42 UTC (rev 5954) +++ software/gofind/Makefile 2008-02-29 11:42:51 UTC (rev 5955) @@ -1,10 +1,10 @@ all: gofind -CFLAGS= -O2 -g `pkg-config libtagcoll2 --cflags` -Wall -Werror +CFLAGS= -O2 -g `pkg-config libtagcoll2 boolstuff-0.1 --cflags` -Wall -Werror LDFLAGS= -LIBS= -lept -lept-core -lapt-pkg -lxapian `pkg-config libtagcoll2 --libs` +LIBS= -lept -lept-core -lapt-pkg -lxapian `pkg-config libtagcoll2 boolstuff-0.1 --libs` -OBJS= Engine.o Environment.o filter.o gofind.o taghandler.o slre.o utf8.o +OBJS= Engine.o Environment.o filter.o gofind.o taghandler.o boolparser.o slre.o utf8.o gofind: $(OBJS) g++ -o $@ $+ $(LDFLAGS) $(LIBS) Modified: software/gofind/filter.cpp =================================================================== --- software/gofind/filter.cpp 2008-02-29 03:46:42 UTC (rev 5954) +++ software/gofind/filter.cpp 2008-02-29 11:42:51 UTC (rev 5955) @@ -20,15 +20,11 @@ #include "filter.h" #include "taghandler.h" +#include "boolparser.h" #include <string> #include <ept/debtags/tag.h> -#define FACET_VIOLENCE "rating:violence" -#define FACET_SEX "rating:sex" -#define FACET_LANGUAGE "rating:language" -#define FACET_DISCRIMINATION "rating:discrimination" - #define GREEN_MINIMUM 2 PackageFilter::PackageFilter() @@ -143,6 +139,11 @@ tagdata.SetTag(element, "rating:language::benign"); tagdata.SetTag(element, "rating:discrimination::none"); AddLast(element); + + AddLast("a&(b|c|d)&d"); + + Print(std::cerr); + std::cerr << std::endl; } PackageFilter::~PackageFilter() @@ -200,6 +201,49 @@ return PackageFilter::Unknown; } +void PackageFilter::AddLast(const char * bool_expr) +{ + bool success = true; + BoolParser parser; + try + { + boolstuff::BoolExpr<std::string> *expr = parser.parse(bool_expr); + assert(expr != NULL); + + expr = boolstuff::BoolExpr<std::string>::getDisjunctiveNormalForm(expr); + if (expr != NULL) + std::cout << expr; + else + { + std::cout << "result too large"; + success = false; + } + + std::cout << std::endl; + + delete expr; + } + catch (BoolParser::Error &err) + { + std::cout << "? column " << err.index + 1 + << " : "; + switch (err.code) + { + case BoolParser::Error::GARBAGE_AT_END: + std::cout << "garbage at end"; + break; + case BoolParser::Error::RUNAWAY_PARENTHESIS: + std::cout << "runaway parenthesis"; + break; + case BoolParser::Error::STRING_EXPECTED: + std::cout << "string expected"; + break; + } + std::cout << std::endl; + success = false; + } +} + PackageFilter pkgfilter; #ifdef UNIT_TEST Modified: software/gofind/filter.h =================================================================== --- software/gofind/filter.h 2008-02-29 03:46:42 UTC (rev 5954) +++ software/gofind/filter.h 2008-02-29 11:42:51 UTC (rev 5955) @@ -84,6 +84,8 @@ list->GetLast()->next = old_list; } + void AddLast(const char * bool_expr); + inline void AddLast(PackageFilter::ResultList *new_list) { if (!list) { list = new_list; } else { list->GetLast()->next = new_list; } Modified: software/gofind/slre.h =================================================================== --- software/gofind/slre.h 2008-02-29 03:46:42 UTC (rev 5954) +++ software/gofind/slre.h 2008-02-29 11:42:51 UTC (rev 5955) @@ -48,9 +48,11 @@ * \meta Match one of the meta character: ^$().[*+?\ */ -#ifndef SLRE_HEADER_DEFINED -#define SLRE_HEADER_DEFINED +#ifndef GOPLAY_SLRE_H_ +#define GOPLAY_SLRE_H_ +#include "common.h" + #ifdef __cplusplus extern "C" { #endif /* __cplusplus */ @@ -107,4 +109,4 @@ } #endif -#endif /* SLRE_HEADER_DEFINED */ +#endif /* GOPLAY_SLRE_H_ */ Modified: software/gofind/utf8.h =================================================================== --- software/gofind/utf8.h 2008-02-29 03:46:42 UTC (rev 5954) +++ software/gofind/utf8.h 2008-02-29 11:42:51 UTC (rev 5955) @@ -15,8 +15,8 @@ * the above three licenses. */ -#ifndef UTF8_HEADER_DEFINED -#define UTF8_HEADER_DEFINED +#ifndef GOPLAY_UTF8_H_ +#define GOPLAY_UTF8_H_ #ifdef __cplusplus extern "C" { @@ -47,4 +47,4 @@ } #endif -#endif /* UTF8_HEADER_DEFINED */ +#endif /* GOPLAY_UTF8_H_ */ _______________________________________________ Pkg-games-commits mailing list [email protected] http://lists.alioth.debian.org/mailman/listinfo/pkg-games-commits
