1228072Sbapt/* dfa - DFA construction routines */ 2228072Sbapt 3228072Sbapt/* Copyright (c) 1990 The Regents of the University of California. */ 4228072Sbapt/* All rights reserved. */ 5228072Sbapt 6228072Sbapt/* This code is derived from software contributed to Berkeley by */ 7228072Sbapt/* Vern Paxson. */ 8228072Sbapt 9228072Sbapt/* The United States Government has rights in this work pursuant */ 10228072Sbapt/* to contract no. DE-AC03-76SF00098 between the United States */ 11228072Sbapt/* Department of Energy and the University of California. */ 12228072Sbapt 13228072Sbapt/* Redistribution and use in source and binary forms, with or without */ 14228072Sbapt/* modification, are permitted provided that the following conditions */ 15228072Sbapt/* are met: */ 16228072Sbapt 17228072Sbapt/* 1. Redistributions of source code must retain the above copyright */ 18228072Sbapt/* notice, this list of conditions and the following disclaimer. */ 19228072Sbapt/* 2. Redistributions in binary form must reproduce the above copyright */ 20228072Sbapt/* notice, this list of conditions and the following disclaimer in the */ 21228072Sbapt/* documentation and/or other materials provided with the distribution. */ 22228072Sbapt 23228072Sbapt/* Neither the name of the University nor the names of its contributors */ 24228072Sbapt/* may be used to endorse or promote products derived from this software */ 25228072Sbapt/* without specific prior written permission. */ 26228072Sbapt 27228072Sbapt/* THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR */ 28228072Sbapt/* IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED */ 29228072Sbapt/* WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR */ 30228072Sbapt/* PURPOSE. */ 31228072Sbapt 32228072Sbapt#include "flexdef.h" 33228072Sbapt#include "tables.h" 34228072Sbapt 35228072Sbapt/* declare functions that have forward references */ 36228072Sbapt 37228072Sbaptvoid dump_associated_rules PROTO ((FILE *, int)); 38228072Sbaptvoid dump_transitions PROTO ((FILE *, int[])); 39228072Sbaptvoid sympartition PROTO ((int[], int, int[], int[])); 40228072Sbaptint symfollowset PROTO ((int[], int, int, int[])); 41228072Sbapt 42228072Sbapt 43228072Sbapt/* check_for_backing_up - check a DFA state for backing up 44228072Sbapt * 45228072Sbapt * synopsis 46228072Sbapt * void check_for_backing_up( int ds, int state[numecs] ); 47228072Sbapt * 48228072Sbapt * ds is the number of the state to check and state[] is its out-transitions, 49228072Sbapt * indexed by equivalence class. 50228072Sbapt */ 51228072Sbapt 52228072Sbaptvoid check_for_backing_up (ds, state) 53228072Sbapt int ds; 54228072Sbapt int state[]; 55228072Sbapt{ 56228072Sbapt if ((reject && !dfaacc[ds].dfaacc_set) || (!reject && !dfaacc[ds].dfaacc_state)) { /* state is non-accepting */ 57228072Sbapt ++num_backing_up; 58228072Sbapt 59228072Sbapt if (backing_up_report) { 60228072Sbapt fprintf (backing_up_file, 61228072Sbapt _("State #%d is non-accepting -\n"), ds); 62228072Sbapt 63228072Sbapt /* identify the state */ 64228072Sbapt dump_associated_rules (backing_up_file, ds); 65228072Sbapt 66228072Sbapt /* Now identify it further using the out- and 67228072Sbapt * jam-transitions. 68228072Sbapt */ 69228072Sbapt dump_transitions (backing_up_file, state); 70228072Sbapt 71228072Sbapt putc ('\n', backing_up_file); 72228072Sbapt } 73228072Sbapt } 74228072Sbapt} 75228072Sbapt 76228072Sbapt 77228072Sbapt/* check_trailing_context - check to see if NFA state set constitutes 78228072Sbapt * "dangerous" trailing context 79228072Sbapt * 80228072Sbapt * synopsis 81228072Sbapt * void check_trailing_context( int nfa_states[num_states+1], int num_states, 82228072Sbapt * int accset[nacc+1], int nacc ); 83228072Sbapt * 84228072Sbapt * NOTES 85228072Sbapt * Trailing context is "dangerous" if both the head and the trailing 86228072Sbapt * part are of variable size \and/ there's a DFA state which contains 87228072Sbapt * both an accepting state for the head part of the rule and NFA states 88228072Sbapt * which occur after the beginning of the trailing context. 89228072Sbapt * 90228072Sbapt * When such a rule is matched, it's impossible to tell if having been 91228072Sbapt * in the DFA state indicates the beginning of the trailing context or 92228072Sbapt * further-along scanning of the pattern. In these cases, a warning 93228072Sbapt * message is issued. 94228072Sbapt * 95228072Sbapt * nfa_states[1 .. num_states] is the list of NFA states in the DFA. 96228072Sbapt * accset[1 .. nacc] is the list of accepting numbers for the DFA state. 97228072Sbapt */ 98228072Sbapt 99228072Sbaptvoid check_trailing_context (nfa_states, num_states, accset, nacc) 100228072Sbapt int *nfa_states, num_states; 101228072Sbapt int *accset; 102228072Sbapt int nacc; 103228072Sbapt{ 104250874Sjkim int i, j; 105228072Sbapt 106228072Sbapt for (i = 1; i <= num_states; ++i) { 107228072Sbapt int ns = nfa_states[i]; 108250874Sjkim int type = state_type[ns]; 109250874Sjkim int ar = assoc_rule[ns]; 110228072Sbapt 111228072Sbapt if (type == STATE_NORMAL || rule_type[ar] != RULE_VARIABLE) { /* do nothing */ 112228072Sbapt } 113228072Sbapt 114228072Sbapt else if (type == STATE_TRAILING_CONTEXT) { 115228072Sbapt /* Potential trouble. Scan set of accepting numbers 116228072Sbapt * for the one marking the end of the "head". We 117228072Sbapt * assume that this looping will be fairly cheap 118228072Sbapt * since it's rare that an accepting number set 119228072Sbapt * is large. 120228072Sbapt */ 121228072Sbapt for (j = 1; j <= nacc; ++j) 122228072Sbapt if (accset[j] & YY_TRAILING_HEAD_MASK) { 123228072Sbapt line_warning (_ 124228072Sbapt ("dangerous trailing context"), 125228072Sbapt rule_linenum[ar]); 126228072Sbapt return; 127228072Sbapt } 128228072Sbapt } 129228072Sbapt } 130228072Sbapt} 131228072Sbapt 132228072Sbapt 133228072Sbapt/* dump_associated_rules - list the rules associated with a DFA state 134228072Sbapt * 135228072Sbapt * Goes through the set of NFA states associated with the DFA and 136228072Sbapt * extracts the first MAX_ASSOC_RULES unique rules, sorts them, 137228072Sbapt * and writes a report to the given file. 138228072Sbapt */ 139228072Sbapt 140228072Sbaptvoid dump_associated_rules (file, ds) 141228072Sbapt FILE *file; 142228072Sbapt int ds; 143228072Sbapt{ 144250874Sjkim int i, j; 145250874Sjkim int num_associated_rules = 0; 146228072Sbapt int rule_set[MAX_ASSOC_RULES + 1]; 147228072Sbapt int *dset = dss[ds]; 148228072Sbapt int size = dfasiz[ds]; 149228072Sbapt 150228072Sbapt for (i = 1; i <= size; ++i) { 151250874Sjkim int rule_num = rule_linenum[assoc_rule[dset[i]]]; 152228072Sbapt 153228072Sbapt for (j = 1; j <= num_associated_rules; ++j) 154228072Sbapt if (rule_num == rule_set[j]) 155228072Sbapt break; 156228072Sbapt 157228072Sbapt if (j > num_associated_rules) { /* new rule */ 158228072Sbapt if (num_associated_rules < MAX_ASSOC_RULES) 159228072Sbapt rule_set[++num_associated_rules] = 160228072Sbapt rule_num; 161228072Sbapt } 162228072Sbapt } 163228072Sbapt 164250125Sjkim qsort (&rule_set [1], num_associated_rules, sizeof (rule_set [1]), intcmp); 165228072Sbapt 166228072Sbapt fprintf (file, _(" associated rule line numbers:")); 167228072Sbapt 168228072Sbapt for (i = 1; i <= num_associated_rules; ++i) { 169228072Sbapt if (i % 8 == 1) 170228072Sbapt putc ('\n', file); 171228072Sbapt 172228072Sbapt fprintf (file, "\t%d", rule_set[i]); 173228072Sbapt } 174228072Sbapt 175228072Sbapt putc ('\n', file); 176228072Sbapt} 177228072Sbapt 178228072Sbapt 179228072Sbapt/* dump_transitions - list the transitions associated with a DFA state 180228072Sbapt * 181228072Sbapt * synopsis 182228072Sbapt * dump_transitions( FILE *file, int state[numecs] ); 183228072Sbapt * 184228072Sbapt * Goes through the set of out-transitions and lists them in human-readable 185228072Sbapt * form (i.e., not as equivalence classes); also lists jam transitions 186228072Sbapt * (i.e., all those which are not out-transitions, plus EOF). The dump 187228072Sbapt * is done to the given file. 188228072Sbapt */ 189228072Sbapt 190228072Sbaptvoid dump_transitions (file, state) 191228072Sbapt FILE *file; 192228072Sbapt int state[]; 193228072Sbapt{ 194250874Sjkim int i, ec; 195228072Sbapt int out_char_set[CSIZE]; 196228072Sbapt 197228072Sbapt for (i = 0; i < csize; ++i) { 198228072Sbapt ec = ABS (ecgroup[i]); 199228072Sbapt out_char_set[i] = state[ec]; 200228072Sbapt } 201228072Sbapt 202228072Sbapt fprintf (file, _(" out-transitions: ")); 203228072Sbapt 204228072Sbapt list_character_set (file, out_char_set); 205228072Sbapt 206228072Sbapt /* now invert the members of the set to get the jam transitions */ 207228072Sbapt for (i = 0; i < csize; ++i) 208228072Sbapt out_char_set[i] = !out_char_set[i]; 209228072Sbapt 210228072Sbapt fprintf (file, _("\n jam-transitions: EOF ")); 211228072Sbapt 212228072Sbapt list_character_set (file, out_char_set); 213228072Sbapt 214228072Sbapt putc ('\n', file); 215228072Sbapt} 216228072Sbapt 217228072Sbapt 218228072Sbapt/* epsclosure - construct the epsilon closure of a set of ndfa states 219228072Sbapt * 220228072Sbapt * synopsis 221228072Sbapt * int *epsclosure( int t[num_states], int *numstates_addr, 222228072Sbapt * int accset[num_rules+1], int *nacc_addr, 223228072Sbapt * int *hashval_addr ); 224228072Sbapt * 225228072Sbapt * NOTES 226228072Sbapt * The epsilon closure is the set of all states reachable by an arbitrary 227228072Sbapt * number of epsilon transitions, which themselves do not have epsilon 228228072Sbapt * transitions going out, unioned with the set of states which have non-null 229228072Sbapt * accepting numbers. t is an array of size numstates of nfa state numbers. 230228072Sbapt * Upon return, t holds the epsilon closure and *numstates_addr is updated. 231228072Sbapt * accset holds a list of the accepting numbers, and the size of accset is 232228072Sbapt * given by *nacc_addr. t may be subjected to reallocation if it is not 233228072Sbapt * large enough to hold the epsilon closure. 234228072Sbapt * 235228072Sbapt * hashval is the hash value for the dfa corresponding to the state set. 236228072Sbapt */ 237228072Sbapt 238228072Sbaptint *epsclosure (t, ns_addr, accset, nacc_addr, hv_addr) 239228072Sbapt int *t, *ns_addr, accset[], *nacc_addr, *hv_addr; 240228072Sbapt{ 241250874Sjkim int stkpos, ns, tsp; 242228072Sbapt int numstates = *ns_addr, nacc, hashval, transsym, nfaccnum; 243228072Sbapt int stkend, nstate; 244228072Sbapt static int did_stk_init = false, *stk; 245228072Sbapt 246228072Sbapt#define MARK_STATE(state) \ 247228072Sbaptdo{ trans1[state] = trans1[state] - MARKER_DIFFERENCE;} while(0) 248228072Sbapt 249228072Sbapt#define IS_MARKED(state) (trans1[state] < 0) 250228072Sbapt 251228072Sbapt#define UNMARK_STATE(state) \ 252228072Sbaptdo{ trans1[state] = trans1[state] + MARKER_DIFFERENCE;} while(0) 253228072Sbapt 254228072Sbapt#define CHECK_ACCEPT(state) \ 255228072Sbaptdo{ \ 256228072Sbaptnfaccnum = accptnum[state]; \ 257228072Sbaptif ( nfaccnum != NIL ) \ 258228072Sbaptaccset[++nacc] = nfaccnum; \ 259228072Sbapt}while(0) 260228072Sbapt 261228072Sbapt#define DO_REALLOCATION() \ 262228072Sbaptdo { \ 263228072Sbaptcurrent_max_dfa_size += MAX_DFA_SIZE_INCREMENT; \ 264228072Sbapt++num_reallocs; \ 265228072Sbaptt = reallocate_integer_array( t, current_max_dfa_size ); \ 266228072Sbaptstk = reallocate_integer_array( stk, current_max_dfa_size ); \ 267228072Sbapt}while(0) \ 268228072Sbapt 269228072Sbapt#define PUT_ON_STACK(state) \ 270228072Sbaptdo { \ 271228072Sbaptif ( ++stkend >= current_max_dfa_size ) \ 272228072SbaptDO_REALLOCATION(); \ 273228072Sbaptstk[stkend] = state; \ 274228072SbaptMARK_STATE(state); \ 275228072Sbapt}while(0) 276228072Sbapt 277228072Sbapt#define ADD_STATE(state) \ 278228072Sbaptdo { \ 279228072Sbaptif ( ++numstates >= current_max_dfa_size ) \ 280228072SbaptDO_REALLOCATION(); \ 281228072Sbaptt[numstates] = state; \ 282228072Sbapthashval += state; \ 283228072Sbapt}while(0) 284228072Sbapt 285228072Sbapt#define STACK_STATE(state) \ 286228072Sbaptdo { \ 287228072SbaptPUT_ON_STACK(state); \ 288228072SbaptCHECK_ACCEPT(state); \ 289228072Sbaptif ( nfaccnum != NIL || transchar[state] != SYM_EPSILON ) \ 290228072SbaptADD_STATE(state); \ 291228072Sbapt}while(0) 292228072Sbapt 293228072Sbapt 294228072Sbapt if (!did_stk_init) { 295228072Sbapt stk = allocate_integer_array (current_max_dfa_size); 296228072Sbapt did_stk_init = true; 297228072Sbapt } 298228072Sbapt 299228072Sbapt nacc = stkend = hashval = 0; 300228072Sbapt 301228072Sbapt for (nstate = 1; nstate <= numstates; ++nstate) { 302228072Sbapt ns = t[nstate]; 303228072Sbapt 304228072Sbapt /* The state could be marked if we've already pushed it onto 305228072Sbapt * the stack. 306228072Sbapt */ 307228072Sbapt if (!IS_MARKED (ns)) { 308228072Sbapt PUT_ON_STACK (ns); 309228072Sbapt CHECK_ACCEPT (ns); 310228072Sbapt hashval += ns; 311228072Sbapt } 312228072Sbapt } 313228072Sbapt 314228072Sbapt for (stkpos = 1; stkpos <= stkend; ++stkpos) { 315228072Sbapt ns = stk[stkpos]; 316228072Sbapt transsym = transchar[ns]; 317228072Sbapt 318228072Sbapt if (transsym == SYM_EPSILON) { 319228072Sbapt tsp = trans1[ns] + MARKER_DIFFERENCE; 320228072Sbapt 321228072Sbapt if (tsp != NO_TRANSITION) { 322228072Sbapt if (!IS_MARKED (tsp)) 323228072Sbapt STACK_STATE (tsp); 324228072Sbapt 325228072Sbapt tsp = trans2[ns]; 326228072Sbapt 327228072Sbapt if (tsp != NO_TRANSITION 328228072Sbapt && !IS_MARKED (tsp)) 329228072Sbapt STACK_STATE (tsp); 330228072Sbapt } 331228072Sbapt } 332228072Sbapt } 333228072Sbapt 334228072Sbapt /* Clear out "visit" markers. */ 335228072Sbapt 336228072Sbapt for (stkpos = 1; stkpos <= stkend; ++stkpos) { 337228072Sbapt if (IS_MARKED (stk[stkpos])) 338228072Sbapt UNMARK_STATE (stk[stkpos]); 339228072Sbapt else 340228072Sbapt flexfatal (_ 341228072Sbapt ("consistency check failed in epsclosure()")); 342228072Sbapt } 343228072Sbapt 344228072Sbapt *ns_addr = numstates; 345228072Sbapt *hv_addr = hashval; 346228072Sbapt *nacc_addr = nacc; 347228072Sbapt 348228072Sbapt return t; 349228072Sbapt} 350228072Sbapt 351228072Sbapt 352228072Sbapt/* increase_max_dfas - increase the maximum number of DFAs */ 353228072Sbapt 354228072Sbaptvoid increase_max_dfas () 355228072Sbapt{ 356228072Sbapt current_max_dfas += MAX_DFAS_INCREMENT; 357228072Sbapt 358228072Sbapt ++num_reallocs; 359228072Sbapt 360228072Sbapt base = reallocate_integer_array (base, current_max_dfas); 361228072Sbapt def = reallocate_integer_array (def, current_max_dfas); 362228072Sbapt dfasiz = reallocate_integer_array (dfasiz, current_max_dfas); 363228072Sbapt accsiz = reallocate_integer_array (accsiz, current_max_dfas); 364228072Sbapt dhash = reallocate_integer_array (dhash, current_max_dfas); 365228072Sbapt dss = reallocate_int_ptr_array (dss, current_max_dfas); 366228072Sbapt dfaacc = reallocate_dfaacc_union (dfaacc, current_max_dfas); 367228072Sbapt 368228072Sbapt if (nultrans) 369228072Sbapt nultrans = 370228072Sbapt reallocate_integer_array (nultrans, 371228072Sbapt current_max_dfas); 372228072Sbapt} 373228072Sbapt 374228072Sbapt 375228072Sbapt/* ntod - convert an ndfa to a dfa 376228072Sbapt * 377228072Sbapt * Creates the dfa corresponding to the ndfa we've constructed. The 378228072Sbapt * dfa starts out in state #1. 379228072Sbapt */ 380228072Sbapt 381228072Sbaptvoid ntod () 382228072Sbapt{ 383228072Sbapt int *accset, ds, nacc, newds; 384228072Sbapt int sym, hashval, numstates, dsize; 385228072Sbapt int num_full_table_rows=0; /* used only for -f */ 386228072Sbapt int *nset, *dset; 387228072Sbapt int targptr, totaltrans, i, comstate, comfreq, targ; 388228072Sbapt int symlist[CSIZE + 1]; 389228072Sbapt int num_start_states; 390228072Sbapt int todo_head, todo_next; 391228072Sbapt 392228072Sbapt struct yytbl_data *yynxt_tbl = 0; 393228072Sbapt flex_int32_t *yynxt_data = 0, yynxt_curr = 0; 394228072Sbapt 395228072Sbapt /* Note that the following are indexed by *equivalence classes* 396228072Sbapt * and not by characters. Since equivalence classes are indexed 397228072Sbapt * beginning with 1, even if the scanner accepts NUL's, this 398228072Sbapt * means that (since every character is potentially in its own 399228072Sbapt * equivalence class) these arrays must have room for indices 400228072Sbapt * from 1 to CSIZE, so their size must be CSIZE + 1. 401228072Sbapt */ 402228072Sbapt int duplist[CSIZE + 1], state[CSIZE + 1]; 403228072Sbapt int targfreq[CSIZE + 1], targstate[CSIZE + 1]; 404228072Sbapt 405228072Sbapt /* accset needs to be large enough to hold all of the rules present 406228072Sbapt * in the input, *plus* their YY_TRAILING_HEAD_MASK variants. 407228072Sbapt */ 408228072Sbapt accset = allocate_integer_array ((num_rules + 1) * 2); 409228072Sbapt nset = allocate_integer_array (current_max_dfa_size); 410228072Sbapt 411228072Sbapt /* The "todo" queue is represented by the head, which is the DFA 412228072Sbapt * state currently being processed, and the "next", which is the 413228072Sbapt * next DFA state number available (not in use). We depend on the 414228072Sbapt * fact that snstods() returns DFA's \in increasing order/, and thus 415228072Sbapt * need only know the bounds of the dfas to be processed. 416228072Sbapt */ 417228072Sbapt todo_head = todo_next = 0; 418228072Sbapt 419228072Sbapt for (i = 0; i <= csize; ++i) { 420228072Sbapt duplist[i] = NIL; 421228072Sbapt symlist[i] = false; 422228072Sbapt } 423228072Sbapt 424228072Sbapt for (i = 0; i <= num_rules; ++i) 425228072Sbapt accset[i] = NIL; 426228072Sbapt 427228072Sbapt if (trace) { 428228072Sbapt dumpnfa (scset[1]); 429228072Sbapt fputs (_("\n\nDFA Dump:\n\n"), stderr); 430228072Sbapt } 431228072Sbapt 432228072Sbapt inittbl (); 433228072Sbapt 434228072Sbapt /* Check to see whether we should build a separate table for 435228072Sbapt * transitions on NUL characters. We don't do this for full-speed 436228072Sbapt * (-F) scanners, since for them we don't have a simple state 437228072Sbapt * number lying around with which to index the table. We also 438228072Sbapt * don't bother doing it for scanners unless (1) NUL is in its own 439228072Sbapt * equivalence class (indicated by a positive value of 440228072Sbapt * ecgroup[NUL]), (2) NUL's equivalence class is the last 441228072Sbapt * equivalence class, and (3) the number of equivalence classes is 442228072Sbapt * the same as the number of characters. This latter case comes 443228072Sbapt * about when useecs is false or when it's true but every character 444228072Sbapt * still manages to land in its own class (unlikely, but it's 445228072Sbapt * cheap to check for). If all these things are true then the 446228072Sbapt * character code needed to represent NUL's equivalence class for 447228072Sbapt * indexing the tables is going to take one more bit than the 448228072Sbapt * number of characters, and therefore we won't be assured of 449228072Sbapt * being able to fit it into a YY_CHAR variable. This rules out 450228072Sbapt * storing the transitions in a compressed table, since the code 451228072Sbapt * for interpreting them uses a YY_CHAR variable (perhaps it 452228072Sbapt * should just use an integer, though; this is worth pondering ... 453228072Sbapt * ###). 454228072Sbapt * 455228072Sbapt * Finally, for full tables, we want the number of entries in the 456228072Sbapt * table to be a power of two so the array references go fast (it 457228072Sbapt * will just take a shift to compute the major index). If 458228072Sbapt * encoding NUL's transitions in the table will spoil this, we 459228072Sbapt * give it its own table (note that this will be the case if we're 460228072Sbapt * not using equivalence classes). 461228072Sbapt */ 462228072Sbapt 463228072Sbapt /* Note that the test for ecgroup[0] == numecs below accomplishes 464228072Sbapt * both (1) and (2) above 465228072Sbapt */ 466228072Sbapt if (!fullspd && ecgroup[0] == numecs) { 467228072Sbapt /* NUL is alone in its equivalence class, which is the 468228072Sbapt * last one. 469228072Sbapt */ 470228072Sbapt int use_NUL_table = (numecs == csize); 471228072Sbapt 472228072Sbapt if (fulltbl && !use_NUL_table) { 473228072Sbapt /* We still may want to use the table if numecs 474228072Sbapt * is a power of 2. 475228072Sbapt */ 476228072Sbapt int power_of_two; 477228072Sbapt 478228072Sbapt for (power_of_two = 1; power_of_two <= csize; 479228072Sbapt power_of_two *= 2) 480228072Sbapt if (numecs == power_of_two) { 481228072Sbapt use_NUL_table = true; 482228072Sbapt break; 483228072Sbapt } 484228072Sbapt } 485228072Sbapt 486228072Sbapt if (use_NUL_table) 487228072Sbapt nultrans = 488228072Sbapt allocate_integer_array (current_max_dfas); 489228072Sbapt 490228072Sbapt /* From now on, nultrans != nil indicates that we're 491228072Sbapt * saving null transitions for later, separate encoding. 492228072Sbapt */ 493228072Sbapt } 494228072Sbapt 495228072Sbapt 496228072Sbapt if (fullspd) { 497228072Sbapt for (i = 0; i <= numecs; ++i) 498228072Sbapt state[i] = 0; 499228072Sbapt 500228072Sbapt place_state (state, 0, 0); 501228072Sbapt dfaacc[0].dfaacc_state = 0; 502228072Sbapt } 503228072Sbapt 504228072Sbapt else if (fulltbl) { 505228072Sbapt if (nultrans) 506228072Sbapt /* We won't be including NUL's transitions in the 507228072Sbapt * table, so build it for entries from 0 .. numecs - 1. 508228072Sbapt */ 509228072Sbapt num_full_table_rows = numecs; 510228072Sbapt 511228072Sbapt else 512228072Sbapt /* Take into account the fact that we'll be including 513228072Sbapt * the NUL entries in the transition table. Build it 514228072Sbapt * from 0 .. numecs. 515228072Sbapt */ 516228072Sbapt num_full_table_rows = numecs + 1; 517228072Sbapt 518228072Sbapt /* Begin generating yy_nxt[][] 519228072Sbapt * This spans the entire LONG function. 520228072Sbapt * This table is tricky because we don't know how big it will be. 521228072Sbapt * So we'll have to realloc() on the way... 522228072Sbapt * we'll wait until we can calculate yynxt_tbl->td_hilen. 523228072Sbapt */ 524228072Sbapt yynxt_tbl = 525228072Sbapt (struct yytbl_data *) calloc (1, 526228072Sbapt sizeof (struct 527228072Sbapt yytbl_data)); 528228072Sbapt yytbl_data_init (yynxt_tbl, YYTD_ID_NXT); 529228072Sbapt yynxt_tbl->td_hilen = 1; 530228072Sbapt yynxt_tbl->td_lolen = num_full_table_rows; 531228072Sbapt yynxt_tbl->td_data = yynxt_data = 532228072Sbapt (flex_int32_t *) calloc (yynxt_tbl->td_lolen * 533228072Sbapt yynxt_tbl->td_hilen, 534228072Sbapt sizeof (flex_int32_t)); 535228072Sbapt yynxt_curr = 0; 536228072Sbapt 537228072Sbapt buf_prints (&yydmap_buf, 538228072Sbapt "\t{YYTD_ID_NXT, (void**)&yy_nxt, sizeof(%s)},\n", 539228072Sbapt long_align ? "flex_int32_t" : "flex_int16_t"); 540228072Sbapt 541228072Sbapt /* Unless -Ca, declare it "short" because it's a real 542228072Sbapt * long-shot that that won't be large enough. 543228072Sbapt */ 544228072Sbapt if (gentables) 545228072Sbapt out_str_dec 546228072Sbapt ("static yyconst %s yy_nxt[][%d] =\n {\n", 547228072Sbapt long_align ? "flex_int32_t" : "flex_int16_t", 548228072Sbapt num_full_table_rows); 549228072Sbapt else { 550228072Sbapt out_dec ("#undef YY_NXT_LOLEN\n#define YY_NXT_LOLEN (%d)\n", num_full_table_rows); 551228072Sbapt out_str ("static yyconst %s *yy_nxt =0;\n", 552228072Sbapt long_align ? "flex_int32_t" : "flex_int16_t"); 553228072Sbapt } 554228072Sbapt 555228072Sbapt 556228072Sbapt if (gentables) 557228072Sbapt outn (" {"); 558228072Sbapt 559228072Sbapt /* Generate 0 entries for state #0. */ 560228072Sbapt for (i = 0; i < num_full_table_rows; ++i) { 561228072Sbapt mk2data (0); 562228072Sbapt yynxt_data[yynxt_curr++] = 0; 563228072Sbapt } 564228072Sbapt 565228072Sbapt dataflush (); 566228072Sbapt if (gentables) 567228072Sbapt outn (" },\n"); 568228072Sbapt } 569228072Sbapt 570228072Sbapt /* Create the first states. */ 571228072Sbapt 572228072Sbapt num_start_states = lastsc * 2; 573228072Sbapt 574228072Sbapt for (i = 1; i <= num_start_states; ++i) { 575228072Sbapt numstates = 1; 576228072Sbapt 577228072Sbapt /* For each start condition, make one state for the case when 578228072Sbapt * we're at the beginning of the line (the '^' operator) and 579228072Sbapt * one for the case when we're not. 580228072Sbapt */ 581228072Sbapt if (i % 2 == 1) 582228072Sbapt nset[numstates] = scset[(i / 2) + 1]; 583228072Sbapt else 584228072Sbapt nset[numstates] = 585228072Sbapt mkbranch (scbol[i / 2], scset[i / 2]); 586228072Sbapt 587228072Sbapt nset = epsclosure (nset, &numstates, accset, &nacc, 588228072Sbapt &hashval); 589228072Sbapt 590228072Sbapt if (snstods (nset, numstates, accset, nacc, hashval, &ds)) { 591228072Sbapt numas += nacc; 592228072Sbapt totnst += numstates; 593228072Sbapt ++todo_next; 594228072Sbapt 595228072Sbapt if (variable_trailing_context_rules && nacc > 0) 596228072Sbapt check_trailing_context (nset, numstates, 597228072Sbapt accset, nacc); 598228072Sbapt } 599228072Sbapt } 600228072Sbapt 601228072Sbapt if (!fullspd) { 602228072Sbapt if (!snstods (nset, 0, accset, 0, 0, &end_of_buffer_state)) 603228072Sbapt flexfatal (_ 604228072Sbapt ("could not create unique end-of-buffer state")); 605228072Sbapt 606228072Sbapt ++numas; 607228072Sbapt ++num_start_states; 608228072Sbapt ++todo_next; 609228072Sbapt } 610228072Sbapt 611228072Sbapt 612228072Sbapt while (todo_head < todo_next) { 613228072Sbapt targptr = 0; 614228072Sbapt totaltrans = 0; 615228072Sbapt 616228072Sbapt for (i = 1; i <= numecs; ++i) 617228072Sbapt state[i] = 0; 618228072Sbapt 619228072Sbapt ds = ++todo_head; 620228072Sbapt 621228072Sbapt dset = dss[ds]; 622228072Sbapt dsize = dfasiz[ds]; 623228072Sbapt 624228072Sbapt if (trace) 625228072Sbapt fprintf (stderr, _("state # %d:\n"), ds); 626228072Sbapt 627228072Sbapt sympartition (dset, dsize, symlist, duplist); 628228072Sbapt 629228072Sbapt for (sym = 1; sym <= numecs; ++sym) { 630228072Sbapt if (symlist[sym]) { 631228072Sbapt symlist[sym] = 0; 632228072Sbapt 633228072Sbapt if (duplist[sym] == NIL) { 634228072Sbapt /* Symbol has unique out-transitions. */ 635228072Sbapt numstates = 636228072Sbapt symfollowset (dset, dsize, 637228072Sbapt sym, nset); 638228072Sbapt nset = epsclosure (nset, 639228072Sbapt &numstates, 640228072Sbapt accset, &nacc, 641228072Sbapt &hashval); 642228072Sbapt 643228072Sbapt if (snstods 644228072Sbapt (nset, numstates, accset, nacc, 645228072Sbapt hashval, &newds)) { 646228072Sbapt totnst = totnst + 647228072Sbapt numstates; 648228072Sbapt ++todo_next; 649228072Sbapt numas += nacc; 650228072Sbapt 651228072Sbapt if (variable_trailing_context_rules && nacc > 0) 652228072Sbapt check_trailing_context 653228072Sbapt (nset, 654228072Sbapt numstates, 655228072Sbapt accset, 656228072Sbapt nacc); 657228072Sbapt } 658228072Sbapt 659228072Sbapt state[sym] = newds; 660228072Sbapt 661228072Sbapt if (trace) 662228072Sbapt fprintf (stderr, 663228072Sbapt "\t%d\t%d\n", sym, 664228072Sbapt newds); 665228072Sbapt 666228072Sbapt targfreq[++targptr] = 1; 667228072Sbapt targstate[targptr] = newds; 668228072Sbapt ++numuniq; 669228072Sbapt } 670228072Sbapt 671228072Sbapt else { 672228072Sbapt /* sym's equivalence class has the same 673228072Sbapt * transitions as duplist(sym)'s 674228072Sbapt * equivalence class. 675228072Sbapt */ 676228072Sbapt targ = state[duplist[sym]]; 677228072Sbapt state[sym] = targ; 678228072Sbapt 679228072Sbapt if (trace) 680228072Sbapt fprintf (stderr, 681228072Sbapt "\t%d\t%d\n", sym, 682228072Sbapt targ); 683228072Sbapt 684228072Sbapt /* Update frequency count for 685228072Sbapt * destination state. 686228072Sbapt */ 687228072Sbapt 688228072Sbapt i = 0; 689228072Sbapt while (targstate[++i] != targ) ; 690228072Sbapt 691228072Sbapt ++targfreq[i]; 692228072Sbapt ++numdup; 693228072Sbapt } 694228072Sbapt 695228072Sbapt ++totaltrans; 696228072Sbapt duplist[sym] = NIL; 697228072Sbapt } 698228072Sbapt } 699228072Sbapt 700228072Sbapt 701228072Sbapt numsnpairs += totaltrans; 702228072Sbapt 703228072Sbapt if (ds > num_start_states) 704228072Sbapt check_for_backing_up (ds, state); 705228072Sbapt 706228072Sbapt if (nultrans) { 707228072Sbapt nultrans[ds] = state[NUL_ec]; 708228072Sbapt state[NUL_ec] = 0; /* remove transition */ 709228072Sbapt } 710228072Sbapt 711228072Sbapt if (fulltbl) { 712228072Sbapt 713228072Sbapt /* Each time we hit here, it's another td_hilen, so we realloc. */ 714228072Sbapt yynxt_tbl->td_hilen++; 715228072Sbapt yynxt_tbl->td_data = yynxt_data = 716228072Sbapt (flex_int32_t *) realloc (yynxt_data, 717228072Sbapt yynxt_tbl->td_hilen * 718228072Sbapt yynxt_tbl->td_lolen * 719228072Sbapt sizeof (flex_int32_t)); 720228072Sbapt 721228072Sbapt 722228072Sbapt if (gentables) 723228072Sbapt outn (" {"); 724228072Sbapt 725228072Sbapt /* Supply array's 0-element. */ 726228072Sbapt if (ds == end_of_buffer_state) { 727228072Sbapt mk2data (-end_of_buffer_state); 728228072Sbapt yynxt_data[yynxt_curr++] = 729228072Sbapt -end_of_buffer_state; 730228072Sbapt } 731228072Sbapt else { 732228072Sbapt mk2data (end_of_buffer_state); 733228072Sbapt yynxt_data[yynxt_curr++] = 734228072Sbapt end_of_buffer_state; 735228072Sbapt } 736228072Sbapt 737228072Sbapt for (i = 1; i < num_full_table_rows; ++i) { 738228072Sbapt /* Jams are marked by negative of state 739228072Sbapt * number. 740228072Sbapt */ 741228072Sbapt mk2data (state[i] ? state[i] : -ds); 742228072Sbapt yynxt_data[yynxt_curr++] = 743228072Sbapt state[i] ? state[i] : -ds; 744228072Sbapt } 745228072Sbapt 746228072Sbapt dataflush (); 747228072Sbapt if (gentables) 748228072Sbapt outn (" },\n"); 749228072Sbapt } 750228072Sbapt 751228072Sbapt else if (fullspd) 752228072Sbapt place_state (state, ds, totaltrans); 753228072Sbapt 754228072Sbapt else if (ds == end_of_buffer_state) 755228072Sbapt /* Special case this state to make sure it does what 756228072Sbapt * it's supposed to, i.e., jam on end-of-buffer. 757228072Sbapt */ 758228072Sbapt stack1 (ds, 0, 0, JAMSTATE); 759228072Sbapt 760228072Sbapt else { /* normal, compressed state */ 761228072Sbapt 762228072Sbapt /* Determine which destination state is the most 763228072Sbapt * common, and how many transitions to it there are. 764228072Sbapt */ 765228072Sbapt 766228072Sbapt comfreq = 0; 767228072Sbapt comstate = 0; 768228072Sbapt 769228072Sbapt for (i = 1; i <= targptr; ++i) 770228072Sbapt if (targfreq[i] > comfreq) { 771228072Sbapt comfreq = targfreq[i]; 772228072Sbapt comstate = targstate[i]; 773228072Sbapt } 774228072Sbapt 775228072Sbapt bldtbl (state, ds, totaltrans, comstate, comfreq); 776228072Sbapt } 777228072Sbapt } 778228072Sbapt 779228072Sbapt if (fulltbl) { 780228072Sbapt dataend (); 781228072Sbapt if (tablesext) { 782228072Sbapt yytbl_data_compress (yynxt_tbl); 783228072Sbapt if (yytbl_data_fwrite (&tableswr, yynxt_tbl) < 0) 784228072Sbapt flexerror (_ 785228072Sbapt ("Could not write yynxt_tbl[][]")); 786228072Sbapt } 787228072Sbapt if (yynxt_tbl) { 788228072Sbapt yytbl_data_destroy (yynxt_tbl); 789228072Sbapt yynxt_tbl = 0; 790228072Sbapt } 791228072Sbapt } 792228072Sbapt 793228072Sbapt else if (!fullspd) { 794228072Sbapt cmptmps (); /* create compressed template entries */ 795228072Sbapt 796228072Sbapt /* Create tables for all the states with only one 797228072Sbapt * out-transition. 798228072Sbapt */ 799228072Sbapt while (onesp > 0) { 800228072Sbapt mk1tbl (onestate[onesp], onesym[onesp], 801228072Sbapt onenext[onesp], onedef[onesp]); 802228072Sbapt --onesp; 803228072Sbapt } 804228072Sbapt 805228072Sbapt mkdeftbl (); 806228072Sbapt } 807228072Sbapt 808228072Sbapt flex_free ((void *) accset); 809228072Sbapt flex_free ((void *) nset); 810228072Sbapt} 811228072Sbapt 812228072Sbapt 813228072Sbapt/* snstods - converts a set of ndfa states into a dfa state 814228072Sbapt * 815228072Sbapt * synopsis 816228072Sbapt * is_new_state = snstods( int sns[numstates], int numstates, 817228072Sbapt * int accset[num_rules+1], int nacc, 818228072Sbapt * int hashval, int *newds_addr ); 819228072Sbapt * 820228072Sbapt * On return, the dfa state number is in newds. 821228072Sbapt */ 822228072Sbapt 823228072Sbaptint snstods (sns, numstates, accset, nacc, hashval, newds_addr) 824228072Sbapt int sns[], numstates, accset[], nacc, hashval, *newds_addr; 825228072Sbapt{ 826228072Sbapt int didsort = 0; 827250874Sjkim int i, j; 828228072Sbapt int newds, *oldsns; 829228072Sbapt 830228072Sbapt for (i = 1; i <= lastdfa; ++i) 831228072Sbapt if (hashval == dhash[i]) { 832228072Sbapt if (numstates == dfasiz[i]) { 833228072Sbapt oldsns = dss[i]; 834228072Sbapt 835228072Sbapt if (!didsort) { 836228072Sbapt /* We sort the states in sns so we 837228072Sbapt * can compare it to oldsns quickly. 838228072Sbapt */ 839250125Sjkim qsort (&sns [1], numstates, sizeof (sns [1]), intcmp); 840228072Sbapt didsort = 1; 841228072Sbapt } 842228072Sbapt 843228072Sbapt for (j = 1; j <= numstates; ++j) 844228072Sbapt if (sns[j] != oldsns[j]) 845228072Sbapt break; 846228072Sbapt 847228072Sbapt if (j > numstates) { 848228072Sbapt ++dfaeql; 849228072Sbapt *newds_addr = i; 850228072Sbapt return 0; 851228072Sbapt } 852228072Sbapt 853228072Sbapt ++hshcol; 854228072Sbapt } 855228072Sbapt 856228072Sbapt else 857228072Sbapt ++hshsave; 858228072Sbapt } 859228072Sbapt 860228072Sbapt /* Make a new dfa. */ 861228072Sbapt 862228072Sbapt if (++lastdfa >= current_max_dfas) 863228072Sbapt increase_max_dfas (); 864228072Sbapt 865228072Sbapt newds = lastdfa; 866228072Sbapt 867228072Sbapt dss[newds] = allocate_integer_array (numstates + 1); 868228072Sbapt 869228072Sbapt /* If we haven't already sorted the states in sns, we do so now, 870228072Sbapt * so that future comparisons with it can be made quickly. 871228072Sbapt */ 872228072Sbapt 873228072Sbapt if (!didsort) 874250125Sjkim qsort (&sns [1], numstates, sizeof (sns [1]), intcmp); 875228072Sbapt 876228072Sbapt for (i = 1; i <= numstates; ++i) 877228072Sbapt dss[newds][i] = sns[i]; 878228072Sbapt 879228072Sbapt dfasiz[newds] = numstates; 880228072Sbapt dhash[newds] = hashval; 881228072Sbapt 882228072Sbapt if (nacc == 0) { 883228072Sbapt if (reject) 884228072Sbapt dfaacc[newds].dfaacc_set = (int *) 0; 885228072Sbapt else 886228072Sbapt dfaacc[newds].dfaacc_state = 0; 887228072Sbapt 888228072Sbapt accsiz[newds] = 0; 889228072Sbapt } 890228072Sbapt 891228072Sbapt else if (reject) { 892228072Sbapt /* We sort the accepting set in increasing order so the 893228072Sbapt * disambiguating rule that the first rule listed is considered 894250125Sjkim * match in the event of ties will work. 895228072Sbapt */ 896228072Sbapt 897250125Sjkim qsort (&accset [1], nacc, sizeof (accset [1]), intcmp); 898228072Sbapt 899228072Sbapt dfaacc[newds].dfaacc_set = 900228072Sbapt allocate_integer_array (nacc + 1); 901228072Sbapt 902228072Sbapt /* Save the accepting set for later */ 903228072Sbapt for (i = 1; i <= nacc; ++i) { 904228072Sbapt dfaacc[newds].dfaacc_set[i] = accset[i]; 905228072Sbapt 906228072Sbapt if (accset[i] <= num_rules) 907228072Sbapt /* Who knows, perhaps a REJECT can yield 908228072Sbapt * this rule. 909228072Sbapt */ 910228072Sbapt rule_useful[accset[i]] = true; 911228072Sbapt } 912228072Sbapt 913228072Sbapt accsiz[newds] = nacc; 914228072Sbapt } 915228072Sbapt 916228072Sbapt else { 917228072Sbapt /* Find lowest numbered rule so the disambiguating rule 918228072Sbapt * will work. 919228072Sbapt */ 920228072Sbapt j = num_rules + 1; 921228072Sbapt 922228072Sbapt for (i = 1; i <= nacc; ++i) 923228072Sbapt if (accset[i] < j) 924228072Sbapt j = accset[i]; 925228072Sbapt 926228072Sbapt dfaacc[newds].dfaacc_state = j; 927228072Sbapt 928228072Sbapt if (j <= num_rules) 929228072Sbapt rule_useful[j] = true; 930228072Sbapt } 931228072Sbapt 932228072Sbapt *newds_addr = newds; 933228072Sbapt 934228072Sbapt return 1; 935228072Sbapt} 936228072Sbapt 937228072Sbapt 938228072Sbapt/* symfollowset - follow the symbol transitions one step 939228072Sbapt * 940228072Sbapt * synopsis 941228072Sbapt * numstates = symfollowset( int ds[current_max_dfa_size], int dsize, 942228072Sbapt * int transsym, int nset[current_max_dfa_size] ); 943228072Sbapt */ 944228072Sbapt 945228072Sbaptint symfollowset (ds, dsize, transsym, nset) 946228072Sbapt int ds[], dsize, transsym, nset[]; 947228072Sbapt{ 948228072Sbapt int ns, tsp, sym, i, j, lenccl, ch, numstates, ccllist; 949228072Sbapt 950228072Sbapt numstates = 0; 951228072Sbapt 952228072Sbapt for (i = 1; i <= dsize; ++i) { /* for each nfa state ns in the state set of ds */ 953228072Sbapt ns = ds[i]; 954228072Sbapt sym = transchar[ns]; 955228072Sbapt tsp = trans1[ns]; 956228072Sbapt 957228072Sbapt if (sym < 0) { /* it's a character class */ 958228072Sbapt sym = -sym; 959228072Sbapt ccllist = cclmap[sym]; 960228072Sbapt lenccl = ccllen[sym]; 961228072Sbapt 962228072Sbapt if (cclng[sym]) { 963228072Sbapt for (j = 0; j < lenccl; ++j) { 964228072Sbapt /* Loop through negated character 965228072Sbapt * class. 966228072Sbapt */ 967228072Sbapt ch = ccltbl[ccllist + j]; 968228072Sbapt 969228072Sbapt if (ch == 0) 970228072Sbapt ch = NUL_ec; 971228072Sbapt 972228072Sbapt if (ch > transsym) 973228072Sbapt /* Transsym isn't in negated 974228072Sbapt * ccl. 975228072Sbapt */ 976228072Sbapt break; 977228072Sbapt 978228072Sbapt else if (ch == transsym) 979228072Sbapt /* next 2 */ 980228072Sbapt goto bottom; 981228072Sbapt } 982228072Sbapt 983228072Sbapt /* Didn't find transsym in ccl. */ 984228072Sbapt nset[++numstates] = tsp; 985228072Sbapt } 986228072Sbapt 987228072Sbapt else 988228072Sbapt for (j = 0; j < lenccl; ++j) { 989228072Sbapt ch = ccltbl[ccllist + j]; 990228072Sbapt 991228072Sbapt if (ch == 0) 992228072Sbapt ch = NUL_ec; 993228072Sbapt 994228072Sbapt if (ch > transsym) 995228072Sbapt break; 996228072Sbapt else if (ch == transsym) { 997228072Sbapt nset[++numstates] = tsp; 998228072Sbapt break; 999228072Sbapt } 1000228072Sbapt } 1001228072Sbapt } 1002228072Sbapt 1003228072Sbapt else if (sym == SYM_EPSILON) { /* do nothing */ 1004228072Sbapt } 1005228072Sbapt 1006228072Sbapt else if (ABS (ecgroup[sym]) == transsym) 1007228072Sbapt nset[++numstates] = tsp; 1008228072Sbapt 1009228072Sbapt bottom:; 1010228072Sbapt } 1011228072Sbapt 1012228072Sbapt return numstates; 1013228072Sbapt} 1014228072Sbapt 1015228072Sbapt 1016228072Sbapt/* sympartition - partition characters with same out-transitions 1017228072Sbapt * 1018228072Sbapt * synopsis 1019228072Sbapt * sympartition( int ds[current_max_dfa_size], int numstates, 1020228072Sbapt * int symlist[numecs], int duplist[numecs] ); 1021228072Sbapt */ 1022228072Sbapt 1023228072Sbaptvoid sympartition (ds, numstates, symlist, duplist) 1024228072Sbapt int ds[], numstates; 1025228072Sbapt int symlist[], duplist[]; 1026228072Sbapt{ 1027228072Sbapt int tch, i, j, k, ns, dupfwd[CSIZE + 1], lenccl, cclp, ich; 1028228072Sbapt 1029228072Sbapt /* Partitioning is done by creating equivalence classes for those 1030228072Sbapt * characters which have out-transitions from the given state. Thus 1031228072Sbapt * we are really creating equivalence classes of equivalence classes. 1032228072Sbapt */ 1033228072Sbapt 1034228072Sbapt for (i = 1; i <= numecs; ++i) { /* initialize equivalence class list */ 1035228072Sbapt duplist[i] = i - 1; 1036228072Sbapt dupfwd[i] = i + 1; 1037228072Sbapt } 1038228072Sbapt 1039228072Sbapt duplist[1] = NIL; 1040228072Sbapt dupfwd[numecs] = NIL; 1041228072Sbapt 1042228072Sbapt for (i = 1; i <= numstates; ++i) { 1043228072Sbapt ns = ds[i]; 1044228072Sbapt tch = transchar[ns]; 1045228072Sbapt 1046228072Sbapt if (tch != SYM_EPSILON) { 1047228072Sbapt if (tch < -lastccl || tch >= csize) { 1048228072Sbapt flexfatal (_ 1049228072Sbapt ("bad transition character detected in sympartition()")); 1050228072Sbapt } 1051228072Sbapt 1052228072Sbapt if (tch >= 0) { /* character transition */ 1053228072Sbapt int ec = ecgroup[tch]; 1054228072Sbapt 1055228072Sbapt mkechar (ec, dupfwd, duplist); 1056228072Sbapt symlist[ec] = 1; 1057228072Sbapt } 1058228072Sbapt 1059228072Sbapt else { /* character class */ 1060228072Sbapt tch = -tch; 1061228072Sbapt 1062228072Sbapt lenccl = ccllen[tch]; 1063228072Sbapt cclp = cclmap[tch]; 1064228072Sbapt mkeccl (ccltbl + cclp, lenccl, dupfwd, 1065228072Sbapt duplist, numecs, NUL_ec); 1066228072Sbapt 1067228072Sbapt if (cclng[tch]) { 1068228072Sbapt j = 0; 1069228072Sbapt 1070228072Sbapt for (k = 0; k < lenccl; ++k) { 1071228072Sbapt ich = ccltbl[cclp + k]; 1072228072Sbapt 1073228072Sbapt if (ich == 0) 1074228072Sbapt ich = NUL_ec; 1075228072Sbapt 1076228072Sbapt for (++j; j < ich; ++j) 1077228072Sbapt symlist[j] = 1; 1078228072Sbapt } 1079228072Sbapt 1080228072Sbapt for (++j; j <= numecs; ++j) 1081228072Sbapt symlist[j] = 1; 1082228072Sbapt } 1083228072Sbapt 1084228072Sbapt else 1085228072Sbapt for (k = 0; k < lenccl; ++k) { 1086228072Sbapt ich = ccltbl[cclp + k]; 1087228072Sbapt 1088228072Sbapt if (ich == 0) 1089228072Sbapt ich = NUL_ec; 1090228072Sbapt 1091228072Sbapt symlist[ich] = 1; 1092228072Sbapt } 1093228072Sbapt } 1094228072Sbapt } 1095228072Sbapt } 1096228072Sbapt} 1097