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