cde/programs/dthelp/parser/canon1/build/fsa.c

   1 /*
   2  * CDE - Common Desktop Environment
   3  *
   4  * Copyright (c) 1993-2012, The Open Group. All rights reserved.
   5  *
   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)
  10  * any later version.
  11  *
  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
  16  * details.
  17  *
  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
  22  */
  23 /* $XConsortium: fsa.c /main/3 1995/11/08 09:25:38 rswiston $ */
  24 /*
  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.
  28 */
  29
  30 /* Fsa.c contains the procedures used by program BUILD to convert a tree
  31    representation of a content model to an FSA */
  32
  33 #include <malloc.h>
  34 #include "build.h"
  35 #include "context.h"
  36 #include "delim.h"
  37
  38 /* Addarc adds an arc from FSA state <from> to state <to> setting other
  39    fields as indicated by the other parameters.*/
  40 #if defined(M_PROTO)
  41 int addarc(STATE *from, STATE *to, ELTSTRUCT *label, ANDGROUP *and, LOGICAL optional, int id, LOGICAL minim, ELTSTRUCT **errelt)
  42 #else
  43 int addarc(from, to, label, and, optional, id, minim, errelt)
  44   STATE *from, *to ;
  45   ELTSTRUCT *label ;
  46   ANDGROUP *and ;
  47   LOGICAL optional ;
  48   int id ;
  49   LOGICAL minim ;
  50   ELTSTRUCT **errelt ;
  51 #endif
  52   {
  53     ARC *parc, *qarc ;
  54     int determ ;
  55
  56     determ = checkdfsa(from, label, and, id, errelt) ;
  57     parc = from->first ;
  58     qarc = (ARC *) m_malloc(sizeof(ARC), "arc") ;
  59     from->first = qarc ;
  60     qarc->label = label ;
  61     qarc->optional = optional ;
  62     qarc->minim = minim ;
  63     qarc->group = and ;
  64     qarc->to = to ;
  65     qarc->next = parc ;
  66     qarc->id = id ;
  67     return(determ) ;
  68     }
  69
  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 ;
  74   STATE *start ;
  75   TREE *root ;
  76   ELTSTRUCT **errelt ;
  77   {
  78     ARC *parc ;
  79     ANDGROUP *pand ;
  80     int c ;
  81
  82     for (parc = start->first ; parc ; parc = parc->next) {
  83       if (parc->group) {
  84         if (parc->group != andstart)
  85           for (pand = parc->group ; pand ; pand = pand->next)
  86             checkand(andstart, andptr, pand->start, root, errelt) ;
  87         }
  88       else if (c = checkdfsa(andptr->start,
  89                              parc->label,
  90                              parc->group,
  91                              parc->id,
  92                              errelt))
  93         nondeterm(root, c, *errelt) ;
  94       }
  95     }
  96
  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)
 101   STATE *from ;
 102   ELTSTRUCT *label ;
 103   ANDGROUP *and ;
 104   int id ;
 105   ELTSTRUCT **errelt ;
 106   {
 107     int c ;
 108     ARC *parc ;
 109     ANDGROUP *group ;
 110
 111     for (parc = from->first ; parc ; parc = parc->next) {
 112       if (parc->group) {
 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))
 116             return(c) ;
 117         }
 118       else if (! and && label == parc->label && parc->id != id) {
 119         if (label) {
 120           *errelt = label ;
 121           return(ELTCONFLICT) ;
 122           }
 123         return(DATACONFLICT) ;
 124         }
 125       }
 126     return(FALSE) ;
 127     }
 128
 129 /* Check use of repeated models with and groups */
 130 int checkrepeat(from, and, errelt)
 131   STATE *from ;
 132   ANDGROUP *and ;
 133   ELTSTRUCT **errelt ;
 134   {
 135     ARC *parc ;
 136     int c ;
 137
 138     for (; and ; and = and->next)
 139       for (parc = and->start->first ; parc ; parc = parc->next) {
 140         if (parc->group)
 141           if (c = checkrepeat(from, parc->group, errelt)) return(c) ;
 142           else ;
 143         else
 144           if (c = checkdfsa(from,
 145                             parc->label,
 146                             M_NULLVAL,
 147                             parc->id,
 148                             errelt))
 149             return(c) ;
 150           else ;
 151         }
 152     return(FALSE) ;
 153     }
 154
 155 /* Copyintolist copies one list of states into another */
 156 void copyintolist(from, to)
 157   STATELIST *from, **to ;
 158   {
 159     STATELIST **new, *old ;
 160
 161     old = *to ;
 162     new = to ;
 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 ;
 169         }
 170       }
 171     *new = old ;
 172     }
 173
 174 /* Dellist deletes a list of states */
 175 void dellist(list)
 176   STATELIST **list ;
 177   {
 178     STATELIST *p, *q ;
 179
 180     for (p = *list ; p ; ) {
 181       q = p ;
 182       p = p->next ;
 183       m_free(q, "state list") ;
 184       }
 185     *list = NULL ;
 186     }
 187
 188 /* Delstartarcs deletes the contents of the starta list of arcs from start
 189    states of a submodel */
 190 void delstartarcs(M_NOPAR)
 191   {
 192     ARC *arcptr ;
 193     ARC *discard ;
 194
 195     for (arcptr = top->starta ; arcptr ; ) {
 196       discard = arcptr ;
 197       arcptr = arcptr->next ;
 198       m_free(discard, "arc") ;
 199       }
 200     top->starta = NULL ;
 201     }
 202
 203 /* Getand allocates and initializes a new andgroup structure */
 204 ANDGROUP *getand(M_NOPAR)
 205   {
 206     ANDGROUP *new ;
 207
 208     new = (ANDGROUP *) m_malloc(sizeof(ANDGROUP), "and group") ;
 209     new->nextptr = new->next = NULL ;
 210     new->count = ++andused ;
 211     *nextand = new ;
 212     nextand = &new->nextptr ;
 213     return(new) ;
 214     }
 215
 216 /* Getstate obtains an FSA state */
 217 STATE *getstate(M_NOPAR)
 218   {
 219     STATE *new ;
 220
 221     new = (STATE *) m_malloc(sizeof(STATE), "state") ;
 222     new->final = FALSE ;
 223     new->datacontent = FALSE ;
 224     new->frompcdata = FALSE ;
 225     new->first = NULL ;
 226     new->count = ++stateused ;
 227     new->next = NULL ;
 228     *nextstate = new ;
 229     nextstate = &new->next ;
 230     return(new) ;
 231     }
 232
 233 /* Makeand processes a submodel whose connector is & */
 234 void makeand(canbenull, root, optional)
 235   LOGICAL *canbenull ;
 236   TREE *root ;
 237   int optional ;
 238   {
 239     TREE *child ;
 240     STATELIST *start, *final ;
 241     LOGICAL groupbenull ;
 242     ANDGROUP *andptr, *saveand, *otherand ;
 243     STATELIST *index ;
 244     ELTSTRUCT *errelt ;
 245
 246     for (child = root->first ; child ; child = child->right) {
 247       if (child == root->first) {
 248         *canbenull = TRUE ;
 249         andptr = getand() ;
 250         saveand = andptr ;
 251         push() ;
 252         copyintolist(top->oldtop->allfinal, &top->allfinal) ;
 253         }
 254       else {
 255         andptr->next = getand() ;
 256         andptr = andptr->next ;
 257         }
 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
 265          completed) */
 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) ;
 283       }
 284     pop() ;
 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 ;
 290     }
 291
 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".
 300
 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.
 321    */
 322 LOGICAL makefsa(root, optional)
 323   TREE *root ;
 324   int optional ;
 325   {
 326     LOGICAL canbenull ;
 327
 328     canbenull = FALSE ;
 329     if (root->occurrence == OPT || root->occurrence == REP)
 330       optional = stacklevels + 1 ;
 331     /* The branch consists of a single element name */
 332     if (root->terminal)
 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) ;
 345
 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) {
 350       repeat(root) ;
 351       copyintolist(top->starts, &top->finals) ;
 352       }
 353     else if (root->occurrence == PLUS) repeat(root) ;
 354     return(canbenull) ;
 355     }
 356
 357 /* Makeor processes a submodel whose connector is | */
 358 void makeor(canbenull, root)
 359   LOGICAL *canbenull ;
 360   TREE *root ;
 361   {
 362     TREE *child ;
 363     STATELIST *final ;
 364
 365     push() ;
 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 ;
 370       savestartarcs() ;
 371       delstartarcs() ;
 372       copyintolist(top->finals, &top->oldtop->finals ) ;
 373       dellist(&top->finals) ;
 374       }
 375     copyintolist(top->newfinal, &top->oldtop->newfinal) ;
 376     pop() ;
 377     for (final = top->finals ; final ; final = final->next)
 378       final->level = stacklevels ;
 379     }
 380
 381 /* Makeseq processes a submodel whose connector is , */
 382 void makeseq(canbenull, root, optional)
 383   LOGICAL *canbenull ;
 384   TREE *root ;
 385   int optional ;
 386   {
 387     LOGICAL branchnull ;
 388     STATELIST *keepfinal = NULL, *final ;
 389     TREE *child ;
 390
 391     push() ;
 392     *canbenull = TRUE ;
 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() ;
 398       if (! branchnull) {
 399         *canbenull = FALSE ;
 400         dellist(&top->allfinal) ;
 401         dellist(&keepfinal) ;
 402         }
 403       copyintolist(top->newfinal, &top->allfinal) ;
 404       copyintolist(top->newfinal, &keepfinal) ;
 405       dellist(&top->newfinal) ;
 406       delstartarcs() ;
 407       dellist(&top->starts) ;
 408       copyintolist(top->finals, &top->starts) ;
 409       dellist(&top->finals) ;
 410       if (! child->occurrence || child->occurrence == PLUS)
 411         optional = FALSE ;
 412       }
 413     copyintolist(top->starts, &top->oldtop->finals) ;
 414     copyintolist(keepfinal, &top->oldtop->newfinal) ;
 415     dellist(&keepfinal) ;
 416     pop() ;
 417     for (final = top->finals ; final ; final = final->next)
 418       final->level = stacklevels ;
 419     }
 420
 421 /* Nondeterm issues a diagnostic when a nondeterministic model is
 422    encountered */
 423 void nondeterm(root, c, eltp)
 424   TREE *root ;
 425   int c ;
 426   ELTSTRUCT *eltp ;
 427   {
 428   M_WCHAR *wtemp;
 429
 430     switch (c) {
 431       case ANDCONFLICT:
 432         wtemp = MakeWideCharString(and);
 433         warning2("Error in model for %s: Conflict in use of '%s'",
 434                  thisrule,
 435                  wtemp) ;
 436         m_free(wtemp, "wide character string");
 437         break ;
 438       case DATACONFLICT:
 439         wtemp = MakeWideCharString(rnicdata);
 440         warning2("Error in model for %s: Conflict in use of '%s'",
 441                  thisrule,
 442                  wtemp) ;
 443         m_free(wtemp, "wide character string");
 444         break ;
 445       case ELTCONFLICT:
 446         warning2("Error in model for %s: Conflict in use of '%s'",
 447                  thisrule,
 448                  eltp->enptr) ;
 449         break ;
 450       }
 451     regenerate(ruletree, root) ;
 452     msgline(" . . .\n") ;
 453     }
 454
 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 ;
 459   {
 460     for ( ; list ; list = list->next)
 461       if (list->value == item->value) {
 462         if (item->level < list->level) list->level = item->level ;
 463         return(FALSE) ;
 464         }
 465     return(TRUE) ;
 466     }
 467
 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)
 471   ARC *a ;
 472   {
 473     ANDGROUP *pand ;
 474     ARC *b ;
 475
 476     if (a->group) {
 477       for (pand = a->group ; pand ; pand = pand->next)
 478         for (b = pand->start->first ;
 479              b ;
 480              b = b->next)
 481           if (permitspcd(b)) return(TRUE) ;
 482       return(FALSE) ;
 483       }
 484     /* Not an and-group */
 485     if (a->label) return(FALSE) ;
 486     return(TRUE) ;
 487     }
 488
 489 /* Pop pops the submodel stack when the end of the current submodel is
 490    encountered */
 491 void pop(M_NOPAR)
 492   {
 493     STACK *discard ;
 494
 495     dellist(&top->starts) ;
 496     dellist(&top->finals) ;
 497     dellist(&top->allfinal) ;
 498     dellist(&top->newfinal) ;
 499     delstartarcs() ;
 500     stacklevels-- ;
 501     discard = top ;
 502     top = top->oldtop ;
 503     m_free((M_POINTER) discard, "stack entry") ;
 504     }
 505
 506 /* Push pushes the submodel stack when a new group is encountered */
 507 void push(M_NOPAR)
 508   {
 509     STACK *new ;
 510
 511     new = (STACK *) m_malloc(sizeof(STACK), "stack entry") ;
 512     new->oldtop = top ;
 513     top = new ;
 514     stacklevels++ ;
 515     top->starts = top->finals = top->newfinal = top->allfinal = NULL ;
 516     top->starta = M_NULLVAL ;
 517     }
 518
 519 /* Regenerate is used in error processing to print the portion of a grammar
 520    rule preceding an error */
 521 LOGICAL regenerate(start, stop)
 522 TREE *start, *stop ;
 523 {
 524 TREE *child ;
 525
 526 if (start == stop) return(TRUE) ;
 527
 528 if (start->terminal)
 529     {
 530     char *mb_enptr;
 531
 532     if (start->value)
 533         mb_enptr = MakeMByteString(start->value->enptr);
 534     else
 535         mb_enptr = NULL;
 536     msg1line("%s", mb_enptr ? mb_enptr : rnicdata) ;
 537     if (mb_enptr)
 538         m_free(mb_enptr,"multi-byte string");
 539     }
 540 else
 541     {
 542     msgline("(") ;
 543     for (child = start->first ; child ; child = child->right)
 544         {
 545         if (regenerate(child, stop)) return(TRUE) ;
 546         if (child->right)
 547             {
 548             if (start->connector == SEQ) msg1line("%s", seq) ;
 549             if (start->connector == OR) msg1line("%s", or) ;
 550             if (start->connector == AND) msg1line("%s", and) ;
 551             }
 552         }
 553     msgline(")") ;
 554     }
 555
 556 if (start->occurrence == OPT) msg1line("%s", opt) ;
 557 if (start->occurrence == PLUS) msg1line("%s", plus) ;
 558 if (start->occurrence == REP) msg1line("%s", rep) ;
 559
 560 return(FALSE) ;
 561 }
 562
 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. */
 568 void repeat(root)
 569   TREE *root ;
 570   {
 571     STATELIST *final ;
 572     ARC *a ;
 573     int c ;
 574     ELTSTRUCT *errelt ;
 575     M_WCHAR *wtemp;
 576
 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) {
 581         if (a->group)
 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) ;
 587             }
 588           else
 589             ;
 590         else
 591           if (c = checkdfsa(final->value,
 592                             a->label,
 593                             a->group,
 594                             a->id,
 595                             &errelt))
 596             nondeterm (root, c, errelt) ;
 597           else
 598             ;
 599         }
 600       for (final = top->finals ; final ; final = final->next) {
 601         if (samelabelarc(a, final->value)) continue ;
 602         if (a->group)
 603           if (c = checkrepeat(final->value, a->group, &errelt))
 604             nondeterm(root, c, errelt) ;
 605         if (a->label ||
 606             a->group ||
 607             ! final->value->frompcdata) {
 608           if (c = addarc(final->value, a->to, a->label,
 609                          a->group, TRUE, a->id,
 610                          a->minim, &errelt))
 611             nondeterm(root, c, errelt) ;
 612           if (permitspcd(a)) final->value->datacontent = TRUE ;
 613           }
 614         }
 615       }
 616     }
 617
 618 /* Used during processing of occurrence indicators in content models such
 619    as (a+)+ to prohibit duplicate arcs */
 620 LOGICAL samelabelarc(a, s)
 621   ARC *a ;
 622   STATE *s ;
 623   {
 624     ARC *b ;
 625
 626     for (b = s->first ; b ; b = b->next)
 627       if (b->id == a->id) return(TRUE) ;
 628     return(FALSE) ;
 629     }
 630
 631 /* Saves the name of an element appearing on the left-hand side of a
 632    grammar rule */
 633 #if defined(M_PROTO)
 634 void savelhs(LOGICAL param)
 635 #else
 636 void savelhs(param)
 637   LOGICAL param ;
 638 #endif
 639   {
 640     STATE *end ;
 641     ELTSTRUCT *errelt ;
 642     ELTSTRUCT *thiselt ;
 643
 644     *nextlhs = (LHS *) m_malloc(sizeof(LHS), "lhs") ;
 645     (*nextlhs)->next = NULL ;
 646     thiselt = ntrelt(name) ;
 647     (*nextlhs)->elt = thiselt ;
 648     nextlhs = &(*nextlhs)->next ;
 649     if (! startstate) {
 650       startstate = getstate() ;
 651       end = getstate() ;
 652       addarc(startstate, end, thiselt, M_NULLVAL, FALSE, 1, FALSE, &errelt) ;
 653       end->final = TRUE ;
 654       }
 655     if (param && thiselt->parptr) {
 656       m_err1("Parameters for %s already defined", thiselt->enptr) ;
 657       return ;
 658       }
 659     if (! param && thiselt->model)
 660       warning1("Duplicate model for element %s", thiselt->enptr) ;
 661     }
 662
 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
 665    starta list */
 666 void savestartarcs(M_NOPAR)
 667   {
 668     ARC *carcptr, *parcptr ;
 669
 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 ;
 680       }
 681     }
 682
 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)
 686   TREE *root ;
 687   ELTSTRUCT *value ;
 688   ANDGROUP *group ;
 689   int optional ;
 690   {
 691     STATE *new = NULL ;
 692     STATELIST *index ;
 693     int c ;
 694     ELTSTRUCT *errelt ;
 695
 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
 698        arc */
 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)
 704         continue ;
 705       if (! new) {
 706         new = getstate() ;
 707         new->frompcdata = (LOGICAL) (! group && ! value) ;
 708         }
 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 ;
 714       }
 715     if (new) {
 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 ;
 728       }
 729     else copyintolist(top->starts, &top->finals) ;
 730     }
 731
 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)
 738   TREE *root ;
 739   LOGICAL *canbenull ;
 740   {
 741     STATELIST *item ;
 742     STATE *first ;
 743
 744     top->starts = (STATELIST *) m_malloc(sizeof(STATELIST), "state list") ;
 745     first = getstate() ;
 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) ;
 753     delstartarcs() ;
 754     return(first) ;
 755     }
 756