summaryrefslogtreecommitdiff
path: root/support/ltx2x/l2xirexp.c
diff options
context:
space:
mode:
authorNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
committerNorbert Preining <norbert@preining.info>2019-09-02 13:46:59 +0900
commite0c6872cf40896c7be36b11dcc744620f10adf1d (patch)
tree60335e10d2f4354b0674ec22d7b53f0f8abee672 /support/ltx2x/l2xirexp.c
Initial commit
Diffstat (limited to 'support/ltx2x/l2xirexp.c')
-rw-r--r--support/ltx2x/l2xirexp.c814
1 files changed, 814 insertions, 0 deletions
diff --git a/support/ltx2x/l2xirexp.c b/support/ltx2x/l2xirexp.c
new file mode 100644
index 0000000000..1da732b35d
--- /dev/null
+++ b/support/ltx2x/l2xirexp.c
@@ -0,0 +1,814 @@
+/* l2xirexp.c builds recognizers for two kinds of regular expressions */
+/* Based on rexpr.c, part of the PCCTS compiler/generator distribution */
+/*
+ * This file contains code for
+ *
+ * int rexpr(char *expr, char *s);
+ *
+ * which answers
+ *
+ * 1 if 's' is in the language described by the regular expression 'expr'
+ * 0 if it is not
+ * -1 if the regular expression is invalid
+ *
+ * Language membership is determined by constructing a non-deterministic
+ * finite automata (NFA) from the regular expression. A depth-
+ * first-search is performed on the NFA (graph) to check for a match of 's'.
+ * Each non-epsilon arc consumes one character from 's'. Backtracking is
+ * performed to check all possible paths through the NFA.
+ *
+ * Regular expressions follow the meta-language:
+ *
+ * <regExpr> ::= <andExpr> ( '|' <andExpr> )*
+ *
+ * <andExpr> ::= <expr> ( <expr> )*
+ *
+ * <expr> ::= {'~'} '[' <atomList> ']' <repeatSymbol>
+ * | '(' <regExpr> ')' <repeatSymbol>
+ * | '{' <regExpr> '}' <repeatSymbol>
+ * | <atom> <repeatSymbol>
+ *
+ * <repeatSymbol> ::= { '*' | '+' }
+ *
+ * <atomList> ::= <atom> ( <atom> )*
+ * | { <atomList> } <atom> '-' <atom> { <atomList> }
+ *
+ * <atom> ::= Token[Atom]
+ *
+ * Notes:
+ * ~ means complement the set in [..]. i.e. all characters
+ * not listed
+ * * means match 0 or more times (can be on expression
+ * or atom)
+ * + means match 1 or more times (can be on expression
+ * or atom)
+ * {} optional
+ * () grouping
+ * [] set of atoms
+ * x-y all characters from x to y (found only in [..])
+ * \xx the character with value xx
+ *
+ * Examples:
+ * [a-z]+
+ * match 1 or more lower-case letters (e.g. variable)
+ *
+ * 0x[0-9A-Fa-f]+
+ * match a hex number with 0x on front (e.g. 0xA1FF)
+ *
+ * [0-9]+.[0-9]+{e[0-9]+}
+ * match a floating point number (e.g. 3.14e21)
+ *
+ * Code example:
+ * if ( rexpr("[a-zA-Z][a-zA-Z0-9]+", str) ) then str is keyword
+ *
+ * Terence Parr
+ * Purdue University
+ * April 1991
+ */
+/**********************************************************************/
+/* some modifications by Peter Wilson, Catholic University of America */
+/*
+* Complement changed from ~[...] to [^...] to match AWK/lex
+* Optional changed from {...} to (r)? to match AWK/lex
+* Swapped parameters in rexpr()
+*
+* Major additions/changes to support the EXPRESS LIKE operator:
+* string LIKE pattern -> TRUE or FALSE
+*
+* @ matches any letter
+* ^ matches any uppercase letter
+* ? matches any character
+* & matches remainder of string
+* # matches any digit
+* $ matches any substring terminated by space or end of string
+* * matches any number of characters
+* \ escape character
+*
+*/
+/**********************************************************************/
+
+#include <stdio.h>
+#include <ctype.h>
+#include <stdlib.h>
+#include "l2xirexp.h"
+#include "l2xiidbg.h"
+
+
+static int regExpr();
+static int andExpr();
+static int expr();
+static int repeatSymbol();
+static int atomList();
+static int next();
+static ArcPtr newGraphArc();
+static NodePtr newNode();
+static int ArcBetweenGraphNode();
+static Graph BuildNFA_atom();
+static Graph BuildNFA_AB();
+static Graph BuildNFA_AorB();
+static Graph BuildNFA_set();
+static Graph BuildNFA_Astar();
+static Graph BuildNFA_Aplus();
+static Graph BuildNFA_Aoptional();
+
+static char *_c;
+static int rx_token, tokchar;
+static NodePtr accept;
+static NodePtr freelist = NULL;
+
+int like_op = 0; /* PRW = 1 iff processing EXPRESS LIKE pattern */
+
+/*
+ * return 1 if s in language described by expr
+ * 0 if s is not
+ * -1 if expr is an invalid regular expression
+ */
+rexpr(s, expr)
+char *expr, *s;
+{
+ NodePtr p,q;
+ Graph nfa;
+ int result;
+
+ entry_debug("rexpr (l2xirexp.c)");
+ sprintf(dbuffer, "rexpr(%s, %s);\n", s, expr);
+ debug_print(dbuffer);
+ like_op = 0;
+ freelist = NULL;
+ _c = expr;
+ next();
+ if ( regExpr(&nfa) == -1 ) return -1;
+ accept = nfa.right;
+ result = match(nfa.left, s);
+ /* free all your memory */
+ p = q = freelist;
+ while ( p!=NULL ) { q = p->track; free(p); p = q; }
+ exit_debug("rexpr");
+ return result;
+}
+
+/*
+ * do a depth-first-search on the NFA looking for a path from start to
+ * accept state labelled with the characters of 's'.
+ */
+match(automaton, s)
+NodePtr automaton;
+char *s;
+{
+ ArcPtr p;
+
+ if ( automaton == accept && *s == '\0' ) return 1; /* match */
+
+ for (p=automaton->arcs; p!=NULL; p=p->next) /* try all arcs */
+ {
+ if ( p->label == Epsilon )
+ {
+ if ( match(p->target, s) ) return 1;
+ }
+ else if ( p->label == *s )
+ if ( match(p->target, s+1) ) return 1;
+ }
+ return 0;
+}
+
+/*
+ * <regExpr> ::= <andExpr> ( '|' {<andExpr>} )*
+ *
+ * Return -1 if syntax error
+ * Return 0 if none found
+ * Return 1 if a regExrp was found
+ */
+static
+regExpr(g)
+GraphPtr g;
+{
+ Graph g1, g2;
+
+ if ( andExpr(&g1) == -1 )
+ {
+ return -1;
+ }
+
+ while ( rx_token == '|' )
+ {
+ int a;
+ next();
+ a = andExpr(&g2);
+ if ( a == -1 ) return -1; /* syntax error below */
+ else if ( !a ) return 1; /* empty alternative */
+ g1 = BuildNFA_AorB(g1, g2);
+ }
+
+ if ( rx_token!='\0' ) return -1;
+
+ *g = g1;
+ return 1;
+}
+
+/*
+ * <andExpr> ::= <expr> ( <expr> )*
+ */
+static
+andExpr(g)
+GraphPtr g;
+{
+ Graph g1, g2;
+
+ if ( expr(&g1) == -1 )
+ {
+ return -1;
+ }
+
+/* PRW while ( rx_token==Atom || rx_token=='{' || rx_token=='(' || rx_token=='~' || rx_token=='[' ) */
+ while ( rx_token==Atom || rx_token=='(' || rx_token=='[' )
+ {
+ if (expr(&g2) == -1) return -1;
+ g1 = BuildNFA_AB(g1, g2);
+ }
+
+ *g = g1;
+ return 1;
+}
+
+/*
+ * <expr> ::= {'~'} '[' <atomList> ']' <repeatSymbol>
+ * | '(' <regExpr> ')' <repeatSymbol>
+ * | '{' <regExpr> '}' <repeatSymbol>
+ * | <atom> <repeatSymbol>
+ * PRW changed above to:
+ * <expr> ::= '[' {'^'} <atomList> ']' <repeatSymbol>
+ * | '(' <regExpr> ')' <repeatSymbol>
+ * | <atom> <repeatSymbol>
+ */
+static
+expr(g)
+GraphPtr g;
+{
+ int complement = 0;
+ char s[257]; /* alloc space for string of char in [] */
+
+/* PRW if ( rx_token == '~' || rx_token == '[' ) */
+ if ( rx_token == '[' )
+ {
+ next();
+ if (rx_token == '^') { complement = 1; next();}
+/* PRW if ( rx_token == '~' ) {complement = 1; next();}
+* if ( rx_token != '[' ) return -1;
+* next();
+*/
+ if ( atomList( s, complement ) == -1 ) return -1;
+ *g = BuildNFA_set( s );
+ if ( rx_token != ']' ) return -1;
+ next();
+ repeatSymbol( g );
+ return 1;
+ }
+ if ( rx_token == '(' )
+ {
+ next();
+ if ( regExpr( g ) == -1 ) return -1;
+ if ( rx_token != ')' ) return -1;
+ next();
+ repeatSymbol( g );
+ return 1;
+ }
+/* PRW if ( rx_token == '{' )
+* {
+* next();
+* if ( regExpr( g ) == -1 ) return -1;
+* if ( rx_token != '}' ) return -1;
+* next();
+* -- S p e c i a l C a s e O p t i o n a l { } --
+* if ( rx_token != '*' && rx_token != '+' )
+* {
+* *g = BuildNFA_Aoptional( *g );
+* }
+* repeatSymbol( g );
+* return 1;
+* }
+*/
+ if ( rx_token == Atom )
+ {
+ *g = BuildNFA_atom( tokchar );
+ next();
+ repeatSymbol( g );
+ return 1;
+ }
+
+ return -1;
+}
+
+/*
+ * <repeatSymbol> ::= { '*' | '+' }
+ * PRW changed to ::= { '*' | '+' | '?' }
+ */
+static
+repeatSymbol(g)
+GraphPtr g;
+{
+ switch ( rx_token )
+ {
+ case '*' : *g = BuildNFA_Astar( *g ); next(); break;
+ case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
+ case '?' : *g = BuildNFA_Aoptional( *g ); next(); break;
+ }
+ return 1;
+}
+
+/*
+ * <atomList> ::= <atom> { <atom> }*
+ * { <atomList> } <atom> '-' <atom> { <atomList> }
+ *
+ * a-b is same as ab
+ * q-a is same as q
+ */
+static
+atomList(p, complement)
+char *p;
+int complement;
+{
+ static unsigned char set[256]; /* no duplicates */
+ int first, last, i;
+ char *s = p;
+
+ if ( rx_token != Atom ) return -1;
+
+ for (i=0; i<256; i++) set[i] = 0;
+ while ( rx_token == Atom )
+ {
+ if ( !set[tokchar] ) *s++ = tokchar;
+ set[tokchar] = 1; /* Add atom to set */
+ next();
+ if ( rx_token == '-' ) /* have we found '-' */
+ {
+ first = *(s-1); /* Get last char */
+ next();
+ if ( rx_token != Atom ) return -1;
+ else
+ {
+ last = tokchar;
+ }
+ for (i = first+1; i <= last; i++)
+ {
+ if ( !set[tokchar] ) *s++ = i;
+ set[i] = 1; /* Add atom to set */
+ }
+ next();
+ }
+ }
+ *s = '\0';
+ if ( complement )
+ {
+ for (i=0; i<256; i++) set[i] = !set[i];
+ for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
+ *s = '\0';
+ }
+ return 1;
+}
+
+/* a somewhat stupid lexical analyzer */
+static
+next()
+{
+ /* PRW seperate scanners for regular expression and LIKE operator */
+ if (like_op == 0) { /* regex scanning */
+ while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
+ if ( *_c=='\\' )
+ {
+ _c++;
+ if ( isdigit(*_c) )
+ {
+ int n=0;
+ while ( isdigit(*_c) )
+ {
+ n = n*10 + (*_c++ - '0');
+ }
+ if ( n>255 ) n=255;
+ tokchar = n;
+ }
+ else
+ {
+ switch (*_c)
+ {
+ case 'n' : tokchar = '\n'; break;
+ case 't' : tokchar = '\t'; break;
+ case 'r' : tokchar = '\r'; break;
+ default : tokchar = *_c;
+ }
+ _c++;
+ }
+ rx_token = Atom;
+ }
+ else if ( isgraph(*_c) && *_c!='['
+ && *_c!='('
+ && *_c!='-'
+ && *_c!=')'
+ && *_c!=']'
+ && *_c!='?'
+ && *_c!='+'
+ && *_c!='*'
+ && *_c!='^'
+ && *_c!='|' )
+ { /* PRW deleted {, } and ~ while adding ^ and ? */
+ rx_token = Atom;
+ tokchar = *_c++;
+ }
+ else
+ {
+ rx_token = tokchar = *_c++;
+ }
+ return;
+ } /* end of regex scanner */
+ else if (like_op == 1) { /* LIKE scanning */
+ while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
+ if ( *_c=='\\' )
+ {
+ _c++;
+ switch (*_c)
+ {
+ case 'n' : tokchar = '\n'; break;
+ case 't' : tokchar = '\t'; break;
+ case 'r' : tokchar = '\r'; break;
+ default : tokchar = *_c;
+ }
+ _c++;
+ rx_token = Atom;
+ }
+ else if ( isgraph(*_c) && *_c!='@'
+ && *_c!='^'
+ && *_c!='?'
+ && *_c!='&'
+ && *_c!='#'
+ && *_c!='$'
+ && *_c!='*'
+ && *_c!='!' )
+ {
+ rx_token = Atom;
+ tokchar = *_c++;
+ }
+ else
+ {
+ rx_token = tokchar = *_c++;
+ }
+ return;
+ } /* end of LIKE scanner */
+}
+
+/* N F A B u i l d i n g R o u t i n e s */
+
+static
+ArcPtr
+newGraphArc()
+{
+ ArcPtr p;
+ p = (ArcPtr) calloc(1, sizeof(Arc));
+ if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
+ if ( freelist != NULL ) p->track = (ArcPtr) freelist;
+ freelist = (NodePtr) p;
+ return p;
+}
+
+static
+NodePtr
+newNode()
+{
+ NodePtr p;
+ p = (NodePtr) calloc(1, sizeof(Node));
+ if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
+ if ( freelist != NULL ) p->track = freelist;
+ freelist = p;
+ return p;
+}
+
+static
+ArcBetweenGraphNodes(i, j, label)
+NodePtr i, j;
+int label;
+{
+ ArcPtr a;
+
+ a = newGraphArc();
+ if ( i->arcs == NULL ) i->arctail = i->arcs = a;
+ else {(i->arctail)->next = a; i->arctail = a;}
+ a->label = label;
+ a->target = j;
+}
+
+static Graph
+BuildNFA_atom(label)
+int label;
+{
+ Graph g;
+
+ g.left = newNode();
+ g.right = newNode();
+ ArcBetweenGraphNodes(g.left, g.right, label);
+ return( g );
+}
+
+static Graph
+BuildNFA_AB(A, B)
+Graph A, B;
+{
+ Graph g;
+
+ ArcBetweenGraphNodes(A.right, B.left, Epsilon);
+ g.left = A.left;
+ g.right = B.right;
+ return( g );
+}
+
+static Graph
+BuildNFA_AorB(A, B)
+Graph A, B;
+{
+ Graph g;
+
+ g.left = newNode();
+ ArcBetweenGraphNodes(g.left, A.left, Epsilon);
+ ArcBetweenGraphNodes(g.left, B.left, Epsilon);
+ g.right = newNode();
+ ArcBetweenGraphNodes(A.right, g.right, Epsilon);
+ ArcBetweenGraphNodes(B.right, g.right, Epsilon);
+ return( g );
+}
+
+static Graph
+BuildNFA_set( s )
+char *s;
+{
+ Graph g;
+
+ if ( s == NULL ) return g;
+
+ g.left = newNode();
+ g.right = newNode();
+ while ( *s != '\0' )
+ {
+ ArcBetweenGraphNodes(g.left, g.right, *s++);
+ }
+ return g;
+}
+
+static Graph
+BuildNFA_Astar( A )
+Graph A;
+{
+ Graph g;
+
+ g.left = newNode();
+ g.right = newNode();
+
+ ArcBetweenGraphNodes(g.left, A.left, Epsilon);
+ ArcBetweenGraphNodes(g.left, g.right, Epsilon);
+ ArcBetweenGraphNodes(A.right, g.right, Epsilon);
+ ArcBetweenGraphNodes(A.right, A.left, Epsilon);
+
+ return( g );
+}
+
+static Graph
+BuildNFA_Aplus( A )
+Graph A;
+{
+ ArcBetweenGraphNodes(A.right, A.left, Epsilon);
+
+ return( A );
+}
+
+static Graph
+BuildNFA_Aoptional( A )
+Graph A;
+{
+ Graph g;
+
+ g.left = newNode();
+ g.right = newNode();
+
+ ArcBetweenGraphNodes(g.left, A.left, Epsilon);
+ ArcBetweenGraphNodes(g.left, g.right, Epsilon);
+ ArcBetweenGraphNodes(A.right, g.right, Epsilon);
+
+ return( g );
+}
+
+
+/* LIKE operator code */
+
+
+
+/************************************************************************/
+/* likeExpr() Process likeExpr */
+
+static likeExpr(g)
+GraphPtr g;
+{
+ int complement = 0;
+ char s[257];
+ int i;
+ Graph g2;
+
+ if (rx_token == '\\') { /* escape char */
+ next();
+ }
+ if (rx_token == '!') { /* NOT char */
+ complement = 1;
+ next();
+ }
+
+ if (rx_token == Atom) {
+ if (complement == 1) {
+ do_not_atom(s, tokchar);
+ *g = BuildNFA_set(s);
+ }
+ else {
+ *g = BuildNFA_atom(tokchar);
+ }
+ next();
+ return(1);
+ }
+ else if ( rx_token == '@'
+ || rx_token == '^'
+ || rx_token == '?'
+ || rx_token == '&'
+ || rx_token == '#'
+ || rx_token == '$'
+ || rx_token == '*' ) {
+ do_like_meta(rx_token, s, complement);
+ *g = BuildNFA_set(s);
+ if ( rx_token == '&'
+ || rx_token == '*'
+ || rx_token == '$' ) { /* multiple chars */
+ *g = BuildNFA_Astar(*g);
+ if (rx_token == '$') { /* add 0 or more following space chars */
+ g2 = BuildNFA_atom(' ');
+ g2 = BuildNFA_Astar(g2);
+ *g = BuildNFA_AB(*g, g2);
+ }
+ }
+ next();
+ return(1);
+ }
+
+ return(-1); /* should not be here */
+} /* end LIKEEXPR */
+/************************************************************************/
+
+
+
+/************************************************************************/
+/* likePat() Process likePat ::= <likeExpr> ( <likeExpr> )* */
+
+static likePat(g)
+GraphPtr g;
+{
+ Graph g1, g2;
+
+ if (likeExpr(&g1) == -1) {
+ return(-1);
+ }
+
+ while (rx_token != '\0') {
+ if (likeExpr(&g2) == -1) {
+ return(-1);
+ }
+ g1 = BuildNFA_AB(g1, g2);
+ }
+ *g = g1;
+ return(1);
+} /* end LIKEPAT */
+/************************************************************************/
+
+/************************************************************************/
+/* like_expr(expr,s) */
+/* returns -1 if expr not an EXPRESS LIKE pattern */
+/* 0 if s does not match pattern expr */
+/* 1 if s matches pattern expr */
+
+int like_expr(s, expr)
+char *s; /* string to be matched */
+char *expr; /* the pattern */
+{
+ NodePtr p, q;
+ Graph nfa;
+ int result;
+
+ entry_debug("like_expr (l2xirexp.c)");
+ sprintf(dbuffer, "like_expr(%s, %s);\n", s, expr);
+ debug_print(dbuffer);
+
+ like_op = 1; /* set correct scanner */
+ freelist = NULL;
+ _c = expr;
+ next();
+ if (likePat(&nfa) == -1) {
+ return(-1);
+ }
+ accept = nfa.right;
+ result = match(nfa.left, s);
+ /* free memory */
+ p = q = freelist;
+ while (p != NULL) {
+ q = p->track;
+ free(p);
+ p = q;
+ }
+ exit_debug("like_expr");
+ return(result);
+} /* end LIKE_EXPR */
+/************************************************************************/
+
+
+
+/************************************************************************/
+/* do_not_atom() Process !a */
+
+int do_not_atom(p, c)
+char *p;
+int c; /* the negated atom char */
+{
+ static unsigned char set [256];
+ int i;
+ char *s = p;
+
+ for (i = 0; i < 256; i++) { /* all characters */
+ set[i] = 1;
+ }
+ set[c] = !set[c]; /* except for this one */
+
+ for (i = 1, s = p; i < 256; i++) {
+ if (set[i]) *s++ = i;
+ }
+ *s = '\0';
+ return(1);
+} /* end DO_NOT_ATOM */
+/************************************************************************/
+
+
+
+/************************************************************************/
+/* do_like_meta() Process EXPRESS LIKE meta character */
+
+int do_like_meta(meta, p, complement)
+int meta; /* the meta character */
+char *p;
+int complement; /* = 1 if complement the set */
+{
+ static unsigned char set[256];
+ int i;
+ char *s = p;
+
+ /* ensure all character are noted in the set */
+ for (i = 0; i < 256; i++) set[i] = 1;
+
+ switch (meta) {
+ case '@' : { /* a single alphabetic character */
+ for (i = 0; i < 256; i++) set[i] = 0;
+ for (i = 'a'; i <= 'z'; i++) set[i] = 1;
+ for (i = 'A'; i <= 'Z'; i++) set[i] = 1;
+ break;
+ }
+ case '^' : { /* a single upper case alphabetic character */
+ for (i = 0; i < 256; i++) set[i] = 0;
+ for (i = 'A'; i <= 'Z'; i++) set[i] = 1;
+ break;
+ }
+ case '?' : { /* a single character */
+ break;
+ }
+ case '&' : { /* remainder of string */
+ break;
+ }
+ case '#' : { /* a single digit */
+ for (i = 0; i < 256; i++) set[i] = 0;
+ for (i = '0'; i <= '9'; i++) set[i] = 1;
+ break;
+ }
+ case '$' : { /* substring ended by space or EOS */
+ i = ' ';
+ set[i] = !set[i];
+ break;
+ }
+ case '*' : { /* any character */
+ break;
+ }
+ default : { /* an ERROR */
+ return(-1);
+ }
+ } /* end switch */
+
+ if (complement == 1) { /* invert the set */
+ for (i = 0; i < 256; i++) set[i] = !set[i];
+ }
+
+ /* add all the search characters to the string */
+ for (i = 1, s = p; i < 256; i++) {
+ if (set[i]) *s++ = i;
+ }
+ *s = '\0';
+ return(1);
+} /* end DO_LIKE_META */
+/************************************************************************/
+
+
+