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