link-grammar-5.8.0/link-grammar/parse/parse.c
/**
 * classic_parse() -- parse the given sentence.
 * Perform parsing, using the original link-grammar parsing algorithm
 * given in the original link-grammar papers.
 *
 * Do the parse with the minimum number of null-links within the range
 * specified by opts->min_null_count and opts->max_null_count.
 *
 * To that end, call do_parse() with an increasing null_count, from
 * opts->min_null_count up to (including) opts->max_null_count, until a
 * parse is found.
 *
 * To increase the parsing speed, before invoking do_parse(), invoke
 * pp_and_power_prune() to remove connectors which have no possibility to
 * connect. Since power_prune() includes a significant optimization if it
 * assumes that the linkage has no more than a specific number of null
 * links (aka null_count), call it with the current number of null_count
 * for which do_count() is invoked.
 *
 * In order to be able to so repeat the pruning step, we need to keep
 * the original disjunct/connectors in order to prune them again.
 * This is done only when needed, i.e. when we are invoked with
 * min_null_count != max_null_count (a typical case is that they are
 * both 0).
 *
 * So in case this optimization has been done and a parse (e.g.
 * a parse when null_count==0) is not found, we are left with sentence
 * disjuncts which are not appropriate to continue do_parse() tries with
 * a greater null_count. To solve that, we need to restore the original
 * disjuncts of the sentence and call pp_and_power_prune() once again.
 */
- parse the given sentence.
Perform parsing, using the original link-grammar parsing algorithm
given in the original link-grammar papers.

Do the parse with the minimum number of null-links within the range
specified by opts->min_null_count and opts->max_null_count.

To that end, call do_parse() with an increasing null_count, from
opts->min_null_count up to (including) opts->max_null_count, until a
parse is found.

To increase the parsing speed, before invoking do_parse(), invoke
pp_and_power_prune() to remove connectors which have no possibility to
connect. Since power_prune() includes a significant optimization if it
assumes that the linkage has no more than a specific number of null
links (aka null_count), call it with the current number of null_count
for which do_count() is invoked.

In order to be able to so repeat the pruning step, we need to keep
the original disjunct/connectors in order to prune them again.
This is done only when needed, i.e. when we are invoked with
min_null_count != max_null_count (a typical case is that they are
both 0).

So in case this optimization has been done and a parse  is not found, we are left with sentence
disjuncts which are not appropriate to continue do_parse() tries with
a greater null_count. To solve that, we need to restore the original
disjuncts of the sentence and call pp_and_power_prune() once again.
- parse the given sentence . Perform parsing using the original link - grammar parsing algorithm given in the original link - grammar papers . Do the parse with the minimum number of null - links within the range specified by opts - > min_null_count and opts - > max_null_count . To that end call do_parse () with an increasing null_count from opts - > min_null_count up to ( including ) opts - > max_null_count until a parse is found . To increase the parsing speed before invoking do_parse () invoke pp_and_power_prune () to remove connectors which have no possibility to connect . Since power_prune () includes a significant optimization if it assumes that the linkage has no more than a specific number of null links ( aka null_count ) call it with the current number of null_count for which do_count () is invoked . In order to be able to so repeat the pruning step we need to keep the original disjunct / connectors in order to prune them again . This is done only when needed i . e . when we are invoked with min_null_count ! = max_null_count ( a typical case is that they are both 0 ) . So in case this optimization has been done and a parse is not found we are left with sentence disjuncts which are not appropriate to continue do_parse () tries with a greater null_count . To solve that we need to restore the original disjuncts of the sentence and call pp_and_power_prune () once again .
void classic_parse(Sentence sent, Parse_Options opts)
{
	fast_matcher_t * mchxt = NULL;
	count_context_t * ctxt = NULL;
	Tracon_sharing *ts_parsing = NULL;
	void *saved_memblock = NULL;
	int current_prune_level = -1; 
	int needed_prune_level = opts->min_null_count;
	bool more_pruning_possible = false;
	unsigned int max_null_count = opts->max_null_count;
	max_null_count = (unsigned int)MIN(max_null_count, sent->length);
	bool one_step_parse = (unsigned int)opts->min_null_count != max_null_count;
	int max_prune_level = (int)max_null_count;
	bool optimize_pruning = true; 
	unsigned int *ncu[2];
	ncu[0] = alloca(sent->length * sizeof(*ncu[0]));
	ncu[1] = alloca(sent->length * sizeof(*ncu[1]));
	if (opts->islands_ok)
		optimize_pruning = false;
	if (sent->length < sent->min_len_multi_pruning)
		optimize_pruning = false;
	if (!optimize_pruning)
	{
		if (opts->min_null_count == 0)
			max_prune_level = 0;
		else
		{
			needed_prune_level = MAX_SENTENCE;
			one_step_parse = false;
		}
	}
	prepare_to_parse(sent, opts);
	if (resources_exhausted(opts->resources)) return;
	Tracon_sharing *ts_pruning = pack_sentence_for_pruning(sent);
	free_sentence_disjuncts(sent);
	if (one_step_parse)
	{
		saved_memblock = save_disjuncts(sent, ts_pruning);
	}
	print_time(opts, "Encoded for pruning%s%s",
	           (NULL == ts_pruning->tracon_list) ? " (skipped)" : "",
	           (one_step_parse) ? " (one-step)" : "");
	for (unsigned int nl = opts->min_null_count; nl <= max_null_count; nl++)
	{
		sent->null_count = nl;
		if (needed_prune_level > current_prune_level)
		{
			current_prune_level = needed_prune_level;
			if (needed_prune_level < max_prune_level)
				needed_prune_level++;
			else
				needed_prune_level = MAX_SENTENCE;
			if (more_pruning_possible)
				restore_disjuncts(sent, saved_memblock, ts_pruning);
			more_pruning_possible =
				one_step_parse && (current_prune_level != MAX_SENTENCE);
			unsigned int expexted_null_count =
				pp_and_power_prune(sent, ts_pruning, current_prune_level, opts,
				                   ncu);
			if (expexted_null_count > nl)
			{
				if (opts->verbosity >= D_USER_TIMES)
				{
					prt_error("#### Skip parsing (w/%u ", nl);
					if (expexted_null_count-1 > nl)
						prt_error("to %u nulls)\n", expexted_null_count-1);
					else
						prt_error("null%s)\n", (nl != 1) ? "s" : "");
				}
				nl = expexted_null_count-1;
				if (nl == sent->length-1) nl--;
				continue;
			}
		}
		if (NULL != ts_pruning)
		{
			ts_parsing = pack_sentence_for_parsing(sent);
			print_time(opts, "Encoded for parsing");
			if (!more_pruning_possible)
			{
				if (NULL != ts_pruning)
				{
					free(ts_pruning->memblock);
					free_tracon_sharing(ts_pruning);
					ts_pruning = NULL;
					if (NULL != saved_memblock)
						free(saved_memblock);
				}
				free_tracon_sharing(ts_parsing);
				ts_parsing = NULL;
			}
			gword_record_in_connector(sent);
			if (resources_exhausted(opts->resources)) break;
			free_count_context(ctxt, sent);
			ctxt = alloc_count_context(sent);
			free_fast_matcher(sent, mchxt);
			mchxt = alloc_fast_matcher(sent, ncu);
			print_time(opts, "Initialized fast matcher");
		}
		if (resources_exhausted(opts->resources)) break;
		free_linkages(sent);
		sent->num_linkages_found = do_parse(sent, mchxt, ctxt, opts);
		print_time(opts, "Counted parses (%d w/%u null%s)",
		           sent->num_linkages_found, sent->null_count,
		           (sent->null_count != 1) ? "s" : "");
		extractor_t * pex = extractor_new(sent->length, sent->rand_state);
		bool ovfl = setup_linkages(sent, pex, mchxt, ctxt, opts);
		process_linkages(sent, pex, ovfl, opts);
		free_extractor(pex);
		post_process_lkgs(sent, opts);
		if (sent->num_valid_linkages > 0) break;
		if (verbosity >= D_USER_INFO)
		{
			if ((sent->num_valid_linkages == 0) &&
			    (sent->num_linkages_post_processed > 0) &&
			    ((int)opts->linkage_limit < sent->num_linkages_found))
				prt_error("Info: All examined linkages (%zu) had P.P. violations.\n"
				          "Consider increasing the linkage limit.\n"
				          "At the command line, use !limit\n",
				          sent->num_linkages_post_processed);
		}
		if ((0 == nl) && (0 < max_null_count) && verbosity > 0)
			prt_error("No complete linkages found.\n");
		free_tracon_sharing(ts_parsing);
		ts_parsing = NULL;
	}
	sort_linkages(sent, opts);
	if (NULL != ts_pruning)
	{
		free(ts_pruning->memblock);
		free_tracon_sharing(ts_pruning);
		free(saved_memblock);
	}
	free_tracon_sharing(ts_parsing);
	free_count_context(ctxt, sent);
	free_fast_matcher(sent, mchxt);
}
void classic_parse ( Sentence sent , Parse_Options opts ) { fast_matcher_t * mchxt = NULL ; count_context_t * ctxt = NULL ; Tracon_sharing * ts_parsing = NULL ; void * saved_memblock = NULL ; int current_prune_level = -1 ; int needed_prune_level = opts -> min_null_count ; bool more_pruning_possible = false ; unsigned int max_null_count = opts -> max_null_count ; max_null_count = ( unsigned int ) MIN ( max_null_count , sent -> length ) ; bool one_step_parse = ( unsigned int ) opts -> min_null_count != max_null_count ; int max_prune_level = ( int ) max_null_count ; bool optimize_pruning = true ; unsigned int * ncu [ 2 ] ; ncu [ 0 ] = alloca ( sent -> length * sizeof ( * ncu [ 0 ] ) ) ; ncu [ 1 ] = alloca ( sent -> length * sizeof ( * ncu [ 1 ] ) ) ; if ( opts -> islands_ok ) optimize_pruning = false ; if ( sent -> length < sent -> min_len_multi_pruning ) optimize_pruning = false ; if ( ! optimize_pruning ) { if ( opts -> min_null_count == 0 ) max_prune_level = 0 ; else { needed_prune_level = MAX_SENTENCE ; one_step_parse = false ; } } prepare_to_parse ( sent , opts ) ; if ( resources_exhausted ( opts -> resources ) ) return ; Tracon_sharing * ts_pruning = pack_sentence_for_pruning ( sent ) ; free_sentence_disjuncts ( sent ) ; if ( one_step_parse ) { saved_memblock = save_disjuncts ( sent , ts_pruning ) ; } print_time ( opts , " " , ( NULL == ts_pruning -> tracon_list ) ? " " : " " , ( one_step_parse ) ? " " : " " ) ; for ( unsigned int nl = opts -> min_null_count ; nl <= max_null_count ; nl ++ ) { sent -> null_count = nl ; if ( needed_prune_level > current_prune_level ) { current_prune_level = needed_prune_level ; if ( needed_prune_level < max_prune_level ) needed_prune_level ++ ; else needed_prune_level = MAX_SENTENCE ; if ( more_pruning_possible ) restore_disjuncts ( sent , saved_memblock , ts_pruning ) ; more_pruning_possible = one_step_parse && ( current_prune_level != MAX_SENTENCE ) ; unsigned int expexted_null_count = pp_and_power_prune ( sent , ts_pruning , current_prune_level , opts , ncu ) ; if ( expexted_null_count > nl ) { if ( opts -> verbosity >= D_USER_TIMES ) { prt_error ( " " , nl ) ; if ( expexted_null_count - 1 > nl ) prt_error ( " \n " , expexted_null_count - 1 ) ; else prt_error ( " \n " , ( nl != 1 ) ? " " : " " ) ; } nl = expexted_null_count - 1 ; if ( nl == sent -> length - 1 ) nl -- ; continue ; } } if ( NULL != ts_pruning ) { ts_parsing = pack_sentence_for_parsing ( sent ) ; print_time ( opts , " " ) ; if ( ! more_pruning_possible ) { if ( NULL != ts_pruning ) { free ( ts_pruning -> memblock ) ; free_tracon_sharing ( ts_pruning ) ; ts_pruning = NULL ; if ( NULL != saved_memblock ) free ( saved_memblock ) ; } free_tracon_sharing ( ts_parsing ) ; ts_parsing = NULL ; } gword_record_in_connector ( sent ) ; if ( resources_exhausted ( opts -> resources ) ) break ; free_count_context ( ctxt , sent ) ; ctxt = alloc_count_context ( sent ) ; free_fast_matcher ( sent , mchxt ) ; mchxt = alloc_fast_matcher ( sent , ncu ) ; print_time ( opts , " " ) ; } if ( resources_exhausted ( opts -> resources ) ) break ; free_linkages ( sent ) ; sent -> num_linkages_found = do_parse ( sent , mchxt , ctxt , opts ) ; print_time ( opts , " " , sent -> num_linkages_found , sent -> null_count , ( sent -> null_count != 1 ) ? " " : " " ) ; extractor_t * pex = extractor_new ( sent -> length , sent -> rand_state ) ; bool ovfl = setup_linkages ( sent , pex , mchxt , ctxt , opts ) ; process_linkages ( sent , pex , ovfl , opts ) ; free_extractor ( pex ) ; post_process_lkgs ( sent , opts ) ; if ( sent -> num_valid_linkages > 0 ) break ; if ( verbosity >= D_USER_INFO ) { if ( ( sent -> num_valid_linkages == 0 ) && ( sent -> num_linkages_post_processed > 0 ) && ( ( int ) opts -> linkage_limit < sent -> num_linkages_found ) ) prt_error ( " \n " " \n " " \n " , sent -> num_linkages_post_processed ) ; } if ( ( 0 == nl ) && ( 0 < max_null_count ) && verbosity > 0 ) prt_error ( " \n " ) ; free_tracon_sharing ( ts_parsing ) ; ts_parsing = NULL ; } sort_linkages ( sent , opts ) ; if ( NULL != ts_pruning ) { free ( ts_pruning -> memblock ) ; free_tracon_sharing ( ts_pruning ) ; free ( saved_memblock ) ; } free_tracon_sharing ( ts_parsing ) ; free_count_context ( ctxt , sent ) ; free_fast_matcher ( sent , mchxt ) ; }
classic_parse() -- parse the given sentence.
classic_parse () -- parse the given sentence .
/* -1: No pruning has been done yet. */ /* Perform pruning null count optimization. */ /* Null-count optimization not implemented for islands_ok==true. */ /* Pruning per null-count and one-step-parse are costly for sentences
	 * whose parsing takes tens of milliseconds or so. Disable them for
	 * short-enough sentences. */ /* Turn-off null-count optimization. */ /* Build lists of disjuncts */ /* Save the disjuncts for possible parse w/ an increased null count. */ /* To get a result, parse w/null count which is at most one less
				 * than the number of tokens (w/all nulls there is no linkage). */ /* At this point no further pruning will be done. Free the
				 * pruning and parsing tracon stuff here instead of at the end. */