Home | History | Annotate | Line # | Download | only in ntpd
keyword-gen.c revision 1.1 
      1 /*	$NetBSD: keyword-gen.c,v 1.1 2009/12/13 16:56:08 kardel Exp $	*/
      2 
      3 /*
      4  * keyword-gen.c -- generate keyword scanner finite state machine and
      5  *		    keyword_text array.
      6  *		    This program is run to generate ntp_keyword.h
      7  */
      8 #include <config.h>
      9 #include <stdio.h>
     10 #include <stdlib.h>
     11 #include <time.h>
     12 
     13 #include <ntp_stdlib.h>
     14 #include <ntp_config.h>
     15 #include <lib_strbuf.h>
     16 #include "ntp_scanner.h"
     17 #include "ntp_parser.h"
     18 
     19 
     20 #ifdef QSORT_USES_VOID_P
     21 typedef const void *	QSORTP;
     22 #else
     23 typedef char *		QSORTP;
     24 #endif
     25 
     26 /* Define a structure to hold a (keyword, token) pair */
     27 struct key_tok {
     28 	char *	key;		/* Keyword */
     29 	int	token;		/* Associated Token */
     30 	follby	followedby;	/* nonzero indicates the next token(s)
     31 				   forced to be string(s) */
     32 };
     33 
     34 struct key_tok ntp_keywords[] = {
     35 { "automax",		T_Automax,		FOLLBY_TOKEN },
     36 { "broadcast",		T_Broadcast,		FOLLBY_STRING },
     37 { "broadcastclient",	T_Broadcastclient,	FOLLBY_TOKEN },
     38 { "broadcastdelay",	T_Broadcastdelay,	FOLLBY_TOKEN },
     39 { "calldelay",		T_Calldelay,		FOLLBY_TOKEN },
     40 { "disable",		T_Disable,		FOLLBY_TOKEN },
     41 { "driftfile",		T_Driftfile,		FOLLBY_STRING },
     42 { "enable",		T_Enable,		FOLLBY_TOKEN },
     43 { "end",		T_End,			FOLLBY_TOKEN },
     44 { "filegen",		T_Filegen,		FOLLBY_TOKEN },
     45 { "fudge",		T_Fudge,		FOLLBY_STRING },
     46 { "includefile",	T_Includefile,		FOLLBY_STRING },
     47 { "leapfile",		T_Leapfile,		FOLLBY_STRING },
     48 { "logconfig",		T_Logconfig,		FOLLBY_STRINGS_TO_EOC },
     49 { "logfile",		T_Logfile,		FOLLBY_STRING },
     50 { "manycastclient",	T_Manycastclient,	FOLLBY_STRING },
     51 { "manycastserver",	T_Manycastserver,	FOLLBY_STRINGS_TO_EOC },
     52 { "multicastclient",	T_Multicastclient,	FOLLBY_STRINGS_TO_EOC },
     53 { "peer",		T_Peer,			FOLLBY_STRING },
     54 { "phone",		T_Phone,		FOLLBY_STRINGS_TO_EOC },
     55 { "pidfile",		T_Pidfile,		FOLLBY_STRING },
     56 { "pool",		T_Pool,			FOLLBY_STRING },
     57 { "discard",		T_Discard,		FOLLBY_TOKEN },
     58 { "restrict",		T_Restrict,		FOLLBY_TOKEN },
     59 { "server",		T_Server,		FOLLBY_STRING },
     60 { "setvar",		T_Setvar,		FOLLBY_STRING },
     61 { "statistics",		T_Statistics,		FOLLBY_TOKEN },
     62 { "statsdir",		T_Statsdir,		FOLLBY_STRING },
     63 { "tick",		T_Tick,			FOLLBY_TOKEN },
     64 { "tinker",		T_Tinker,		FOLLBY_TOKEN },
     65 { "tos",		T_Tos,			FOLLBY_TOKEN },
     66 { "trap",		T_Trap,			FOLLBY_STRING },
     67 { "unconfig",		T_Unconfig,		FOLLBY_STRING },
     68 { "unpeer",		T_Unpeer,		FOLLBY_STRING },
     69 /* authentication_command */
     70 { "controlkey",		T_ControlKey,		FOLLBY_TOKEN },
     71 { "crypto",		T_Crypto,		FOLLBY_TOKEN },
     72 { "keys",		T_Keys,			FOLLBY_STRING },
     73 { "keysdir",		T_Keysdir,		FOLLBY_STRING },
     74 { "ntpsigndsocket",	T_NtpSignDsocket,	FOLLBY_STRING },
     75 { "requestkey",		T_Requestkey,		FOLLBY_TOKEN },
     76 { "revoke",		T_Revoke,		FOLLBY_TOKEN },
     77 { "trustedkey",		T_Trustedkey,		FOLLBY_TOKEN },
     78 /* IPv4/IPv6 protocol override flag */
     79 { "-4",			T_Ipv4_flag,		FOLLBY_TOKEN },
     80 { "-6",			T_Ipv6_flag,		FOLLBY_TOKEN },
     81 /* option */
     82 { "autokey",		T_Autokey,		FOLLBY_TOKEN },
     83 { "bias",		T_Bias,			FOLLBY_TOKEN },
     84 { "burst",		T_Burst,		FOLLBY_TOKEN },
     85 { "iburst",		T_Iburst,		FOLLBY_TOKEN },
     86 { "key",		T_Key,			FOLLBY_TOKEN },
     87 { "maxpoll",		T_Maxpoll,		FOLLBY_TOKEN },
     88 { "minpoll",		T_Minpoll,		FOLLBY_TOKEN },
     89 { "mode",		T_Mode,			FOLLBY_TOKEN },
     90 { "noselect",		T_Noselect,		FOLLBY_TOKEN },
     91 { "preempt",		T_Preempt,		FOLLBY_TOKEN },
     92 { "true",		T_True,			FOLLBY_TOKEN },
     93 { "prefer",		T_Prefer,		FOLLBY_TOKEN },
     94 { "ttl",		T_Ttl,			FOLLBY_TOKEN },
     95 { "version",		T_Version,		FOLLBY_TOKEN },
     96 { "xleave",		T_Xleave,		FOLLBY_TOKEN },
     97 /* crypto_command */
     98 { "host",		T_Host,			FOLLBY_STRING },
     99 { "ident",		T_Ident,		FOLLBY_STRING },
    100 { "pw",			T_Pw,			FOLLBY_STRING },
    101 { "randfile",		T_Randfile,		FOLLBY_STRING },
    102 { "sign",		T_Sign,			FOLLBY_STRING },
    103 { "digest",		T_Digest,		FOLLBY_STRING },
    104 /*** MONITORING COMMANDS ***/
    105 /* stat */
    106 { "clockstats",		T_Clockstats,		FOLLBY_TOKEN },
    107 { "cryptostats",	T_Cryptostats,		FOLLBY_TOKEN },
    108 { "loopstats",		T_Loopstats,		FOLLBY_TOKEN },
    109 { "peerstats",		T_Peerstats,		FOLLBY_TOKEN },
    110 { "rawstats",		T_Rawstats,		FOLLBY_TOKEN },
    111 { "sysstats", 		T_Sysstats,		FOLLBY_TOKEN },
    112 { "protostats",		T_Protostats,		FOLLBY_TOKEN },
    113 { "timingstats",	T_Timingstats,		FOLLBY_TOKEN },
    114 /* filegen_option */
    115 { "file",		T_File,			FOLLBY_STRING },
    116 { "link",		T_Link,			FOLLBY_TOKEN },
    117 { "nolink",		T_Nolink,		FOLLBY_TOKEN },
    118 { "type",		T_Type,			FOLLBY_TOKEN },
    119 /* filegen_type */
    120 { "age",		T_Age,			FOLLBY_TOKEN },
    121 { "day",		T_Day,			FOLLBY_TOKEN },
    122 { "month",		T_Month,		FOLLBY_TOKEN },
    123 { "none",		T_None,			FOLLBY_TOKEN },
    124 { "pid",		T_Pid,			FOLLBY_TOKEN },
    125 { "week",		T_Week,			FOLLBY_TOKEN },
    126 { "year",		T_Year,			FOLLBY_TOKEN },
    127 /*** ORPHAN MODE COMMANDS ***/
    128 /* tos_option */
    129 { "minclock",		T_Minclock,		FOLLBY_TOKEN },
    130 { "maxclock",		T_Maxclock,		FOLLBY_TOKEN },
    131 { "minsane",		T_Minsane,		FOLLBY_TOKEN },
    132 { "floor",		T_Floor,		FOLLBY_TOKEN },
    133 { "ceiling",		T_Ceiling,		FOLLBY_TOKEN },
    134 { "cohort",		T_Cohort,		FOLLBY_TOKEN },
    135 { "mindist",		T_Mindist,		FOLLBY_TOKEN },
    136 { "maxdist",		T_Maxdist,		FOLLBY_TOKEN },
    137 { "beacon",		T_Beacon,		FOLLBY_TOKEN },
    138 { "orphan",		T_Orphan,		FOLLBY_TOKEN },
    139 /* access_control_flag */
    140 { "default",		T_Default,		FOLLBY_TOKEN },
    141 { "flake",		T_Flake,		FOLLBY_TOKEN },
    142 { "ignore",		T_Ignore,		FOLLBY_TOKEN },
    143 { "limited",		T_Limited,		FOLLBY_TOKEN },
    144 { "mssntp",		T_Mssntp,		FOLLBY_TOKEN },
    145 { "kod",		T_Kod,			FOLLBY_TOKEN },
    146 { "lowpriotrap",	T_Lowpriotrap,		FOLLBY_TOKEN },
    147 { "mask",		T_Mask,			FOLLBY_TOKEN },
    148 { "nomodify",		T_Nomodify,		FOLLBY_TOKEN },
    149 { "nopeer",		T_Nopeer,		FOLLBY_TOKEN },
    150 { "noquery",		T_Noquery,		FOLLBY_TOKEN },
    151 { "noserve",		T_Noserve,		FOLLBY_TOKEN },
    152 { "notrap",		T_Notrap,		FOLLBY_TOKEN },
    153 { "notrust",		T_Notrust,		FOLLBY_TOKEN },
    154 { "ntpport",		T_Ntpport,		FOLLBY_TOKEN },
    155 /* discard_option */
    156 { "average",		T_Average,		FOLLBY_TOKEN },
    157 { "minimum",		T_Minimum,		FOLLBY_TOKEN },
    158 { "monitor",		T_Monitor,		FOLLBY_TOKEN },
    159 /* fudge_factor */
    160 { "flag1",		T_Flag1,		FOLLBY_TOKEN },
    161 { "flag2",		T_Flag2,		FOLLBY_TOKEN },
    162 { "flag3",		T_Flag3,		FOLLBY_TOKEN },
    163 { "flag4",		T_Flag4,		FOLLBY_TOKEN },
    164 { "refid",		T_Refid,		FOLLBY_STRING },
    165 { "stratum",		T_Stratum,		FOLLBY_TOKEN },
    166 { "time1",		T_Time1,		FOLLBY_TOKEN },
    167 { "time2",		T_Time2,		FOLLBY_TOKEN },
    168 /* system_option */
    169 { "auth",		T_Auth,			FOLLBY_TOKEN },
    170 { "bclient",		T_Bclient,		FOLLBY_TOKEN },
    171 { "calibrate",		T_Calibrate,		FOLLBY_TOKEN },
    172 { "kernel",		T_Kernel,		FOLLBY_TOKEN },
    173 { "ntp",		T_Ntp,			FOLLBY_TOKEN },
    174 { "stats",		T_Stats,		FOLLBY_TOKEN },
    175 /* tinker_option */
    176 { "step",		T_Step,			FOLLBY_TOKEN },
    177 { "panic",		T_Panic,		FOLLBY_TOKEN },
    178 { "dispersion",		T_Dispersion,		FOLLBY_TOKEN },
    179 { "stepout",		T_Stepout,		FOLLBY_TOKEN },
    180 { "allan",		T_Allan,		FOLLBY_TOKEN },
    181 { "huffpuff",		T_Huffpuff,		FOLLBY_TOKEN },
    182 { "freq",		T_Freq,			FOLLBY_TOKEN },
    183 /* miscellaneous_command */
    184 { "port",		T_Port,			FOLLBY_TOKEN },
    185 { "interface",		T_Interface,		FOLLBY_TOKEN },
    186 { "qos",		T_Qos,			FOLLBY_TOKEN },
    187 { "saveconfigdir",	T_Saveconfigdir,	FOLLBY_STRING },
    188 /* interface_command (ignore and interface already defined) */
    189 { "nic",		T_Nic,			FOLLBY_TOKEN },
    190 { "all",		T_All,			FOLLBY_TOKEN },
    191 { "ipv4",		T_Ipv4,			FOLLBY_TOKEN },
    192 { "ipv6",		T_Ipv6,			FOLLBY_TOKEN },
    193 { "wildcard",		T_Wildcard,		FOLLBY_TOKEN },
    194 { "listen",		T_Listen,		FOLLBY_TOKEN },
    195 { "drop",		T_Drop,			FOLLBY_TOKEN },
    196 /* simulator commands */
    197 { "simulate",		T_Simulate,		FOLLBY_TOKEN },
    198 { "simulation_duration",T_Sim_Duration,		FOLLBY_TOKEN },
    199 { "beep_delay",		T_Beep_Delay,		FOLLBY_TOKEN },
    200 { "duration",		T_Duration,		FOLLBY_TOKEN },
    201 { "server_offset",	T_Server_Offset,	FOLLBY_TOKEN },
    202 { "freq_offset",	T_Freq_Offset,		FOLLBY_TOKEN },
    203 { "wander",		T_Wander,		FOLLBY_TOKEN },
    204 { "jitter",		T_Jitter,		FOLLBY_TOKEN },
    205 { "prop_delay",		T_Prop_Delay,		FOLLBY_TOKEN },
    206 { "proc_delay",		T_Proc_Delay,		FOLLBY_TOKEN },
    207 };
    208 
    209 
    210 typedef struct big_scan_state_tag {
    211 	char	ch;		/* Character this state matches on */
    212 	char	followedby;	/* Forces next token(s) to T_String */
    213 	u_short	finishes_token;	/* nonzero ID if last keyword char */
    214 	u_short	match_next_s;	/* next state to check matching ch */
    215 	u_short	other_next_s;	/* next state to check if not ch */
    216 } big_scan_state;
    217 
    218 /*
    219  * Note: to increase MAXSTATES beyond 2048, be aware it is currently
    220  * crammed into 11 bits in scan_state form.  Raising to 4096 would be
    221  * relatively easy by storing the followedby value in a separate
    222  * array with one entry per token, and shrinking the char value to
    223  * 7 bits to free a bit for accepting/non-accepting.  More than 4096
    224  * states will require expanding scan_state beyond 32 bits each.
    225  */
    226 #define MAXSTATES 2048
    227 
    228 const char *	current_keyword;/* for error reporting */
    229 big_scan_state	sst[MAXSTATES];	/* scanner FSM state entries */
    230 int		sst_highwater;	/* next entry index to consider */
    231 char *		symb[1024];	/* map token ID to symbolic name */
    232 
    233 /* for libntp */
    234 const char *	progname = "keyword-gen";
    235 volatile int	debug = 1;
    236 
    237 int		main			(int, char **);
    238 static void	generate_preamble	(void);
    239 static void	generate_fsm		(void);
    240 static void	generate_token_text	(void);
    241 static int	create_keyword_scanner	(void);
    242 static int	create_scan_states	(char *, int, follby, int);
    243 int		compare_key_tok_id	(QSORTP, QSORTP);
    244 int		compare_key_tok_text	(QSORTP, QSORTP);
    245 void		populate_symb		(char *);
    246 const char *	symbname		(int);
    247 
    248 
    249 int main(int argc, char **argv)
    250 {
    251 	if (argc < 2) {
    252 		fprintf(stderr, "Usage:\n%s t_header.h\n", argv[0]);
    253 		exit(1);
    254 	}
    255 	populate_symb(argv[1]);
    256 
    257 	generate_preamble();
    258 	generate_token_text();
    259 	generate_fsm();
    260 
    261 	return 0;
    262 }
    263 
    264 
    265 static void
    266 generate_preamble(void)
    267 {
    268 	time_t now;
    269 	char timestamp[128];
    270 	char preamble[] =
    271 "/*\n"
    272 " * ntp_keyword.h\n"
    273 " * \n"
    274 " * NOTE: edit this file with caution, it is generated by keyword-gen.c\n"
    275 " *\t Generated %s UTC	  diff_ignore_line\n"
    276 " *\n"
    277 " */\n"
    278 "#include \"ntp_scanner.h\"\n"
    279 "#include \"ntp_parser.h\"\n"
    280 "\n";
    281 
    282 	time(&now);
    283 	if (!strftime(timestamp, sizeof(timestamp),
    284 		      "%Y-%m-%d %H:%M:%S", gmtime(&now)))
    285 		timestamp[0] = '\0';
    286 
    287 	printf(preamble, timestamp);
    288 }
    289 
    290 
    291 static void
    292 generate_fsm(void)
    293 {
    294 	char token_id_comment[128];
    295 	int initial_state;
    296 	int i;
    297 	int token;
    298 
    299 	/*
    300 	 * Sort ntp_keywords in alphabetical keyword order.  This is
    301 	 * not necessary, but minimizes nonfunctional changes in the
    302 	 * generated finite state machine when keywords are modified.
    303 	 */
    304 	qsort(ntp_keywords, COUNTOF(ntp_keywords),
    305 	      sizeof(ntp_keywords[0]), compare_key_tok_text);
    306 
    307 	/*
    308 	 * To save space, reserve the state array entry matching each
    309 	 * token number for its terminal state, so the token identifier
    310 	 * does not need to be stored in each state, but can be
    311 	 * recovered trivially.  To mark the entry reserved,
    312 	 * finishes_token is nonzero.
    313 	 */
    314 
    315 	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
    316 		token = ntp_keywords[i].token;
    317 		if (1 > token || token >= COUNTOF(sst)) {
    318 			fprintf(stderr,
    319 				"keyword-gen sst[%u] too small "
    320 				"for keyword '%s' id %d\n",
    321 				COUNTOF(sst),
    322 				ntp_keywords[i].key,
    323 				token);
    324 			exit(4);
    325 		}
    326 		sst[token].finishes_token = token;
    327 	}
    328 
    329 	initial_state = create_keyword_scanner();
    330 
    331 	fprintf(stderr,
    332 		"%d keywords consumed %d states of %d max.\n",
    333 		(int)COUNTOF(ntp_keywords),
    334 		sst_highwater - 1,
    335 		(int)COUNTOF(sst) - 1);
    336 
    337 	printf("#define SCANNER_INIT_S %d\n\n", initial_state);
    338 
    339 	printf("const scan_state sst[%d] = {\n"
    340 	       "/*SS_T( ch,\tf-by, match, other ),\t\t\t\t */\n"
    341 	       "  0,\t\t\t\t      /* %5d %-17s */\n",
    342 	       sst_highwater,
    343 	       0, "");
    344 
    345 	for (i = 1; i < sst_highwater; i++) {
    346 
    347 		/* verify fields will fit */
    348 		if (sst[i].followedby & ~0x3) {
    349 			fprintf(stderr,
    350 				"keyword-gen internal error "
    351 				"sst[%d].followedby %d too big\n",
    352 				i, sst[i].followedby);
    353 			exit(7);
    354 		}
    355 
    356 		if (sst_highwater <= sst[i].match_next_s
    357 		    || sst[i].match_next_s & ~0x7ff) {
    358 			fprintf(stderr,
    359 				"keyword-gen internal error "
    360 				"sst[%d].match_next_s %d too big\n",
    361 				i, sst[i].match_next_s);
    362 			exit(8);
    363 		}
    364 
    365 		if (sst_highwater <= sst[i].other_next_s
    366 		    || sst[i].other_next_s & ~0x7ff) {
    367 			fprintf(stderr,
    368 				"keyword-gen internal error "
    369 				"sst[%d].other_next_s %d too big\n",
    370 				i, sst[i].other_next_s);
    371 			exit(9);
    372 		}
    373 
    374 		if (!sst[i].finishes_token)
    375 			snprintf(token_id_comment,
    376 				 sizeof(token_id_comment), "%5d %-17s",
    377 				 i, (initial_state == i)
    378 					? "initial state"
    379 					: "");
    380 		else {
    381 			snprintf(token_id_comment,
    382 				 sizeof(token_id_comment), "%5d %-17s",
    383 				 i, symbname(sst[i].finishes_token));
    384 			if (i != sst[i].finishes_token) {
    385 				fprintf(stderr,
    386 					"keyword-gen internal error "
    387 					"entry %d finishes token %d\n",
    388 					i, sst[i].finishes_token);
    389 				exit(5);
    390 			}
    391 		}
    392 
    393 		printf("  S_ST( '%c',\t%d,    %5u, %5u )%s /* %s */\n",
    394 		       sst[i].ch,
    395 		       sst[i].followedby,
    396 		       sst[i].match_next_s,
    397 		       sst[i].other_next_s,
    398 		       (i + 1 < sst_highwater)
    399 			   ? ","
    400 			   : " ",
    401 		       token_id_comment);
    402 	}
    403 
    404 	printf("};\n\n");
    405 }
    406 
    407 
    408 /* Define a function to create the states of the scanner. This function
    409  * is used by the create_keyword_scanner function below.
    410  *
    411  * This function takes a suffix of a keyword, the token to be returned on
    412  * recognizing the complete keyword, and any pre-existing state that exists
    413  * for some other keyword that has the same prefix as the current one.
    414  */
    415 static int
    416 create_scan_states(
    417 	char *	text,
    418 	int	token,
    419 	follby	followedby,
    420 	int	prev_state
    421 	)
    422 {
    423 	int my_state;
    424 	int return_state;
    425 	int prev_char_s;
    426 	int curr_char_s;
    427 
    428 	return_state = prev_state;
    429 	curr_char_s = prev_state;
    430 	prev_char_s = 0;
    431 
    432 	/* Find the correct position to insert the state.
    433 	 * All states should be in alphabetical order
    434 	 */
    435 	while (curr_char_s && (text[0] < sst[curr_char_s].ch)) {
    436 		prev_char_s = curr_char_s;
    437 		curr_char_s = sst[curr_char_s].other_next_s;
    438 	}
    439 
    440 	/*
    441 	 * Check if a previously seen keyword has the same prefix as
    442 	 * the current keyword.  If so, simply use the state for that
    443 	 * keyword as my_state, otherwise, allocate a new state.
    444 	 */
    445 	if (curr_char_s && (text[0] == sst[curr_char_s].ch)) {
    446 		my_state = curr_char_s;
    447 		if ('\0' == text[1]) {
    448 			fprintf(stderr,
    449 				"Duplicate entries for keyword '%s' in"
    450 				" keyword_gen.c ntp_keywords[].\n",
    451 				current_keyword);
    452 			exit(2);
    453 		}
    454 	} else {
    455 		do
    456 			my_state = sst_highwater++;
    457 		while (my_state < COUNTOF(sst)
    458 		       && sst[my_state].finishes_token);
    459 		if (my_state >= COUNTOF(sst)) {
    460 			fprintf(stderr,
    461 				"fatal, keyword scanner state array "
    462 				"sst[%d] is too small, modify\n"
    463 				"keyword-gen.c to increase.\n",
    464 				(int)COUNTOF(sst));
    465 			exit(3);
    466 		}
    467 		/* Store the next character of the keyword */
    468 		sst[my_state].ch = text[0];
    469 		sst[my_state].other_next_s = curr_char_s;
    470 		sst[my_state].followedby = FOLLBY_NON_ACCEPTING;
    471 
    472 		if (prev_char_s)
    473 			sst[prev_char_s].other_next_s = my_state;
    474 		else
    475 			return_state = my_state;
    476 	}
    477 
    478 	/* Check if the next character is '\0'.
    479 	 * If yes, we are done with the recognition and this is an accepting
    480 	 * state.
    481 	 * If not, we need to continue scanning
    482 	 */
    483 	if ('\0' == text[1]) {
    484 		sst[my_state].finishes_token = (u_short)token;
    485 		sst[my_state].followedby = (char)followedby;
    486 
    487 		if (sst[token].finishes_token != (u_short)token) {
    488 			fprintf(stderr,
    489 				"fatal, sst[%d] not reserved for %s.\n",
    490 				token, symbname(token));
    491 			exit(6);
    492 		}
    493 		/* relocate so token id is sst[] index */
    494 		if (my_state != token) {
    495 			sst[token] = sst[my_state];
    496 			memset(&sst[my_state], 0,
    497 			       sizeof(sst[my_state]));
    498 			do
    499 				sst_highwater--;
    500 			while (sst[sst_highwater].finishes_token);
    501 			my_state = token;
    502 			if (prev_char_s)
    503 				sst[prev_char_s].other_next_s = my_state;
    504 			else
    505 				return_state = my_state;
    506 		}
    507 	} else
    508 		sst[my_state].match_next_s =
    509 		    create_scan_states(
    510 			&text[1],
    511 			token,
    512 			followedby,
    513 			sst[my_state].match_next_s);
    514 
    515 	return return_state;
    516 }
    517 
    518 
    519 /* Define a function that takes a list of (keyword, token) values and
    520  * creates a keywords scanner out of it.
    521  */
    522 
    523 static int
    524 create_keyword_scanner(void)
    525 {
    526 	int scanner;
    527 	int i;
    528 
    529 	sst_highwater = 1;	/* index 0 invalid, unused */
    530 	scanner = 0;
    531 
    532 	for (i = 0; i < COUNTOF(ntp_keywords); i++) {
    533 		current_keyword = ntp_keywords[i].key;
    534 		scanner =
    535 		    create_scan_states(
    536 			ntp_keywords[i].key,
    537 			ntp_keywords[i].token,
    538 			ntp_keywords[i].followedby,
    539 			scanner);
    540 	}
    541 
    542 	return scanner;
    543 }
    544 
    545 
    546 static void
    547 generate_token_text(void)
    548 {
    549 	int lowest_id;
    550 	int highest_id;
    551 	int id_count;
    552 	int id;
    553 	int i;
    554 
    555 	/* sort ntp_keywords in token ID order */
    556 	qsort(ntp_keywords, COUNTOF(ntp_keywords),
    557 	      sizeof(ntp_keywords[0]), compare_key_tok_id);
    558 
    559 	lowest_id = ntp_keywords[0].token;
    560 	highest_id = ntp_keywords[COUNTOF(ntp_keywords) - 1].token;
    561 	id_count = highest_id - lowest_id + 1;
    562 
    563 	printf("#define LOWEST_KEYWORD_ID %d\n\n", lowest_id);
    564 
    565 	printf("const char * const keyword_text[%d] = {", id_count);
    566 
    567 	id = lowest_id;
    568 	i = 0;
    569 	while (i < COUNTOF(ntp_keywords)) {
    570 		while (id < ntp_keywords[i].token) {
    571 			printf(",\n\t/* %-5d %5d %20s */\tNULL",
    572 			       id - lowest_id, id, symbname(id));
    573 			id++;
    574 		}
    575 		if (i > 0)
    576 			printf(",");
    577 		printf("\n\t/* %-5d %5d %20s */\t\"%s\"",
    578 		       id - lowest_id, id, symbname(id),
    579 		       ntp_keywords[i].key);
    580 		i++;
    581 		id++;
    582 	}
    583 
    584 	printf("\n};\n\n");
    585 }
    586 
    587 
    588 int
    589 compare_key_tok_id(
    590 	QSORTP a1,
    591 	QSORTP a2
    592 	)
    593 {
    594 	const struct key_tok *p1 = (const void *)a1;
    595 	const struct key_tok *p2 = (const void *)a2;
    596 
    597 	if (p1->token == p2->token)
    598 		return 0;
    599 
    600 	if (p1->token < p2->token)
    601 		return -1;
    602 	else
    603 		return 1;
    604 }
    605 
    606 
    607 int
    608 compare_key_tok_text(
    609 	QSORTP a1,
    610 	QSORTP a2
    611 	)
    612 {
    613 	const struct key_tok *p1 = (const void *)a1;
    614 	const struct key_tok *p2 = (const void *)a2;
    615 
    616 	return strcmp(p1->key, p2->key);
    617 }
    618 
    619 
    620 /*
    621  * populate_symb() - populate symb[] lookup array with symbolic token
    622  *		     names such that symb[T_Age] == "T_Age", etc.
    623  */
    624 void
    625 populate_symb(
    626 	char *header_file
    627 	)
    628 {
    629 	FILE *	yh;
    630 	char	line[128];
    631 	char	name[128];
    632 	int	token;
    633 
    634 	yh = fopen(header_file, "r");
    635 	if (NULL == yh) {
    636 		perror("unable to open yacc/bison header file");
    637 		exit(4);
    638 	}
    639 
    640 	while (NULL != fgets(line, sizeof(line), yh))
    641 		if (2 == sscanf(line, "#define %s %d", name, &token)
    642 		    && 'T' == name[0] && '_' == name[1] && token >= 0
    643 		    && token < COUNTOF(symb))
    644 
    645 			symb[token] = estrdup(name);
    646 
    647 	fclose(yh);
    648 }
    649 
    650 
    651 const char *
    652 symbname(
    653 	int token
    654 	)
    655 {
    656 	char *name;
    657 
    658 	if (token >= 0 && token < COUNTOF(symb) && symb[token] != NULL)
    659 		return symb[token];
    660 
    661 	LIB_GETBUF(name);
    662 	snprintf(name, LIB_BUFLENGTH, "%d", token);
    663 	return name;
    664 }
    665