[net.sources] Pattern recognition in C

fnf@unisoft.UUCP (Fred Fish) (01/21/85)

[--------------]

A recent posting to net.lang.c of a "shell style" pattern matching
routine by Gary Moss appeared to be incomplete so I decided to post
an alternate.

This posting contains my version (nmatch.c) and Gary's two
routines (match.c and matchtest.c) for the benefit of those
who might have missed the original posting since it wasn't
in net.sources.  By the way, it appears that the usage message
for matchtest is wrong.  It apparently wants the arguments
[string pattern] rather than [pattern string].

I'm sure there are many ways to do this, and probably some that
are far more compact than my solution.  I would love to see some
alternate versions (that I can understand that is :-).

#--------CUT---------CUT---------CUT---------CUT--------#
#########################################################
#                                                       #
# This is a shell archive file.  To extract files:      #
#                                                       #
#    1)	Make a directory for the files.                 #
#    2) Write a file, such as "file.shar", containing   #
#       this archive file into the directory.           #
#    3) Type "sh file.shar".  Do not use csh.           #
#                                                       #
#########################################################
#
#
echo Extracting nmatch.c:
sed 's/^Z//' >nmatch.c <<\STUNKYFLUFF
Z#include <stdio.h>
Z#include <sys/types.h>
Z
Z#define ASTERISK '*'		/* The '*' metacharacter */
Z#define QUESTION '?'		/* The '?' metacharacter */
Z#define LEFT_BRACKET '['	/* The '[' metacharacter */
Z#define RIGHT_BRACKET ']'	/* The ']' metacharacter */
Z
Z#define IS_OCTAL(ch) (ch >= '0' && ch <= '7')
Z
Ztypedef int BOOLEAN;
Z#define VOID void
Z#define TRUE 1
Z#define FALSE 0
Z#define EOS '\000'
Z
Zstatic BOOLEAN do_list ();
Zstatic char nextch ();
Zstatic VOID list_parse ();
Z
Z
Z/*
Z *  FUNCTION
Z *
Z *	match   test string for wildcard match
Z *
Z *  SYNOPSIS
Z *
Z *	BOOLEAN match (string, pattern)
Z *	register char *string;
Z *	register char *pattern;
Z *
Z *  DESCRIPTION
Z *
Z *	Test string for match using pattern.  The pattern may
Z *	contain the normal shell metacharacters for pattern
Z *	matching.  The '*' character matches any string,
Z *	including the null string.  The '?' character matches
Z *	any single character.  A list of characters enclosed
Z *	in '[' and ']' matches any character in the list.
Z *	If the first character following the beginning '['
Z *	is a '!' then any character not in the list is matched.
Z *
Z */
Z
Z
Z/*
Z *  PSEUDO CODE
Z *
Z *	Begin match
Z *	    Switch on type of pattern character
Z *		Case ASTERISK:
Z *		    Attempt to match asterisk
Z *		    Break
Z *		Case QUESTION MARK:
Z *		    Attempt to match question mark
Z *		    Break
Z *		Case EOS:
Z *		    Match is result of EOS on string test
Z *		    Break
Z *		Case default:
Z *		    If explicit match then
Z *			Match is result of submatch
Z *		    Else
Z *			Match is FALSE
Z *		    End if
Z *		    Break
Z *	    End switch
Z *	    Return result of match test
Z *	End match
Z *
Z */
Z
ZBOOLEAN match (string, pattern)
Zregister char *string;
Zregister char *pattern;
Z{
Z    register BOOLEAN ismatch;
Z
Z    ismatch = FALSE;
Z    switch (*pattern) {
Z	case ASTERISK:
Z	    pattern++;
Z	    do {
Z		ismatch = match (string, pattern);
Z	    } while (!ismatch && *string++ != EOS);
Z	    break;
Z	case QUESTION:
Z	    if (*string != EOS) {
Z		ismatch = match (++string, ++pattern);
Z	    }
Z	    break;
Z	case EOS:
Z	    if (*string == EOS) {
Z		ismatch = TRUE;
Z	    }
Z	    break;
Z	case LEFT_BRACKET:
Z	    if (*string != EOS) {
Z		ismatch = do_list (string, pattern);
Z	    }
Z	    break;
Z	default:
Z	    if (*string++ == *pattern++) {
Z		ismatch = match (string, pattern);
Z	    } else {
Z		ismatch = FALSE;
Z	    }
Z	    break;
Z    }
Z    return (ismatch);
Z}
Z
Z
Z/*
Z *  FUNCTION
Z *
Z *	do_list    process a list and following substring
Z *
Z *  SYNOPSIS
Z *
Z *	static BOOLEAN do_list (string, pattern)
Z *	register char *string;
Z *	register char *pattern;
Z *
Z *  DESCRIPTION
Z *
Z *	Called when a list is found in the pattern.  Returns
Z *	TRUE if the current character matches the list and
Z *	the remaining substring matches the remaining pattern.
Z *
Z *	Returns FALSE if either the current character fails to
Z *	match the list or the list matches but the remaining
Z *	substring and subpattern's don't.
Z *
Z *  RESTRICTIONS
Z *
Z *	The mechanism used to match characters in an inclusive
Z *	pair (I.E. [a-d]) may not be portable to machines
Z *	in which the native character set is not ASCII.
Z *
Z *	The rules implemented here are:
Z *
Z *		(1)	The backslash character may be
Z *			used to quote any special character.
Z *			I.E.  "\]" and "\-" anywhere in list,
Z *			or "\!" at start of list.
Z *
Z *		(2)	The sequence \nnn becomes the character
Z *			given by nnn (in octal).
Z *
Z *		(3)	Any non-escaped ']' marks the end of list.
Z *
Z *		(4)	A list beginning with the special character
Z *			'!' matches any character NOT in list.
Z *			The '!' character is only special if it
Z *			is the first character in the list.
Z *
Z */
Z
Z
Z/*
Z *  PSEUDO CODE
Z *
Z *	Begin do_list
Z *	    Default result is no match
Z *	    Skip over the opening left bracket
Z *	    If the next pattern character is a '!' then
Z *		List match gives FALSE
Z *		Skip over the '!' character
Z *	    Else
Z *		List match gives TRUE
Z *	    End if
Z *	    While not at closing bracket or EOS
Z *		Get lower and upper bounds
Z *		If character in bounds then
Z *		    Result is same as sense flag.
Z *		    Skip over rest of list
Z *		End if
Z *	    End while
Z *	    If match found then
Z *		If not at end of pattern then
Z *		    Call match with rest of pattern
Z *		End if
Z *	    End if
Z *	    Return match result
Z *	End do_list
Z *
Z */
Z
Zstatic BOOLEAN do_list (string, pattern)
Zregister char *string;
Zchar *pattern;
Z{
Z    register BOOLEAN ismatch;
Z    register BOOLEAN if_found;
Z    register BOOLEAN if_not_found;
Z    auto char lower;
Z    auto char upper;
Z
Z    pattern++;
Z    if (*pattern == '!') {
Z	if_found = FALSE;
Z	if_not_found = TRUE;
Z	pattern++;
Z    } else {
Z	if_found = TRUE;
Z	if_not_found = FALSE;
Z    }
Z    ismatch = if_not_found;
Z    while (*pattern != ']' && *pattern != EOS) {
Z	list_parse (&pattern, &lower, &upper);
Z	if (*string >= lower && *string <= upper) {
Z	    ismatch = if_found;
Z	    while (*pattern != ']' && *pattern != EOS) {pattern++;}
Z	}
Z    }
Z    if (*pattern++ != ']') {
Z	fprintf (stderr, "warning - character class error\n");
Z    } else {
Z	if (ismatch) {
Z	    ismatch = match (++string, pattern);
Z	}
Z    }
Z    return (ismatch);
Z}
Z
Z
Z/*
Z *  FUNCTION
Z *
Z *	list_parse    parse part of list into lower and upper bounds
Z *
Z *  SYNOPSIS
Z *
Z *	static VOID list_parse (patp, lowp, highp)
Z *	char **patp;
Z *	char *lowp;
Z *	char *highp;
Z *
Z *  DESCRIPTION
Z *
Z *	Given pointer to a pattern pointer (patp), pointer to
Z *	a place to store lower bound (lowp), and pointer to a
Z *	place to store upper bound (highp), parses part of
Z *	the list, updating the pattern pointer in the process.
Z *
Z *	For list characters which are not part of a range,
Z *	the lower and upper bounds are set to that character.
Z *
Z */
Z
Zstatic VOID list_parse (patp, lowp, highp)
Zchar **patp;
Zchar *lowp;
Zchar *highp;
Z{
Z    *lowp = nextch (patp);
Z    if (**patp == '-') {
Z	(*patp)++;
Z	*highp = nextch (patp);
Z    } else {
Z	*highp = *lowp;
Z    }
Z}
Z
Z
Z/*
Z *  FUNCTION
Z *
Z *	nextch    determine next character in a pattern
Z *
Z *  SYNOPSIS
Z *
Z *	static char nextch (patp)
Z *	char **patp;
Z *
Z *  DESCRIPTION
Z *
Z *	Given pointer to a pointer to a pattern, uses the pattern
Z *	pointer to determine the next character in the pattern,
Z *	subject to translation of backslash-char and backslash-octal
Z *	sequences.
Z *
Z *	The character pointer is updated to point at the next pattern
Z *	character to be processed.
Z *
Z */
Z
Zstatic char nextch (patp)
Zchar **patp;
Z{
Z    register char ch;
Z    register char chsum;
Z    register int count;
Z
Z    ch = *(*patp)++;
Z    if (ch == '\\') {
Z	ch = *(*patp)++;
Z	if (IS_OCTAL (ch)) {
Z	    chsum = 0;
Z	    for (count = 0; count < 3 && IS_OCTAL (ch); count++) {
Z		chsum *= 8;
Z		chsum += ch - '0';
Z		ch = *(*patp)++;
Z	    }
Z	    (*patp)--;
Z	    ch = chsum;
Z	}
Z    }
Z    return (ch);
Z}
STUNKYFLUFF
set `sum nmatch.c`
if test 38794 != $1
then
echo nmatch.c: Checksum error. Is: $1, should be: 38794.
fi
#
#
echo Extracting match.c:
sed 's/^Z//' >match.c <<\STUNKYFLUFF
Z/*
Z	SCCS id:	@(#) match.c	1.3
Z	Last edit: 	1/16/85 at 21:18:57
Z	Retrieved: 	1/16/85 at 21:19:58
Z	SCCS archive:	/vld/moss/work/libWIND/s.match.c
Z
Z	Author:		Gary S. Moss
Z			U. S. Army Ballistic Research Laboratory
Z			Aberdeen Proving Ground
Z			Maryland 21005-5066
Z			(301)278-6647 or AV-283-6647
Z */
Zstatic
Zchar	sccsTag[] = "@(#) match.c	1.3	last edit 1/16/85 at 21:18:57";
Z#include <stdio.h>
Z#include <string.h>
Z#include "./ascii.h"
Zextern void	prnt1Err();
Z
Z/*	 m a t c h ( )
Z	if string matches pattern, return 1, else return 0
Z	special characters:
Z		*	Matches any string including the null string.
Z		?	Matches any single character.
Z		[...]	Matches any one of the characters enclosed.
Z		[!..]	Matchea any character NOT enclosed.
Z		-	May be used inside brackets to specify range
Z			(i.e. str[1-58] matches str1, str2, ... str5, str8)
Z		\	Escapes special characters.
Z */
Zmatch(	 pattern,  string )
Zregister
Zchar	*pattern, *string;
Z	{
Z	do
Z		{
Z		switch( pattern[0] )
Z		{
Z		case '*': /* Match any string including null string.	*/
Z			if( pattern[1] == NUL || string[0] == NUL )
Z				return	1;
Z			while( string[0] != NUL )
Z				{
Z				if( match( &pattern[1], string ) )
Z					return	1;
Z				++string;
Z				}
Z			return	0;
Z		case '?': /* Match any character.			*/
Z			break;
Z		case '[': /* Match one of the characters in brackets
Z				unless first is a '!', then match
Z				any character not inside brackets.
Z			   */
Z			{ register char	*rgtBracket;
Z			  static int	negation;
Z
Z			++pattern; /* Skip over left bracket.		*/
Z			/* Find matching right bracket.			*/
Z			if( (rgtBracket = strchr( pattern, ']' )) == NULL )
Z				{
Z				prnt1Err( "Unmatched '['." );
Z				return	0;
Z				}
Z			/* Check for negation operator.			*/
Z			if( pattern[0] == '!' )
Z				{
Z				++pattern;
Z				negation = 1;
Z				}
Z			else	{
Z				negation = 0;
Z				}	
Z			/* Traverse pattern inside brackets.		*/
Z			for(	;
Z				pattern < rgtBracket
Z			     &&	pattern[0] != string[0];
Z				++pattern
Z				)
Z				{
Z				if(	pattern[ 0] == '-'
Z				    &&	pattern[-1] != '\\'
Z					)
Z					{
Z					if(	pattern[-1] <= string[0]
Z					    &&	pattern[-1] != '['
Z					    &&	pattern[ 1] >= string[0]
Z					    &&	pattern[ 1] != ']'
Z					)
Z						break;
Z					}
Z				}
Z			if( pattern == rgtBracket )
Z				{
Z				if( ! negation )
Z					{
Z					return	0;
Z					}
Z				}
Z			else
Z				{
Z				if( negation )
Z					{
Z					return	0;
Z					}
Z				}
Z			pattern = rgtBracket; /* Skip to right bracket.	*/
Z			break;
Z			}
Z		case '\\': /* Escape special character.			*/
Z			++pattern;
Z			/* WARNING: falls through to default case.	*/
Z		default:  /* Compare characters.			*/
Z			if( pattern[0] != string[0] )
Z				return	0;
Z		}
Z		++pattern;
Z		++string;
Z		}
Z	while( pattern[0] != NUL && string[0]  != NUL );
Z	if( (pattern[0] == NUL || pattern[0] == '*' ) && string[0]  == NUL )
Z		{
Z		return	1;
Z		}
Z	else
Z		{
Z		return	0;
Z		}
Z	}
STUNKYFLUFF
set `sum match.c`
if test 25740 != $1
then
echo match.c: Checksum error. Is: $1, should be: 25740.
fi
#
#
echo Extracting matchtest.c:
sed 's/^Z//' >matchtest.c <<\STUNKYFLUFF
Z/*
Z	SCCS id:	@(#) matchtest.c	1.2
Z	Last edit: 	1/16/85 at 21:19:12
Z	Retrieved: 	1/16/85 at 21:20:06
Z	SCCS archive:	/vld/moss/work/libWIND/s.matchtest.c
Z
Z	Author:		Gary S. Moss
Z			U. S. Army Ballistic Research Laboratory
Z			Aberdeen Proving Ground
Z			Maryland 21005-5066
Z			(301)278-6647 or AV-283-6647
Z */
Z#if ! defined( lint )
Zstatic
Zchar	sccsTag[] = "@(#) matchtest.c	1.2	last edit 1/16/85 at 21:19:12";
Z#endif
Z#include <stdio.h>
Zextern int	match();
Zchar	*usage[] = {
Z"",
Z"matchtest(1.2)",
Z"",
Z"Usage: matchtest [pattern string]",
Z"",
Z"If no arguments are given, the program reads words on its standard input.",
Z"The program writes to its standard output.",
Z0
Z};
Zvoid		prntUsage(), prnt1Err();
Zstatic char	*pattern, *string;
Zstatic char	patbuf[BUFSIZ], strbuf[BUFSIZ];
Z/*	m a i n ( )
Z */
Zmain( argc, argv )
Zchar	*argv[];
Z	{
Z	if( ! parsArgv( argc, argv ) )
Z		{
Z		prntUsage();
Z		exit( 1 );
Z		}
Z	if( pattern != NULL )
Z		{
Z		if( match( pattern, string ) )
Z			{
Z			(void) printf( "'%s' matches '%s'.\n", pattern, string );
Z			exit( 0 );
Z			}
Z		else
Z			{
Z			(void) printf(	"'%s' does not match '%s'.\n",
Z					pattern,
Z					string
Z					);
Z			exit( 1 );
Z			}
Z		}
Z	while( scanf( "%s %s", patbuf, strbuf ) == 2 )
Z		{
Z		if( match( patbuf, strbuf ) )
Z			{
Z			(void) printf( "'%s' matches '%s'.\n", patbuf, strbuf );
Z			}
Z		else
Z			{
Z			(void) printf(	"'%s' does not match '%s'.\n",
Z					patbuf,
Z					strbuf
Z					);
Z			}
Z		}		
Z	exit( 0 );
Z	}
Z
Z
Z/*	p a r s A r g v ( )
Z */
ZparsArgv( argc, argv )
Zregister char	**argv;
Z	{
Z	register int	c;
Z	extern int	optind;
Z	extern char	*optarg;
Z
Z	/* Parse options.					*/
Z	while( (c = getopt( argc, argv, "" )) != EOF )
Z		{
Z		switch( c )
Z			{
Z			case '?' :
Z				return	0;
Z			}
Z		}
Z	if( argc - optind != 2 )
Z		{
Z		if( argc == optind )
Z			{
Z			pattern = string = NULL;
Z			} 
Z		else 
Z			{
Z			(void) fprintf( stderr, "Arg count wrong!\n" );
Z			return	0;
Z			}
Z		} 
Z	else
Z		{
Z		pattern = argv[optind++];
Z		string = argv[optind++];
Z		}
Z	return	1;
Z	}
Z
Z/*	p r n t U s a g e ( )
Z	Print usage message.
Z */
Zvoid
ZprntUsage()
Z	{
Z	register char	**p = usage;
Z	while( *p )
Z		(void) fprintf( stderr, "%s\n", *p++ );
Z	return;
Z	}
Z
STUNKYFLUFF
set `sum matchtest.c`
if test 57239 != $1
then
echo matchtest.c: Checksum error. Is: $1, should be: 57239.
fi
echo ALL DONE BUNKY!
exit 0