/* RECOGNIZ.C - recognizer function for Kimmo analysis *************************************************************************** * * RESULT *recognizer(surf_form,lang,limit,trace,logfp) * unsigned char *surf_form; * LANGUAGE *lang; * int limit; * int trace; * FILE *logfp; * *************************************************************************** * EDIT HISTORY * 18-Jul-89 written by Dave Smith * 18-Sep-89 SRMc - regularize some comments and includes * - reorganize and label static functions * - replace malloc() with myalloc() * - replace free() with myfree() * - replace (bogus) index() with strpos() * 21-Sep-89 SRMc - change char to unsigned char for 8-bit safety * - fiddle with format of traceR() output * 22-Sep-89 SRMc - more fiddling with tracing * - change call interface for recognizer() * - clean up the code in recognizer() * 23-Sep-89 SRMc - rename MORPH.H to KIMMO.H * 25-Sep-89 SRMc - finetune tracing display * - fill in some more comments * 26-Sep-89 SRMc - use STAMP's newstyle TRIE * - replace struct endlst with struct lex_info * - move findCClass() to bldlex.c * 27-Sep-89 SRMc - replace typedef Rule with typedef RULE * - modify interface to moveAutomata() * 28-Sep-89 SRMc - make Lang global, remove "lang" arguments * - simplify tracing and logging variables * 29-Sep-89 SRMc - change interface to recognizer(), move guts * of it to recog() * - revise traceR() * 30-Sep-89 SRMc - finish changing lexicon storage * 2-Oct-89 SRMc - consolidated lexicon storage was a mistake -- * back up to previous scheme * - rename Language to LANGUAGE * - rename ResNode to RESULT * - replace typedefs ContClass and Alt with * typedef ALTERNATION * - replace typedef Lexicon with typedef LEXICON * - eliminate appendCha() * 11-Oct-89 SRMc - use new initial_lex field in LANGUAGE * 12-Oct-89 SRMc - check for lexicons with nonexistent TRIE * 13-Oct-89 SRMc - revise tracing output * - add SET LIMIT {ON|OFF} command * - add Lang.boundary field processing * 14-Oct-89 SRMc - fix bug in Lang.boundary processing * - move recordResult() to PCKFUNCS.C * - eliminate resHead and resTail as global * variables * - revise interface to recordResult(), rename * it to add_result() * 16-Oct-89 SRMc - finetune tracing output * 17-Oct-89 SRMc - more finetuning of tracing output * 18-Oct-89 SRMc - even more finetuning of tracing output * 19-Oct-89 SRMc - yet even more finetuning of tracing output * 21-Oct-89 SRMc - eliminate global variables * - rename moveAutomata() to move_automata() * - rename finalConfig() to final_config() * 24-Oct-89 SRMc - some delinting * 12-Dec-89 SRMc - fiddle with tracing output * 13-Dec-89 SRMc - add filename to report_error() argument list * 2-Jan-90 SRMc - add function protypes, more delinting * 3-Jan-90 SRMc - will we never run out of lint? * 24-Jan-90 SRMc - edit MISMATCH_T and NULLENTRY_T trace messages * 26-Jan-90 SRMc - edit NULLENTRY_T trace message * 12-Jul-90 SRMc - replace "void *" with "VOIDP", as suggested * by Greg Lee (lee@uhccux.uhcc.hawaii.edu) for * port to ULTRIX * 6-Sep-90 SRMc - fix bug reported by Richard Sproat of AT&T * Bell Labs (Murray Hill) * 15-Sep-90 SRMc - undo part of the fix of 6-Sep-90. the hack * to eliminate duplicated output also gets rid * of some valid output. *************************************************************************** * Copyright 1989, 1990 by the Summer Institute of Linguistics, Inc. * All rights reserved. */ #ifdef BSD #include #else #endif #ifdef __STDC__ /* from pckfuncs.c */ extern RESULT *add_result(unsigned char *pres, unsigned char *pfeat, RESULT *headp, unsigned char nullchar, int trace, FILE *logfp); extern int final_config(int *config, LANGUAGE *lang); extern int move_automata(unsigned char lexChar, unsigned char surfChar, int *config, LANGUAGE *lang); /* extern VOIDP myalloc(unsigned size); */ extern void myfree(VOIDP s); extern VOIDP myrealloc(VOIDP s, unsigned size); extern void report_error(int severity, struct message *err_msg, int *pline, char *filename, ...); extern int strpos(unsigned char *s, unsigned char c); /* extern int valid_form(unsigned char *form, LANGUAGE *lang, FILE *logfp); */ #else /* from pckfuncs.c */ extern RESULT *add_result(); /* extern VOIDP myalloc(); */ extern VOIDP myrealloc(); extern void report_error(), myfree(); extern int move_automata(), final_config() /* , valid_form() */ , strpos(); #endif static LANGUAGE static2_Lang; /* data for the current language */ /* marwan, 10-15-91 -- replaced the static 'Limit_flag's name with the */ /* name 'static2_Limit_flag' to solve a kcl problem */ static int static2_Limit_flag; /* flag for limit on/off */ static int static2_Trace_flag; /* flag for tracing on/off */ static FILE *Log_fp; /* log FILE pointer */ static RESULT *resHead; /* local RESULT pointer */ static unsigned char *result = (unsigned char *)NULL; static int result_size = 0; static unsigned char *feature = (unsigned char *)NULL; static int feature_size = 0; /* * error messages */ static struct message Bad_recog_lex = { 802, "Invalid lexicon for recognizer" }; static struct message Empty_lexicon = { 803, "Lexicon section %s is empty" }; static struct message No_lexicon = { 804, "Cannot recognize forms without a lexicon" }; /* * simplify tracing both to stderr and an optional log file */ #define static2_TRACE(tracelevel,reclev,dir,lex,lc,sc,states,rul,rem,type) \ {\ if (static2_Trace_flag >= tracelevel)\ {\ if (Log_fp != (FILE *)NULL)\ traceR(Log_fp,reclev,dir,lex,lc,sc,states,rul,rem,type);\ traceR(stderr,reclev,dir,lex,lc,sc,states,rul,rem,type);\ }\ } #define NORMAL_T 0 #define BLOCK_T 1 #define RULEFAIL_T 2 #define ENTERING_T 3 #define BACKING_T 4 #define MISMATCH_T 5 #define NOTMATCH_T 6 #define NULLENTRY_T 7 /**************************************************************************** * Name * traceR * ARGUMENTS * outfp - tracing output FILE pointer * lev - level number (actually length of result string) * dir - < or space * lexN - lexicon name * lc - underlying character * sc - surface character * states - states of the rules * rNr - rule number (of blocking rule) * rem - current remainder (used only w/ "BLOCKED IN LEX" msg) * tracetype - type of trace output desired * DESCRIPTION * Publish the current state for trace output. * RETURN VALUE * none */ static void traceR(outfp, lev, dir, lexN, lc, sc, states, rNr, rem, tracetype) FILE *outfp; int lev; unsigned char dir; unsigned char *lexN; unsigned char lc; unsigned char sc; int *states; int rNr; unsigned char *rem; int tracetype; { int i; if (lexN == (unsigned char *)NULL) lexN = (unsigned char *)""; if (rem == (unsigned char *)NULL) rem = (unsigned char *)""; if ( (tracetype == BACKING_T) || (tracetype == ENTERING_T) || (tracetype == NULLENTRY_T) ) fprintf(outfp, " "); else fprintf(outfp, "%2d%c %c%c%c ", lev,dir,lc, (lc==' ')?' ' : ':', sc ); switch(tracetype) { case NORMAL_T: for ( i = 0 ; i < static2_Lang.num_rules ; ++i ) fprintf(outfp, "%2d ", states[i] ); if (result != (unsigned char *)NULL) { fprintf(outfp, " %s", result); if ((feature != (unsigned char *)NULL) && (*feature != NUL)) fprintf(outfp, " %s", feature); } putc( '\n', outfp); break; case BLOCK_T: if (static2_Trace_flag >= 3) { for ( i = 0 ; i < static2_Lang.num_rules ; ++i ) { if (i < rNr) fprintf(outfp, "%2d ", states[i] ); else fprintf(outfp, " ? " ); } if (result != (unsigned char *)NULL) { fprintf(outfp, " %s", result); if ((feature != (unsigned char *)NULL) && (*feature != NUL)) fprintf(outfp, " %s", feature); } fprintf(outfp, "\n "); } fprintf(outfp, "BLOCKED BY RULE %d: %s\n", rNr, static2_Lang.automata[rNr-1].name ); break; case RULEFAIL_T: for ( i = 0 ; i < static2_Lang.num_rules ; ++i ) fprintf(outfp, "%2d ", states[i] ); if (result != (unsigned char *)NULL) { fprintf(outfp, " %s", result); if ((feature != (unsigned char *)NULL) && (*feature != NUL)) fprintf(outfp, " %s", feature); } putc( '\n', outfp); fprintf( outfp, " END OF INPUT, FAILED RULE %d: %s\n", rNr, static2_Lang.automata[rNr-1].name ); break; case ENTERING_T: fprintf(outfp, "ENTERING LEXICON %s\n", lexN ); break; case BACKING_T: fprintf(outfp, "BACKING UP FROM LEXICON %s TO LEXICON %s\n", rem, lexN ); break; case MISMATCH_T: fprintf(outfp, "BLOCKED IN LEXICON %s: INPUT = %s\n", lexN, rem ); break; case NOTMATCH_T: fprintf(outfp, "LEXICAL CHARACTER NOT MATCHED IN LEXICON %s\n", lexN ); break; case NULLENTRY_T: fprintf(outfp, "ACCEPTING NULL ENTRY IN LEXICON %s\n", lexN); break; default: putc('\n', outfp); break; } } /**************************************************************************** * NAME * recog * ARGUMENTS * remainder - pointer to remainder of word to process * level - recursion level (actually current length of result) * config - pointer to rules activation array * lexp - pointer to current Lexicon * alt_wanted - pointer to acceptable alternative lexicon sections * feat_size - length of features of result we've computed so far * DESCRIPTION * Recursively recognize a word (if possible). * RETURN VALUE * nonzero if succeeded at least once, zero if recognition failed */ static int recog(remainder, level, config, lexp, feat_size) unsigned char *remainder; int level; int *config; LEXICON *lexp; int feat_size; { unsigned char sc; /* surface character */ unsigned char *sp; /* pointer to current surface character */ unsigned char lc; /* lexical character */ unsigned char *lp; /* pointer to current lexical character */ TRIE *lexTP; TRIE *newTP; struct lex_item *lip; int fprX; int fprSize; int lexX; int i, j; int new_feat_size; int *newConfig, *old, *new; int blockR; int newLexFlag; int have_good_result; int fin; int rec; LEXICON **ccp; ALTERNATION *altp; LEXICON subLexicon; LEXICON *newlexp; /* * check for valid lexicon, then initialize for the rest of the function */ if ( lexp == (LEXICON *)NULL ) { report_error(FATAL, &Bad_recog_lex, (int *)NULL, (char *)NULL); return(0); } lexTP = lexp->lex_storage; if (lexTP == (TRIE *)NULL) { report_error(FATAL, &Empty_lexicon, (int *)NULL, (char *)NULL, lexp->lex_name); return(0); } newConfig = (int *)myalloc(static2_Lang.num_rules * sizeof(int)); have_good_result = 0; newLexFlag = FALSE; /******************************************************************* * If Lexicon starts with an entry, construct new tasks for each * * lexicon in its continuation class with current Remainder, * * Configuration, and Result where Lexicon = the new lexicon * * and Features = Features with the features of the entry * * appended to it. * *******************************************************************/ for ( lip = (struct lex_item *)lexTP->trieinfo ; lip != (struct lex_item *)NULL ; lip = lip->link ) { altp = lip->lex_continue; if (altp != (ALTERNATION *)NULL) { /* * step through each of the continuation lexicons */ for ( ccp = altp->alt_lexicons ; *ccp != (LEXICON *)NULL ; ++ccp ) { newlexp = *ccp; newLexFlag = TRUE; static2_TRACE(1, 0, 0, newlexp->lex_name, 0,0, NULL, 0, NULL, ENTERING_T) for (new=newConfig, old=config, j=0 ; j < static2_Lang.num_rules ; ++j) *new++ = *old++; /* * add the feature of the lexical item we've just recognized */ new_feat_size = feat_size + strlen( (char *)lip->lex_gloss ); while (new_feat_size >= feature_size) { feature_size += MAXLINELEN; feature = (unsigned char *)myrealloc(feature, feature_size+1); } strcat((char *)feature, (char *)lip->lex_gloss); /* * process the rest of the surface form with the current * continuation lexicon */ rec = recog(remainder, level, newConfig, newlexp, new_feat_size); feature[feat_size] = NUL; have_good_result += rec; static2_TRACE(1, 0, 0, lexp->lex_name, 0, 0, NULL, 0, newlexp->lex_name, BACKING_T) if (static2_Limit_flag && have_good_result) { myfree( newConfig ); return( have_good_result ); } } } else if (remainder[0] == NUL) { /************************/ /* we may have a result */ /************************/ /***************************************************************** * check the boundary character if applicable */ if ( (static2_Lang.boundary != NUL) && (strchr((char *)static2_Lang.lex_pair, static2_Lang.boundary) != (char *)NULL)) { lc = static2_Lang.boundary; sc = static2_Lang.boundary; static2_TRACE(2, level, ' ', lexp->lex_name, lc,sc, config, 0, NULL, NORMAL_T) if ((blockR = move_automata(lc, sc, config, &static2_Lang)) == 0) static2_TRACE(2, level, ' ', lexp->lex_name, ' ',' ', config, 0, NULL, NORMAL_T) else { static2_TRACE(2, level, '-', lexp->lex_name, ' ',' ', config, blockR, NULL, BLOCK_T) goto no_result_here; /* ugh, but ... */ } } fin = final_config(config,&static2_Lang); if (fin == 0) { ++have_good_result; /* * add the feature of the lexical item we've just recognized */ new_feat_size = feat_size + strlen( (char *)lip->lex_gloss ); while (new_feat_size >= feature_size) { feature_size += MAXLINELEN; feature = (unsigned char *)myrealloc(feature, feature_size+1); } strcat((char *)feature, (char *)lip->lex_gloss); resHead = add_result(result, feature, resHead, static2_Lang.null, static2_Trace_flag, Log_fp ); feature[feat_size] = NUL; } else static2_TRACE(2, level, ' ', lexp->lex_name, ' ',' ', config, fin, NULL, RULEFAIL_T ) } no_result_here: if (static2_Limit_flag && have_good_result) { myfree( newConfig ); return( have_good_result ); } } /********************************************************************* * Consider all feasible pairs (LexCha.0) where LexCha is the head * * of a branch in Lexicon. If MoveAutomata succeeds with that * * pair and Configuration, construct a new task with current * * Remainder and Features where Result = Result with LexCha * * appended, Lexicon = that branch, and Configuration = the new * * configuration returned by MoveAutomata. * *********************************************************************/ fprSize = strlen((char *)static2_Lang.surf_pair); for ( sc = static2_Lang.null, fprX = 0 ; fprX < fprSize ; ++fprX ) { if (static2_Lang.surf_pair[fprX] != static2_Lang.null) continue; lc = static2_Lang.lex_pair[fprX]; if ((lexX = strpos(lexTP->letters,lc)) >= 0) { for (new = newConfig, old = config, j = 0 ; j < static2_Lang.num_rules ; ++j) *new++ = *old++; static2_TRACE(2, level,' ', lexp->lex_name, lc, sc, config, 0, NULL, NORMAL_T) if ((blockR = move_automata(lc, sc, newConfig, &static2_Lang)) == 0) { /* * add one character to the result */ if (level >= result_size) { result_size += MAXLINELEN; result = (unsigned char *)myrealloc(result, result_size+1); } result[level] = lc; result[level+1] = NUL; /* * point to the proper subTRIE */ newTP = lexTP->children; for ( i = 0 ; i < lexX ; i++ ) newTP = newTP->siblings; subLexicon.lex_name = lexp->lex_name; subLexicon.lex_storage = newTP; rec = recog(remainder, level+1, newConfig, &subLexicon, feat_size); result[level] = NUL; have_good_result += rec; if (!rec) static2_TRACE(2, level+1,'-', lexp->lex_name, ' ', ' ', newConfig, 0, remainder, MISMATCH_T) static2_TRACE(2, level, '<', lexp->lex_name, ' ', ' ', config, 0, NULL, NORMAL_T) } else static2_TRACE(2, level, '-', lexp->lex_name,' ',' ',newConfig, blockR, NULL, BLOCK_T) } else static2_TRACE(3, level, '-', lexp->lex_name, lc, sc, NULL, 0, NULL, NOTMATCH_T) if (static2_Limit_flag && have_good_result) { myfree( newConfig ); return( have_good_result ); } } /***************************************************************** * if we didn't get a good result, ignore "end of lexicon" flag * [ fix bug of missing valid result under these circumstances: * 1. (infix) insertion constrained only by preceeding characters * 2. one lexical item is the leading substring of another up to * exactly the point where the insertion occurs ] */ if ( !have_good_result ) newLexFlag = FALSE; /******************************************************************** * Consider all feasible pairs (LexCha.SurfCha) where LexCha is * * the head of a branch in Lexicon and SurfCha is the first * * character of Remainder. If MoveAutomata succeeds with that * * pair and Configuration, construct a new task with current * * Features where Result = Result with LexCha appended, Lexicon = * * that branch, Remainder = tail of Remainder, and Configuration = * * the new configuration returned by MoveAutomata * ********************************************************************/ for ( sp = static2_Lang.surf_pair, lp = static2_Lang.lex_pair ; *lp ; ) { lc = *lp++; sc = *sp++; if (sc != *remainder) continue; /* need matching surface character */ lexX = strpos(lexTP->letters,lc); if ((lexX >= 0) || ((lc == static2_Lang.null) && !newLexFlag)) { for (new = newConfig, old = config, j = 0 ; j < static2_Lang.num_rules ; ++j) *new++ = *old++; static2_TRACE(2, level,' ',lexp->lex_name, lc,sc, config, 0, NULL, NORMAL_T) if ((blockR = move_automata(lc, sc, newConfig, &static2_Lang)) == 0) { /* * add the lexical character to the result */ if (level >= result_size) { result_size += MAXLINELEN; result = (unsigned char *)myrealloc(result, result_size+1); } result[level] = lc; result[level+1] = NUL; if (lc != static2_Lang.null) { /* * point to the proper subTRIE */ newTP = lexTP->children; for ( i = 0 ; i < lexX ; i++ ) newTP = newTP->siblings; } else { /* * null lexical character -- keep the same spot in the TRIE */ newTP = lexTP; } subLexicon.lex_name = lexp->lex_name; subLexicon.lex_storage = newTP; rec = recog(remainder+1,level+1,newConfig, &subLexicon, feat_size); result[level] = NUL; have_good_result += rec; if (!rec) static2_TRACE(2, level+1,'-', lexp->lex_name, ' ', ' ', newConfig, 0, remainder+1, MISMATCH_T) static2_TRACE(2, level, '<', lexp->lex_name, ' ', ' ', config, 0, NULL, NORMAL_T) } else static2_TRACE(2, level, '-', lexp->lex_name,' ',' ',newConfig, blockR, NULL, BLOCK_T) } else static2_TRACE(3, level, '-', lexp->lex_name, lc, sc, NULL, 0, NULL, NOTMATCH_T) if (static2_Limit_flag && have_good_result) { myfree( newConfig ); return( have_good_result ); } } /******************************************************************* * Consider the pair (0.0). If 0 is the head of a branch of the * * lexicon, recurse with the same remainder, state configuration, * * "level", result string, and feature string. Only modify the * * lexicon trie to pursue the indicated branch of this lexicon. * *******************************************************************/ if ((lexX = strpos(lexTP->letters,static2_Lang.null)) >= 0) { lc = static2_Lang.null; sc = static2_Lang.null; static2_TRACE(2, level, ' ', lexp->lex_name, lc, sc, config, 0, NULL, NULLENTRY_T) for ( new = newConfig, old = config, j = 0 ; j < static2_Lang.num_rules ; ++j ) *new++ = *old++; /* * point to the proper subTRIE */ newTP = lexTP->children; for ( i = 0 ; i < lexX ; i++ ) newTP = newTP->siblings; subLexicon.lex_name = lexp->lex_name; subLexicon.lex_storage = newTP; rec = recog(remainder, level, newConfig, &subLexicon, feat_size); have_good_result += rec; static2_TRACE(2, level, '<', lexp->lex_name, ' ',' ', config, 0, NULL, NORMAL_T ) if (static2_Limit_flag && have_good_result) { myfree( newConfig ); return( have_good_result ); } } myfree( newConfig ); return( have_good_result ); } /**************************************************************************** * NAME * recognizer * ARGUMENTS * surf_form - pointer to surface form to analyze * lang - data for the current language * limit - flag for limit on/off * trace - flag for tracing on/off * logfp - log FILE pointer * DESCRIPTION * Set up for the call to recog() for recursive recognition of the surface * form. * RETURN VALUE * pointer to the list of results, or NULL if no results found */ RESULT *recognizer(surf_form,lang,limit,trace,logfp) unsigned char *surf_form; LANGUAGE *lang; int limit; int trace; FILE *logfp; { register int i; int *config; LEXICON *lexp; if (lang == (LANGUAGE *)NULL) return( (RESULT *)NULL ); /* don't bother if no language data */ /* * copy language data into local structure (for faster access) */ static2_Lang.alphabet = lang->alphabet; static2_Lang.null = lang->null; static2_Lang.any = lang->any; static2_Lang.boundary = lang->boundary; static2_Lang.subsets = lang->subsets; static2_Lang.numsubsets = lang->numsubsets; static2_Lang.automata = lang->automata; static2_Lang.num_rules = lang->num_rules; static2_Lang.lex_pair = lang->lex_pair; static2_Lang.surf_pair = lang->surf_pair; static2_Lang.num_pairs = lang->num_pairs; static2_Lang.alterns = lang->alterns; static2_Lang.num_alterns = lang->num_alterns; static2_Lang.lex_sections = lang->lex_sections; static2_Lang.initial_lex = lang->initial_lex; static2_Lang.num_lex_sections = lang->num_lex_sections; /* * copy other invariant parameters to local storage */ static2_Limit_flag = limit; static2_Trace_flag = trace; Log_fp = logfp; /* * start with the initial section of the lexicon */ if (static2_Lang.initial_lex == (LEXICON *)NULL) { report_error(FATAL, &No_lexicon, (int *)NULL, (char *)NULL); return((RESULT *)NULL); } lexp = static2_Lang.initial_lex; /* * check for valid form, print a trace message, and then initialize * for the call to recog() */ if (!valid_form(surf_form,&static2_Lang,Log_fp)) return((RESULT *)NULL); config = (int *)myalloc(static2_Lang.num_rules*sizeof(int)); for ( i = 0 ; i < static2_Lang.num_rules ; ++i ) config[i] = 1; /***************************************************************** * check the boundary character if applicable */ if ( (static2_Lang.boundary != NUL) && (strchr((char *)static2_Lang.lex_pair, static2_Lang.boundary) != (char *)NULL) ) { static2_TRACE(2, 0, ' ', lexp->lex_name, static2_Lang.boundary, static2_Lang.boundary, config, 0, surf_form, NORMAL_T ) if ((i = move_automata(static2_Lang.boundary, static2_Lang.boundary, config, &static2_Lang)) != 0) { static2_TRACE(2, 0, '-', lexp->lex_name,' ',' ',config, i, surf_form, BLOCK_T) myfree(config); return( (RESULT *)NULL ); } } static2_TRACE(1, 0, 0, lexp->lex_name, 0, 0, NULL, 0, NULL, ENTERING_T) result = (unsigned char *)myalloc(MAXLINELEN+1); result_size = MAXLINELEN; feature = (unsigned char *)myalloc(MAXLINELEN+1); feature_size = MAXLINELEN; resHead = (RESULT *)NULL; recog( surf_form, 0, config, lexp, 0); myfree(result); result = (unsigned char *)NULL; result_size = 0; myfree(feature); feature = (unsigned char *)NULL; feature_size = 0; myfree(config); return( resHead ); }