4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * This file contains code for
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * int rexpr(char *expr, char *s);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * which answers
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * 1 if 's' is in the language described by the regular expression 'expr'
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * 0 if it is not
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * -1 if the regular expression is invalid
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Language membership is determined by constructing a non-deterministic
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * finite automata (NFA) from the regular expression. A depth-
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * first-search is performed on the NFA (graph) to check for a match of 's'.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Each non-epsilon arc consumes one character from 's'. Backtracking is
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * performed to check all possible paths through the NFA.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Regular expressions follow the meta-language:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <regExpr> ::= <andExpr> ( '|' <andExpr> )*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <andExpr> ::= <expr> ( <expr> )*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <expr> ::= {'~'} '[' <atomList> ']' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | '(' <regExpr> ')' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | '{' <regExpr> '}' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | <atom> <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <repeatSymbol> ::= { '*' | '+' }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <atomList> ::= <atom> ( <atom> )*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | { <atomList> } <atom> '-' <atom> { <atomList> }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <atom> ::= Token[Atom]
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Notes:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * ~ means complement the set in [..]. i.e. all characters not listed
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * * means match 0 or more times (can be on expression or atom)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * + means match 1 or more times (can be on expression or atom)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * {} optional
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * () grouping
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * [] set of atoms
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * x-y all characters from x to y (found only in [..])
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * \xx the character with value xx
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Examples:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * [a-z]+
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * match 1 or more lower-case letters (e.g. variable)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * 0x[0-9A-Fa-f]+
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * match a hex number with 0x on front (e.g. 0xA1FF)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * [0-9]+.[0-9]+{e[0-9]+}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * match a floating point number (e.g. 3.14e21)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Code example:
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * if ( rexpr("[a-zA-Z][a-zA-Z0-9]+", str) ) then str is keyword
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Terence Parr
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Purdue University
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * April 1991
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include <stdio.h>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include <ctype.h>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __STDC__
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include <stdlib.h>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include <malloc.h>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#include "rexpr.h"
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int regExpr( GraphPtr g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int andExpr( GraphPtr g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int expr( GraphPtr g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int repeatSymbol( GraphPtr g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int atomList( char *p, int complement );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void next( void );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic ArcPtr newGraphArc( void );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr newNode( void );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int ArcBetweenGraphNode( NodePtr i, NodePtr j, int label );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_atom( int label );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AB( Graph A, Graph B );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AorB( Graph A, Graph B );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_set( char *s );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Astar( Graph A );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aplus( Graph A );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aoptional( Graph A );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int regExpr();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int andExpr();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int expr();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int repeatSymbol();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int atomList();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic ArcPtr newGraphArc();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int ArcBetweenGraphNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_atom();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AB();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AorB();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_set();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Astar();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aplus();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aoptional();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic char *_c;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int token, tokchar;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr accept;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr freelist = NULL;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * return 1 if s in language described by expr
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * 0 if s is not
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * -1 if expr is an invalid regular expression
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int rexpr(char *expr,char *s)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int rexpr(expr, s)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncchar *expr, *s;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync NodePtr p,q;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph nfa;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync int result;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync fprintf(stderr, "rexpr(%s,%s);\n", expr,s);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync freelist = NULL;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync _c = expr;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( regExpr(&nfa) == -1 ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync accept = nfa.right;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync result = match(nfa.left, s);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync /* free all your memory */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync p = q = freelist;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( p!=NULL ) { q = p->track; free(p); p = q; }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return result;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * do a depth-first-search on the NFA looking for a path from start to
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * accept state labelled with the characters of 's'.
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int match(NodePtr automaton,char *s)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int match(automaton, s)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncNodePtr automaton;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncchar *s;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcPtr p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( automaton == accept && *s == '\0' ) return 1; /* match */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for (p=automaton->arcs; p!=NULL; p=p->next) /* try all arcs */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( p->label == Epsilon )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( match(p->target, s) ) return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else if ( p->label == *s )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( match(p->target, s+1) ) return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 0;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <regExpr> ::= <andExpr> ( '|' {<andExpr>} )*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Return -1 if syntax error
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Return 0 if none found
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * Return 1 if a regExrp was found
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int regExpr(GraphPtr g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int regExpr(g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraphPtr g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g1, g2;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( andExpr(&g1) == -1 )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( token == '|' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync int a;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync a = andExpr(&g2);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( a == -1 ) return -1; /* syntax error below */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else if ( !a ) return 1; /* empty alternative */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g1 = BuildNFA_AorB(g1, g2);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token!='\0' ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *g = g1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <andExpr> ::= <expr> ( <expr> )*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int andExpr(GraphPtr g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int andExpr(g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraphPtr g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g1, g2;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( expr(&g1) == -1 )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( token==Atom || token=='{' || token=='(' || token=='~' || token=='[' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if (expr(&g2) == -1) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g1 = BuildNFA_AB(g1, g2);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *g = g1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <expr> ::= {'~'} '[' <atomList> ']' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | '(' <regExpr> ')' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | '{' <regExpr> '}' <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * | <atom> <repeatSymbol>
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int expr(GraphPtr g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int expr(g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraphPtr g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync int complement = 0;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync char s[257]; /* alloc space for string of char in [] */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == '~' || token == '[' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == '~' ) {complement = 1; next();}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != '[' ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( atomList( s, complement ) == -1 ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *g = BuildNFA_set( s );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != ']' ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync repeatSymbol( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == '(' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( regExpr( g ) == -1 ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != ')' ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync repeatSymbol( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == '{' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( regExpr( g ) == -1 ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != '}' ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync /* S p e c i a l C a s e O p t i o n a l { } */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != '*' && token != '+' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *g = BuildNFA_Aoptional( *g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync repeatSymbol( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == Atom )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *g = BuildNFA_atom( tokchar );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync repeatSymbol( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <repeatSymbol> ::= { '*' | '+' }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int repeatSymbol(GraphPtr g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int repeatSymbol(g)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraphPtr g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync switch ( token )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync case '*' : *g = BuildNFA_Astar( *g ); next(); break;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync case '+' : *g = BuildNFA_Aplus( *g ); next(); break;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * <atomList> ::= <atom> { <atom> }*
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * { <atomList> } <atom> '-' <atom> { <atomList> }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * a-b is same as ab
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync * q-a is same as q
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int atomList(char *p, int complement)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic int atomList(p, complement)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncchar *p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncint complement;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync static unsigned char set[256]; /* no duplicates */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync int first, last, i;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync char *s = p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != Atom ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for (i=0; i<256; i++) set[i] = 0;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( token == Atom )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( !set[tokchar] ) *s++ = tokchar;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync set[tokchar] = 1; /* Add atom to set */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token == '-' ) /* have we found '-' */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync first = *(s-1); /* Get last char */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( token != Atom ) return -1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync last = tokchar;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for (i = first+1; i <= last; i++)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( !set[tokchar] ) *s++ = i;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync set[i] = 1; /* Add atom to set */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync next();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *s = '\0';
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( complement )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for (i=0; i<256; i++) set[i] = !set[i];
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync for (i=1,s=p; i<256; i++) if ( set[i] ) *s++ = i;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *s = '\0';
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return 1;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/* a somewhat stupid lexical analyzer */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void next(void)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void next()
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( *_c==' ' || *_c=='\t' || *_c=='\n' ) _c++;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( *_c=='\\' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync _c++;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( isdigit(*_c) )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync int n=0;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( isdigit(*_c) )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync n = n*10 + (*_c++ - '0');
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( n>255 ) n=255;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync tokchar = n;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync switch (*_c)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync case 'n' : tokchar = '\n'; break;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync case 't' : tokchar = '\t'; break;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync case 'r' : tokchar = '\r'; break;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync default : tokchar = *_c;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync _c++;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync token = Atom;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else if ( isgraph(*_c) && *_c!='[' && *_c!='(' && *_c!='{' &&
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *_c!='-' && *_c!='}' && *_c!=')' && *_c!=']' &&
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync *_c!='+' && *_c!='*' && *_c!='~' && *_c!='|' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync token = Atom;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync tokchar = *_c++;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync token = tokchar = *_c++;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync/* N F A B u i l d i n g R o u t i n e s */
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic ArcPtr newGraphArc(void)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic ArcPtr newGraphArc()
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcPtr p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync p = (ArcPtr) calloc(1, sizeof(Arc));
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( freelist != NULL ) p->track = (ArcPtr) freelist;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync freelist = (NodePtr) p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr newNode(void)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic NodePtr newNode()
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync NodePtr p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync p = (NodePtr) calloc(1, sizeof(Node));
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( p==NULL ) {fprintf(stderr,"rexpr: out of memory\n"); exit(-1);}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( freelist != NULL ) p->track = freelist;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync freelist = p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return p;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void ArcBetweenGraphNodes(NodePtr i,NodePtr j,int label)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic void ArcBetweenGraphNodes(i, j, label)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncNodePtr i, j;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncint label;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcPtr a;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync a = newGraphArc();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( i->arcs == NULL ) i->arctail = i->arcs = a;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync else {(i->arctail)->next = a; i->arctail = a;}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync a->label = label;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync a->target = j;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_atom(int label)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_atom(label)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncint label;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, g.right, label);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AB(Graph A,Graph B)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AB(A, B)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraph A, B;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, B.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = A.left;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = B.right;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AorB(Graph A,Graph B)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_AorB(A, B)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraph A, B;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, A.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, B.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(B.right, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_set(char *s)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_set( s )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncchar *s;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync if ( s == NULL ) return g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync while ( *s != '\0' )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync {
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, g.right, *s++);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync }
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Astar(Graph A)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Astar( A )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraph A;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, A.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, A.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aplus(Graph A)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aplus( A )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraph A;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, A.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( A );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#ifdef __USE_PROTOS
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aoptional(Graph A)
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#else
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncstatic Graph BuildNFA_Aoptional( A )
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsyncGraph A;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync#endif
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync{
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync Graph g;
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.left = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync g.right = newNode();
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, A.left, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(g.left, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync ArcBetweenGraphNodes(A.right, g.right, Epsilon);
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync return( g );
4fd606d1f5abe38e1f42c38de1d2e895166bd0f4vboxsync}