RPA Toolkit
Work on REX documentation.
authorMartin Stoilov <martin@rpasearch.com>
Sat, 18 Feb 2012 04:38:58 +0000 (20:38 -0800)
committerMartin Stoilov <martin@rpasearch.com>
Sat, 18 Feb 2012 04:38:58 +0000 (20:38 -0800)
doc/doxygen/rpa.cfg
rex/doc/rex_main.txt [new file with mode: 0644]
rex/doc/rexdb.txt [new file with mode: 0644]
rex/doc/rexdfa.txt [new file with mode: 0644]
rex/rexdb.h
rex/rexdfa.c
rex/rexdfa.h
rpa/doc/main.txt
rpa/doc/rpa_main.txt
tests/testrexcc/tokenjs.rex

index 99e3963..d3bac28 100644 (file)
@@ -104,7 +104,13 @@ INPUT                  = ../../rpa/rpadbex.h \
                          ../../rpa/doc/rpa_stat.txt \
                          ../../rpa/doc/rpa_record.txt \
                          ../../rpa/doc/rpa_error.txt \
-                         ../../rpa/doc/introduction.txt 
+                         ../../rpa/doc/introduction.txt \
+                         ../../rex/doc/rex_main.txt \
+                         ../../rex/doc/rexdb.txt \
+                         ../../rex/doc/rexdfa.txt \
+                         ../../rex/rexdb.h \                         
+                         ../../rex/rexdfa.h \                         
+                         
 
 INPUT_ENCODING         = UTF-8
 FILE_PATTERNS          =
diff --git a/rex/doc/rex_main.txt b/rex/doc/rex_main.txt
new file mode 100644 (file)
index 0000000..cc7a1fa
--- /dev/null
@@ -0,0 +1,39 @@
+/** \page rex_main "Regular Expressions Library (REX)"
+REX is Automata Compiler - it turns regular expressions into Automaton (NFA or DFA).
+REX does not support back references. REX doesn't support anchors directly, but the support can be added externally.
+The REX library is based on the theory of Deterministic Finite Automata (DFA).
+Regular expressions like '[a-zA-Z_][a-zA-Z0-9_]*' are first compiled to
+Non-deterministic Finite Automata(NFA) and then transformed to DFA, using
+algorithm similar to the DFA subset construction method. 
+
+\section features Features
+- Regular expressions based on Automata theory
+
+- Support for wide characters. By default 32-bit, but it could be redefined at compile time to 64-bit or any other integral size.
+
+\section usage How to use.
+To implement matching using REX, the user has to run the input through the DFA states until the automaton
+arrives at accepting state. For example, if the input is a string:
+@code
+nstate = REX_DFA_STARTSTATE;
+while (*str) {
+    nstate = REX_DFA_NEXT(dfa, nstate, *str);
+    if (REX_DFA_STATE(dfa, nstate)->type == REX_STATETYPE_DEAD) {
+        /* Did not match */
+        break;
+    } else if (REX_DFA_STATE(dfa, nstate)->type == REX_STATETYPE_ACCEPT) {
+        /* The DFA is in accepting state, lets find out what exactly is being accepted. */
+        ++str;     
+        break;
+    } else {
+        /* Keep going... */
+        ++str;
+    }
+}
+@endcode
+
+REX doesn't provide API for matching or searching directly, it is up to the user to decide how to
+implement whatever functionality they need using the automaton.
+
+*/
\ No newline at end of file
diff --git a/rex/doc/rexdb.txt b/rex/doc/rexdb.txt
new file mode 100644 (file)
index 0000000..e9c4ed8
--- /dev/null
@@ -0,0 +1,8 @@
+/** \page rexdb rexdb_t - Loading and compiling regular expressions.
+To load regular expressions, use the rexdb_t API.
+
+- 1. Create a rexdb_t object of type @ref REXDB_TYPE_NFA, using @ref rex_db_create.
+- 2. Load regular expressions, using @ref rex_db_addexpression or @ref rex_db_addexpression_s
+- 3. Create @ref rexdb_t object of type @ref REXDB_TYPE_DFA, using @ref rex_db_createdfa
+
+*/
\ No newline at end of file
diff --git a/rex/doc/rexdfa.txt b/rex/doc/rexdfa.txt
new file mode 100644 (file)
index 0000000..aca5400
--- /dev/null
@@ -0,0 +1,11 @@
+/** \page rexdfa rexdfa_t - Using the DFA for matching.
+
+- 1. Create @ref rexdfa_t object using @ref rex_db_todfa. At this point you can destroy the rexdb_t objects.
+- 2. Use @ref rexdfa_t to implement matching/searching.
+- 3. Destroy the rexdfa_t object when you are done with it.
+
+
+Note: You could also create a @ref rex_nfasimulator_t and/or @ref rex_dfasimulator_t object to run the NFA/DFA automaton directly
+from rexdb_t object, but the recommended way is to create rexdfa_t object.
+
+*/
\ No newline at end of file
index b8bca7e..b572230 100644 (file)
  *  Martin Stoilov <martin@rpasearch.com>
  */
 
+
+/**
+ * @file rex/rexdb.h
+ * @brief Public interface for creating regular expressions.
+ *
+ *
+ * <h2>Synopsis</h2>
+ * The following APIs are used to create a database of regular expressions.
+ */
+
 #ifndef _REXDB_H_
 #define _REXDB_H_
 
index cd7f2d2..f0a9ede 100644 (file)
@@ -173,7 +173,7 @@ void rex_dfa_dumpstate(rexdfa_t *dfa, rexuint_t nstate)
                t = &dfa->trans[s->trans + index];
                n = 0;
                if (t->lowin != t->highin) {
-                       if (isprint(t->lowin) && !isspace(t->lowin) && isprint(t->highin) && !isspace(t->highin))
+                       if (isprint(t->lowin) && !isspace(t->lowin) && isprint(t->highin) && !isspace(t->highin) && !r_strchr("[]-^", t->lowin) && !r_strchr("[]-^", t->highin))
                                n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    [%c - %c] ", t->lowin, t->highin);
                        else
                                n += r_snprintf(buf + n, n < bufsize ? bufsize - n : 0, "    [0x%X - 0x%X] ", t->lowin, t->highin);
index 858d332..1a319a8 100644 (file)
  *  Martin Stoilov <martin@rpasearch.com>
  */
 
+/**
+ * @file rex/rexdfa.h
+ * @brief Definition of DFA interface
+ *
+ *
+ * <h2>Synopsis</h2>
+ * This file defines the data structures and the macros for the DFA implementation.
+ */
+
 #ifndef _REXDFA_H_
 #define _REXDFA_H_
 
@@ -52,15 +61,19 @@ typedef REX_CHAR_TYPE rexchar_t;
 #define REX_CHAR_MAX ((rexchar_t)-1)
 #define REX_CHAR_MIN ((rexchar_t)0)
 
+/**
+ * Definition of state types.
+ */
 typedef enum {
-       REX_STATETYPE_NONE = 0,
-       REX_STATETYPE_START = 1,
-       REX_STATETYPE_ACCEPT = 2,
-       REX_STATETYPE_DEAD = 3,
+       REX_STATETYPE_NONE = 0,                 /**< There is nothing interesting about this state */
+       REX_STATETYPE_START = 1,                /**< This state is marked as starting point for the automaton */
+       REX_STATETYPE_ACCEPT = 2,               /**< This type indicates that one or more regular expressions compiled in the automaton matched. */
+       REX_STATETYPE_DEAD = 3,                 /**< The automaton is in the dead state(all transitions lead back to the same state) */
 } rex_statetype_t;
 
-#define REX_DFA_DEADSTATE (0)
-#define REX_DFA_STARTSTATE (1)
+
+#define REX_DFA_DEADSTATE (0)          /**< DFA Dead State ID, In rexdfa_t object the state at offset 0 is always the dead state  */
+#define REX_DFA_STARTSTATE (1)         /**< DFA Start State ID, In rexdfa_t object the start state is always at offset 1  */
 
 #define REX_DFA_STATE(__dfa__, __nstate__)                                                     (&(__dfa__)->states[__nstate__])
 #define REX_DFA_TRANSITION(__dfa__, __nstate__, __ntrans__)                    (&(__dfa__)->trans[(REX_DFA_STATE(__dfa__, __nstate__)->trans) + (__ntrans__)])
@@ -84,52 +97,54 @@ typedef enum {
                })
 
 
-/*
- * Sub-state info definition
+
+/**
+ * Define DFA sub-state.
  */
 typedef struct rexdfss_s {
-       rexuint_t type;
-       rexuint_t uid;
-       rexuserdata_t userdata;
+       rexuint_t type;                                 /**< This is the original NFA state type(substate of a DFA state). */
+       rexuint_t uid;                                  /**< Unique ID of the NFA state(substate of a DFA state). */
+       rexuserdata_t userdata;                 /**< If this is an accepting sub-state, this parameter has the value specified in the @ref rex_db_addexpression call.
+                                                                                This parameter is used to track which regular expression is matching, when the DFA gets to accepting state. */
 } rexdfss_t;
 
 
-/*
- * Transition definition
+/**
+ * Define DFA transition.
  */
 typedef struct rexdft_s {
-       rexchar_t lowin;
-       rexchar_t highin;
-       rexuint_t state;
+       rexchar_t lowin;                                /**< Low input boundary */
+       rexchar_t highin;                               /**< High input boundary */
+       rexuint_t state;                                /**< New state to go to if the input is within the boundary */
 } rexdft_t;
 
 
-/*
+/**
  * State definition
  */
 typedef struct rexdfs_s {
-       rexuint_t type;
-       rexuint_t trans;
-       rexuint_t ntrans;
-       rexuint_t accsubstates;
-       rexuint_t naccsubstates;
-       rexuint_t substates;
-       rexuint_t nsubstates;
+       rexuint_t type;                                 /**< Type of DFA state. */
+       rexuint_t trans;                                /**< The offset of the first transition for this state in the dfa->trans array. */
+       rexuint_t ntrans;                               /**< Total number of transitions. */
+       rexuint_t accsubstates;                 /**< The offset of the first accepting sub-state for this state in the dfa->accsubstates array. */
+       rexuint_t naccsubstates;                /**< Total number of accepting sub-states. */
+       rexuint_t substates;                    /**< The offset of the first sub-state for this state in the dfa->substates array. */
+       rexuint_t nsubstates;                   /**< Total number of sub-states. */
 } rexdfs_t;
 
 
-/*
- * Automata definition
+/**
+ * Define DFA.
  */
 typedef struct rexdfa_s {
-       rexuint_t nstates;
-       rexdfs_t *states;
-       rexuint_t ntrans;
-       rexdft_t *trans;
-       rexuint_t naccsubstates;
-       rexdfss_t *accsubstates;
-       rexuint_t nsubstates;
-       rexdfss_t *substates;
+       rexuint_t nstates;                              /**< Total number of states. */
+       rexdfs_t *states;                               /**< Array of states */
+       rexuint_t ntrans;                               /**< Total number of transitions */
+       rexdft_t *trans;                                /**< Array of transitions, all states transitions are recorded here. Each state keeps the offset of its first transition it this array */
+       rexuint_t naccsubstates;                /**< Total number of accepting substates */
+       rexdfss_t *accsubstates;                /**< Array of accepting sub-states, all states accepting sub-states are recorded here. */
+       rexuint_t nsubstates;                   /**< Total number of substates */
+       rexdfss_t *substates;                   /**< Array of sub-states, all states sub-states are recorded here. */
        rexuword_t reserved[64];
 } rexdfa_t;
 
index 77dffef..b7a218d 100644 (file)
@@ -3,6 +3,9 @@
 /** 
 @mainpage Rpa/Tk Documentation (Under Development!)
 - @subpage rpatk_build
+- @subpage rex_main "Regular Expressions"
+       - @subpage rexdb
+       - @subpage rexdfa
 - @subpage rpa_main "Regular Pattern Analyzer"
        - @subpage rpa_bnf      
        - @subpage rpa_dbex
index ae32311..6ef3684 100644 (file)
@@ -1,7 +1,9 @@
 /** \page rpa_main "Regular Pattern Analyzer (RPA)"
-Regular Pattern Analyzer (RPA) is a bottom-up, recursive parser. 
+Regular Pattern Analyzer (RPA) is a top-down, recursive parser. 
 The input grammar notation is Backus–Naur Form (BNF) and the produced output is a browsable Abstract Syntax Tree (AST).
-The grammar allows Regular Expressions, so the parser can also be used as RegEx or search engine. The execution
+The grammar allows Regular Expressions, so the parser can also be used as RegEx or search engine. The regular expressions
+in the RPA library are NOT based on the automata theory and they are not the same as the traditional Unix regular expressions. 
+If you need Unix compatible regular expressions, please check the REX library. The execution
 engine supports muti-threading and it can parse multiple input streams simultaneously.
 
 \section features Features
index 6466028..5c85913 100644 (file)
@@ -1,3 +1,32 @@
+/*
+ *  Regular Pattern Analyzer (RPA)
+ *  Copyright (c) 2009-2010 Martin Stoilov
+ *
+ *  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 3 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, see <http://www.gnu.org/licenses/>.
+ *
+ *  Martin Stoilov <martin@rpasearch.com>
+ */
+
+/*
+ * To build:
+ * # rexcc tokenjs.rex -o tokenjs.c
+ * # gcc -I/usr/include/rpatk/rex -o tokenjs tokenjs.c
+ *
+ * To run:
+ * # echo "function add(a,b) { var c = a + b; return c; }" | ./tokenjs
+ */
+
 #include <stdio.h>
 #include <wchar.h>
 #include <locale.h>