2 * CDE - Common Desktop Environment
4 * Copyright (c) 1993-2012, The Open Group. All rights reserved.
6 * These libraries and programs are free software; you can
7 * redistribute them and/or modify them under the terms of the GNU
8 * Lesser General Public License as published by the Free Software
9 * Foundation; either version 2 of the License, or (at your option)
12 * These libraries and programs are distributed in the hope that
13 * they will be useful, but WITHOUT ANY WARRANTY; without even the
14 * implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
15 * PURPOSE. See the GNU Lesser General Public License for more
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with these librararies and programs; if not, write
20 * to the Free Software Foundation, Inc., 51 Franklin Street, Fifth
21 * Floor, Boston, MA 02110-1301 USA
23 /* $XConsortium: fsa.c /main/3 1995/11/08 10:42:48 rswiston $ */
25 Copyright 1986 Tandem Computers Incorporated.
26 This product and information is proprietary of Tandem Computers Incorporated.
27 Copyright (c) 1986, 1987, 1988, 1989 Hewlett-Packard Co.
30 /* Fsa.c contains the procedures used by program BUILD to convert a tree
31 representation of a content model to an FSA */
38 /* Addarc adds an arc from FSA state <from> to state <to> setting other
39 fields as indicated by the other parameters.*/
41 int addarc(STATE *from, STATE *to, ELTSTRUCT *label, ANDGROUP *and, LOGICAL optional, int id, LOGICAL minim, ELTSTRUCT **errelt)
43 int addarc(from, to, label, and, optional, id, minim, errelt)
56 determ = checkdfsa(from, label, and, id, errelt) ;
58 qarc = (ARC *) m_malloc(sizeof(ARC), "arc") ;
61 qarc->optional = optional ;
70 /*checkand is used to verify nondeterminism from start and final states
71 of FSA's generated from and groups*/
72 void checkand(andstart, andptr, start, root, errelt)
73 ANDGROUP *andstart, *andptr ;
82 for (parc = start->first ; parc ; parc = parc->next) {
84 if (parc->group != andstart)
85 for (pand = parc->group ; pand ; pand = pand->next)
86 checkand(andstart, andptr, pand->start, root, errelt) ;
88 else if (c = checkdfsa(andptr->start,
93 nondeterm(root, c, *errelt) ;
97 /*Checkdfsa is called when adding an arc to an FSA in order to verify that
98 no existing arc from the same state (or from a start state of an and-group
99 FSA labelling an arc from the same state) has the same label. */
100 int checkdfsa(from, label, and, id, errelt)
111 for (parc = from->first ; parc ; parc = parc->next) {
113 if (and == parc->group) return(ANDCONFLICT) ;
114 for (group = parc->group ; group ; group = group->next)
115 if (c = checkdfsa(group->start, label, and, id, errelt))
118 else if (! and && label == parc->label && parc->id != id) {
121 return(ELTCONFLICT) ;
123 return(DATACONFLICT) ;
129 /* Check use of repeated models with and groups */
130 int checkrepeat(from, and, errelt)
138 for (; and ; and = and->next)
139 for (parc = and->start->first ; parc ; parc = parc->next) {
141 if (c = checkrepeat(from, parc->group, errelt)) return(c) ;
144 if (c = checkdfsa(from,
155 /* Copyintolist copies one list of states into another */
156 void copyintolist(from, to)
157 STATELIST *from, **to ;
159 STATELIST **new, *old ;
163 for ( ; from ; from = from->next) {
164 if (notinlist(from, old)) {
165 *new = (STATELIST *) m_malloc(sizeof(STATELIST), "state list") ;
166 (*new)->value = from->value ;
167 (*new)->level = from->level ;
168 new = &(*new)->next ;
174 /* Dellist deletes a list of states */
180 for (p = *list ; p ; ) {
183 m_free(q, "state list") ;
188 /* Delstartarcs deletes the contents of the starta list of arcs from start
189 states of a submodel */
190 void delstartarcs(M_NOPAR)
195 for (arcptr = top->starta ; arcptr ; ) {
197 arcptr = arcptr->next ;
198 m_free(discard, "arc") ;
203 /* Getand allocates and initializes a new andgroup structure */
204 ANDGROUP *getand(M_NOPAR)
208 new = (ANDGROUP *) m_malloc(sizeof(ANDGROUP), "and group") ;
209 new->nextptr = new->next = NULL ;
210 new->count = ++andused ;
212 nextand = &new->nextptr ;
216 /* Getstate obtains an FSA state */
217 STATE *getstate(M_NOPAR)
221 new = (STATE *) m_malloc(sizeof(STATE), "state") ;
223 new->datacontent = FALSE ;
224 new->frompcdata = FALSE ;
226 new->count = ++stateused ;
229 nextstate = &new->next ;
233 /* Makeand processes a submodel whose connector is & */
234 void makeand(canbenull, root, optional)
240 STATELIST *start, *final ;
241 LOGICAL groupbenull ;
242 ANDGROUP *andptr, *saveand, *otherand ;
246 for (child = root->first ; child ; child = child->right) {
247 if (child == root->first) {
252 copyintolist(top->oldtop->allfinal, &top->allfinal) ;
255 andptr->next = getand() ;
256 andptr = andptr->next ;
258 andptr->start = startfsa(child, &groupbenull) ;
259 if (andptr->start->datacontent)
260 for (index = top->oldtop->starts ; index ; index = index->next)
261 index->value->datacontent = TRUE ;
262 if (! groupbenull) *canbenull = FALSE ;
263 /* Check for ambiguity between start state of branch just completed
264 and start state of the and-group (i.e., parent of branch just
266 for (start = top->oldtop->starts ; start ; start = start->next)
267 checkand(saveand, andptr, start->value, root, &errelt) ;
268 /* Check for ambiguity between start state of branch just completed
269 and final states of previous branches */
270 for (final = top->allfinal ; final ; final = final->next)
271 checkand(saveand, andptr, final->value, root, &errelt) ;
272 copyintolist(top->finals, &top->allfinal) ;
273 copyintolist(top->newfinal, &top->allfinal) ;
274 copyintolist(top->finals, &top->oldtop->newfinal) ;
275 copyintolist(top->newfinal, &top->oldtop->newfinal) ;
276 dellist(&top->finals) ;
277 dellist(&top->newfinal) ;
278 /* Check for ambiguity between start states of branch just completed
279 and start states of previous branches */
280 for (otherand = saveand ; otherand != andptr ;
281 otherand = otherand->next)
282 checkand(saveand, andptr, otherand->start, root, &errelt) ;
285 if (*canbenull) optional = stacklevels + 1 ;
286 simplebranch(root, M_NULLVAL, saveand, optional) ;
287 if (*canbenull) copyintolist(top->starts, &top->finals) ;
288 for (final = top->finals ; final ; final = final->next)
289 final->level = stacklevels ;
292 /* Makefsa builds the portion of an FSA that corresponds to an entire
293 submodel (i.e., a subtree of the tree representation of the rule).
294 The value returned indicates whether the submodel can be null (i.e.,
295 whether all its elements are optional). The parameters are a pointer
296 to the root of the subtree and an integer indicating the level of
297 nesting (if any) of submodels at which the subtree became optional.
298 Note that as used here, "optional" means "not contextually required" in
299 the terminology of the Standard rather than "contextually optional".
301 Makefsa is a recursive procedure. As the FSA is built, a stack is
302 maintained of the nested content models that have been encountered
303 but not yet terminated. For each open model on the stack, starts is
304 a list of its start states (i.e., FSA states from which transitions
305 correspond to elements which can occur at the beginning of the rule
306 being processed), finals is a list of its final states, starta is a
307 list of arcs emanating from the start states of the model, and
308 allfinal and newfinal are lists of final states used in checking for
309 determinism when and-groups are used. In more detail, allfinal is a
310 list of final states of FSA's in and-groups that may occur just prior
311 to the current context; i.e., 1) when starting a new FSA in an and-group,
312 the set of final states of already-constructed FSA's in the same group
313 (or final states of FSA's in submodel and-groups that end such FSA's)
314 or 2) the set of final states of FSA's in an and-group that precedes
315 the current context (e.g., the final states of the and-group FSA's
316 when processing 'x' in ((a&b),x)). At each stage in the parse (or level
317 on the stack), newfinal is the set of states to be added to those in
318 allfinal as a result of processing at that level. Information in
319 allfinal is passed from model to submodel; information in newfinal
320 goes from submodel to model.
322 LOGICAL makefsa(root, optional)
329 if (root->occurrence == OPT || root->occurrence == REP)
330 optional = stacklevels + 1 ;
331 /* The branch consists of a single element name */
333 simplebranch(root, root->value, M_NULLVAL, optional) ;
334 /* The submodel's connector is SEQ (,) */
335 else if (root->connector == SEQ)
336 makeseq(&canbenull, root, optional) ;
337 /* The submodel's connector is OR (|) */
338 else if (root->connector == OR)
339 makeor(&canbenull, root) ;
340 /* The submodel's connector is AND (&) */
341 else if (root->connector == AND)
342 makeand(&canbenull, root, optional) ;
343 /* The submodel is a single item in parentheses */
344 else canbenull = makefsa(root->first, optional) ;
346 /* The FSA is built, now repeat if occurrence indicator so indicates */
347 if (root->occurrence == OPT || root->occurrence == REP) canbenull = TRUE ;
348 if (root->occurrence == OPT) copyintolist(top->starts, &top->finals) ;
349 else if (root->occurrence == REP) {
351 copyintolist(top->starts, &top->finals) ;
353 else if (root->occurrence == PLUS) repeat(root) ;
357 /* Makeor processes a submodel whose connector is | */
358 void makeor(canbenull, root)
366 copyintolist(top->oldtop->starts, &top->starts) ;
367 copyintolist(top->oldtop->allfinal, &top->allfinal) ;
368 for (child = root->first ; child ; child = child->right) {
369 if (makefsa(child, stacklevels)) *canbenull = TRUE ;
372 copyintolist(top->finals, &top->oldtop->finals ) ;
373 dellist(&top->finals) ;
375 copyintolist(top->newfinal, &top->oldtop->newfinal) ;
377 for (final = top->finals ; final ; final = final->next)
378 final->level = stacklevels ;
381 /* Makeseq processes a submodel whose connector is , */
382 void makeseq(canbenull, root, optional)
388 STATELIST *keepfinal = NULL, *final ;
393 copyintolist(top->oldtop->starts, &top->starts) ;
394 copyintolist(top->oldtop->allfinal, &top->allfinal) ;
395 for (child = root->first ; child ; child = child->right) {
396 branchnull = makefsa(child, optional) ;
397 if (*canbenull) savestartarcs() ;
400 dellist(&top->allfinal) ;
401 dellist(&keepfinal) ;
403 copyintolist(top->newfinal, &top->allfinal) ;
404 copyintolist(top->newfinal, &keepfinal) ;
405 dellist(&top->newfinal) ;
407 dellist(&top->starts) ;
408 copyintolist(top->finals, &top->starts) ;
409 dellist(&top->finals) ;
410 if (! child->occurrence || child->occurrence == PLUS)
413 copyintolist(top->starts, &top->oldtop->finals) ;
414 copyintolist(keepfinal, &top->oldtop->newfinal) ;
415 dellist(&keepfinal) ;
417 for (final = top->finals ; final ; final = final->next)
418 final->level = stacklevels ;
421 /* Nondeterm issues a diagnostic when a nondeterministic model is
423 void nondeterm(root, c, eltp)
432 wtemp = MakeWideCharString(and);
433 warning2("Error in model for %s: Conflict in use of '%s'",
436 m_free(wtemp, "wide character string");
439 wtemp = MakeWideCharString(rnicdata);
440 warning2("Error in model for %s: Conflict in use of '%s'",
443 m_free(wtemp, "wide character string");
446 warning2("Error in model for %s: Conflict in use of '%s'",
451 regenerate(ruletree, root) ;
452 msgline(" . . .\n") ;
455 /* Notinlist returns TRUE iff item is not in list. If item is in list,
456 it makes sure that the stored nesting level is the smaller of the two */
457 LOGICAL notinlist(item, list)
458 STATELIST *item, *list ;
460 for ( ; list ; list = list->next)
461 if (list->value == item->value) {
462 if (item->level < list->level) list->level = item->level ;
468 /* Returns true if the arc is labeled #PCDATA or with an and-group that
469 has an arc labelled #PCDATA from a start state */
470 LOGICAL permitspcd(a)
477 for (pand = a->group ; pand ; pand = pand->next)
478 for (b = pand->start->first ;
481 if (permitspcd(b)) return(TRUE) ;
484 /* Not an and-group */
485 if (a->label) return(FALSE) ;
489 /* Pop pops the submodel stack when the end of the current submodel is
495 dellist(&top->starts) ;
496 dellist(&top->finals) ;
497 dellist(&top->allfinal) ;
498 dellist(&top->newfinal) ;
503 m_free((M_POINTER) discard, "stack entry") ;
506 /* Push pushes the submodel stack when a new group is encountered */
511 new = (STACK *) m_malloc(sizeof(STACK), "stack entry") ;
515 top->starts = top->finals = top->newfinal = top->allfinal = NULL ;
516 top->starta = M_NULLVAL ;
519 /* Regenerate is used in error processing to print the portion of a grammar
520 rule preceding an error */
521 LOGICAL regenerate(start, stop)
526 if (start == stop) return(TRUE) ;
533 mb_enptr = MakeMByteString(start->value->enptr);
536 msg1line("%s", mb_enptr ? mb_enptr : rnicdata) ;
538 m_free(mb_enptr,"multi-byte string");
543 for (child = start->first ; child ; child = child->right)
545 if (regenerate(child, stop)) return(TRUE) ;
548 if (start->connector == SEQ) msg1line("%s", seq) ;
549 if (start->connector == OR) msg1line("%s", or) ;
550 if (start->connector == AND) msg1line("%s", and) ;
556 if (start->occurrence == OPT) msg1line("%s", opt) ;
557 if (start->occurrence == PLUS) msg1line("%s", plus) ;
558 if (start->occurrence == REP) msg1line("%s", rep) ;
563 /* Repeat is called after a partial FSA is built for a submodel whose
564 occurrence indicator is RPT (*) or PLUS (+). It handles repetition
565 by adding arcs from all the final states to all the states reachable
566 in one transition from a start state, labelling them as arcs from
567 start states are labelled. */
577 copyintolist(top->newfinal, &top->allfinal) ;
578 dellist(&top->newfinal) ;
579 for (a = top->starta ; a ; a = a->next) {
580 for (final = top->allfinal ; final ; final = final->next) {
582 if (c = checkrepeat(final->value, a->group, &errelt)) {
583 wtemp = MakeWideCharString(root->occurrence == PLUS ? plus : rep);
584 warning1("Conflict in use of %s", wtemp);
585 m_free(wtemp, "wide character string");
586 nondeterm(root, c, errelt) ;
591 if (c = checkdfsa(final->value,
596 nondeterm (root, c, errelt) ;
600 for (final = top->finals ; final ; final = final->next) {
601 if (samelabelarc(a, final->value)) continue ;
603 if (c = checkrepeat(final->value, a->group, &errelt))
604 nondeterm(root, c, errelt) ;
607 ! final->value->frompcdata) {
608 if (c = addarc(final->value, a->to, a->label,
609 a->group, TRUE, a->id,
611 nondeterm(root, c, errelt) ;
612 if (permitspcd(a)) final->value->datacontent = TRUE ;
618 /* Used during processing of occurrence indicators in content models such
619 as (a+)+ to prohibit duplicate arcs */
620 LOGICAL samelabelarc(a, s)
626 for (b = s->first ; b ; b = b->next)
627 if (b->id == a->id) return(TRUE) ;
631 /* Saves the name of an element appearing on the left-hand side of a
634 void savelhs(LOGICAL param)
644 *nextlhs = (LHS *) m_malloc(sizeof(LHS), "lhs") ;
645 (*nextlhs)->next = NULL ;
646 thiselt = ntrelt(name) ;
647 (*nextlhs)->elt = thiselt ;
648 nextlhs = &(*nextlhs)->next ;
650 startstate = getstate() ;
652 addarc(startstate, end, thiselt, M_NULLVAL, FALSE, 1, FALSE, &errelt) ;
655 if (param && thiselt->parptr) {
656 m_err1("Parameters for %s already defined", thiselt->enptr) ;
659 if (! param && thiselt->model)
660 warning1("Duplicate model for element %s", thiselt->enptr) ;
663 /* Called when arcs are added to the start state of a submodel that is
664 also a start state of the parent model to set the parent model's
666 void savestartarcs(M_NOPAR)
668 ARC *carcptr, *parcptr ;
670 for (carcptr = top->starta ; carcptr ; carcptr = carcptr->next) {
671 parcptr = (ARC *) m_malloc(sizeof(ARC), "arc") ;
672 parcptr->label = carcptr->label ;
673 parcptr->optional = carcptr->optional ;
674 parcptr->minim = carcptr->minim ;
675 parcptr->group = carcptr->group ;
676 parcptr->to = carcptr->to ;
677 parcptr->next = top->oldtop->starta ;
678 parcptr->id = carcptr->id ;
679 top->oldtop->starta = parcptr ;
683 /* Simplebranch adds a new state and transition to it in an FSA when a
684 submodel consists of a single element or of an and group */
685 void simplebranch(root, value, group, optional)
696 /* Check for ambiguity between an arc to be added and arcs from final
697 states of and-groups that terminate at the start state of the new
699 for (index = top->allfinal ; index ; index = index->next)
700 if (c = checkdfsa(index->value, value, group, root->eltid, &errelt))
701 nondeterm(root, c, errelt) ;
702 for (index = top->starts ; index ; index = index->next) {
703 if (! group && ! value && index->value->frompcdata)
707 new->frompcdata = (LOGICAL) (! group && ! value) ;
709 c = addarc(index->value, new, value, group,
710 (LOGICAL) (optional > index->level),
711 root->eltid, root->minim, &errelt) ;
712 if (c) nondeterm(root, c, errelt) ;
713 if (! group && ! value) index->value->datacontent = TRUE ;
716 top->finals = (STATELIST *) m_malloc(sizeof(STATELIST), "state list") ;
717 top->finals->value = new ;
718 top->finals->level = stacklevels ;
719 top->finals->next = NULL ;
720 top->starta = (ARC *) m_malloc(sizeof(ARC), "arc") ;
721 top->starta->label = value ;
722 top->starta->optional = FALSE ;
723 top->starta->minim = root->minim ;
724 top->starta->group = group ;
725 top->starta->to = new ;
726 top->starta->next = NULL ;
727 top->starta->id = root->eltid ;
729 else copyintolist(top->starts, &top->finals) ;
732 /* Startfsa creates a new FSA. It is called once for each content model and
733 once for each and group. Its parameters are the root of the
734 subtree in the tree representing the grammar rule being processed and
735 the pointer to a flag that is set to indicate whether or not the
736 submodel can be null. */
737 STATE *startfsa(root, canbenull)
744 top->starts = (STATELIST *) m_malloc(sizeof(STATELIST), "state list") ;
746 top->starts->value = first ;
747 top->starts->level = stacklevels ;
748 top->starts->next = NULL ;
749 *canbenull = makefsa(root, FALSE) ;
750 for (item = top->finals ; item ; item = item->next)
751 item->value->final = TRUE ;
752 dellist(&top->starts) ;