parse.y 14 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702
  1. /* parse.y - parser for flex input */
  2. %token CHAR NUMBER SECTEND SCDECL XSCDECL WHITESPACE NAME PREVCCL EOF_OP
  3. %{
  4. /*-
  5. * Copyright (c) 1990 The Regents of the University of California.
  6. * All rights reserved.
  7. *
  8. * This code is derived from software contributed to Berkeley by
  9. * Vern Paxson.
  10. *
  11. * The United States Government has rights in this work pursuant
  12. * to contract no. DE-AC03-76SF00098 between the United States
  13. * Department of Energy and the University of California.
  14. *
  15. * Redistribution and use in source and binary forms are permitted provided
  16. * that: (1) source distributions retain this entire copyright notice and
  17. * comment, and (2) distributions including binaries display the following
  18. * acknowledgement: ``This product includes software developed by the
  19. * University of California, Berkeley and its contributors'' in the
  20. * documentation or other materials provided with the distribution and in
  21. * all advertising materials mentioning features or use of this software.
  22. * Neither the name of the University nor the names of its contributors may
  23. * be used to endorse or promote products derived from this software without
  24. * specific prior written permission.
  25. * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR IMPLIED
  26. * WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED WARRANTIES OF
  27. * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
  28. */
  29. #ifndef lint
  30. static char rcsid[] =
  31. "@(#) $Id$ (LBL)";
  32. #endif
  33. #include "flexdef.h"
  34. int pat, scnum, eps, headcnt, trailcnt, anyccl, lastchar, i, actvp, rulelen;
  35. int trlcontxt, xcluflg, cclsorted, varlength, variable_trail_rule;
  36. Char clower();
  37. static int madeany = false; /* whether we've made the '.' character class */
  38. int previous_continued_action; /* whether the previous rule's action was '|' */
  39. %}
  40. %%
  41. goal : initlex sect1 sect1end sect2 initforrule
  42. { /* add default rule */
  43. int def_rule;
  44. pat = cclinit();
  45. cclnegate( pat );
  46. def_rule = mkstate( -pat );
  47. finish_rule( def_rule, false, 0, 0 );
  48. for ( i = 1; i <= lastsc; ++i )
  49. scset[i] = mkbranch( scset[i], def_rule );
  50. if ( spprdflt )
  51. fputs( "YY_FATAL_ERROR( \"flex scanner jammed\" )",
  52. temp_action_file );
  53. else
  54. fputs( "ECHO", temp_action_file );
  55. fputs( ";\n\tYY_BREAK\n", temp_action_file );
  56. }
  57. ;
  58. initlex :
  59. {
  60. /* initialize for processing rules */
  61. /* create default DFA start condition */
  62. scinstal( "INITIAL", false );
  63. }
  64. ;
  65. sect1 : sect1 startconddecl WHITESPACE namelist1 '\n'
  66. |
  67. | error '\n'
  68. { synerr( "unknown error processing section 1" ); }
  69. ;
  70. sect1end : SECTEND
  71. ;
  72. startconddecl : SCDECL
  73. {
  74. /* these productions are separate from the s1object
  75. * rule because the semantics must be done before
  76. * we parse the remainder of an s1object
  77. */
  78. xcluflg = false;
  79. }
  80. | XSCDECL
  81. { xcluflg = true; }
  82. ;
  83. namelist1 : namelist1 WHITESPACE NAME
  84. { scinstal( nmstr, xcluflg ); }
  85. | NAME
  86. { scinstal( nmstr, xcluflg ); }
  87. | error
  88. { synerr( "bad start condition list" ); }
  89. ;
  90. sect2 : sect2 initforrule flexrule '\n'
  91. |
  92. ;
  93. initforrule :
  94. {
  95. /* initialize for a parse of one rule */
  96. trlcontxt = variable_trail_rule = varlength = false;
  97. trailcnt = headcnt = rulelen = 0;
  98. current_state_type = STATE_NORMAL;
  99. previous_continued_action = continued_action;
  100. new_rule();
  101. }
  102. ;
  103. flexrule : scon '^' rule
  104. {
  105. pat = $3;
  106. finish_rule( pat, variable_trail_rule,
  107. headcnt, trailcnt );
  108. for ( i = 1; i <= actvp; ++i )
  109. scbol[actvsc[i]] =
  110. mkbranch( scbol[actvsc[i]], pat );
  111. if ( ! bol_needed )
  112. {
  113. bol_needed = true;
  114. if ( performance_report )
  115. pinpoint_message(
  116. "'^' operator results in sub-optimal performance" );
  117. }
  118. }
  119. | scon rule
  120. {
  121. pat = $2;
  122. finish_rule( pat, variable_trail_rule,
  123. headcnt, trailcnt );
  124. for ( i = 1; i <= actvp; ++i )
  125. scset[actvsc[i]] =
  126. mkbranch( scset[actvsc[i]], pat );
  127. }
  128. | '^' rule
  129. {
  130. pat = $2;
  131. finish_rule( pat, variable_trail_rule,
  132. headcnt, trailcnt );
  133. /* add to all non-exclusive start conditions,
  134. * including the default (0) start condition
  135. */
  136. for ( i = 1; i <= lastsc; ++i )
  137. if ( ! scxclu[i] )
  138. scbol[i] = mkbranch( scbol[i], pat );
  139. if ( ! bol_needed )
  140. {
  141. bol_needed = true;
  142. if ( performance_report )
  143. pinpoint_message(
  144. "'^' operator results in sub-optimal performance" );
  145. }
  146. }
  147. | rule
  148. {
  149. pat = $1;
  150. finish_rule( pat, variable_trail_rule,
  151. headcnt, trailcnt );
  152. for ( i = 1; i <= lastsc; ++i )
  153. if ( ! scxclu[i] )
  154. scset[i] = mkbranch( scset[i], pat );
  155. }
  156. | scon EOF_OP
  157. { build_eof_action(); }
  158. | EOF_OP
  159. {
  160. /* this EOF applies to all start conditions
  161. * which don't already have EOF actions
  162. */
  163. actvp = 0;
  164. for ( i = 1; i <= lastsc; ++i )
  165. if ( ! sceof[i] )
  166. actvsc[++actvp] = i;
  167. if ( actvp == 0 )
  168. pinpoint_message(
  169. "warning - all start conditions already have <<EOF>> rules" );
  170. else
  171. build_eof_action();
  172. }
  173. | error
  174. { synerr( "unrecognized rule" ); }
  175. ;
  176. scon : '<' namelist2 '>'
  177. ;
  178. namelist2 : namelist2 ',' NAME
  179. {
  180. if ( (scnum = sclookup( nmstr )) == 0 )
  181. format_pinpoint_message(
  182. "undeclared start condition %s", nmstr );
  183. else
  184. actvsc[++actvp] = scnum;
  185. }
  186. | NAME
  187. {
  188. if ( (scnum = sclookup( nmstr )) == 0 )
  189. format_pinpoint_message(
  190. "undeclared start condition %s", nmstr );
  191. else
  192. actvsc[actvp = 1] = scnum;
  193. }
  194. | error
  195. { synerr( "bad start condition list" ); }
  196. ;
  197. rule : re2 re
  198. {
  199. if ( transchar[lastst[$2]] != SYM_EPSILON )
  200. /* provide final transition \now/ so it
  201. * will be marked as a trailing context
  202. * state
  203. */
  204. $2 = link_machines( $2, mkstate( SYM_EPSILON ) );
  205. mark_beginning_as_normal( $2 );
  206. current_state_type = STATE_NORMAL;
  207. if ( previous_continued_action )
  208. {
  209. /* we need to treat this as variable trailing
  210. * context so that the backup does not happen
  211. * in the action but before the action switch
  212. * statement. If the backup happens in the
  213. * action, then the rules "falling into" this
  214. * one's action will *also* do the backup,
  215. * erroneously.
  216. */
  217. if ( ! varlength || headcnt != 0 )
  218. {
  219. fprintf( stderr,
  220. "%s: warning - trailing context rule at line %d made variable because\n",
  221. program_name, linenum );
  222. fprintf( stderr,
  223. " of preceding '|' action\n" );
  224. }
  225. /* mark as variable */
  226. varlength = true;
  227. headcnt = 0;
  228. }
  229. if ( varlength && headcnt == 0 )
  230. { /* variable trailing context rule */
  231. /* mark the first part of the rule as the accepting
  232. * "head" part of a trailing context rule
  233. */
  234. /* by the way, we didn't do this at the beginning
  235. * of this production because back then
  236. * current_state_type was set up for a trail
  237. * rule, and add_accept() can create a new
  238. * state ...
  239. */
  240. add_accept( $1, num_rules | YY_TRAILING_HEAD_MASK );
  241. variable_trail_rule = true;
  242. }
  243. else
  244. trailcnt = rulelen;
  245. $$ = link_machines( $1, $2 );
  246. }
  247. | re2 re '$'
  248. { synerr( "trailing context used twice" ); }
  249. | re '$'
  250. {
  251. if ( trlcontxt )
  252. {
  253. synerr( "trailing context used twice" );
  254. $$ = mkstate( SYM_EPSILON );
  255. }
  256. else if ( previous_continued_action )
  257. {
  258. /* see the comment in the rule for "re2 re"
  259. * above
  260. */
  261. if ( ! varlength || headcnt != 0 )
  262. {
  263. fprintf( stderr,
  264. "%s: warning - trailing context rule at line %d made variable because\n",
  265. program_name, linenum );
  266. fprintf( stderr,
  267. " of preceding '|' action\n" );
  268. }
  269. /* mark as variable */
  270. varlength = true;
  271. headcnt = 0;
  272. }
  273. trlcontxt = true;
  274. if ( ! varlength )
  275. headcnt = rulelen;
  276. ++rulelen;
  277. trailcnt = 1;
  278. eps = mkstate( SYM_EPSILON );
  279. $$ = link_machines( $1,
  280. link_machines( eps, mkstate( '\n' ) ) );
  281. }
  282. | re
  283. {
  284. $$ = $1;
  285. if ( trlcontxt )
  286. {
  287. if ( varlength && headcnt == 0 )
  288. /* both head and trail are variable-length */
  289. variable_trail_rule = true;
  290. else
  291. trailcnt = rulelen;
  292. }
  293. }
  294. ;
  295. re : re '|' series
  296. {
  297. varlength = true;
  298. $$ = mkor( $1, $3 );
  299. }
  300. | series
  301. { $$ = $1; }
  302. ;
  303. re2 : re '/'
  304. {
  305. /* this rule is written separately so
  306. * the reduction will occur before the trailing
  307. * series is parsed
  308. */
  309. if ( trlcontxt )
  310. synerr( "trailing context used twice" );
  311. else
  312. trlcontxt = true;
  313. if ( varlength )
  314. /* we hope the trailing context is fixed-length */
  315. varlength = false;
  316. else
  317. headcnt = rulelen;
  318. rulelen = 0;
  319. current_state_type = STATE_TRAILING_CONTEXT;
  320. $$ = $1;
  321. }
  322. ;
  323. series : series singleton
  324. {
  325. /* this is where concatenation of adjacent patterns
  326. * gets done
  327. */
  328. $$ = link_machines( $1, $2 );
  329. }
  330. | singleton
  331. { $$ = $1; }
  332. ;
  333. singleton : singleton '*'
  334. {
  335. varlength = true;
  336. $$ = mkclos( $1 );
  337. }
  338. | singleton '+'
  339. {
  340. varlength = true;
  341. $$ = mkposcl( $1 );
  342. }
  343. | singleton '?'
  344. {
  345. varlength = true;
  346. $$ = mkopt( $1 );
  347. }
  348. | singleton '{' NUMBER ',' NUMBER '}'
  349. {
  350. varlength = true;
  351. if ( $3 > $5 || $3 < 0 )
  352. {
  353. synerr( "bad iteration values" );
  354. $$ = $1;
  355. }
  356. else
  357. {
  358. if ( $3 == 0 )
  359. $$ = mkopt( mkrep( $1, $3, $5 ) );
  360. else
  361. $$ = mkrep( $1, $3, $5 );
  362. }
  363. }
  364. | singleton '{' NUMBER ',' '}'
  365. {
  366. varlength = true;
  367. if ( $3 <= 0 )
  368. {
  369. synerr( "iteration value must be positive" );
  370. $$ = $1;
  371. }
  372. else
  373. $$ = mkrep( $1, $3, INFINITY );
  374. }
  375. | singleton '{' NUMBER '}'
  376. {
  377. /* the singleton could be something like "(foo)",
  378. * in which case we have no idea what its length
  379. * is, so we punt here.
  380. */
  381. varlength = true;
  382. if ( $3 <= 0 )
  383. {
  384. synerr( "iteration value must be positive" );
  385. $$ = $1;
  386. }
  387. else
  388. $$ = link_machines( $1, copysingl( $1, $3 - 1 ) );
  389. }
  390. | '.'
  391. {
  392. if ( ! madeany )
  393. {
  394. /* create the '.' character class */
  395. anyccl = cclinit();
  396. ccladd( anyccl, '\n' );
  397. cclnegate( anyccl );
  398. if ( useecs )
  399. mkeccl( ccltbl + cclmap[anyccl],
  400. ccllen[anyccl], nextecm,
  401. ecgroup, csize, csize );
  402. madeany = true;
  403. }
  404. ++rulelen;
  405. $$ = mkstate( -anyccl );
  406. }
  407. | fullccl
  408. {
  409. if ( ! cclsorted )
  410. /* sort characters for fast searching. We use a
  411. * shell sort since this list could be large.
  412. */
  413. cshell( ccltbl + cclmap[$1], ccllen[$1], true );
  414. if ( useecs )
  415. mkeccl( ccltbl + cclmap[$1], ccllen[$1],
  416. nextecm, ecgroup, csize, csize );
  417. ++rulelen;
  418. $$ = mkstate( -$1 );
  419. }
  420. | PREVCCL
  421. {
  422. ++rulelen;
  423. $$ = mkstate( -$1 );
  424. }
  425. | '"' string '"'
  426. { $$ = $2; }
  427. | '(' re ')'
  428. { $$ = $2; }
  429. | CHAR
  430. {
  431. ++rulelen;
  432. if ( caseins && $1 >= 'A' && $1 <= 'Z' )
  433. $1 = clower( $1 );
  434. $$ = mkstate( $1 );
  435. }
  436. ;
  437. fullccl : '[' ccl ']'
  438. { $$ = $2; }
  439. | '[' '^' ccl ']'
  440. {
  441. /* *Sigh* - to be compatible Unix lex, negated ccls
  442. * match newlines
  443. */
  444. #ifdef NOTDEF
  445. ccladd( $3, '\n' ); /* negated ccls don't match '\n' */
  446. cclsorted = false; /* because we added the newline */
  447. #endif
  448. cclnegate( $3 );
  449. $$ = $3;
  450. }
  451. ;
  452. ccl : ccl CHAR '-' CHAR
  453. {
  454. if ( $2 > $4 )
  455. synerr( "negative range in character class" );
  456. else
  457. {
  458. if ( caseins )
  459. {
  460. if ( $2 >= 'A' && $2 <= 'Z' )
  461. $2 = clower( $2 );
  462. if ( $4 >= 'A' && $4 <= 'Z' )
  463. $4 = clower( $4 );
  464. }
  465. for ( i = $2; i <= $4; ++i )
  466. ccladd( $1, i );
  467. /* keep track if this ccl is staying in alphabetical
  468. * order
  469. */
  470. cclsorted = cclsorted && ($2 > lastchar);
  471. lastchar = $4;
  472. }
  473. $$ = $1;
  474. }
  475. | ccl CHAR
  476. {
  477. if ( caseins )
  478. if ( $2 >= 'A' && $2 <= 'Z' )
  479. $2 = clower( $2 );
  480. ccladd( $1, $2 );
  481. cclsorted = cclsorted && ($2 > lastchar);
  482. lastchar = $2;
  483. $$ = $1;
  484. }
  485. |
  486. {
  487. cclsorted = true;
  488. lastchar = 0;
  489. $$ = cclinit();
  490. }
  491. ;
  492. string : string CHAR
  493. {
  494. if ( caseins )
  495. if ( $2 >= 'A' && $2 <= 'Z' )
  496. $2 = clower( $2 );
  497. ++rulelen;
  498. $$ = link_machines( $1, mkstate( $2 ) );
  499. }
  500. |
  501. { $$ = mkstate( SYM_EPSILON ); }
  502. ;
  503. %%
  504. /* build_eof_action - build the "<<EOF>>" action for the active start
  505. * conditions
  506. */
  507. void build_eof_action()
  508. {
  509. register int i;
  510. for ( i = 1; i <= actvp; ++i )
  511. {
  512. if ( sceof[actvsc[i]] )
  513. format_pinpoint_message(
  514. "multiple <<EOF>> rules for start condition %s",
  515. scname[actvsc[i]] );
  516. else
  517. {
  518. sceof[actvsc[i]] = true;
  519. fprintf( temp_action_file, "case YY_STATE_EOF(%s):\n",
  520. scname[actvsc[i]] );
  521. }
  522. }
  523. line_directive_out( temp_action_file );
  524. }
  525. /* synerr - report a syntax error */
  526. void synerr( str )
  527. char str[];
  528. {
  529. syntaxerror = true;
  530. pinpoint_message( str );
  531. }
  532. /* format_pinpoint_message - write out a message formatted with one string,
  533. * pinpointing its location
  534. */
  535. void format_pinpoint_message( msg, arg )
  536. char msg[], arg[];
  537. {
  538. char errmsg[MAXLINE];
  539. (void) sprintf( errmsg, msg, arg );
  540. pinpoint_message( errmsg );
  541. }
  542. /* pinpoint_message - write out a message, pinpointing its location */
  543. void pinpoint_message( str )
  544. char str[];
  545. {
  546. fprintf( stderr, "\"%s\", line %d: %s\n", infilename, linenum, str );
  547. }
  548. /* yyerror - eat up an error message from the parser;
  549. * currently, messages are ignore
  550. */
  551. void yyerror( msg )
  552. char msg[];
  553. {
  554. }