Boyer-Moore Search

February 10, 2012

Boyer-Moore search algorithms.

Boyer-Moore algorithms for searching a text for a single substring.
These modules use a reverse (right->left), pattern scan with two predefined shift functions resulting in an average sub-linear performance:  O(text-length/pattern-length).
______________________

MAKEFILE
BM.H
BM.C
BM.TST
______________________

Tuned Boyer-Moore search algorithm.

Tuned Boyer-Moore (BM) algorithm for fast string searching.
These modules implement a compact, portable and fast BM algorithm, ie. an unrolled variant of search forward for rightmost char in the pattern.

______________________

MAKEFILE
TBM.H
TBM.C
______________________


Aho-Corasic Search

February 10, 2012

Aho-Corasic search algorithm.

Aho-Corasic algorithm for searching a text for several fixed substrings. These modules implement a simple “Finite State Automaton” (FSA) to locate all occurences of any of a number of keywords in a string of text.
______________________

MAKEFILE
AC.H
AC.C
______________________


Bool

March 29, 2010

Boolean expression evaluation

These modules implement a simple compiler for evaluating boolean expressions.
The compiler is structured into two parts :

1: a front end for transforming a boolean expression from infix form to postfix form (consisting of : SCANNER, PARSER, EMITTER);

2: a back end for interpreting the postfix boolean expression using an abstract/software stack machine (consisting of : INTERPRETER).

The compiler “front end” and “back end” communicate using a common symbol table (cf BOOL.H).
______________________
MAKEFILE
BOOL.H
BOOL.C
BOOLTST.BAT
______________________
BOOL.C includes the general header files (see blog post: General):
general.h, error.h and stack.h


General

March 29, 2010

General header files for C-program compilation

Targeting MS-DOS or UNIX OS.
Includes macros (in STACK.H) for creating stacks of simple objects.
Includes macros (in ERROR.H) for general error handling.
______________________
GENERAL.H
STACK.H
STACK.C
STACK.TST
______________________
MAKEFILE
ERROR.H
ERROR.C
ERROR.TST