« back to all changes in this revision
Viewing changes to source/analysis.c
- browse files at revision 4
- compare with another revision
- download diff
- download tarball
- view history from revision 4
- Committer: Bazaar Package Importer
- Author(s): Thomas Bushnell, BSG
- Date: 2004-08-20 12:58:50 UTC
- mfrom: (1.1.1 upstream)
- Revision ID: james.westby@ubuntu.com-20040820125850-rx9s8bn0ep8jgist
Tags: 6.13-4
This should have been urgency=high, because it is an important and
long-delayed accomodation to new upstream with a bajillion bug fixes.
long-delayed accomodation to new upstream with a bajillion bug fixes.
- files added:
- COPYING.txt
- files removed:
- LICENSE.txt
- bin
- doc
- lib
- man
- man/man1
- source
- tcl
- files modified:
- CHANGES.txt
added
removed
source/analysis.c
1
/* This file is part of Malaga, a system for Natural Language Analysis.
2
* Copyright (C) 1995-1999 Bjoern Beutel
3
*
4
* Bjoern Beutel
5
* Universitaet Erlangen-Nuernberg
6
* Abteilung fuer Computerlinguistik
7
* Bismarckstrasse 12
8
* D-91054 Erlangen
9
* e-mail: malaga@linguistik.uni-erlangen.de
10
*
11
* This program is free software; you can redistribute it and/or modify
12
* it under the terms of the GNU General Public License as published by
13
* the Free Software Foundation; either version 2 of the License, or
14
* (at your option) any later version.
15
*
16
* This program is distributed in the hope that it will be useful,
17
* but WITHOUT ANY WARRANTY; without even the implied warranty of
18
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19
* GNU General Public License for more details.
20
*
21
* You should have received a copy of the GNU General Public License
22
* along with this program; if not, write to the Free Software
23
* Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA */
24
25
/* description ==============================================================*/
26
27
/* This file contains data structures and functions used for grammatical
28
* analysis. */
29
30
/* includes =================================================================*/
31
32
#include <ctype.h>
33
#include <stdio.h>
34
#include <stdlib.h>
35
#include "basic.h"
36
#include "pools.h"
37
#include "values.h"
38
#include "rule_type.h"
39
#include "rules.h"
40
#include "lexicon.h"
41
#include "cache.h"
42
43
#undef GLOBAL
44
#define GLOBAL
45
#include "analysis.h"
46
47
/* types ====================================================================*/
48
49
typedef struct TREE_NODE_T /* a rule application is stored in "tree_node" */
50
{
51
struct TREE_NODE_T *mother; /* predecessor of this tree node */
52
struct TREE_NODE_T *first_daughter; /* first successor of this tree node */
53
struct TREE_NODE_T *sister; /* alternative tree node */
54
tree_node_type_t type; /* type of this tree node */
55
int_t rule; /* number of the executed rule */
56
int_t index; /* index of this tree node */
57
value_t right_cat; /* category of segment being added */
58
value_t result_cat; /* result cat of rule application */
59
int_t rule_set; /* successor rules (-1 for end state) */
60
string_t input; /* the input that is not yet analysed */
61
} tree_node_t;
62
63
typedef struct STATE_T /* a state in morphological or syntactical analysis */
64
{
65
struct STATE_T *next; /* link to state with same or higher <input> */
66
value_t cat; /* category of input read so far */
67
string_t input; /* pointer to input that is analysed next */
68
int_t rule_set; /* set of rules to be applied */
69
tree_node_t *tree_node; /* tree node of rule application that created
70
* this state (NULL if no tree) */
71
int_t item_index; /* number of items read in so far */
72
} state_t;
73
74
typedef struct /* the structure for morphological and syntactical analysis */
75
{
76
pool_t state_pool; /* all states are saved in <state_pool> */
77
pool_t value_pool; /* all categories are saved in <value_pool> */
78
79
/* states are chained by their attribute <next>. There are three chains: */
80
state_t *running_states; /* states that need further analysis
81
* (in the order of their <input> indexes) */
82
state_t *end_states; /* end states */
83
state_t *free_states; /* states that can be reused */
84
} analysis_t;
85
86
/* variables ================================================================*/
87
88
/* structures used for LAG analysis, one for morphology and one for syntax. */
89
LOCAL analysis_t *analyses[2];
90
91
/* the data structure used to save the analysis tree */
92
LOCAL tree_node_t *root_tree_node; /* a pointer to the root tree node */
93
LOCAL pool_t tree_pool; /* pool where tree nodes are stored */
94
LOCAL int_t number_of_tree_nodes;
95
96
LOCAL state_t *next_result_state; /* needed for "get_next_analysis_result" */
97
LOCAL tree_node_t *next_tree_node; /* needed for "get_next_analysis_node" */
98
99
LOCAL string_t left_start, right_start, right_end;
100
/* start and end position of surface when rule is executed. READ ONLY! */
101
102
/* information needed to generate states and tree nodes */
103
LOCAL struct {
104
analysis_t *analysis;
105
bool_t build_tree; /* entering tree nodes? */
106
bool_t analyse_all; /* analyse the whole input? */
107
int_t rule; /* rule just executed */
108
value_t right_cat; /* right category */
109
tree_node_t *mother; /* predecessor tree node */
110
int_t item_index; /* index of item that is added */
111
string_t input; /* end of analysed input */
112
} state_info;
113
114
LOCAL bool_t options[NUM_ANALYSIS_OPTIONS];
115
116
/* functions for analysis options ===========================================*/
117
118
GLOBAL void set_analysis_option (analysis_option_t selected, bool_t setting)
119
/* Set analysis option <selected> to <setting>. */
120
{
121
switch (selected)
122
{
123
case ROBUST_OPTION:
124
if (rule_system[MORPHOLOGY]->robust_rule == -1)
125
error ("no morphology \"robust_rule\"");
126
break;
127
case PRUNING_OPTION:
128
if (rule_system[SYNTAX] == NULL
129
|| rule_system[SYNTAX]->pruning_rule == -1)
130
error ("no morphology \"pruning_rule\"");
131
break;
132
case MOR_OUT_FILTER_OPTION:
133
if (rule_system[MORPHOLOGY]->output_filter == -1)
134
error ("no morphology \"output_filter\"");
135
break;
136
case SYN_OUT_FILTER_OPTION:
137
if (rule_system[SYNTAX] == NULL
138
|| rule_system[SYNTAX]->output_filter == -1)
139
error ("no syntax \"output_filter\"");
140
break;
141
case SYN_IN_FILTER_OPTION:
142
if (rule_system[SYNTAX] == NULL
143
|| rule_system[SYNTAX]->input_filter == -1)
144
error ("no syntax \"input_filter\"");
145
break;
146
case CACHE_OPTION:
147
break;
148
default:
149
error ("internal (unknown option)");
150
}
151
options[selected] = setting;
152
}
153
154
/*---------------------------------------------------------------------------*/
155
156
GLOBAL bool_t get_analysis_option (analysis_option_t selected)
157
/* return the current setting of analysis option <selected>. */
158
{
159
return options[selected];
160
}
161
162
/* functions for segmentation and preprocessing =============================*/
163
164
LOCAL bool_t is_word_part (string_t string)
165
/* Return whether the character *<string> may be part of a word. */
166
{
167
/* *<string> is part of a word if it is a letter, a digit
168
* or one of {".", ",", "-"} followed by a letter or a digit. */
169
return (IS_ALPHA (*string) || isdigit (*string)
170
|| ((*string == ',' || *string == '.' || *string == '-')
171
&& (IS_ALPHA (string[1]) || isdigit (string[1]))));
172
}
173
174
/*---------------------------------------------------------------------------*/
175
176
GLOBAL void preprocess_input (string_t input)
177
/* Delete heading and trailing spaces in <input>
178
* and compress all whitespace sequences to a single space. */
179
{
180
string_t input_ptr, output_ptr;
181
182
output_ptr = input;
183
184
/* Cut heading spaces. */
185
input_ptr = next_non_space (input);
186
while (*input_ptr != EOS)
187
{
188
if (isspace (*input_ptr))
189
{
190
/* Overread all whitespace and write a single space. */
191
input_ptr = next_non_space (input_ptr);
192
*output_ptr++ = ' ';
193
}
194
else
195
*output_ptr++ = *input_ptr++;
196
}
197
198
/* Cut trailing spaces. */
199
while (output_ptr > input && isspace (output_ptr[-1]))
200
output_ptr--;
201
*output_ptr = EOS;
202
}
203
204
/* functions for state list processing ======================================*/
205
206
LOCAL void remove_state (analysis_t *analysis, state_t **state_list_ptr)
207
/* Remove state <state_list_ptr> points to and enter it into the free list. */
208
{
209
state_t *state = *state_list_ptr;
210
211
if (state != NULL)
212
{
213
/* Unlink from old list. */
214
*state_list_ptr = state->next;
215
216
/* Enter in free list. */
217
state->next = analysis->free_states;
218
analysis->free_states = state;
219
}
220
}
221
222
/*---------------------------------------------------------------------------*/
223
224
LOCAL state_t *insert_state (analysis_t *analysis,
225
state_t **state_list_ptr,
226
value_t cat,
227
string_t input,
228
int_t rule_set,
229
int_t item_index)
230
/* Insert a state, composed of <cat>, <input>, <rule_set>, and <item_index>
231
* in the list *<state_list_ptr> points to, in front of all states with a
232
* higher <input> index. Return this state. */
233
{
234
state_t *new_state;
235
236
if (analysis->free_states != NULL)
237
{
238
/* Get first state in the free list. */
239
new_state = analysis->free_states;
240
analysis->free_states = new_state->next;
241
}
242
else
243
new_state = (state_t *) get_pool_space (analysis->state_pool, 1, NULL);
244
245
/* Set values. */
246
new_state->cat = cat;
247
new_state->input = input;
248
new_state->rule_set = rule_set;
249
new_state->item_index = item_index;
250
new_state->tree_node = NULL;
251
252
/* Insert new state in list. */
253
while (*state_list_ptr != NULL && (*state_list_ptr)->input <= input)
254
state_list_ptr = &(*state_list_ptr)->next;
255
new_state->next = *state_list_ptr;
256
*state_list_ptr = new_state;
257
258
return new_state;
259
}
260
261
/*---------------------------------------------------------------------------*/
262
263
LOCAL tree_node_t *add_tree_node (value_t result_cat,
264
string_t input,
265
int_t rule_set,
266
tree_node_type_t type)
267
/* Add a tree node for a rule that fired with <result_cat> and <rule_set>,
268
* where <input> is yet to be analysed. */
269
{
270
tree_node_t **tree_node_ptr;
271
tree_node_t *tree_node;
272
273
/* Get a new tree node. */
274
tree_node = (tree_node_t *) get_pool_space (tree_pool, 1, NULL);
275
276
tree_node->mother = state_info.mother;
277
tree_node->first_daughter = NULL;
278
tree_node->sister = NULL;
279
tree_node->type = type;
280
tree_node->rule = state_info.rule;
281
tree_node->index = number_of_tree_nodes;
282
tree_node->right_cat = state_info.right_cat;
283
tree_node->result_cat = result_cat;
284
tree_node->rule_set = rule_set;
285
tree_node->input = input;
286
287
/* Link the tree node into the tree structure. */
288
tree_node_ptr = &state_info.mother->first_daughter;
289
while (*tree_node_ptr != NULL)
290
tree_node_ptr = &(*tree_node_ptr)->sister;
291
*tree_node_ptr = tree_node;
292
293
/* Increment the number of tree nodes. */
294
number_of_tree_nodes++;
295
296
return tree_node;
297
}
298
299
/*---------------------------------------------------------------------------*/
300
301
LOCAL void add_state (state_t **list,
302
value_t cat,
303
int_t rule_set,
304
tree_node_type_t type)
305
/* Add state, consisting of <cat> and <rule_set> in list **<list>.
306
* When <state_info.build_tree> == TRUE, also generate a tree node. */
307
{
308
value_t new_value;
309
state_t *state;
310
311
/* Preserve the category. */
312
new_value = copy_value_to_pool (state_info.analysis->value_pool, cat, NULL);
313
314
state = insert_state (state_info.analysis, list, new_value, state_info.input,
315
rule_set, state_info.item_index);
316
if (state_info.build_tree)
317
state->tree_node = add_tree_node (new_value, state_info.input, rule_set,
318
type);
319
}
320
321
/* callback functions needed by rules =======================================*/
322
323
LOCAL void local_add_end_state (value_t cat)
324
/* Add a state, consisting of <cat>, as an end state. */
325
{
326
string_t input = state_info.input;
327
328
/* Only add an end state if at the end of input
329
* or at the end of a word in a subordinate morphological analysis. */
330
if (*input == EOS || ! (state_info.analyse_all
331
|| (is_word_part (input-1) && is_word_part (input))))
332
add_state (&state_info.analysis->end_states, cat, -1, FINAL_NODE);
333
}
334
335
/*---------------------------------------------------------------------------*/
336
337
LOCAL void local_add_running_state (value_t cat, int_t rule_set)
338
/* Add a running state, consisting of <cat> and <rule_set>. */
339
{
340
add_state (&state_info.analysis->running_states, cat, rule_set, INTER_NODE);
341
}
342
343
/*---------------------------------------------------------------------------*/
344
345
LOCAL string_t local_get_surface (surface_t surface_type)
346
/* Return surface <surface_type> for currently executed rule.
347
* The result must be freed after use. */
348
{
349
string_t left_end;
350
351
if (right_start > left_start && right_start[-1] == ' ')
352
left_end = right_start - 1;
353
else
354
left_end = right_start;
355
356
switch (surface_type)
357
{
358
case LEFT_SURFACE:
359
return new_string_readable (left_start, left_end);
360
case RIGHT_SURFACE:
361
return new_string_readable (right_start, right_end);
362
case RESULT_SURFACE:
363
return new_string_readable (left_start, right_end);
364
default:
365
error ("internal (unknown surface type)");
366
}
367
}
368
369
/* analysis functions =======================================================*/
370
371
LOCAL analysis_t *new_analysis (void)
372
/* Create a new analysis structure. */
373
{
374
analysis_t *analysis = new_mem (sizeof (analysis_t));
375
376
analysis->state_pool = new_pool (sizeof (state_t));
377
analysis->value_pool = new_pool (sizeof (cell_t));
378
analysis->running_states = NULL;
379
analysis->end_states = NULL;
380
analysis->free_states = NULL;
381
382
return analysis;
383
}
384
385
/*---------------------------------------------------------------------------*/
386
387
LOCAL void free_analysis (analysis_t **analysis)
388
/* Destroy an analysis structure. */
389
{
390
if (*analysis != NULL)
391
{
392
free_pool (&(*analysis)->state_pool);
393
free_pool (&(*analysis)->value_pool);
394
free_mem (analysis);
395
}
396
}
397
398
/*---------------------------------------------------------------------------*/
399
400
GLOBAL void init_analysis (string_t morphology_file, string_t syntax_file)
401
/* Initialise the analysis module.
402
* <morphology_file> and <syntax_file> are the rule files to load.
403
* <syntax_file> may be NULL. */
404
{
405
int_t i;
406
407
/* Read rule files. */
408
rule_system[MORPHOLOGY] = read_rule_sys (morphology_file);
409
if (syntax_file != NULL)
410
rule_system[SYNTAX] = read_rule_sys (syntax_file);
411
412
/* Init analysis structure. */
413
analyses[MORPHOLOGY] = new_analysis ();
414
analyses[SYNTAX] = new_analysis ();
415
tree_pool = new_pool (sizeof (tree_node_t));
416
417
/* Set analysis options to start values. */
418
for (i = 0; i < NUM_ANALYSIS_OPTIONS; i++)
419
options[i] = FALSE;
420
options[MOR_OUT_FILTER_OPTION] =
421
(rule_system[MORPHOLOGY]->output_filter != -1);
422
options[SYN_IN_FILTER_OPTION] =
423
(rule_system[SYNTAX] != NULL && rule_system[SYNTAX]->input_filter != -1);
424
options[SYN_OUT_FILTER_OPTION] =
425
(rule_system[SYNTAX] != NULL && rule_system[SYNTAX]->output_filter != -1);
426
}
427
428
/*---------------------------------------------------------------------------*/
429
430
GLOBAL void terminate_analysis (void)
431
/* Terminate the analysis module. */
432
{
433
free_rule_sys (&rule_system[SYNTAX]);
434
free_rule_sys (&rule_system[MORPHOLOGY]);
435
free_analysis (&analyses[MORPHOLOGY]);
436
free_analysis (&analyses[SYNTAX]);
437
free_pool (&tree_pool);
438
clear_cache ();
439
free_switches ();
440
}
441
442
/*---------------------------------------------------------------------------*/
443
444
GLOBAL bool_t reset_analysis_results (void)
445
/* Restart to read analysis results.
446
* Return TRUE iff there are any analysis results. */
447
{
448
next_result_state = analyses[top_grammar]->end_states;
449
return next_result_state != NULL;
450
}
451
452
/*---------------------------------------------------------------------------*/
453
454
GLOBAL value_t get_next_analysis_result (void)
455
/* Return the category of the next analysis result. */
456
{
457
if (next_result_state != NULL)
458
{
459
value_t result = next_result_state->cat;
460
461
next_result_state = next_result_state->next;
462
return result;
463
}
464
else
465
return NULL;
466
}
467
468
/*---------------------------------------------------------------------------*/
469
470
GLOBAL bool_t reset_analysis_nodes (void)
471
/* Restart to read analysis nodes.
472
* Return TRUE iff there are any analysis nodes. */
473
{
474
next_tree_node = root_tree_node;
475
return next_tree_node != NULL;
476
}
477
478
/*---------------------------------------------------------------------------*/
479
480
GLOBAL void free_analysis_node (analysis_node_t **node)
481
/* Free the memory occupied by <node>. */
482
{
483
if (*node != NULL)
484
{
485
free_mem (&(*node)->right_surf);
486
free_mem (&(*node)->result_surf);
487
free_mem (&(*node)->rule_set);
488
free_mem (node);
489
}
490
}
491
492
/*---------------------------------------------------------------------------*/
493
494
GLOBAL analysis_node_t *get_next_analysis_node (void)
495
/* Return the next analysis tree node of the last call of "analyse_item".
496
* Return NULL if there is no more node.
497
* The node must be freed with "free_analysis_node" after use. */
498
{
499
analysis_node_t *node;
500
string_t right_start;
501
rule_sys_t *rule_sys = rule_system[top_grammar];
502
503
if (next_tree_node == NULL)
504
return NULL;
505
506
node = new_mem (sizeof (analysis_node_t));
507
508
/* Set node index. */
509
node->index = next_tree_node->index;
510
511
/* Set node type. */
512
node->type = next_tree_node->type;
513
514
/* Set mother index. */
515
if (next_tree_node->mother == NULL)
516
node->mother_index = -1;
517
else
518
node->mother_index = next_tree_node->mother->index;
519
520
/* Set rule name. */
521
if (next_tree_node->rule != -1)
522
node->rule_name = (rule_sys->strings
523
+ rule_sys->rules[next_tree_node->rule].name);
524
else
525
node->rule_name = NULL;
526
527
/* Set right surface and category. */
528
if (next_tree_node->mother == NULL) /* no predecessor */
529
right_start = last_analysis_input;
530
else
531
right_start = next_non_space (next_tree_node->mother->input);
532
if (right_start != next_tree_node->input)
533
node->right_surf = new_string (right_start, next_tree_node->input);
534
node->right_cat = next_tree_node->right_cat;
535
536
/* Set result surface. */
537
node->result_surf = new_string (last_analysis_input, next_tree_node->input);
538
node->result_cat = next_tree_node->result_cat;
539
540
/* Set rule set. */
541
if (next_tree_node->result_cat != NULL)
542
node->rule_set = rule_set_readable (rule_sys, next_tree_node->rule_set);
543
544
/* Update <next_tree_node>. */
545
if (next_tree_node->first_daughter != NULL)
546
next_tree_node = next_tree_node->first_daughter;
547
else if (next_tree_node->sister != NULL)
548
next_tree_node = next_tree_node->sister;
549
else /* Go back to the next node not yet visited. */
550
{
551
while (TRUE)
552
{
553
next_tree_node = next_tree_node->mother;
554
if (next_tree_node == NULL)
555
break;
556
557
if (next_tree_node->sister != NULL)
558
{
559
next_tree_node = next_tree_node->sister;
560
break;
561
}
562
}
563
}
564
565
return node;
566
}
567
568
/*---------------------------------------------------------------------------*/
569
570
LOCAL string_t get_word_end (string_t input, bool_t analyse_all)
571
/* Return the end of the word that starts at <input>. */
572
{
573
string_t input_end;
574
575
if (analyse_all)
576
input_end = input + strlen (input);
577
else if (! is_word_part (input))
578
input_end = input + 1;
579
else
580
{
581
input_end = input + 1;
582
while (is_word_part (input_end))
583
input_end++;
584
}
585
586
return input_end;
587
}
588
589
/*---------------------------------------------------------------------------*/
590
591
LOCAL bool_t get_from_cache (analysis_t *analysis, string_t input,
592
bool_t analyse_all)
593
/* If next word at <input> is in analysis cache,
594
* enter its results in <analysis>, and return TRUE. Otherwise return FALSE. */
595
{
596
string_t input_end = get_word_end (input, analyse_all);
597
598
if (word_in_cache (input, input_end))
599
{
600
value_t result;
601
602
while (TRUE)
603
{
604
result = next_result_in_cache ();
605
if (result == NULL)
606
break;
607
608
insert_state (analysis, &analysis->end_states, result, input_end, -1, 0);
609
}
610
return TRUE;
611
}
612
else
613
return FALSE;
614
}
615
616
/*---------------------------------------------------------------------------*/
617
618
LOCAL void put_into_cache (analysis_t *analysis, string_t input,
619
bool_t analyse_all)
620
/* Store the results in <analysis> for the word form that starts at <input>
621
* in the cache. */
622
{
623
value_t *cats;
624
int_t num_cats, i;
625
state_t *state;
626
string_t input_end = get_word_end (input, analyse_all);
627
628
/* Count categories. */
629
num_cats = 0;
630
for (state = analysis->end_states; state != NULL; state = state->next)
631
{
632
if (state->input != input_end)
633
/* Only put into cache if all entries will be found in cache. */
634
return;
635
num_cats++;
636
}
637
638
/* Allocate a new vector which takes the categories. */
639
cats = new_vector (sizeof (value_t), num_cats);
640
for (i = 0, state = analysis->end_states;
641
state != NULL && state->input == input_end;
642
i++, state = state->next)
643
cats[i] = new_value (state->cat);
644
645
enter_in_cache (input, input_end, num_cats, cats);
646
}
647
648
/*---------------------------------------------------------------------------*/
649
650
LOCAL void execute_robust_rule (analysis_t *analysis,
651
rule_sys_t *rule_sys,
652
string_t input,
653
bool_t analyse_all)
654
/* Execute robust_rule in <rule_sys> for the next word in <analysis>.
655
* Word starts at <input>.
656
* Word must extend until end of string iff <analyse_all> == TRUE. */
657
{
658
string_t input_end;
659
660
input_end = get_word_end (input, analyse_all);
661
662
/* Set debugging information. */
663
left_start = input;
664
right_start = input;
665
right_end = input_end;
666
667
/* Setup <state_info>. */
668
state_info.analysis = analysis;
669
state_info.build_tree = FALSE;
670
state_info.analyse_all = analyse_all;
671
state_info.item_index = 1;
672
state_info.input = input_end;
673
674
top = 0;
675
push_string_value (input, input_end);
676
execute_rule (rule_sys, rule_sys->robust_rule);
677
if (analysis->end_states != NULL && analyse_all)
678
recognised_by_robust_rule = TRUE;
679
}
680
681
/*---------------------------------------------------------------------------*/
682
683
LOCAL void execute_filter_rule (analysis_t *analysis,
684
rule_sys_t *rule_sys,
685
int_t filter_rule,
686
bool_t analyse_all)
687
/* Execute <filter_rule> in <rule_sys> for <analysis>. */
688
{
689
state_t *old_end_states = analysis->end_states;
690
691
/* Go through all results with the same length. */
692
old_end_states = analysis->end_states;
693
analysis->end_states = NULL;
694
while (old_end_states != NULL)
695
{
696
int_t results, i;
697
state_t *state;
698
string_t input = old_end_states->input;
699
700
/* Count number of results. */
701
results = 0;
702
for (state = old_end_states;
703
state != NULL && state->input == input;
704
state = state->next)
705
results++;
706
707
/* Create a list with the results of all states and remove states. */
708
top = 0;
709
for (i = 0; i < results; i++)
710
{
711
push_value (old_end_states->cat);
712
remove_state (analysis, &old_end_states);
713
}
714
build_list (results);
715
716
/* Set debugging information. */
717
right_start = right_end = input;
718
719
state_info.analysis = analysis;
720
state_info.build_tree = FALSE;
721
state_info.analyse_all = analyse_all;
722
state_info.item_index = 0;
723
state_info.input = input;
724
execute_rule (rule_sys, filter_rule);
725
}
726
727
}
728
729
/*---------------------------------------------------------------------------*/
730
731
LOCAL void execute_pruning_rule (analysis_t *analysis, grammar_t grammar)
732
/* Execute pruning_rule in <grammar> for the running states in <analysis>. */
733
{
734
int_t results, i;
735
state_t *state;
736
state_t **state_ptr;
737
string_t input = analysis->running_states->input;
738
rule_sys_t *rule_sys = rule_system[grammar];
739
value_t list;
740
symbol_t symbol;
741
742
/* Create a list that contains the results. */
743
top = 0;
744
results = 0;
745
for (state = analysis->running_states;
746
state != NULL && state->input == input;
747
state = state->next)
748
{
749
results++;
750
push_value (state->cat);
751
}
752
build_list (results);
753
754
/* Set debugging information. */
755
right_start = right_end = input;
756
757
execute_rule (rule_sys, rule_sys->pruning_rule);
758
759
list = value_stack[top-1];
760
if (get_value_type (list) != LIST_SYMBOL)
761
error ("pruning rule result must be a list");
762
if (get_list_length (list) != results)
763
error ("pruning rule result must have as much elements as rule argument");
764
765
state_ptr = &analysis->running_states;
766
for (i = 0; i < results; i++)
767
{
768
symbol = value_to_symbol (get_element (list, i + 1));
769
if (symbol == NO_SYMBOL)
770
{
771
if ((*state_ptr)->tree_node != NULL)
772
(*state_ptr)->tree_node->type = PRUNED_NODE;
773
remove_state (analysis, state_ptr);
774
}
775
else if (symbol == YES_SYMBOL)
776
state_ptr = &(*state_ptr)->next;
777
else
778
error ("pruning rule result list may only contain yes/no symbols");
779
}
780
}
781
782
/*---------------------------------------------------------------------------*/
783
784
LOCAL void execute_rules (analysis_t *analysis,
785
rule_sys_t *rule_sys,
786
state_t *state,
787
value_t right_cat,
788
string_t right_surf_start,
789
string_t right_surf_end,
790
bool_t build_tree,
791
rule_type_t rule_type,
792
bool_t analyse_all)
793
/* Execute the successor rules in <rule_sys> for <state> in <analysis>.
794
* Consume the segment from <right_surf_start> to <right_surf_end>
795
* with category <right_cat>. Enter a tree node if <build_tree> == TRUE. */
796
{
797
int_t *rule_ptr;
798
bool_t rules_successful;
799
800
/* Setup <state_info>. */
801
state_info.analysis = analysis;
802
state_info.build_tree = build_tree;
803
state_info.analyse_all = analyse_all;
804
state_info.right_cat = right_cat;
805
state_info.mother = state->tree_node;
806
state_info.item_index = state->item_index + 1;
807
state_info.input = right_surf_end;
808
809
/* Set debugging information. */
810
right_start = right_surf_start;
811
right_end = right_surf_end;
812
813
/* Check if we are now executing the rules for a state to be debugged */
814
if (debug_state != NULL && state->tree_node != NULL)
815
debug_state (state->tree_node->index);
816
817
rules_successful = FALSE;
818
for (rule_ptr = rule_sys->rule_sets + state->rule_set;
819
*rule_ptr != -1;
820
rule_ptr++)
821
{
822
if (*rule_ptr == -2)
823
{
824
if (rule_type == END_RULE || rules_successful)
825
break;
826
}
827
else if (rule_sys->rules[*rule_ptr].type == rule_type)
828
{
829
state_info.rule = *rule_ptr;
830
top = 0;
831
push_value (state->cat);
832
push_value (right_cat);
833
push_string_value (right_surf_start, right_surf_end);
834
push_number_value (state_info.item_index);
835
execute_rule (rule_sys, *rule_ptr);
836
rules_successful |= rule_successful;
837
}
838
}
839
840
if (build_tree && rule_type != END_RULE)
841
{
842
/* Enter a tree node for a rule set that did not fire. */
843
state_info.rule = -1;
844
add_tree_node (NULL, right_surf_end, -1, BREAK_NODE);
845
}
846
}
847
848
/*---------------------------------------------------------------------------*/
849
850
GLOBAL void analyse (grammar_t grammar,
851
string_t input,
852
bool_t build_tree,
853
bool_t analyse_all)
854
/* Perform a LAG analysis of <input> using <grammar> (MORPHOLOGY or SYNTAX).
855
* An analysis tree will be built if <build_tree> == TRUE.
856
* The whole input will be analysed if <analyse_all> == TRUE. */
857
{
858
rule_sys_t *rule_sys;
859
state_t *initial_state;
860
analysis_t *analysis;
861
862
if (analyse_all)
863
{
864
top_grammar = grammar;
865
root_tree_node = NULL;
866
last_analysis_input = input;
867
recognised_by_robust_rule = recognised_by_combi_rules = FALSE;
868
}
869
870
analysis = analyses[grammar];
871
rule_sys = rule_system[grammar];
872
if (rule_sys == NULL)
873
error ("missing rule system");
874
875
/* Set callback functions for <execute_rules>. */
876
add_running_state = local_add_running_state;
877
add_end_state = local_add_end_state;
878
879
/* Reset the analysis, we start anew. */
880
analysis->running_states = NULL;
881
analysis->end_states = NULL;
882
analysis->free_states = NULL;
883
clear_pool (analysis->state_pool);
884
clear_pool (analysis->value_pool);
885
886
/* Set debug information. */
887
get_surface = local_get_surface;
888
left_start = input;
889
890
if (grammar == MORPHOLOGY && options[CACHE_OPTION] && ! build_tree)
891
{
892
if (get_from_cache (analysis, input, analyse_all))
893
return;
894
}
895
896
/* Enter the initial state. */
897
DB_ASSERT (rule_sys->initial_cat < rule_sys->values_size);
898
initial_state = insert_state (analysis, &analysis->running_states,
899
rule_sys->values
900
+ rule_sys->initial_cat,
901
input, rule_sys->initial_rule_set, 0);
902
903
if (build_tree)
904
{
905
/* Clear all tree nodes and setup <root_tree_node>. */
906
clear_pool (tree_pool);
907
root_tree_node = (tree_node_t *) get_pool_space (tree_pool, 1, NULL);
908
root_tree_node->mother = NULL;
909
root_tree_node->first_daughter = NULL;
910
root_tree_node->sister = NULL;
911
root_tree_node->type = INTER_NODE;
912
root_tree_node->rule = -1;
913
root_tree_node->index = 0;
914
root_tree_node->right_cat = NULL;
915
root_tree_node->result_cat = rule_sys->values + rule_sys->initial_cat;
916
root_tree_node->rule_set = rule_sys->initial_rule_set;
917
root_tree_node->input = input;
918
initial_state->tree_node = root_tree_node;
919
number_of_tree_nodes = 1;
920
}
921
922
/* Analyse while there are running states. */
923
while (analysis->running_states != NULL)
924
{
925
state_t *state;
926
string_t current_input = analysis->running_states->input;
927
928
if (options[PRUNING_OPTION] && current_input > input
929
&& rule_sys->pruning_rule != -1)
930
execute_pruning_rule (analysis, grammar);
931
932
/* Apply end_rules only if all input has been parsed
933
* or if in subordinate analysis. */
934
if (current_input > input
935
&& (*current_input == EOS
936
|| ! (analyse_all || (is_word_part (current_input-1)
937
&& is_word_part (current_input)))))
938
{
939
/* Apply all end_rules to states at <current_input>. */
940
for (state = analysis->running_states;
941
state != NULL && state->input == current_input;
942
state = state->next)
943
execute_rules (analysis, rule_sys, state, NULL, current_input,
944
current_input, build_tree, END_RULE, analyse_all);
945
}
946
947
/* If analysis has consumed all input, leave. */
948
if (*current_input == EOS)
949
break;
950
951
if (grammar == MORPHOLOGY)
952
{
953
string_t right_surf_end; /* end of surface of the next allomorph */
954
value_t cat;
955
956
/* Look for prefixes of increasing length
957
* that match the string at <current_input>. */
958
search_for_prefix (current_input);
959
while (get_next_prefix (&right_surf_end, &cat))
960
{
961
/* Apply this next-variable to all morphological states. */
962
for (state = analysis->running_states;
963
state != NULL && state->input == current_input;
964
state = state->next)
965
execute_rules (analysis, rule_sys, state, cat, current_input,
966
right_surf_end, build_tree, COMBI_RULE, analyse_all);
967
}
968
}
969
else /* <grammar> == SYNTAX */
970
{
971
state_t *morph_result;
972
string_t input_behind_space = next_non_space (current_input);
973
974
/* Call morphological analysis to get right-categories. */
975
analyse (MORPHOLOGY, input_behind_space, FALSE, FALSE);
976
977
/* Execution of morphology rules has changed <left_start>. */
978
left_start = input;
979
980
/* Step through all morphological results. */
981
for (morph_result = analyses[MORPHOLOGY]->end_states;
982
morph_result != NULL;
983
morph_result = morph_result->next)
984
{
985
/* The morphology pool may be cleared,
986
* so copy <cat> to the syntax pool. */
987
value_t right_cat = copy_value_to_pool (analysis->value_pool,
988
morph_result->cat, NULL);
989
990
/* Apply this right category to all syntactic states. */
991
for (state = analysis->running_states;
992
state != NULL && state->input == current_input;
993
state = state->next)
994
execute_rules (analysis, rule_sys, state, right_cat,
995
input_behind_space, morph_result->input,
996
build_tree, COMBI_RULE, TRUE);
997
}
998
}
999
1000
/* We have combined all analyses at <current_input> with all states
1001
* that were at <current_input>, so we can kill these states. */
1002
while (analysis->running_states != NULL
1003
&& analysis->running_states->input == current_input)
1004
remove_state (analysis, &analysis->running_states);
1005
} /* end of loop that consumes all running states */
1006
1007
if (analysis->end_states != NULL)
1008
recognised_by_combi_rules = TRUE;
1009
1010
if (grammar == MORPHOLOGY)
1011
{
1012
if (analysis->end_states == NULL && options[ROBUST_OPTION])
1013
execute_robust_rule (analysis, rule_sys, input, analyse_all);
1014
1015
if (options[MOR_OUT_FILTER_OPTION])
1016
execute_filter_rule (analysis, rule_system[MORPHOLOGY],
1017
rule_system[MORPHOLOGY]->output_filter,
1018
analyse_all);
1019
1020
if (options[SYN_IN_FILTER_OPTION])
1021
execute_filter_rule (analysis, rule_system[SYNTAX],
1022
rule_system[SYNTAX]->input_filter, analyse_all);
1023
1024
if (options[CACHE_OPTION] && ! build_tree)
1025
put_into_cache (analysis, input, analyse_all);
1026
}
1027
else /* grammar == SYNTAX */
1028
{
1029
if (options[SYN_OUT_FILTER_OPTION])
1030
execute_filter_rule (analysis, rule_system[SYNTAX],
1031
rule_system[SYNTAX]->output_filter, analyse_all);
1032
}
1033
}
1034
1035
/* end of file ==============================================================*/
Loggerhead is a web-based interface for Breezy
Version: 2.0.1