home *** CD-ROM | disk | FTP | other *** search
open in: 
MacOS 8.1
|
Win98
|
DOS
browse contents |
view JSON data
|
view as text
This file was processed as: SHell self-extracting ARchive
(archive/shar).
| Confidence | Program | Detection | Match Type | Support
|
|---|
| 100%
| dexvert
| Newsgroup Content (archive/news)
| magic
| Supported |
| 100%
| dexvert
| SHell self-extracting ARchive (archive/shar)
| magic
| Supported |
| 100%
| dexvert
| Internet Message Format (text/imf)
| magic
| Supported |
| 1%
| dexvert
| Text File (text/txt)
| fallback
| Supported |
| 100%
| file
| news or mail, ASCII text
| default
| |
| 100%
| checkBytes
| Printable ASCII
| default
| |
| 100%
| perlTextCheck
| Likely Text (Perl)
| default
| |
| 100%
| siegfried
| fmt/329 Shell Archive Format
| default
| |
| 100%
| detectItEasy
| Format: plain text[LF]
| default (weak)
| |
| 100%
| xdgMime
| message/rfc822
| default
|
|
hex view+--------+-------------------------+-------------------------+--------+--------+
|00000000| 53 75 62 6a 65 63 74 3a | 20 20 76 32 33 69 30 34 |Subject:| v23i04|
|00000010| 32 3a 20 20 46 6c 65 78 | 2c 20 61 20 66 61 73 74 |2: Flex|, a fast|
|00000020| 20 6c 65 78 20 72 65 70 | 6c 61 63 65 6d 65 6e 74 | lex rep|lacement|
|00000030| 2c 20 50 61 72 74 30 36 | 2f 31 30 0a 4e 65 77 73 |, Part06|/10.News|
|00000040| 67 72 6f 75 70 73 3a 20 | 63 6f 6d 70 2e 73 6f 75 |groups: |comp.sou|
|00000050| 72 63 65 73 2e 75 6e 69 | 78 0a 41 70 70 72 6f 76 |rces.uni|x.Approv|
|00000060| 65 64 3a 20 72 73 61 6c | 7a 40 75 75 6e 65 74 2e |ed: rsal|z@uunet.|
|00000070| 55 55 2e 4e 45 54 0a 58 | 2d 43 68 65 63 6b 73 75 |UU.NET.X|-Checksu|
|00000080| 6d 2d 53 6e 65 66 72 75 | 3a 20 66 37 65 65 34 38 |m-Snefru|: f7ee48|
|00000090| 64 34 20 65 63 31 64 31 | 37 37 66 20 39 34 33 37 |d4 ec1d1|77f 9437|
|000000a0| 64 63 63 33 20 34 34 61 | 34 65 65 63 32 0a 0a 53 |dcc3 44a|4eec2..S|
|000000b0| 75 62 6d 69 74 74 65 64 | 2d 62 79 3a 20 56 65 72 |ubmitted|-by: Ver|
|000000c0| 6e 20 50 61 78 73 6f 6e | 20 3c 76 65 72 6e 40 63 |n Paxson| <vern@c|
|000000d0| 73 2e 63 6f 72 6e 65 6c | 6c 2e 65 64 75 3e 0a 50 |s.cornel|l.edu>.P|
|000000e0| 6f 73 74 69 6e 67 2d 6e | 75 6d 62 65 72 3a 20 56 |osting-n|umber: V|
|000000f0| 6f 6c 75 6d 65 20 32 33 | 2c 20 49 73 73 75 65 20 |olume 23|, Issue |
|00000100| 34 32 0a 41 72 63 68 69 | 76 65 2d 6e 61 6d 65 3a |42.Archi|ve-name:|
|00000110| 20 66 6c 65 78 32 2e 33 | 2f 70 61 72 74 30 36 0a | flex2.3|/part06.|
|00000120| 0a 23 21 20 2f 62 69 6e | 2f 73 68 0a 23 20 54 68 |.#! /bin|/sh.# Th|
|00000130| 69 73 20 69 73 20 61 20 | 73 68 65 6c 6c 20 61 72 |is is a |shell ar|
|00000140| 63 68 69 76 65 2e 20 20 | 52 65 6d 6f 76 65 20 61 |chive. |Remove a|
|00000150| 6e 79 74 68 69 6e 67 20 | 62 65 66 6f 72 65 20 74 |nything |before t|
|00000160| 68 69 73 20 6c 69 6e 65 | 2c 20 74 68 65 6e 20 66 |his line|, then f|
|00000170| 65 65 64 20 69 74 0a 23 | 20 69 6e 74 6f 20 61 20 |eed it.#| into a |
|00000180| 73 68 65 6c 6c 20 76 69 | 61 20 22 73 68 20 66 69 |shell vi|a "sh fi|
|00000190| 6c 65 22 20 6f 72 20 73 | 69 6d 69 6c 61 72 2e 20 |le" or s|imilar. |
|000001a0| 20 54 6f 20 6f 76 65 72 | 77 72 69 74 65 20 65 78 | To over|write ex|
|000001b0| 69 73 74 69 6e 67 20 66 | 69 6c 65 73 2c 0a 23 20 |isting f|iles,.# |
|000001c0| 74 79 70 65 20 22 73 68 | 20 66 69 6c 65 20 2d 63 |type "sh| file -c|
|000001d0| 22 2e 0a 23 20 54 68 65 | 20 74 6f 6f 6c 20 74 68 |"..# The| tool th|
|000001e0| 61 74 20 67 65 6e 65 72 | 61 74 65 64 20 74 68 69 |at gener|ated thi|
|000001f0| 73 20 61 70 70 65 61 72 | 65 64 20 69 6e 20 74 68 |s appear|ed in th|
|00000200| 65 20 63 6f 6d 70 2e 73 | 6f 75 72 63 65 73 2e 75 |e comp.s|ources.u|
|00000210| 6e 69 78 20 6e 65 77 73 | 67 72 6f 75 70 3b 0a 23 |nix news|group;.#|
|00000220| 20 73 65 6e 64 20 6d 61 | 69 6c 20 74 6f 20 63 6f | send ma|il to co|
|00000230| 6d 70 2d 73 6f 75 72 63 | 65 73 2d 75 6e 69 78 40 |mp-sourc|es-unix@|
|00000240| 75 75 6e 65 74 2e 75 75 | 2e 6e 65 74 20 69 66 20 |uunet.uu|.net if |
|00000250| 79 6f 75 20 77 61 6e 74 | 20 74 68 61 74 20 74 6f |you want| that to|
|00000260| 6f 6c 2e 0a 23 20 43 6f | 6e 74 65 6e 74 73 3a 20 |ol..# Co|ntents: |
|00000270| 20 64 66 61 2e 63 20 66 | 6c 65 78 2e 73 6b 65 6c | dfa.c f|lex.skel|
|00000280| 20 79 79 6c 65 78 2e 63 | 0a 23 20 57 72 61 70 70 | yylex.c|.# Wrapp|
|00000290| 65 64 20 62 79 20 72 73 | 61 6c 7a 40 6c 69 74 63 |ed by rs|alz@litc|
|000002a0| 68 69 2e 62 62 6e 2e 63 | 6f 6d 20 6f 6e 20 57 65 |hi.bbn.c|om on We|
|000002b0| 64 20 4f 63 74 20 31 30 | 20 31 33 3a 32 34 3a 30 |d Oct 10| 13:24:0|
|000002c0| 32 20 31 39 39 30 0a 50 | 41 54 48 3d 2f 62 69 6e |2 1990.P|ATH=/bin|
|000002d0| 3a 2f 75 73 72 2f 62 69 | 6e 3a 2f 75 73 72 2f 75 |:/usr/bi|n:/usr/u|
|000002e0| 63 62 20 3b 20 65 78 70 | 6f 72 74 20 50 41 54 48 |cb ; exp|ort PATH|
|000002f0| 0a 65 63 68 6f 20 49 66 | 20 74 68 69 73 20 61 72 |.echo If| this ar|
|00000300| 63 68 69 76 65 20 69 73 | 20 63 6f 6d 70 6c 65 74 |chive is| complet|
|00000310| 65 2c 20 79 6f 75 20 77 | 69 6c 6c 20 73 65 65 20 |e, you w|ill see |
|00000320| 74 68 65 20 66 6f 6c 6c | 6f 77 69 6e 67 20 6d 65 |the foll|owing me|
|00000330| 73 73 61 67 65 3a 0a 65 | 63 68 6f 20 27 20 20 20 |ssage:.e|cho ' |
|00000340| 20 20 20 20 20 20 20 22 | 73 68 61 72 3a 20 45 6e | "|shar: En|
|00000350| 64 20 6f 66 20 61 72 63 | 68 69 76 65 20 36 20 28 |d of arc|hive 6 (|
|00000360| 6f 66 20 31 30 29 2e 22 | 27 0a 69 66 20 74 65 73 |of 10)."|'.if tes|
|00000370| 74 20 2d 66 20 27 64 66 | 61 2e 63 27 20 2d 61 20 |t -f 'df|a.c' -a |
|00000380| 22 24 7b 31 7d 22 20 21 | 3d 20 22 2d 63 22 20 3b |"${1}" !|= "-c" ;|
|00000390| 20 74 68 65 6e 20 0a 20 | 20 65 63 68 6f 20 73 68 | then . | echo sh|
|000003a0| 61 72 3a 20 57 69 6c 6c | 20 6e 6f 74 20 63 6c 6f |ar: Will| not clo|
|000003b0| 62 62 65 72 20 65 78 69 | 73 74 69 6e 67 20 66 69 |bber exi|sting fi|
|000003c0| 6c 65 20 5c 22 27 64 66 | 61 2e 63 27 5c 22 0a 65 |le \"'df|a.c'\".e|
|000003d0| 6c 73 65 0a 20 20 65 63 | 68 6f 20 73 68 61 72 3a |lse. ec|ho shar:|
|000003e0| 20 45 78 74 72 61 63 74 | 69 6e 67 20 5c 22 27 64 | Extract|ing \"'d|
|000003f0| 66 61 2e 63 27 5c 22 20 | 5c 28 32 36 39 31 39 20 |fa.c'\" |\(26919 |
|00000400| 63 68 61 72 61 63 74 65 | 72 73 5c 29 0a 20 20 73 |characte|rs\). s|
|00000410| 65 64 20 22 73 2f 5e 58 | 2f 2f 22 20 3e 27 64 66 |ed "s/^X|//" >'df|
|00000420| 61 2e 63 27 20 3c 3c 27 | 45 4e 44 5f 4f 46 5f 46 |a.c' <<'|END_OF_F|
|00000430| 49 4c 45 27 0a 58 2f 2a | 20 64 66 61 20 2d 20 44 |ILE'.X/*| dfa - D|
|00000440| 46 41 20 63 6f 6e 73 74 | 72 75 63 74 69 6f 6e 20 |FA const|ruction |
|00000450| 72 6f 75 74 69 6e 65 73 | 20 2a 2f 0a 58 0a 58 2f |routines| */.X.X/|
|00000460| 2a 2d 0a 58 20 2a 20 43 | 6f 70 79 72 69 67 68 74 |*-.X * C|opyright|
|00000470| 20 28 63 29 20 31 39 39 | 30 20 54 68 65 20 52 65 | (c) 199|0 The Re|
|00000480| 67 65 6e 74 73 20 6f 66 | 20 74 68 65 20 55 6e 69 |gents of| the Uni|
|00000490| 76 65 72 73 69 74 79 20 | 6f 66 20 43 61 6c 69 66 |versity |of Calif|
|000004a0| 6f 72 6e 69 61 2e 0a 58 | 20 2a 20 41 6c 6c 20 72 |ornia..X| * All r|
|000004b0| 69 67 68 74 73 20 72 65 | 73 65 72 76 65 64 2e 0a |ights re|served..|
|000004c0| 58 20 2a 0a 58 20 2a 20 | 54 68 69 73 20 63 6f 64 |X *.X * |This cod|
|000004d0| 65 20 69 73 20 64 65 72 | 69 76 65 64 20 66 72 6f |e is der|ived fro|
|000004e0| 6d 20 73 6f 66 74 77 61 | 72 65 20 63 6f 6e 74 72 |m softwa|re contr|
|000004f0| 69 62 75 74 65 64 20 74 | 6f 20 42 65 72 6b 65 6c |ibuted t|o Berkel|
|00000500| 65 79 20 62 79 0a 58 20 | 2a 20 56 65 72 6e 20 50 |ey by.X |* Vern P|
|00000510| 61 78 73 6f 6e 2e 0a 58 | 20 2a 20 0a 58 20 2a 20 |axson..X| * .X * |
|00000520| 54 68 65 20 55 6e 69 74 | 65 64 20 53 74 61 74 65 |The Unit|ed State|
|00000530| 73 20 47 6f 76 65 72 6e | 6d 65 6e 74 20 68 61 73 |s Govern|ment has|
|00000540| 20 72 69 67 68 74 73 20 | 69 6e 20 74 68 69 73 20 | rights |in this |
|00000550| 77 6f 72 6b 20 70 75 72 | 73 75 61 6e 74 0a 58 20 |work pur|suant.X |
|00000560| 2a 20 74 6f 20 63 6f 6e | 74 72 61 63 74 20 6e 6f |* to con|tract no|
|00000570| 2e 20 44 45 2d 41 43 30 | 33 2d 37 36 53 46 30 30 |. DE-AC0|3-76SF00|
|00000580| 30 39 38 20 62 65 74 77 | 65 65 6e 20 74 68 65 20 |098 betw|een the |
|00000590| 55 6e 69 74 65 64 20 53 | 74 61 74 65 73 0a 58 20 |United S|tates.X |
|000005a0| 2a 20 44 65 70 61 72 74 | 6d 65 6e 74 20 6f 66 20 |* Depart|ment of |
|000005b0| 45 6e 65 72 67 79 20 61 | 6e 64 20 74 68 65 20 55 |Energy a|nd the U|
|000005c0| 6e 69 76 65 72 73 69 74 | 79 20 6f 66 20 43 61 6c |niversit|y of Cal|
|000005d0| 69 66 6f 72 6e 69 61 2e | 0a 58 20 2a 0a 58 20 2a |ifornia.|.X *.X *|
|000005e0| 20 52 65 64 69 73 74 72 | 69 62 75 74 69 6f 6e 20 | Redistr|ibution |
|000005f0| 61 6e 64 20 75 73 65 20 | 69 6e 20 73 6f 75 72 63 |and use |in sourc|
|00000600| 65 20 61 6e 64 20 62 69 | 6e 61 72 79 20 66 6f 72 |e and bi|nary for|
|00000610| 6d 73 20 61 72 65 20 70 | 65 72 6d 69 74 74 65 64 |ms are p|ermitted|
|00000620| 20 70 72 6f 76 69 64 65 | 64 0a 58 20 2a 20 74 68 | provide|d.X * th|
|00000630| 61 74 3a 20 28 31 29 20 | 73 6f 75 72 63 65 20 64 |at: (1) |source d|
|00000640| 69 73 74 72 69 62 75 74 | 69 6f 6e 73 20 72 65 74 |istribut|ions ret|
|00000650| 61 69 6e 20 74 68 69 73 | 20 65 6e 74 69 72 65 20 |ain this| entire |
|00000660| 63 6f 70 79 72 69 67 68 | 74 20 6e 6f 74 69 63 65 |copyrigh|t notice|
|00000670| 20 61 6e 64 0a 58 20 2a | 20 63 6f 6d 6d 65 6e 74 | and.X *| comment|
|00000680| 2c 20 61 6e 64 20 28 32 | 29 20 64 69 73 74 72 69 |, and (2|) distri|
|00000690| 62 75 74 69 6f 6e 73 20 | 69 6e 63 6c 75 64 69 6e |butions |includin|
|000006a0| 67 20 62 69 6e 61 72 69 | 65 73 20 64 69 73 70 6c |g binari|es displ|
|000006b0| 61 79 20 74 68 65 20 66 | 6f 6c 6c 6f 77 69 6e 67 |ay the f|ollowing|
|000006c0| 0a 58 20 2a 20 61 63 6b | 6e 6f 77 6c 65 64 67 65 |.X * ack|nowledge|
|000006d0| 6d 65 6e 74 3a 20 20 60 | 60 54 68 69 73 20 70 72 |ment: `|`This pr|
|000006e0| 6f 64 75 63 74 20 69 6e | 63 6c 75 64 65 73 20 73 |oduct in|cludes s|
|000006f0| 6f 66 74 77 61 72 65 20 | 64 65 76 65 6c 6f 70 65 |oftware |develope|
|00000700| 64 20 62 79 20 74 68 65 | 0a 58 20 2a 20 55 6e 69 |d by the|.X * Uni|
|00000710| 76 65 72 73 69 74 79 20 | 6f 66 20 43 61 6c 69 66 |versity |of Calif|
|00000720| 6f 72 6e 69 61 2c 20 42 | 65 72 6b 65 6c 65 79 20 |ornia, B|erkeley |
|00000730| 61 6e 64 20 69 74 73 20 | 63 6f 6e 74 72 69 62 75 |and its |contribu|
|00000740| 74 6f 72 73 27 27 20 69 | 6e 20 74 68 65 0a 58 20 |tors'' i|n the.X |
|00000750| 2a 20 64 6f 63 75 6d 65 | 6e 74 61 74 69 6f 6e 20 |* docume|ntation |
|00000760| 6f 72 20 6f 74 68 65 72 | 20 6d 61 74 65 72 69 61 |or other| materia|
|00000770| 6c 73 20 70 72 6f 76 69 | 64 65 64 20 77 69 74 68 |ls provi|ded with|
|00000780| 20 74 68 65 20 64 69 73 | 74 72 69 62 75 74 69 6f | the dis|tributio|
|00000790| 6e 20 61 6e 64 20 69 6e | 0a 58 20 2a 20 61 6c 6c |n and in|.X * all|
|000007a0| 20 61 64 76 65 72 74 69 | 73 69 6e 67 20 6d 61 74 | adverti|sing mat|
|000007b0| 65 72 69 61 6c 73 20 6d | 65 6e 74 69 6f 6e 69 6e |erials m|entionin|
|000007c0| 67 20 66 65 61 74 75 72 | 65 73 20 6f 72 20 75 73 |g featur|es or us|
|000007d0| 65 20 6f 66 20 74 68 69 | 73 20 73 6f 66 74 77 61 |e of thi|s softwa|
|000007e0| 72 65 2e 0a 58 20 2a 20 | 4e 65 69 74 68 65 72 20 |re..X * |Neither |
|000007f0| 74 68 65 20 6e 61 6d 65 | 20 6f 66 20 74 68 65 20 |the name| of the |
|00000800| 55 6e 69 76 65 72 73 69 | 74 79 20 6e 6f 72 20 74 |Universi|ty nor t|
|00000810| 68 65 20 6e 61 6d 65 73 | 20 6f 66 20 69 74 73 20 |he names| of its |
|00000820| 63 6f 6e 74 72 69 62 75 | 74 6f 72 73 20 6d 61 79 |contribu|tors may|
|00000830| 0a 58 20 2a 20 62 65 20 | 75 73 65 64 20 74 6f 20 |.X * be |used to |
|00000840| 65 6e 64 6f 72 73 65 20 | 6f 72 20 70 72 6f 6d 6f |endorse |or promo|
|00000850| 74 65 20 70 72 6f 64 75 | 63 74 73 20 64 65 72 69 |te produ|cts deri|
|00000860| 76 65 64 20 66 72 6f 6d | 20 74 68 69 73 20 73 6f |ved from| this so|
|00000870| 66 74 77 61 72 65 20 77 | 69 74 68 6f 75 74 0a 58 |ftware w|ithout.X|
|00000880| 20 2a 20 73 70 65 63 69 | 66 69 63 20 70 72 69 6f | * speci|fic prio|
|00000890| 72 20 77 72 69 74 74 65 | 6e 20 70 65 72 6d 69 73 |r writte|n permis|
|000008a0| 73 69 6f 6e 2e 0a 58 20 | 2a 20 54 48 49 53 20 53 |sion..X |* THIS S|
|000008b0| 4f 46 54 57 41 52 45 20 | 49 53 20 50 52 4f 56 49 |OFTWARE |IS PROVI|
|000008c0| 44 45 44 20 60 60 41 53 | 20 49 53 27 27 20 41 4e |DED ``AS| IS'' AN|
|000008d0| 44 20 57 49 54 48 4f 55 | 54 20 41 4e 59 20 45 58 |D WITHOU|T ANY EX|
|000008e0| 50 52 45 53 53 20 4f 52 | 20 49 4d 50 4c 49 45 44 |PRESS OR| IMPLIED|
|000008f0| 0a 58 20 2a 20 57 41 52 | 52 41 4e 54 49 45 53 2c |.X * WAR|RANTIES,|
|00000900| 20 49 4e 43 4c 55 44 49 | 4e 47 2c 20 57 49 54 48 | INCLUDI|NG, WITH|
|00000910| 4f 55 54 20 4c 49 4d 49 | 54 41 54 49 4f 4e 2c 20 |OUT LIMI|TATION, |
|00000920| 54 48 45 20 49 4d 50 4c | 49 45 44 20 57 41 52 52 |THE IMPL|IED WARR|
|00000930| 41 4e 54 49 45 53 20 4f | 46 0a 58 20 2a 20 4d 45 |ANTIES O|F.X * ME|
|00000940| 52 43 48 41 4e 54 41 42 | 49 4c 49 54 59 20 41 4e |RCHANTAB|ILITY AN|
|00000950| 44 20 46 49 54 4e 45 53 | 53 20 46 4f 52 20 41 20 |D FITNES|S FOR A |
|00000960| 50 41 52 54 49 43 55 4c | 41 52 20 50 55 52 50 4f |PARTICUL|AR PURPO|
|00000970| 53 45 2e 0a 58 20 2a 2f | 0a 58 0a 58 23 69 66 6e |SE..X */|.X.X#ifn|
|00000980| 64 65 66 20 6c 69 6e 74 | 0a 58 73 74 61 74 69 63 |def lint|.Xstatic|
|00000990| 20 63 68 61 72 20 72 63 | 73 69 64 5b 5d 20 3d 0a | char rc|sid[] =.|
|000009a0| 58 20 20 20 20 22 40 28 | 23 29 20 24 48 65 61 64 |X "@(|#) $Head|
|000009b0| 65 72 3a 20 2f 75 73 72 | 2f 66 73 79 73 2f 6f 64 |er: /usr|/fsys/od|
|000009c0| 69 6e 2f 61 2f 76 65 72 | 6e 2f 66 6c 65 78 2f 52 |in/a/ver|n/flex/R|
|000009d0| 43 53 2f 64 66 61 2e 63 | 2c 76 20 32 2e 37 20 39 |CS/dfa.c|,v 2.7 9|
|000009e0| 30 2f 30 36 2f 32 37 20 | 32 33 3a 34 38 3a 31 35 |0/06/27 |23:48:15|
|000009f0| 20 76 65 72 6e 20 45 78 | 70 20 24 20 28 4c 42 4c | vern Ex|p $ (LBL|
|00000a00| 29 22 3b 0a 58 23 65 6e | 64 69 66 0a 58 0a 58 23 |)";.X#en|dif.X.X#|
|00000a10| 69 6e 63 6c 75 64 65 20 | 22 66 6c 65 78 64 65 66 |include |"flexdef|
|00000a20| 2e 68 22 0a 58 0a 58 0a | 58 2f 2a 20 64 65 63 6c |.h".X.X.|X/* decl|
|00000a30| 61 72 65 20 66 75 6e 63 | 74 69 6f 6e 73 20 74 68 |are func|tions th|
|00000a40| 61 74 20 68 61 76 65 20 | 66 6f 72 77 61 72 64 20 |at have |forward |
|00000a50| 72 65 66 65 72 65 6e 63 | 65 73 20 2a 2f 0a 58 0a |referenc|es */.X.|
|00000a60| 58 76 6f 69 64 20 64 75 | 6d 70 5f 61 73 73 6f 63 |Xvoid du|mp_assoc|
|00000a70| 69 61 74 65 64 5f 72 75 | 6c 65 73 20 50 52 4f 54 |iated_ru|les PROT|
|00000a80| 4f 28 28 46 49 4c 45 2a | 2c 20 69 6e 74 29 29 3b |O((FILE*|, int));|
|00000a90| 0a 58 76 6f 69 64 20 64 | 75 6d 70 5f 74 72 61 6e |.Xvoid d|ump_tran|
|00000aa0| 73 69 74 69 6f 6e 73 20 | 50 52 4f 54 4f 28 28 46 |sitions |PROTO((F|
|00000ab0| 49 4c 45 2a 2c 20 69 6e | 74 5b 5d 29 29 3b 0a 58 |ILE*, in|t[]));.X|
|00000ac0| 76 6f 69 64 20 73 79 6d | 70 61 72 74 69 74 69 6f |void sym|partitio|
|00000ad0| 6e 20 50 52 4f 54 4f 28 | 28 69 6e 74 5b 5d 2c 20 |n PROTO(|(int[], |
|00000ae0| 69 6e 74 2c 20 69 6e 74 | 5b 5d 2c 20 69 6e 74 5b |int, int|[], int[|
|00000af0| 5d 29 29 3b 0a 58 69 6e | 74 20 73 79 6d 66 6f 6c |]));.Xin|t symfol|
|00000b00| 6c 6f 77 73 65 74 20 50 | 52 4f 54 4f 28 28 69 6e |lowset P|ROTO((in|
|00000b10| 74 5b 5d 2c 20 69 6e 74 | 2c 20 69 6e 74 2c 20 69 |t[], int|, int, i|
|00000b20| 6e 74 5b 5d 29 29 3b 0a | 58 0a 58 0a 58 2f 2a 20 |nt[]));.|X.X.X/* |
|00000b30| 63 68 65 63 6b 5f 66 6f | 72 5f 62 61 63 6b 74 72 |check_fo|r_backtr|
|00000b40| 61 63 6b 69 6e 67 20 2d | 20 63 68 65 63 6b 20 61 |acking -| check a|
|00000b50| 20 44 46 41 20 73 74 61 | 74 65 20 66 6f 72 20 62 | DFA sta|te for b|
|00000b60| 61 63 6b 74 72 61 63 6b | 69 6e 67 0a 58 20 2a 0a |acktrack|ing.X *.|
|00000b70| 58 20 2a 20 73 79 6e 6f | 70 73 69 73 0a 58 20 2a |X * syno|psis.X *|
|00000b80| 20 20 20 20 20 69 6e 74 | 20 64 73 2c 20 73 74 61 | int| ds, sta|
|00000b90| 74 65 5b 6e 75 6d 65 63 | 73 5d 3b 0a 58 20 2a 20 |te[numec|s];.X * |
|00000ba0| 20 20 20 20 63 68 65 63 | 6b 5f 66 6f 72 5f 62 61 | chec|k_for_ba|
|00000bb0| 63 6b 74 72 61 63 6b 69 | 6e 67 28 20 64 73 2c 20 |cktracki|ng( ds, |
|00000bc0| 73 74 61 74 65 20 29 3b | 0a 58 20 2a 0a 58 20 2a |state );|.X *.X *|
|00000bd0| 20 64 73 20 69 73 20 74 | 68 65 20 6e 75 6d 62 65 | ds is t|he numbe|
|00000be0| 72 20 6f 66 20 74 68 65 | 20 73 74 61 74 65 20 74 |r of the| state t|
|00000bf0| 6f 20 63 68 65 63 6b 20 | 61 6e 64 20 73 74 61 74 |o check |and stat|
|00000c00| 65 5b 5d 20 69 73 20 69 | 74 73 20 6f 75 74 2d 74 |e[] is i|ts out-t|
|00000c10| 72 61 6e 73 69 74 69 6f | 6e 73 2c 0a 58 20 2a 20 |ransitio|ns,.X * |
|00000c20| 69 6e 64 65 78 65 64 20 | 62 79 20 65 71 75 69 76 |indexed |by equiv|
|00000c30| 61 6c 65 6e 63 65 20 63 | 6c 61 73 73 2c 20 61 6e |alence c|lass, an|
|00000c40| 64 20 73 74 61 74 65 5f | 72 75 6c 65 73 5b 5d 20 |d state_|rules[] |
|00000c50| 69 73 20 74 68 65 20 73 | 65 74 20 6f 66 20 72 75 |is the s|et of ru|
|00000c60| 6c 65 73 0a 58 20 2a 20 | 61 73 73 6f 63 69 61 74 |les.X * |associat|
|00000c70| 65 64 20 77 69 74 68 20 | 74 68 69 73 20 73 74 61 |ed with |this sta|
|00000c80| 74 65 0a 58 20 2a 2f 0a | 58 0a 58 76 6f 69 64 20 |te.X */.|X.Xvoid |
|00000c90| 63 68 65 63 6b 5f 66 6f | 72 5f 62 61 63 6b 74 72 |check_fo|r_backtr|
|00000ca0| 61 63 6b 69 6e 67 28 20 | 64 73 2c 20 73 74 61 74 |acking( |ds, stat|
|00000cb0| 65 20 29 0a 58 69 6e 74 | 20 64 73 3b 0a 58 69 6e |e ).Xint| ds;.Xin|
|00000cc0| 74 20 73 74 61 74 65 5b | 5d 3b 0a 58 0a 58 20 20 |t state[|];.X.X |
|00000cd0| 20 20 7b 0a 58 20 20 20 | 20 69 66 20 28 20 28 72 | {.X | if ( (r|
|00000ce0| 65 6a 65 63 74 20 26 26 | 20 21 20 64 66 61 61 63 |eject &&| ! dfaac|
|00000cf0| 63 5b 64 73 5d 2e 64 66 | 61 61 63 63 5f 73 65 74 |c[ds].df|aacc_set|
|00000d00| 29 20 7c 7c 20 21 20 64 | 66 61 61 63 63 5b 64 73 |) || ! d|faacc[ds|
|00000d10| 5d 2e 64 66 61 61 63 63 | 5f 73 74 61 74 65 20 29 |].dfaacc|_state )|
|00000d20| 0a 58 09 7b 20 2f 2a 20 | 73 74 61 74 65 20 69 73 |.X.{ /* |state is|
|00000d30| 20 6e 6f 6e 2d 61 63 63 | 65 70 74 69 6e 67 20 2a | non-acc|epting *|
|00000d40| 2f 0a 58 09 2b 2b 6e 75 | 6d 5f 62 61 63 6b 74 72 |/.X.++nu|m_backtr|
|00000d50| 61 63 6b 69 6e 67 3b 0a | 58 0a 58 09 69 66 20 28 |acking;.|X.X.if (|
|00000d60| 20 62 61 63 6b 74 72 61 | 63 6b 5f 72 65 70 6f 72 | backtra|ck_repor|
|00000d70| 74 20 29 0a 58 09 20 20 | 20 20 7b 0a 58 09 20 20 |t ).X. | {.X. |
|00000d80| 20 20 66 70 72 69 6e 74 | 66 28 20 62 61 63 6b 74 | fprint|f( backt|
|00000d90| 72 61 63 6b 5f 66 69 6c | 65 2c 20 22 53 74 61 74 |rack_fil|e, "Stat|
|00000da0| 65 20 23 25 64 20 69 73 | 20 6e 6f 6e 2d 61 63 63 |e #%d is| non-acc|
|00000db0| 65 70 74 69 6e 67 20 2d | 5c 6e 22 2c 20 64 73 20 |epting -|\n", ds |
|00000dc0| 29 3b 0a 58 0a 58 09 20 | 20 20 20 2f 2a 20 69 64 |);.X.X. | /* id|
|00000dd0| 65 6e 74 69 66 79 20 74 | 68 65 20 73 74 61 74 65 |entify t|he state|
|00000de0| 20 2a 2f 0a 58 09 20 20 | 20 20 64 75 6d 70 5f 61 | */.X. | dump_a|
|00000df0| 73 73 6f 63 69 61 74 65 | 64 5f 72 75 6c 65 73 28 |ssociate|d_rules(|
|00000e00| 20 62 61 63 6b 74 72 61 | 63 6b 5f 66 69 6c 65 2c | backtra|ck_file,|
|00000e10| 20 64 73 20 29 3b 0a 58 | 0a 58 09 20 20 20 20 2f | ds );.X|.X. /|
|00000e20| 2a 20 6e 6f 77 20 69 64 | 65 6e 74 69 66 79 20 69 |* now id|entify i|
|00000e30| 74 20 66 75 72 74 68 65 | 72 20 75 73 69 6e 67 20 |t furthe|r using |
|00000e40| 74 68 65 20 6f 75 74 2d | 20 61 6e 64 20 6a 61 6d |the out-| and jam|
|00000e50| 2d 74 72 61 6e 73 69 74 | 69 6f 6e 73 20 2a 2f 0a |-transit|ions */.|
|00000e60| 58 09 20 20 20 20 64 75 | 6d 70 5f 74 72 61 6e 73 |X. du|mp_trans|
|00000e70| 69 74 69 6f 6e 73 28 20 | 62 61 63 6b 74 72 61 63 |itions( |backtrac|
|00000e80| 6b 5f 66 69 6c 65 2c 20 | 73 74 61 74 65 20 29 3b |k_file, |state );|
|00000e90| 0a 58 0a 58 09 20 20 20 | 20 70 75 74 63 28 20 27 |.X.X. | putc( '|
|00000ea0| 5c 6e 27 2c 20 62 61 63 | 6b 74 72 61 63 6b 5f 66 |\n', bac|ktrack_f|
|00000eb0| 69 6c 65 20 29 3b 0a 58 | 09 20 20 20 20 7d 0a 58 |ile );.X|. }.X|
|00000ec0| 09 7d 0a 58 20 20 20 20 | 7d 0a 58 0a 58 0a 58 2f |.}.X |}.X.X.X/|
|00000ed0| 2a 20 63 68 65 63 6b 5f | 74 72 61 69 6c 69 6e 67 |* check_|trailing|
|00000ee0| 5f 63 6f 6e 74 65 78 74 | 20 2d 20 63 68 65 63 6b |_context| - check|
|00000ef0| 20 74 6f 20 73 65 65 20 | 69 66 20 4e 46 41 20 73 | to see |if NFA s|
|00000f00| 74 61 74 65 20 73 65 74 | 20 63 6f 6e 73 74 69 74 |tate set| constit|
|00000f10| 75 74 65 73 0a 58 20 2a | 20 20 20 20 20 20 20 20 |utes.X *| |
|00000f20| 20 20 20 20 20 20 20 20 | 20 20 20 20 20 20 20 20 | | |
|00000f30| 20 20 22 64 61 6e 67 65 | 72 6f 75 73 22 20 74 72 | "dange|rous" tr|
|00000f40| 61 69 6c 69 6e 67 20 63 | 6f 6e 74 65 78 74 0a 58 |ailing c|ontext.X|
|00000f50| 20 2a 0a 58 20 2a 20 73 | 79 6e 6f 70 73 69 73 0a | *.X * s|ynopsis.|
|00000f60| 58 20 2a 20 20 20 20 69 | 6e 74 20 6e 66 61 5f 73 |X * i|nt nfa_s|
|00000f70| 74 61 74 65 73 5b 6e 75 | 6d 5f 73 74 61 74 65 73 |tates[nu|m_states|
|00000f80| 2b 31 5d 2c 20 6e 75 6d | 5f 73 74 61 74 65 73 3b |+1], num|_states;|
|00000f90| 0a 58 20 2a 20 20 20 20 | 69 6e 74 20 61 63 63 73 |.X * |int accs|
|00000fa0| 65 74 5b 6e 61 63 63 2b | 31 5d 2c 20 6e 61 63 63 |et[nacc+|1], nacc|
|00000fb0| 3b 0a 58 20 2a 20 20 20 | 20 63 68 65 63 6b 5f 74 |;.X * | check_t|
|00000fc0| 72 61 69 6c 69 6e 67 5f | 63 6f 6e 74 65 78 74 28 |railing_|context(|
|00000fd0| 20 6e 66 61 5f 73 74 61 | 74 65 73 2c 20 6e 75 6d | nfa_sta|tes, num|
|00000fe0| 5f 73 74 61 74 65 73 2c | 20 61 63 63 73 65 74 2c |_states,| accset,|
|00000ff0| 20 6e 61 63 63 20 29 3b | 0a 58 20 2a 0a 58 20 2a | nacc );|.X *.X *|
|00001000| 20 4e 4f 54 45 53 0a 58 | 20 2a 20 20 20 20 54 72 | NOTES.X| * Tr|
|00001010| 61 69 6c 69 6e 67 20 63 | 6f 6e 74 65 78 74 20 69 |ailing c|ontext i|
|00001020| 73 20 22 64 61 6e 67 65 | 72 6f 75 73 22 20 69 66 |s "dange|rous" if|
|00001030| 20 62 6f 74 68 20 74 68 | 65 20 68 65 61 64 20 61 | both th|e head a|
|00001040| 6e 64 20 74 68 65 20 74 | 72 61 69 6c 69 6e 67 0a |nd the t|railing.|
|00001050| 58 20 2a 20 20 70 61 72 | 74 20 61 72 65 20 6f 66 |X * par|t are of|
|00001060| 20 76 61 72 69 61 62 6c | 65 20 73 69 7a 65 20 5c | variabl|e size \|
|00001070| 61 6e 64 2f 20 74 68 65 | 72 65 27 73 20 61 20 44 |and/ the|re's a D|
|00001080| 46 41 20 73 74 61 74 65 | 20 77 68 69 63 68 20 63 |FA state| which c|
|00001090| 6f 6e 74 61 69 6e 73 0a | 58 20 2a 20 20 62 6f 74 |ontains.|X * bot|
|000010a0| 68 20 61 6e 20 61 63 63 | 65 70 74 69 6e 67 20 73 |h an acc|epting s|
|000010b0| 74 61 74 65 20 66 6f 72 | 20 74 68 65 20 68 65 61 |tate for| the hea|
|000010c0| 64 20 70 61 72 74 20 6f | 66 20 74 68 65 20 72 75 |d part o|f the ru|
|000010d0| 6c 65 20 61 6e 64 20 4e | 46 41 20 73 74 61 74 65 |le and N|FA state|
|000010e0| 73 0a 58 20 2a 20 20 77 | 68 69 63 68 20 6f 63 63 |s.X * w|hich occ|
|000010f0| 75 72 20 61 66 74 65 72 | 20 74 68 65 20 62 65 67 |ur after| the beg|
|00001100| 69 6e 6e 69 6e 67 20 6f | 66 20 74 68 65 20 74 72 |inning o|f the tr|
|00001110| 61 69 6c 69 6e 67 20 63 | 6f 6e 74 65 78 74 2e 0a |ailing c|ontext..|
|00001120| 58 20 2a 20 20 57 68 65 | 6e 20 73 75 63 68 20 61 |X * Whe|n such a|
|00001130| 20 72 75 6c 65 20 69 73 | 20 6d 61 74 63 68 65 64 | rule is| matched|
|00001140| 2c 20 69 74 27 73 20 69 | 6d 70 6f 73 73 69 62 6c |, it's i|mpossibl|
|00001150| 65 20 74 6f 20 74 65 6c | 6c 20 69 66 20 68 61 76 |e to tel|l if hav|
|00001160| 69 6e 67 20 62 65 65 6e | 0a 58 20 2a 20 20 69 6e |ing been|.X * in|
|00001170| 20 74 68 65 20 44 46 41 | 20 73 74 61 74 65 20 69 | the DFA| state i|
|00001180| 6e 64 69 63 61 74 65 73 | 20 74 68 65 20 62 65 67 |ndicates| the beg|
|00001190| 69 6e 6e 69 6e 67 20 6f | 66 20 74 68 65 20 74 72 |inning o|f the tr|
|000011a0| 61 69 6c 69 6e 67 20 63 | 6f 6e 74 65 78 74 0a 58 |ailing c|ontext.X|
|000011b0| 20 2a 20 20 6f 72 20 66 | 75 72 74 68 65 72 2d 61 | * or f|urther-a|
|000011c0| 6c 6f 6e 67 20 73 63 61 | 6e 6e 69 6e 67 20 6f 66 |long sca|nning of|
|000011d0| 20 74 68 65 20 70 61 74 | 74 65 72 6e 2e 20 20 49 | the pat|tern. I|
|000011e0| 6e 20 74 68 65 73 65 20 | 63 61 73 65 73 2c 20 61 |n these |cases, a|
|000011f0| 20 77 61 72 6e 69 6e 67 | 0a 58 20 2a 20 20 6d 65 | warning|.X * me|
|00001200| 73 73 61 67 65 20 69 73 | 20 69 73 73 75 65 64 2e |ssage is| issued.|
|00001210| 0a 58 20 2a 0a 58 20 2a | 20 20 20 20 6e 66 61 5f |.X *.X *| nfa_|
|00001220| 73 74 61 74 65 73 5b 31 | 20 2e 2e 20 6e 75 6d 5f |states[1| .. num_|
|00001230| 73 74 61 74 65 73 5d 20 | 69 73 20 74 68 65 20 6c |states] |is the l|
|00001240| 69 73 74 20 6f 66 20 4e | 46 41 20 73 74 61 74 65 |ist of N|FA state|
|00001250| 73 20 69 6e 20 74 68 65 | 20 44 46 41 2e 0a 58 20 |s in the| DFA..X |
|00001260| 2a 20 20 20 20 61 63 63 | 73 65 74 5b 31 20 2e 2e |* acc|set[1 ..|
|00001270| 20 6e 61 63 63 5d 20 69 | 73 20 74 68 65 20 6c 69 | nacc] i|s the li|
|00001280| 73 74 20 6f 66 20 61 63 | 63 65 70 74 69 6e 67 20 |st of ac|cepting |
|00001290| 6e 75 6d 62 65 72 73 20 | 66 6f 72 20 74 68 65 20 |numbers |for the |
|000012a0| 44 46 41 20 73 74 61 74 | 65 2e 0a 58 20 2a 2f 0a |DFA stat|e..X */.|
|000012b0| 58 0a 58 76 6f 69 64 20 | 63 68 65 63 6b 5f 74 72 |X.Xvoid |check_tr|
|000012c0| 61 69 6c 69 6e 67 5f 63 | 6f 6e 74 65 78 74 28 20 |ailing_c|ontext( |
|000012d0| 6e 66 61 5f 73 74 61 74 | 65 73 2c 20 6e 75 6d 5f |nfa_stat|es, num_|
|000012e0| 73 74 61 74 65 73 2c 20 | 61 63 63 73 65 74 2c 20 |states, |accset, |
|000012f0| 6e 61 63 63 20 29 0a 58 | 69 6e 74 20 2a 6e 66 61 |nacc ).X|int *nfa|
|00001300| 5f 73 74 61 74 65 73 2c | 20 6e 75 6d 5f 73 74 61 |_states,| num_sta|
|00001310| 74 65 73 3b 0a 58 69 6e | 74 20 2a 61 63 63 73 65 |tes;.Xin|t *accse|
|00001320| 74 3b 0a 58 72 65 67 69 | 73 74 65 72 20 69 6e 74 |t;.Xregi|ster int|
|00001330| 20 6e 61 63 63 3b 0a 58 | 0a 58 20 20 20 20 7b 0a | nacc;.X|.X {.|
|00001340| 58 20 20 20 20 72 65 67 | 69 73 74 65 72 20 69 6e |X reg|ister in|
|00001350| 74 20 69 2c 20 6a 3b 0a | 58 0a 58 20 20 20 20 66 |t i, j;.|X.X f|
|00001360| 6f 72 20 28 20 69 20 3d | 20 31 3b 20 69 20 3c 3d |or ( i =| 1; i <=|
|00001370| 20 6e 75 6d 5f 73 74 61 | 74 65 73 3b 20 2b 2b 69 | num_sta|tes; ++i|
|00001380| 20 29 0a 58 09 7b 0a 58 | 09 69 6e 74 20 6e 73 20 | ).X.{.X|.int ns |
|00001390| 3d 20 6e 66 61 5f 73 74 | 61 74 65 73 5b 69 5d 3b |= nfa_st|ates[i];|
|000013a0| 0a 58 09 72 65 67 69 73 | 74 65 72 20 69 6e 74 20 |.X.regis|ter int |
|000013b0| 74 79 70 65 20 3d 20 73 | 74 61 74 65 5f 74 79 70 |type = s|tate_typ|
|000013c0| 65 5b 6e 73 5d 3b 0a 58 | 09 72 65 67 69 73 74 65 |e[ns];.X|.registe|
|000013d0| 72 20 69 6e 74 20 61 72 | 20 3d 20 61 73 73 6f 63 |r int ar| = assoc|
|000013e0| 5f 72 75 6c 65 5b 6e 73 | 5d 3b 0a 58 0a 58 09 69 |_rule[ns|];.X.X.i|
|000013f0| 66 20 28 20 74 79 70 65 | 20 3d 3d 20 53 54 41 54 |f ( type| == STAT|
|00001400| 45 5f 4e 4f 52 4d 41 4c | 20 7c 7c 20 72 75 6c 65 |E_NORMAL| || rule|
|00001410| 5f 74 79 70 65 5b 61 72 | 5d 20 21 3d 20 52 55 4c |_type[ar|] != RUL|
|00001420| 45 5f 56 41 52 49 41 42 | 4c 45 20 29 0a 58 09 20 |E_VARIAB|LE ).X. |
|00001430| 20 20 20 7b 20 2f 2a 20 | 64 6f 20 6e 6f 74 68 69 | { /* |do nothi|
|00001440| 6e 67 20 2a 2f 0a 58 09 | 20 20 20 20 7d 0a 58 0a |ng */.X.| }.X.|
|00001450| 58 09 65 6c 73 65 20 69 | 66 20 28 20 74 79 70 65 |X.else i|f ( type|
|00001460| 20 3d 3d 20 53 54 41 54 | 45 5f 54 52 41 49 4c 49 | == STAT|E_TRAILI|
|00001470| 4e 47 5f 43 4f 4e 54 45 | 58 54 20 29 0a 58 09 20 |NG_CONTE|XT ).X. |
|00001480| 20 20 20 7b 0a 58 09 20 | 20 20 20 2f 2a 20 70 6f | {.X. | /* po|
|00001490| 74 65 6e 74 69 61 6c 20 | 74 72 6f 75 62 6c 65 2e |tential |trouble.|
|000014a0| 20 20 53 63 61 6e 20 73 | 65 74 20 6f 66 20 61 63 | Scan s|et of ac|
|000014b0| 63 65 70 74 69 6e 67 20 | 6e 75 6d 62 65 72 73 20 |cepting |numbers |
|000014c0| 66 6f 72 0a 58 09 20 20 | 20 20 20 2a 20 74 68 65 |for.X. | * the|
|000014d0| 20 6f 6e 65 20 6d 61 72 | 6b 69 6e 67 20 74 68 65 | one mar|king the|
|000014e0| 20 65 6e 64 20 6f 66 20 | 74 68 65 20 22 68 65 61 | end of |the "hea|
|000014f0| 64 22 2e 20 20 57 65 20 | 61 73 73 75 6d 65 20 74 |d". We |assume t|
|00001500| 68 61 74 0a 58 09 20 20 | 20 20 20 2a 20 74 68 69 |hat.X. | * thi|
|00001510| 73 20 6c 6f 6f 70 69 6e | 67 20 77 69 6c 6c 20 62 |s loopin|g will b|
|00001520| 65 20 66 61 69 72 6c 79 | 20 63 68 65 61 70 20 73 |e fairly| cheap s|
|00001530| 69 6e 63 65 20 69 74 27 | 73 20 72 61 72 65 20 74 |ince it'|s rare t|
|00001540| 68 61 74 0a 58 09 20 20 | 20 20 20 2a 20 61 6e 20 |hat.X. | * an |
|00001550| 61 63 63 65 70 74 69 6e | 67 20 6e 75 6d 62 65 72 |acceptin|g number|
|00001560| 20 73 65 74 20 69 73 20 | 6c 61 72 67 65 2e 0a 58 | set is |large..X|
|00001570| 09 20 20 20 20 20 2a 2f | 0a 58 09 20 20 20 20 66 |. */|.X. f|
|00001580| 6f 72 20 28 20 6a 20 3d | 20 31 3b 20 6a 20 3c 3d |or ( j =| 1; j <=|
|00001590| 20 6e 61 63 63 3b 20 2b | 2b 6a 20 29 0a 58 09 09 | nacc; +|+j ).X..|
|000015a0| 69 66 20 28 20 61 63 63 | 73 65 74 5b 6a 5d 20 26 |if ( acc|set[j] &|
|000015b0| 20 59 59 5f 54 52 41 49 | 4c 49 4e 47 5f 48 45 41 | YY_TRAI|LING_HEA|
|000015c0| 44 5f 4d 41 53 4b 20 29 | 0a 58 09 09 20 20 20 20 |D_MASK )|.X.. |
|000015d0| 7b 0a 58 09 09 20 20 20 | 20 66 70 72 69 6e 74 66 |{.X.. | fprintf|
|000015e0| 28 20 73 74 64 65 72 72 | 2c 0a 58 09 09 20 20 20 |( stderr|,.X.. |
|000015f0| 20 20 22 25 73 3a 20 44 | 61 6e 67 65 72 6f 75 73 | "%s: D|angerous|
|00001600| 20 74 72 61 69 6c 69 6e | 67 20 63 6f 6e 74 65 78 | trailin|g contex|
|00001610| 74 20 69 6e 20 72 75 6c | 65 20 61 74 20 6c 69 6e |t in rul|e at lin|
|00001620| 65 20 25 64 5c 6e 22 2c | 0a 58 09 09 09 20 20 20 |e %d\n",|.X... |
|00001630| 20 20 70 72 6f 67 72 61 | 6d 5f 6e 61 6d 65 2c 20 | progra|m_name, |
|00001640| 72 75 6c 65 5f 6c 69 6e | 65 6e 75 6d 5b 61 72 5d |rule_lin|enum[ar]|
|00001650| 20 29 3b 0a 58 09 09 20 | 20 20 20 72 65 74 75 72 | );.X.. | retur|
|00001660| 6e 3b 0a 58 09 09 20 20 | 20 20 7d 0a 58 09 20 20 |n;.X.. | }.X. |
|00001670| 20 20 7d 0a 58 09 7d 0a | 58 20 20 20 20 7d 0a 58 | }.X.}.|X }.X|
|00001680| 0a 58 0a 58 2f 2a 20 64 | 75 6d 70 5f 61 73 73 6f |.X.X/* d|ump_asso|
|00001690| 63 69 61 74 65 64 5f 72 | 75 6c 65 73 20 2d 20 6c |ciated_r|ules - l|
|000016a0| 69 73 74 20 74 68 65 20 | 72 75 6c 65 73 20 61 73 |ist the |rules as|
|000016b0| 73 6f 63 69 61 74 65 64 | 20 77 69 74 68 20 61 20 |sociated| with a |
|000016c0| 44 46 41 20 73 74 61 74 | 65 0a 58 20 2a 0a 58 20 |DFA stat|e.X *.X |
|000016d0| 2a 20 73 79 6e 6f 70 69 | 73 69 73 0a 58 20 2a 20 |* synopi|sis.X * |
|000016e0| 20 20 20 20 69 6e 74 20 | 64 73 3b 0a 58 20 2a 20 | int |ds;.X * |
|000016f0| 20 20 20 20 46 49 4c 45 | 20 2a 66 69 6c 65 3b 0a | FILE| *file;.|
|00001700| 58 20 2a 20 20 20 20 20 | 64 75 6d 70 5f 61 73 73 |X * |dump_ass|
|00001710| 6f 63 69 61 74 65 64 5f | 72 75 6c 65 73 28 20 66 |ociated_|rules( f|
|00001720| 69 6c 65 2c 20 64 73 20 | 29 3b 0a 58 20 2a 0a 58 |ile, ds |);.X *.X|
|00001730| 20 2a 20 67 6f 65 73 20 | 74 68 72 6f 75 67 68 20 | * goes |through |
|00001740| 74 68 65 20 73 65 74 20 | 6f 66 20 4e 46 41 20 73 |the set |of NFA s|
|00001750| 74 61 74 65 73 20 61 73 | 73 6f 63 69 61 74 65 64 |tates as|sociated|
|00001760| 20 77 69 74 68 20 74 68 | 65 20 44 46 41 20 61 6e | with th|e DFA an|
|00001770| 64 0a 58 20 2a 20 65 78 | 74 72 61 63 74 73 20 74 |d.X * ex|tracts t|
|00001780| 68 65 20 66 69 72 73 74 | 20 4d 41 58 5f 41 53 53 |he first| MAX_ASS|
|00001790| 4f 43 5f 52 55 4c 45 53 | 20 75 6e 69 71 75 65 20 |OC_RULES| unique |
|000017a0| 72 75 6c 65 73 2c 20 73 | 6f 72 74 73 20 74 68 65 |rules, s|orts the|
|000017b0| 6d 2c 0a 58 20 2a 20 61 | 6e 64 20 77 72 69 74 65 |m,.X * a|nd write|
|000017c0| 73 20 61 20 72 65 70 6f | 72 74 20 74 6f 20 74 68 |s a repo|rt to th|
|000017d0| 65 20 67 69 76 65 6e 20 | 66 69 6c 65 0a 58 20 2a |e given |file.X *|
|000017e0| 2f 0a 58 0a 58 76 6f 69 | 64 20 64 75 6d 70 5f 61 |/.X.Xvoi|d dump_a|
|000017f0| 73 73 6f 63 69 61 74 65 | 64 5f 72 75 6c 65 73 28 |ssociate|d_rules(|
|00001800| 20 66 69 6c 65 2c 20 64 | 73 20 29 0a 58 46 49 4c | file, d|s ).XFIL|
|00001810| 45 20 2a 66 69 6c 65 3b | 0a 58 69 6e 74 20 64 73 |E *file;|.Xint ds|
|00001820| 3b 0a 58 0a 58 20 20 20 | 20 7b 0a 58 20 20 20 20 |;.X.X | {.X |
|00001830| 72 65 67 69 73 74 65 72 | 20 69 6e 74 20 69 2c 20 |register| int i, |
|00001840| 6a 3b 0a 58 20 20 20 20 | 72 65 67 69 73 74 65 72 |j;.X |register|
|00001850| 20 69 6e 74 20 6e 75 6d | 5f 61 73 73 6f 63 69 61 | int num|_associa|
|00001860| 74 65 64 5f 72 75 6c 65 | 73 20 3d 20 30 3b 0a 58 |ted_rule|s = 0;.X|
|00001870| 20 20 20 20 69 6e 74 20 | 72 75 6c 65 5f 73 65 74 | int |rule_set|
|00001880| 5b 4d 41 58 5f 41 53 53 | 4f 43 5f 52 55 4c 45 53 |[MAX_ASS|OC_RULES|
|00001890| 20 2b 20 31 5d 3b 0a 58 | 20 20 20 20 69 6e 74 20 | + 1];.X| int |
|000018a0| 2a 64 73 65 74 20 3d 20 | 64 73 73 5b 64 73 5d 3b |*dset = |dss[ds];|
|000018b0| 0a 58 20 20 20 20 69 6e | 74 20 73 69 7a 65 20 3d |.X in|t size =|
|000018c0| 20 64 66 61 73 69 7a 5b | 64 73 5d 3b 0a 58 20 20 | dfasiz[|ds];.X |
|000018d0| 20 20 0a 58 20 20 20 20 | 66 6f 72 20 28 20 69 20 | .X |for ( i |
|000018e0| 3d 20 31 3b 20 69 20 3c | 3d 20 73 69 7a 65 3b 20 |= 1; i <|= size; |
|000018f0| 2b 2b 69 20 29 0a 58 09 | 7b 0a 58 09 72 65 67 69 |++i ).X.|{.X.regi|
|00001900| 73 74 65 72 20 72 75 6c | 65 5f 6e 75 6d 20 3d 20 |ster rul|e_num = |
|00001910| 72 75 6c 65 5f 6c 69 6e | 65 6e 75 6d 5b 61 73 73 |rule_lin|enum[ass|
|00001920| 6f 63 5f 72 75 6c 65 5b | 64 73 65 74 5b 69 5d 5d |oc_rule[|dset[i]]|
|00001930| 5d 3b 0a 58 0a 58 09 66 | 6f 72 20 28 20 6a 20 3d |];.X.X.f|or ( j =|
|00001940| 20 31 3b 20 6a 20 3c 3d | 20 6e 75 6d 5f 61 73 73 | 1; j <=| num_ass|
|00001950| 6f 63 69 61 74 65 64 5f | 72 75 6c 65 73 3b 20 2b |ociated_|rules; +|
|00001960| 2b 6a 20 29 0a 58 09 20 | 20 20 20 69 66 20 28 20 |+j ).X. | if ( |
|00001970| 72 75 6c 65 5f 6e 75 6d | 20 3d 3d 20 72 75 6c 65 |rule_num| == rule|
|00001980| 5f 73 65 74 5b 6a 5d 20 | 29 0a 58 09 09 62 72 65 |_set[j] |).X..bre|
|00001990| 61 6b 3b 0a 58 0a 58 09 | 69 66 20 28 20 6a 20 3e |ak;.X.X.|if ( j >|
|000019a0| 20 6e 75 6d 5f 61 73 73 | 6f 63 69 61 74 65 64 5f | num_ass|ociated_|
|000019b0| 72 75 6c 65 73 20 29 0a | 58 09 20 20 20 20 7b 20 |rules ).|X. { |
|000019c0| 2f 2a 20 6e 65 77 20 72 | 75 6c 65 20 2a 2f 0a 58 |/* new r|ule */.X|
|000019d0| 09 20 20 20 20 69 66 20 | 28 20 6e 75 6d 5f 61 73 |. if |( num_as|
|000019e0| 73 6f 63 69 61 74 65 64 | 5f 72 75 6c 65 73 20 3c |sociated|_rules <|
|000019f0| 20 4d 41 58 5f 41 53 53 | 4f 43 5f 52 55 4c 45 53 | MAX_ASS|OC_RULES|
|00001a00| 20 29 0a 58 09 09 72 75 | 6c 65 5f 73 65 74 5b 2b | ).X..ru|le_set[+|
|00001a10| 2b 6e 75 6d 5f 61 73 73 | 6f 63 69 61 74 65 64 5f |+num_ass|ociated_|
|00001a20| 72 75 6c 65 73 5d 20 3d | 20 72 75 6c 65 5f 6e 75 |rules] =| rule_nu|
|00001a30| 6d 3b 0a 58 09 20 20 20 | 20 7d 0a 58 09 7d 0a 58 |m;.X. | }.X.}.X|
|00001a40| 0a 58 20 20 20 20 62 75 | 62 62 6c 65 28 20 72 75 |.X bu|bble( ru|
|00001a50| 6c 65 5f 73 65 74 2c 20 | 6e 75 6d 5f 61 73 73 6f |le_set, |num_asso|
|00001a60| 63 69 61 74 65 64 5f 72 | 75 6c 65 73 20 29 3b 0a |ciated_r|ules );.|
|00001a70| 58 0a 58 20 20 20 20 66 | 70 72 69 6e 74 66 28 20 |X.X f|printf( |
|00001a80| 66 69 6c 65 2c 20 22 20 | 61 73 73 6f 63 69 61 74 |file, " |associat|
|00001a90| 65 64 20 72 75 6c 65 20 | 6c 69 6e 65 20 6e 75 6d |ed rule |line num|
|00001aa0| 62 65 72 73 3a 22 20 29 | 3b 0a 58 0a 58 20 20 20 |bers:" )|;.X.X |
|00001ab0| 20 66 6f 72 20 28 20 69 | 20 3d 20 31 3b 20 69 20 | for ( i| = 1; i |
|00001ac0| 3c 3d 20 6e 75 6d 5f 61 | 73 73 6f 63 69 61 74 65 |<= num_a|ssociate|
|00001ad0| 64 5f 72 75 6c 65 73 3b | 20 2b 2b 69 20 29 0a 58 |d_rules;| ++i ).X|
|00001ae0| 09 7b 0a 58 09 69 66 20 | 28 20 69 20 25 20 38 20 |.{.X.if |( i % 8 |
|00001af0| 3d 3d 20 31 20 29 0a 58 | 09 20 20 20 20 70 75 74 |== 1 ).X|. put|
|00001b00| 63 28 20 27 5c 6e 27 2c | 20 66 69 6c 65 20 29 3b |c( '\n',| file );|
|00001b10| 0a 58 09 0a 58 09 66 70 | 72 69 6e 74 66 28 20 66 |.X..X.fp|rintf( f|
|00001b20| 69 6c 65 2c 20 22 5c 74 | 25 64 22 2c 20 72 75 6c |ile, "\t|%d", rul|
|00001b30| 65 5f 73 65 74 5b 69 5d | 20 29 3b 0a 58 09 7d 0a |e_set[i]| );.X.}.|
|00001b40| 58 20 20 20 20 0a 58 20 | 20 20 20 70 75 74 63 28 |X .X | putc(|
|00001b50| 20 27 5c 6e 27 2c 20 66 | 69 6c 65 20 29 3b 0a 58 | '\n', f|ile );.X|
|00001b60| 20 20 20 20 7d 0a 58 0a | 58 0a 58 2f 2a 20 64 75 | }.X.|X.X/* du|
|00001b70| 6d 70 5f 74 72 61 6e 73 | 69 74 69 6f 6e 73 20 2d |mp_trans|itions -|
|00001b80| 20 6c 69 73 74 20 74 68 | 65 20 74 72 61 6e 73 69 | list th|e transi|
|00001b90| 74 69 6f 6e 73 20 61 73 | 73 6f 63 69 61 74 65 64 |tions as|sociated|
|00001ba0| 20 77 69 74 68 20 61 20 | 44 46 41 20 73 74 61 74 | with a |DFA stat|
|00001bb0| 65 0a 58 20 2a 0a 58 20 | 2a 20 73 79 6e 6f 70 69 |e.X *.X |* synopi|
|00001bc0| 73 69 73 0a 58 20 2a 20 | 20 20 20 20 69 6e 74 20 |sis.X * | int |
|00001bd0| 73 74 61 74 65 5b 6e 75 | 6d 65 63 73 5d 3b 0a 58 |state[nu|mecs];.X|
|00001be0| 20 2a 20 20 20 20 20 46 | 49 4c 45 20 2a 66 69 6c | * F|ILE *fil|
|00001bf0| 65 3b 0a 58 20 2a 20 20 | 20 20 20 64 75 6d 70 5f |e;.X * | dump_|
|00001c00| 74 72 61 6e 73 69 74 69 | 6f 6e 73 28 20 66 69 6c |transiti|ons( fil|
|00001c10| 65 2c 20 73 74 61 74 65 | 20 29 3b 0a 58 20 2a 0a |e, state| );.X *.|
|00001c20| 58 20 2a 20 67 6f 65 73 | 20 74 68 72 6f 75 67 68 |X * goes| through|
|00001c30| 20 74 68 65 20 73 65 74 | 20 6f 66 20 6f 75 74 2d | the set| of out-|
|00001c40| 74 72 61 6e 73 69 74 69 | 6f 6e 73 20 61 6e 64 20 |transiti|ons and |
|00001c50| 6c 69 73 74 73 20 74 68 | 65 6d 20 69 6e 20 68 75 |lists th|em in hu|
|00001c60| 6d 61 6e 2d 72 65 61 64 | 61 62 6c 65 0a 58 20 2a |man-read|able.X *|
|00001c70| 20 66 6f 72 6d 20 28 69 | 2e 65 2e 2c 20 6e 6f 74 | form (i|.e., not|
|00001c80| 20 61 73 20 65 71 75 69 | 76 61 6c 65 6e 63 65 20 | as equi|valence |
|00001c90| 63 6c 61 73 73 65 73 29 | 3b 20 61 6c 73 6f 20 6c |classes)|; also l|
|00001ca0| 69 73 74 73 20 6a 61 6d | 20 74 72 61 6e 73 69 74 |ists jam| transit|
|00001cb0| 69 6f 6e 73 0a 58 20 2a | 20 28 69 2e 65 2e 2c 20 |ions.X *| (i.e., |
|00001cc0| 61 6c 6c 20 74 68 6f 73 | 65 20 77 68 69 63 68 20 |all thos|e which |
|00001cd0| 61 72 65 20 6e 6f 74 20 | 6f 75 74 2d 74 72 61 6e |are not |out-tran|
|00001ce0| 73 69 74 69 6f 6e 73 2c | 20 70 6c 75 73 20 45 4f |sitions,| plus EO|
|00001cf0| 46 29 2e 20 20 54 68 65 | 20 64 75 6d 70 0a 58 20 |F). The| dump.X |
|00001d00| 2a 20 69 73 20 64 6f 6e | 65 20 74 6f 20 74 68 65 |* is don|e to the|
|00001d10| 20 67 69 76 65 6e 20 66 | 69 6c 65 2e 0a 58 20 2a | given f|ile..X *|
|00001d20| 2f 0a 58 0a 58 76 6f 69 | 64 20 64 75 6d 70 5f 74 |/.X.Xvoi|d dump_t|
|00001d30| 72 61 6e 73 69 74 69 6f | 6e 73 28 20 66 69 6c 65 |ransitio|ns( file|
|00001d40| 2c 20 73 74 61 74 65 20 | 29 0a 58 46 49 4c 45 20 |, state |).XFILE |
|00001d50| 2a 66 69 6c 65 3b 0a 58 | 69 6e 74 20 73 74 61 74 |*file;.X|int stat|
|00001d60| 65 5b 5d 3b 0a 58 0a 58 | 20 20 20 20 7b 0a 58 20 |e[];.X.X| {.X |
|00001d70| 20 20 20 72 65 67 69 73 | 74 65 72 20 69 6e 74 20 | regis|ter int |
|00001d80| 69 2c 20 65 63 3b 0a 58 | 20 20 20 20 69 6e 74 20 |i, ec;.X| int |
|00001d90| 6f 75 74 5f 63 68 61 72 | 5f 73 65 74 5b 43 53 49 |out_char|_set[CSI|
|00001da0| 5a 45 5d 3b 0a 58 0a 58 | 20 20 20 20 66 6f 72 20 |ZE];.X.X| for |
|00001db0| 28 20 69 20 3d 20 30 3b | 20 69 20 3c 20 63 73 69 |( i = 0;| i < csi|
|00001dc0| 7a 65 3b 20 2b 2b 69 20 | 29 0a 58 09 7b 0a 58 09 |ze; ++i |).X.{.X.|
|00001dd0| 65 63 20 3d 20 61 62 73 | 28 20 65 63 67 72 6f 75 |ec = abs|( ecgrou|
|00001de0| 70 5b 69 5d 20 29 3b 0a | 58 09 6f 75 74 5f 63 68 |p[i] );.|X.out_ch|
|00001df0| 61 72 5f 73 65 74 5b 69 | 5d 20 3d 20 73 74 61 74 |ar_set[i|] = stat|
|00001e00| 65 5b 65 63 5d 3b 0a 58 | 09 7d 0a 58 20 20 20 20 |e[ec];.X|.}.X |
|00001e10| 0a 58 20 20 20 20 66 70 | 72 69 6e 74 66 28 20 66 |.X fp|rintf( f|
|00001e20| 69 6c 65 2c 20 22 20 6f | 75 74 2d 74 72 61 6e 73 |ile, " o|ut-trans|
|00001e30| 69 74 69 6f 6e 73 3a 20 | 22 20 29 3b 0a 58 0a 58 |itions: |" );.X.X|
|00001e40| 20 20 20 20 6c 69 73 74 | 5f 63 68 61 72 61 63 74 | list|_charact|
|00001e50| 65 72 5f 73 65 74 28 20 | 66 69 6c 65 2c 20 6f 75 |er_set( |file, ou|
|00001e60| 74 5f 63 68 61 72 5f 73 | 65 74 20 29 3b 0a 58 0a |t_char_s|et );.X.|
|00001e70| 58 20 20 20 20 2f 2a 20 | 6e 6f 77 20 69 6e 76 65 |X /* |now inve|
|00001e80| 72 74 20 74 68 65 20 6d | 65 6d 62 65 72 73 20 6f |rt the m|embers o|
|00001e90| 66 20 74 68 65 20 73 65 | 74 20 74 6f 20 67 65 74 |f the se|t to get|
|00001ea0| 20 74 68 65 20 6a 61 6d | 20 74 72 61 6e 73 69 74 | the jam| transit|
|00001eb0| 69 6f 6e 73 20 2a 2f 0a | 58 20 20 20 20 66 6f 72 |ions */.|X for|
|00001ec0| 20 28 20 69 20 3d 20 30 | 3b 20 69 20 3c 20 63 73 | ( i = 0|; i < cs|
|00001ed0| 69 7a 65 3b 20 2b 2b 69 | 20 29 0a 58 09 6f 75 74 |ize; ++i| ).X.out|
|00001ee0| 5f 63 68 61 72 5f 73 65 | 74 5b 69 5d 20 3d 20 21 |_char_se|t[i] = !|
|00001ef0| 20 6f 75 74 5f 63 68 61 | 72 5f 73 65 74 5b 69 5d | out_cha|r_set[i]|
|00001f00| 3b 0a 58 0a 58 20 20 20 | 20 66 70 72 69 6e 74 66 |;.X.X | fprintf|
|00001f10| 28 20 66 69 6c 65 2c 20 | 22 5c 6e 20 6a 61 6d 2d |( file, |"\n jam-|
|00001f20| 74 72 61 6e 73 69 74 69 | 6f 6e 73 3a 20 45 4f 46 |transiti|ons: EOF|
|00001f30| 20 22 20 29 3b 0a 58 0a | 58 20 20 20 20 6c 69 73 | " );.X.|X lis|
|00001f40| 74 5f 63 68 61 72 61 63 | 74 65 72 5f 73 65 74 28 |t_charac|ter_set(|
|00001f50| 20 66 69 6c 65 2c 20 6f | 75 74 5f 63 68 61 72 5f | file, o|ut_char_|
|00001f60| 73 65 74 20 29 3b 0a 58 | 0a 58 20 20 20 20 70 75 |set );.X|.X pu|
|00001f70| 74 63 28 20 27 5c 6e 27 | 2c 20 66 69 6c 65 20 29 |tc( '\n'|, file )|
|00001f80| 3b 0a 58 20 20 20 20 7d | 0a 58 0a 58 0a 58 2f 2a |;.X }|.X.X.X/*|
|00001f90| 20 65 70 73 63 6c 6f 73 | 75 72 65 20 2d 20 63 6f | epsclos|ure - co|
|00001fa0| 6e 73 74 72 75 63 74 20 | 74 68 65 20 65 70 73 69 |nstruct |the epsi|
|00001fb0| 6c 6f 6e 20 63 6c 6f 73 | 75 72 65 20 6f 66 20 61 |lon clos|ure of a|
|00001fc0| 20 73 65 74 20 6f 66 20 | 6e 64 66 61 20 73 74 61 | set of |ndfa sta|
|00001fd0| 74 65 73 0a 58 20 2a 0a | 58 20 2a 20 73 79 6e 6f |tes.X *.|X * syno|
|00001fe0| 70 73 69 73 0a 58 20 2a | 20 20 20 20 69 6e 74 20 |psis.X *| int |
|00001ff0| 74 5b 63 75 72 72 65 6e | 74 5f 6d 61 78 5f 64 66 |t[curren|t_max_df|
|00002000| 61 5f 73 69 7a 65 5d 2c | 20 6e 75 6d 73 74 61 74 |a_size],| numstat|
|00002010| 65 73 2c 20 61 63 63 73 | 65 74 5b 6e 75 6d 5f 72 |es, accs|et[num_r|
|00002020| 75 6c 65 73 20 2b 20 31 | 5d 2c 20 6e 61 63 63 3b |ules + 1|], nacc;|
|00002030| 0a 58 20 2a 20 20 20 20 | 69 6e 74 20 68 61 73 68 |.X * |int hash|
|00002040| 76 61 6c 3b 0a 58 20 2a | 20 20 20 20 69 6e 74 20 |val;.X *| int |
|00002050| 2a 65 70 73 63 6c 6f 73 | 75 72 65 28 29 3b 0a 58 |*epsclos|ure();.X|
|00002060| 20 2a 20 20 20 20 74 20 | 3d 20 65 70 73 63 6c 6f | * t |= epsclo|
|00002070| 73 75 72 65 28 20 74 2c | 20 26 6e 75 6d 73 74 61 |sure( t,| &numsta|
|00002080| 74 65 73 2c 20 61 63 63 | 73 65 74 2c 20 26 6e 61 |tes, acc|set, &na|
|00002090| 63 63 2c 20 26 68 61 73 | 68 76 61 6c 20 29 3b 0a |cc, &has|hval );.|
|000020a0| 58 20 2a 0a 58 20 2a 20 | 4e 4f 54 45 53 0a 58 20 |X *.X * |NOTES.X |
|000020b0| 2a 20 20 20 20 74 68 65 | 20 65 70 73 69 6c 6f 6e |* the| epsilon|
|000020c0| 20 63 6c 6f 73 75 72 65 | 20 69 73 20 74 68 65 20 | closure| is the |
|000020d0| 73 65 74 20 6f 66 20 61 | 6c 6c 20 73 74 61 74 65 |set of a|ll state|
|000020e0| 73 20 72 65 61 63 68 61 | 62 6c 65 20 62 79 20 61 |s reacha|ble by a|
|000020f0| 6e 20 61 72 62 69 74 72 | 61 72 79 0a 58 20 2a 20 |n arbitr|ary.X * |
|00002100| 20 6e 75 6d 62 65 72 20 | 6f 66 20 65 70 73 69 6c | number |of epsil|
|00002110| 6f 6e 20 74 72 61 6e 73 | 69 74 69 6f 6e 73 20 77 |on trans|itions w|
|00002120| 68 69 63 68 20 74 68 65 | 6d 73 65 6c 76 65 73 20 |hich the|mselves |
|00002130| 64 6f 20 6e 6f 74 20 68 | 61 76 65 20 65 70 73 69 |do not h|ave epsi|
|00002140| 6c 6f 6e 0a 58 20 2a 20 | 20 74 72 61 6e 73 69 74 |lon.X * | transit|
|00002150| 69 6f 6e 73 20 67 6f 69 | 6e 67 20 6f 75 74 2c 20 |ions goi|ng out, |
|00002160| 75 6e 69 6f 6e 65 64 20 | 77 69 74 68 20 74 68 65 |unioned |with the|
|00002170| 20 73 65 74 20 6f 66 20 | 73 74 61 74 65 73 20 77 | set of |states w|
|00002180| 68 69 63 68 20 68 61 76 | 65 20 6e 6f 6e 2d 6e 75 |hich hav|e non-nu|
|00002190| 6c 6c 0a 58 20 2a 20 20 | 61 63 63 65 70 74 69 6e |ll.X * |acceptin|
|000021a0| 67 20 6e 75 6d 62 65 72 | 73 2e 20 20 74 20 69 73 |g number|s. t is|
|000021b0| 20 61 6e 20 61 72 72 61 | 79 20 6f 66 20 73 69 7a | an arra|y of siz|
|000021c0| 65 20 6e 75 6d 73 74 61 | 74 65 73 20 6f 66 20 6e |e numsta|tes of n|
|000021d0| 66 61 20 73 74 61 74 65 | 20 6e 75 6d 62 65 72 73 |fa state| numbers|
|000021e0| 2e 0a 58 20 2a 20 20 55 | 70 6f 6e 20 72 65 74 75 |..X * U|pon retu|
|000021f0| 72 6e 2c 20 74 20 68 6f | 6c 64 73 20 74 68 65 20 |rn, t ho|lds the |
|00002200| 65 70 73 69 6c 6f 6e 20 | 63 6c 6f 73 75 72 65 20 |epsilon |closure |
|00002210| 61 6e 64 20 6e 75 6d 73 | 74 61 74 65 73 20 69 73 |and nums|tates is|
|00002220| 20 75 70 64 61 74 65 64 | 2e 20 20 61 63 63 73 65 | updated|. accse|
|00002230| 74 0a 58 20 2a 20 20 68 | 6f 6c 64 73 20 61 20 6c |t.X * h|olds a l|
|00002240| 69 73 74 20 6f 66 20 74 | 68 65 20 61 63 63 65 70 |ist of t|he accep|
|00002250| 74 69 6e 67 20 6e 75 6d | 62 65 72 73 2c 20 61 6e |ting num|bers, an|
|00002260| 64 20 74 68 65 20 73 69 | 7a 65 20 6f 66 20 61 63 |d the si|ze of ac|
|00002270| 63 73 65 74 20 69 73 20 | 67 69 76 65 6e 0a 58 20 |cset is |given.X |
|00002280| 2a 20 20 62 79 20 6e 61 | 63 63 2e 20 20 74 20 6d |* by na|cc. t m|
|00002290| 61 79 20 62 65 20 73 75 | 62 6a 65 63 74 65 64 20 |ay be su|bjected |
|000022a0| 74 6f 20 72 65 61 6c 6c | 6f 63 61 74 69 6f 6e 20 |to reall|ocation |
|000022b0| 69 66 20 69 74 20 69 73 | 20 6e 6f 74 20 6c 61 72 |if it is| not lar|
|000022c0| 67 65 20 65 6e 6f 75 67 | 68 0a 58 20 2a 20 20 74 |ge enoug|h.X * t|
|000022d0| 6f 20 68 6f 6c 64 20 74 | 68 65 20 65 70 73 69 6c |o hold t|he epsil|
|000022e0| 6f 6e 20 63 6c 6f 73 75 | 72 65 2e 0a 58 20 2a 0a |on closu|re..X *.|
|000022f0| 58 20 2a 20 20 20 20 68 | 61 73 68 76 61 6c 20 69 |X * h|ashval i|
|00002300| 73 20 74 68 65 20 68 61 | 73 68 20 76 61 6c 75 65 |s the ha|sh value|
|00002310| 20 66 6f 72 20 74 68 65 | 20 64 66 61 20 63 6f 72 | for the| dfa cor|
|00002320| 72 65 73 70 6f 6e 64 69 | 6e 67 20 74 6f 20 74 68 |respondi|ng to th|
|00002330| 65 20 73 74 61 74 65 20 | 73 65 74 0a 58 20 2a 2f |e state |set.X */|
|00002340| 0a 58 0a 58 69 6e 74 20 | 2a 65 70 73 63 6c 6f 73 |.X.Xint |*epsclos|
|00002350| 75 72 65 28 20 74 2c 20 | 6e 73 5f 61 64 64 72 2c |ure( t, |ns_addr,|
|00002360| 20 61 63 63 73 65 74 2c | 20 6e 61 63 63 5f 61 64 | accset,| nacc_ad|
|00002370| 64 72 2c 20 68 76 5f 61 | 64 64 72 20 29 0a 58 69 |dr, hv_a|ddr ).Xi|
|00002380| 6e 74 20 2a 74 2c 20 2a | 6e 73 5f 61 64 64 72 2c |nt *t, *|ns_addr,|
|00002390| 20 61 63 63 73 65 74 5b | 5d 2c 20 2a 6e 61 63 63 | accset[|], *nacc|
|000023a0| 5f 61 64 64 72 2c 20 2a | 68 76 5f 61 64 64 72 3b |_addr, *|hv_addr;|
|000023b0| 0a 58 0a 58 20 20 20 20 | 7b 0a 58 20 20 20 20 72 |.X.X |{.X r|
|000023c0| 65 67 69 73 74 65 72 20 | 69 6e 74 20 73 74 6b 70 |egister |int stkp|
|000023d0| 6f 73 2c 20 6e 73 2c 20 | 74 73 70 3b 0a 58 20 20 |os, ns, |tsp;.X |
|000023e0| 20 20 69 6e 74 20 6e 75 | 6d 73 74 61 74 65 73 20 | int nu|mstates |
|000023f0| 3d 20 2a 6e 73 5f 61 64 | 64 72 2c 20 6e 61 63 63 |= *ns_ad|dr, nacc|
|00002400| 2c 20 68 61 73 68 76 61 | 6c 2c 20 74 72 61 6e 73 |, hashva|l, trans|
|00002410| 73 79 6d 2c 20 6e 66 61 | 63 63 6e 75 6d 3b 0a 58 |sym, nfa|ccnum;.X|
|00002420| 20 20 20 20 69 6e 74 20 | 73 74 6b 65 6e 64 2c 20 | int |stkend, |
|00002430| 6e 73 74 61 74 65 3b 0a | 58 20 20 20 20 73 74 61 |nstate;.|X sta|
|00002440| 74 69 63 20 69 6e 74 20 | 64 69 64 5f 73 74 6b 5f |tic int |did_stk_|
|00002450| 69 6e 69 74 20 3d 20 66 | 61 6c 73 65 2c 20 2a 73 |init = f|alse, *s|
|00002460| 74 6b 3b 20 0a 58 0a 58 | 23 64 65 66 69 6e 65 20 |tk; .X.X|#define |
|00002470| 4d 41 52 4b 5f 53 54 41 | 54 45 28 73 74 61 74 65 |MARK_STA|TE(state|
|00002480| 29 20 5c 0a 58 09 74 72 | 61 6e 73 31 5b 73 74 61 |) \.X.tr|ans1[sta|
|00002490| 74 65 5d 20 3d 20 74 72 | 61 6e 73 31 5b 73 74 61 |te] = tr|ans1[sta|
|000024a0| 74 65 5d 20 2d 20 4d 41 | 52 4b 45 52 5f 44 49 46 |te] - MA|RKER_DIF|
|000024b0| 46 45 52 45 4e 43 45 3b | 0a 58 0a 58 23 64 65 66 |FERENCE;|.X.X#def|
|000024c0| 69 6e 65 20 49 53 5f 4d | 41 52 4b 45 44 28 73 74 |ine IS_M|ARKED(st|
|000024d0| 61 74 65 29 20 28 74 72 | 61 6e 73 31 5b 73 74 61 |ate) (tr|ans1[sta|
|000024e0| 74 65 5d 20 3c 20 30 29 | 0a 58 0a 58 23 64 65 66 |te] < 0)|.X.X#def|
|000024f0| 69 6e 65 20 55 4e 4d 41 | 52 4b 5f 53 54 41 54 45 |ine UNMA|RK_STATE|
|00002500| 28 73 74 61 74 65 29 20 | 5c 0a 58 09 74 72 61 6e |(state) |\.X.tran|
|00002510| 73 31 5b 73 74 61 74 65 | 5d 20 3d 20 74 72 61 6e |s1[state|] = tran|
|00002520| 73 31 5b 73 74 61 74 65 | 5d 20 2b 20 4d 41 52 4b |s1[state|] + MARK|
|00002530| 45 52 5f 44 49 46 46 45 | 52 45 4e 43 45 3b 0a 58 |ER_DIFFE|RENCE;.X|
|00002540| 0a 58 23 64 65 66 69 6e | 65 20 43 48 45 43 4b 5f |.X#defin|e CHECK_|
|00002550| 41 43 43 45 50 54 28 73 | 74 61 74 65 29 20 5c 0a |ACCEPT(s|tate) \.|
|00002560| 58 09 7b 20 5c 0a 58 09 | 6e 66 61 63 63 6e 75 6d |X.{ \.X.|nfaccnum|
|00002570| 20 3d 20 61 63 63 70 74 | 6e 75 6d 5b 73 74 61 74 | = accpt|num[stat|
|00002580| 65 5d 3b 20 5c 0a 58 09 | 69 66 20 28 20 6e 66 61 |e]; \.X.|if ( nfa|
|00002590| 63 63 6e 75 6d 20 21 3d | 20 4e 49 4c 20 29 20 5c |ccnum !=| NIL ) \|
|000025a0| 0a 58 09 20 20 20 20 61 | 63 63 73 65 74 5b 2b 2b |.X. a|ccset[++|
|000025b0| 6e 61 63 63 5d 20 3d 20 | 6e 66 61 63 63 6e 75 6d |nacc] = |nfaccnum|
|000025c0| 3b 20 5c 0a 58 09 7d 0a | 58 0a 58 23 64 65 66 69 |; \.X.}.|X.X#defi|
|000025d0| 6e 65 20 44 4f 5f 52 45 | 41 4c 4c 4f 43 41 54 49 |ne DO_RE|ALLOCATI|
|000025e0| 4f 4e 20 5c 0a 58 09 7b | 20 5c 0a 58 09 63 75 72 |ON \.X.{| \.X.cur|
|000025f0| 72 65 6e 74 5f 6d 61 78 | 5f 64 66 61 5f 73 69 7a |rent_max|_dfa_siz|
|00002600| 65 20 2b 3d 20 4d 41 58 | 5f 44 46 41 5f 53 49 5a |e += MAX|_DFA_SIZ|
|00002610| 45 5f 49 4e 43 52 45 4d | 45 4e 54 3b 20 5c 0a 58 |E_INCREM|ENT; \.X|
|00002620| 09 2b 2b 6e 75 6d 5f 72 | 65 61 6c 6c 6f 63 73 3b |.++num_r|eallocs;|
|00002630| 20 5c 0a 58 09 74 20 3d | 20 72 65 61 6c 6c 6f 63 | \.X.t =| realloc|
|00002640| 61 74 65 5f 69 6e 74 65 | 67 65 72 5f 61 72 72 61 |ate_inte|ger_arra|
|00002650| 79 28 20 74 2c 20 63 75 | 72 72 65 6e 74 5f 6d 61 |y( t, cu|rrent_ma|
|00002660| 78 5f 64 66 61 5f 73 69 | 7a 65 20 29 3b 20 5c 0a |x_dfa_si|ze ); \.|
|00002670| 58 09 73 74 6b 20 3d 20 | 72 65 61 6c 6c 6f 63 61 |X.stk = |realloca|
|00002680| 74 65 5f 69 6e 74 65 67 | 65 72 5f 61 72 72 61 79 |te_integ|er_array|
|00002690| 28 20 73 74 6b 2c 20 63 | 75 72 72 65 6e 74 5f 6d |( stk, c|urrent_m|
|000026a0| 61 78 5f 64 66 61 5f 73 | 69 7a 65 20 29 3b 20 5c |ax_dfa_s|ize ); \|
|000026b0| 0a 58 09 7d 20 5c 0a 58 | 0a 58 23 64 65 66 69 6e |.X.} \.X|.X#defin|
|000026c0| 65 20 50 55 54 5f 4f 4e | 5f 53 54 41 43 4b 28 73 |e PUT_ON|_STACK(s|
|000026d0| 74 61 74 65 29 20 5c 0a | 58 09 7b 20 5c 0a 58 09 |tate) \.|X.{ \.X.|
|000026e0| 69 66 20 28 20 2b 2b 73 | 74 6b 65 6e 64 20 3e 3d |if ( ++s|tkend >=|
|000026f0| 20 63 75 72 72 65 6e 74 | 5f 6d 61 78 5f 64 66 61 | current|_max_dfa|
|00002700| 5f 73 69 7a 65 20 29 20 | 5c 0a 58 09 20 20 20 20 |_size ) |\.X. |
|00002710| 44 4f 5f 52 45 41 4c 4c | 4f 43 41 54 49 4f 4e 20 |DO_REALL|OCATION |
|00002720| 5c 0a 58 09 73 74 6b 5b | 73 74 6b 65 6e 64 5d 20 |\.X.stk[|stkend] |
|00002730| 3d 20 73 74 61 74 65 3b | 20 5c 0a 58 09 4d 41 52 |= state;| \.X.MAR|
|00002740| 4b 5f 53 54 41 54 45 28 | 73 74 61 74 65 29 20 5c |K_STATE(|state) \|
|00002750| 0a 58 09 7d 0a 58 0a 58 | 23 64 65 66 69 6e 65 20 |.X.}.X.X|#define |
|00002760| 41 44 44 5f 53 54 41 54 | 45 28 73 74 61 74 65 29 |ADD_STAT|E(state)|
|00002770| 20 5c 0a 58 09 7b 20 5c | 0a 58 09 69 66 20 28 20 | \.X.{ \|.X.if ( |
|00002780| 2b 2b 6e 75 6d 73 74 61 | 74 65 73 20 3e 3d 20 63 |++numsta|tes >= c|
|00002790| 75 72 72 65 6e 74 5f 6d | 61 78 5f 64 66 61 5f 73 |urrent_m|ax_dfa_s|
|000027a0| 69 7a 65 20 29 20 5c 0a | 58 09 20 20 20 20 44 4f |ize ) \.|X. DO|
|000027b0| 5f 52 45 41 4c 4c 4f 43 | 41 54 49 4f 4e 20 5c 0a |_REALLOC|ATION \.|
|000027c0| 58 09 74 5b 6e 75 6d 73 | 74 61 74 65 73 5d 20 3d |X.t[nums|tates] =|
|000027d0| 20 73 74 61 74 65 3b 20 | 5c 0a 58 09 68 61 73 68 | state; |\.X.hash|
|000027e0| 76 61 6c 20 3d 20 68 61 | 73 68 76 61 6c 20 2b 20 |val = ha|shval + |
|000027f0| 73 74 61 74 65 3b 20 5c | 0a 58 09 7d 0a 58 0a 58 |state; \|.X.}.X.X|
|00002800| 23 64 65 66 69 6e 65 20 | 53 54 41 43 4b 5f 53 54 |#define |STACK_ST|
|00002810| 41 54 45 28 73 74 61 74 | 65 29 20 5c 0a 58 09 7b |ATE(stat|e) \.X.{|
|00002820| 20 5c 0a 58 09 50 55 54 | 5f 4f 4e 5f 53 54 41 43 | \.X.PUT|_ON_STAC|
|00002830| 4b 28 73 74 61 74 65 29 | 20 5c 0a 58 09 43 48 45 |K(state)| \.X.CHE|
|00002840| 43 4b 5f 41 43 43 45 50 | 54 28 73 74 61 74 65 29 |CK_ACCEP|T(state)|
|00002850| 20 5c 0a 58 09 69 66 20 | 28 20 6e 66 61 63 63 6e | \.X.if |( nfaccn|
|00002860| 75 6d 20 21 3d 20 4e 49 | 4c 20 7c 7c 20 74 72 61 |um != NI|L || tra|
|00002870| 6e 73 63 68 61 72 5b 73 | 74 61 74 65 5d 20 21 3d |nschar[s|tate] !=|
|00002880| 20 53 59 4d 5f 45 50 53 | 49 4c 4f 4e 20 29 20 5c | SYM_EPS|ILON ) \|
|00002890| 0a 58 09 20 20 20 20 41 | 44 44 5f 53 54 41 54 45 |.X. A|DD_STATE|
|000028a0| 28 73 74 61 74 65 29 20 | 5c 0a 58 09 7d 0a 58 0a |(state) |\.X.}.X.|
|000028b0| 58 20 20 20 20 69 66 20 | 28 20 21 20 64 69 64 5f |X if |( ! did_|
|000028c0| 73 74 6b 5f 69 6e 69 74 | 20 29 0a 58 09 7b 0a 58 |stk_init| ).X.{.X|
|000028d0| 09 73 74 6b 20 3d 20 61 | 6c 6c 6f 63 61 74 65 5f |.stk = a|llocate_|
|000028e0| 69 6e 74 65 67 65 72 5f | 61 72 72 61 79 28 20 63 |integer_|array( c|
|000028f0| 75 72 72 65 6e 74 5f 6d | 61 78 5f 64 66 61 5f 73 |urrent_m|ax_dfa_s|
|00002900| 69 7a 65 20 29 3b 0a 58 | 09 64 69 64 5f 73 74 6b |ize );.X|.did_stk|
|00002910| 5f 69 6e 69 74 20 3d 20 | 74 72 75 65 3b 0a 58 09 |_init = |true;.X.|
|00002920| 7d 0a 58 0a 58 20 20 20 | 20 6e 61 63 63 20 3d 20 |}.X.X | nacc = |
|00002930| 73 74 6b 65 6e 64 20 3d | 20 68 61 73 68 76 61 6c |stkend =| hashval|
|00002940| 20 3d 20 30 3b 0a 58 0a | 58 20 20 20 20 66 6f 72 | = 0;.X.|X for|
|00002950| 20 28 20 6e 73 74 61 74 | 65 20 3d 20 31 3b 20 6e | ( nstat|e = 1; n|
|00002960| 73 74 61 74 65 20 3c 3d | 20 6e 75 6d 73 74 61 74 |state <=| numstat|
|00002970| 65 73 3b 20 2b 2b 6e 73 | 74 61 74 65 20 29 0a 58 |es; ++ns|tate ).X|
|00002980| 09 7b 0a 58 09 6e 73 20 | 3d 20 74 5b 6e 73 74 61 |.{.X.ns |= t[nsta|
|00002990| 74 65 5d 3b 0a 58 0a 58 | 09 2f 2a 20 74 68 65 20 |te];.X.X|./* the |
|000029a0| 73 74 61 74 65 20 63 6f | 75 6c 64 20 62 65 20 6d |state co|uld be m|
|000029b0| 61 72 6b 65 64 20 69 66 | 20 77 65 27 76 65 20 61 |arked if| we've a|
|000029c0| 6c 72 65 61 64 79 20 70 | 75 73 68 65 64 20 69 74 |lready p|ushed it|
|000029d0| 20 6f 6e 74 6f 0a 58 09 | 20 2a 20 74 68 65 20 73 | onto.X.| * the s|
|000029e0| 74 61 63 6b 0a 58 09 20 | 2a 2f 0a 58 09 69 66 20 |tack.X. |*/.X.if |
|000029f0| 28 20 21 20 49 53 5f 4d | 41 52 4b 45 44 28 6e 73 |( ! IS_M|ARKED(ns|
|00002a00| 29 20 29 0a 58 09 20 20 | 20 20 50 55 54 5f 4f 4e |) ).X. | PUT_ON|
|00002a10| 5f 53 54 41 43 4b 28 6e | 73 29 0a 58 0a 58 09 43 |_STACK(n|s).X.X.C|
|00002a20| 48 45 43 4b 5f 41 43 43 | 45 50 54 28 6e 73 29 0a |HECK_ACC|EPT(ns).|
|00002a30| 58 09 68 61 73 68 76 61 | 6c 20 3d 20 68 61 73 68 |X.hashva|l = hash|
|00002a40| 76 61 6c 20 2b 20 6e 73 | 3b 0a 58 09 7d 0a 58 0a |val + ns|;.X.}.X.|
|00002a50| 58 20 20 20 20 66 6f 72 | 20 28 20 73 74 6b 70 6f |X for| ( stkpo|
|00002a60| 73 20 3d 20 31 3b 20 73 | 74 6b 70 6f 73 20 3c 3d |s = 1; s|tkpos <=|
|00002a70| 20 73 74 6b 65 6e 64 3b | 20 2b 2b 73 74 6b 70 6f | stkend;| ++stkpo|
|00002a80| 73 20 29 0a 58 09 7b 0a | 58 09 6e 73 20 3d 20 73 |s ).X.{.|X.ns = s|
|00002a90| 74 6b 5b 73 74 6b 70 6f | 73 5d 3b 0a 58 09 74 72 |tk[stkpo|s];.X.tr|
|00002aa0| 61 6e 73 73 79 6d 20 3d | 20 74 72 61 6e 73 63 68 |anssym =| transch|
|00002ab0| 61 72 5b 6e 73 5d 3b 0a | 58 0a 58 09 69 66 20 28 |ar[ns];.|X.X.if (|
|00002ac0| 20 74 72 61 6e 73 73 79 | 6d 20 3d 3d 20 53 59 4d | transsy|m == SYM|
|00002ad0| 5f 45 50 53 49 4c 4f 4e | 20 29 0a 58 09 20 20 20 |_EPSILON| ).X. |
|00002ae0| 20 7b 0a 58 09 20 20 20 | 20 74 73 70 20 3d 20 74 | {.X. | tsp = t|
|00002af0| 72 61 6e 73 31 5b 6e 73 | 5d 20 2b 20 4d 41 52 4b |rans1[ns|] + MARK|
|00002b00| 45 52 5f 44 49 46 46 45 | 52 45 4e 43 45 3b 0a 58 |ER_DIFFE|RENCE;.X|
|00002b10| 0a 58 09 20 20 20 20 69 | 66 20 28 20 74 73 70 20 |.X. i|f ( tsp |
|00002b20| 21 3d 20 4e 4f 5f 54 52 | 41 4e 53 49 54 49 4f 4e |!= NO_TR|ANSITION|
|00002b30| 20 29 0a 58 09 09 7b 0a | 58 09 09 69 66 20 28 20 | ).X..{.|X..if ( |
|00002b40| 21 20 49 53 5f 4d 41 52 | 4b 45 44 28 74 73 70 29 |! IS_MAR|KED(tsp)|
|00002b50| 20 29 0a 58 09 09 20 20 | 20 20 53 54 41 43 4b 5f | ).X.. | STACK_|
|00002b60| 53 54 41 54 45 28 74 73 | 70 29 0a 58 0a 58 09 09 |STATE(ts|p).X.X..|
|00002b70| 74 73 70 20 3d 20 74 72 | 61 6e 73 32 5b 6e 73 5d |tsp = tr|ans2[ns]|
|00002b80| 3b 0a 58 0a 58 09 09 69 | 66 20 28 20 74 73 70 20 |;.X.X..i|f ( tsp |
|00002b90| 21 3d 20 4e 4f 5f 54 52 | 41 4e 53 49 54 49 4f 4e |!= NO_TR|ANSITION|
|00002ba0| 20 29 0a 58 09 09 20 20 | 20 20 69 66 20 28 20 21 | ).X.. | if ( !|
|00002bb0| 20 49 53 5f 4d 41 52 4b | 45 44 28 74 73 70 29 20 | IS_MARK|ED(tsp) |
|00002bc0| 29 0a 58 09 09 09 53 54 | 41 43 4b 5f 53 54 41 54 |).X...ST|ACK_STAT|
|00002bd0| 45 28 74 73 70 29 0a 58 | 09 09 7d 0a 58 09 20 20 |E(tsp).X|..}.X. |
|00002be0| 20 20 7d 0a 58 09 7d 0a | 58 0a 58 20 20 20 20 2f | }.X.}.|X.X /|
|00002bf0| 2a 20 63 6c 65 61 72 20 | 6f 75 74 20 22 76 69 73 |* clear |out "vis|
|00002c00| 69 74 22 20 6d 61 72 6b | 65 72 73 20 2a 2f 0a 58 |it" mark|ers */.X|
|00002c10| 0a 58 20 20 20 20 66 6f | 72 20 28 20 73 74 6b 70 |.X fo|r ( stkp|
|00002c20| 6f 73 20 3d 20 31 3b 20 | 73 74 6b 70 6f 73 20 3c |os = 1; |stkpos <|
|00002c30| 3d 20 73 74 6b 65 6e 64 | 3b 20 2b 2b 73 74 6b 70 |= stkend|; ++stkp|
|00002c40| 6f 73 20 29 0a 58 09 7b | 0a 58 09 69 66 20 28 20 |os ).X.{|.X.if ( |
|00002c50| 49 53 5f 4d 41 52 4b 45 | 44 28 73 74 6b 5b 73 74 |IS_MARKE|D(stk[st|
|00002c60| 6b 70 6f 73 5d 29 20 29 | 0a 58 09 20 20 20 20 7b |kpos]) )|.X. {|
|00002c70| 0a 58 09 20 20 20 20 55 | 4e 4d 41 52 4b 5f 53 54 |.X. U|NMARK_ST|
|00002c80| 41 54 45 28 73 74 6b 5b | 73 74 6b 70 6f 73 5d 29 |ATE(stk[|stkpos])|
|00002c90| 0a 58 09 20 20 20 20 7d | 0a 58 09 65 6c 73 65 0a |.X. }|.X.else.|
|00002ca0| 58 09 20 20 20 20 66 6c | 65 78 66 61 74 61 6c 28 |X. fl|exfatal(|
|00002cb0| 20 22 63 6f 6e 73 69 73 | 74 65 6e 63 79 20 63 68 | "consis|tency ch|
|00002cc0| 65 63 6b 20 66 61 69 6c | 65 64 20 69 6e 20 65 70 |eck fail|ed in ep|
|00002cd0| 73 63 6c 6f 73 75 72 65 | 28 29 22 20 29 3b 0a 58 |sclosure|()" );.X|
|00002ce0| 09 7d 0a 58 0a 58 20 20 | 20 20 2a 6e 73 5f 61 64 |.}.X.X | *ns_ad|
|00002cf0| 64 72 20 3d 20 6e 75 6d | 73 74 61 74 65 73 3b 0a |dr = num|states;.|
|00002d00| 58 20 20 20 20 2a 68 76 | 5f 61 64 64 72 20 3d 20 |X *hv|_addr = |
|00002d10| 68 61 73 68 76 61 6c 3b | 0a 58 20 20 20 20 2a 6e |hashval;|.X *n|
|00002d20| 61 63 63 5f 61 64 64 72 | 20 3d 20 6e 61 63 63 3b |acc_addr| = nacc;|
|00002d30| 0a 58 0a 58 20 20 20 20 | 72 65 74 75 72 6e 20 28 |.X.X |return (|
|00002d40| 20 74 20 29 3b 0a 58 20 | 20 20 20 7d 0a 58 0a 58 | t );.X | }.X.X|
|00002d50| 0a 58 2f 2a 20 69 6e 63 | 72 65 61 73 65 5f 6d 61 |.X/* inc|rease_ma|
|00002d60| 78 5f 64 66 61 73 20 2d | 20 69 6e 63 72 65 61 73 |x_dfas -| increas|
|00002d70| 65 20 74 68 65 20 6d 61 | 78 69 6d 75 6d 20 6e 75 |e the ma|ximum nu|
|00002d80| 6d 62 65 72 20 6f 66 20 | 44 46 41 73 20 2a 2f 0a |mber of |DFAs */.|
|00002d90| 58 0a 58 76 6f 69 64 20 | 69 6e 63 72 65 61 73 65 |X.Xvoid |increase|
|00002da0| 5f 6d 61 78 5f 64 66 61 | 73 28 29 0a 58 0a 58 20 |_max_dfa|s().X.X |
|00002db0| 20 20 20 7b 0a 58 20 20 | 20 20 63 75 72 72 65 6e | {.X | curren|
|00002dc0| 74 5f 6d 61 78 5f 64 66 | 61 73 20 2b 3d 20 4d 41 |t_max_df|as += MA|
|00002dd0| 58 5f 44 46 41 53 5f 49 | 4e 43 52 45 4d 45 4e 54 |X_DFAS_I|NCREMENT|
|00002de0| 3b 0a 58 0a 58 20 20 20 | 20 2b 2b 6e 75 6d 5f 72 |;.X.X | ++num_r|
|00002df0| 65 61 6c 6c 6f 63 73 3b | 0a 58 0a 58 20 20 20 20 |eallocs;|.X.X |
|00002e00| 62 61 73 65 20 3d 20 72 | 65 61 6c 6c 6f 63 61 74 |base = r|eallocat|
|00002e10| 65 5f 69 6e 74 65 67 65 | 72 5f 61 72 72 61 79 28 |e_intege|r_array(|
|00002e20| 20 62 61 73 65 2c 20 63 | 75 72 72 65 6e 74 5f 6d | base, c|urrent_m|
|00002e30| 61 78 5f 64 66 61 73 20 | 29 3b 0a 58 20 20 20 20 |ax_dfas |);.X |
|00002e40| 64 65 66 20 3d 20 72 65 | 61 6c 6c 6f 63 61 74 65 |def = re|allocate|
|00002e50| 5f 69 6e 74 65 67 65 72 | 5f 61 72 72 61 79 28 20 |_integer|_array( |
|00002e60| 64 65 66 2c 20 63 75 72 | 72 65 6e 74 5f 6d 61 78 |def, cur|rent_max|
|00002e70| 5f 64 66 61 73 20 29 3b | 0a 58 20 20 20 20 64 66 |_dfas );|.X df|
|00002e80| 61 73 69 7a 20 3d 20 72 | 65 61 6c 6c 6f 63 61 74 |asiz = r|eallocat|
|00002e90| 65 5f 69 6e 74 65 67 65 | 72 5f 61 72 72 61 79 28 |e_intege|r_array(|
|00002ea0| 20 64 66 61 73 69 7a 2c | 20 63 75 72 72 65 6e 74 | dfasiz,| current|
|00002eb0| 5f 6d 61 78 5f 64 66 61 | 73 20 29 3b 0a 58 20 20 |_max_dfa|s );.X |
|00002ec0| 20 20 61 63 63 73 69 7a | 20 3d 20 72 65 61 6c 6c | accsiz| = reall|
|00002ed0| 6f 63 61 74 65 5f 69 6e | 74 65 67 65 72 5f 61 72 |ocate_in|teger_ar|
|00002ee0| 72 61 79 28 20 61 63 63 | 73 69 7a 2c 20 63 75 72 |ray( acc|siz, cur|
|00002ef0| 72 65 6e 74 5f 6d 61 78 | 5f 64 66 61 73 20 29 3b |rent_max|_dfas );|
|00002f00| 0a 58 20 20 20 20 64 68 | 61 73 68 20 3d 20 72 65 |.X dh|ash = re|
|00002f10| 61 6c 6c 6f 63 61 74 65 | 5f 69 6e 74 65 67 65 72 |allocate|_integer|
|00002f20| 5f 61 72 72 61 79 28 20 | 64 68 61 73 68 2c 20 63 |_array( |dhash, c|
|00002f30| 75 72 72 65 6e 74 5f 6d | 61 78 5f 64 66 61 73 20 |urrent_m|ax_dfas |
|00002f40| 29 3b 0a 58 20 20 20 20 | 64 73 73 20 3d 20 72 65 |);.X |dss = re|
|00002f50| 61 6c 6c 6f 63 61 74 65 | 5f 69 6e 74 5f 70 74 72 |allocate|_int_ptr|
|00002f60| 5f 61 72 72 61 79 28 20 | 64 73 73 2c 20 63 75 72 |_array( |dss, cur|
|00002f70| 72 65 6e 74 5f 6d 61 78 | 5f 64 66 61 73 20 29 3b |rent_max|_dfas );|
|00002f80| 0a 58 20 20 20 20 64 66 | 61 61 63 63 20 3d 20 72 |.X df|aacc = r|
|00002f90| 65 61 6c 6c 6f 63 61 74 | 65 5f 64 66 61 61 63 63 |eallocat|e_dfaacc|
|00002fa0| 5f 75 6e 69 6f 6e 28 20 | 64 66 61 61 63 63 2c 20 |_union( |dfaacc, |
|00002fb0| 63 75 72 72 65 6e 74 5f | 6d 61 78 5f 64 66 61 73 |current_|max_dfas|
|00002fc0| 20 29 3b 0a 58 0a 58 20 | 20 20 20 69 66 20 28 20 | );.X.X | if ( |
|00002fd0| 6e 75 6c 74 72 61 6e 73 | 20 29 0a 58 09 6e 75 6c |nultrans| ).X.nul|
|00002fe0| 74 72 61 6e 73 20 3d 20 | 72 65 61 6c 6c 6f 63 61 |trans = |realloca|
|00002ff0| 74 65 5f 69 6e 74 65 67 | 65 72 5f 61 72 72 61 79 |te_integ|er_array|
|00003000| 28 20 6e 75 6c 74 72 61 | 6e 73 2c 20 63 75 72 72 |( nultra|ns, curr|
|00003010| 65 6e 74 5f 6d 61 78 5f | 64 66 61 73 20 29 3b 0a |ent_max_|dfas );.|
|00003020| 58 20 20 20 20 7d 0a 58 | 0a 58 0a 58 2f 2a 20 6e |X }.X|.X.X/* n|
|00003030| 74 6f 64 20 2d 20 63 6f | 6e 76 65 72 74 20 61 6e |tod - co|nvert an|
|00003040| 20 6e 64 66 61 20 74 6f | 20 61 20 64 66 61 0a 58 | ndfa to| a dfa.X|
|00003050| 20 2a 0a 58 20 2a 20 73 | 79 6e 6f 70 73 69 73 0a | *.X * s|ynopsis.|
|00003060| 58 20 2a 20 20 20 20 6e | 74 6f 64 28 29 3b 0a 58 |X * n|tod();.X|
|00003070| 20 2a 0a 58 20 2a 20 20 | 63 72 65 61 74 65 73 20 | *.X * |creates |
|00003080| 74 68 65 20 64 66 61 20 | 63 6f 72 72 65 73 70 6f |the dfa |correspo|
|00003090| 6e 64 69 6e 67 20 74 6f | 20 74 68 65 20 6e 64 66 |nding to| the ndf|
|000030a0| 61 20 77 65 27 76 65 20 | 63 6f 6e 73 74 72 75 63 |a we've |construc|
|000030b0| 74 65 64 2e 20 20 74 68 | 65 0a 58 20 2a 20 20 64 |ted. th|e.X * d|
|000030c0| 66 61 20 73 74 61 72 74 | 73 20 6f 75 74 20 69 6e |fa start|s out in|
|000030d0| 20 73 74 61 74 65 20 23 | 31 2e 0a 58 20 2a 2f 0a | state #|1..X */.|
|000030e0| 58 0a 58 76 6f 69 64 20 | 6e 74 6f 64 28 29 0a 58 |X.Xvoid |ntod().X|
|000030f0| 0a 58 20 20 20 20 7b 0a | 58 20 20 20 20 69 6e 74 |.X {.|X int|
|00003100| 20 2a 61 63 63 73 65 74 | 2c 20 64 73 2c 20 6e 61 | *accset|, ds, na|
|00003110| 63 63 2c 20 6e 65 77 64 | 73 3b 0a 58 20 20 20 20 |cc, newd|s;.X |
|00003120| 69 6e 74 20 73 79 6d 2c | 20 68 61 73 68 76 61 6c |int sym,| hashval|
|00003130| 2c 20 6e 75 6d 73 74 61 | 74 65 73 2c 20 64 73 69 |, numsta|tes, dsi|
|00003140| 7a 65 3b 0a 58 20 20 20 | 20 69 6e 74 20 6e 75 6d |ze;.X | int num|
|00003150| 5f 66 75 6c 6c 5f 74 61 | 62 6c 65 5f 72 6f 77 73 |_full_ta|ble_rows|
|00003160| 3b 09 2f 2a 20 75 73 65 | 64 20 6f 6e 6c 79 20 66 |;./* use|d only f|
|00003170| 6f 72 20 2d 66 20 2a 2f | 0a 58 20 20 20 20 69 6e |or -f */|.X in|
|00003180| 74 20 2a 6e 73 65 74 2c | 20 2a 64 73 65 74 3b 0a |t *nset,| *dset;.|
|00003190| 58 20 20 20 20 69 6e 74 | 20 74 61 72 67 70 74 72 |X int| targptr|
|000031a0| 2c 20 74 6f 74 61 6c 74 | 72 61 6e 73 2c 20 69 2c |, totalt|rans, i,|
|000031b0| 20 63 6f 6d 73 74 61 74 | 65 2c 20 63 6f 6d 66 72 | comstat|e, comfr|
|000031c0| 65 71 2c 20 74 61 72 67 | 3b 0a 58 20 20 20 20 69 |eq, targ|;.X i|
|000031d0| 6e 74 20 2a 65 70 73 63 | 6c 6f 73 75 72 65 28 29 |nt *epsc|losure()|
|000031e0| 2c 20 73 6e 73 74 6f 64 | 73 28 29 2c 20 73 79 6d |, snstod|s(), sym|
|000031f0| 6c 69 73 74 5b 43 53 49 | 5a 45 20 2b 20 31 5d 3b |list[CSI|ZE + 1];|
|00003200| 0a 58 20 20 20 20 69 6e | 74 20 6e 75 6d 5f 73 74 |.X in|t num_st|
|00003210| 61 72 74 5f 73 74 61 74 | 65 73 3b 0a 58 20 20 20 |art_stat|es;.X |
|00003220| 20 69 6e 74 20 74 6f 64 | 6f 5f 68 65 61 64 2c 20 | int tod|o_head, |
|00003230| 74 6f 64 6f 5f 6e 65 78 | 74 3b 0a 58 0a 58 20 20 |todo_nex|t;.X.X |
|00003240| 20 20 2f 2a 20 6e 6f 74 | 65 20 74 68 61 74 20 74 | /* not|e that t|
|00003250| 68 65 20 66 6f 6c 6c 6f | 77 69 6e 67 20 61 72 65 |he follo|wing are|
|00003260| 20 69 6e 64 65 78 65 64 | 20 62 79 20 2a 65 71 75 | indexed| by *equ|
|00003270| 69 76 61 6c 65 6e 63 65 | 20 63 6c 61 73 73 65 73 |ivalence| classes|
|00003280| 2a 0a 58 20 20 20 20 20 | 2a 20 61 6e 64 20 6e 6f |*.X |* and no|
|00003290| 74 20 62 79 20 63 68 61 | 72 61 63 74 65 72 73 2e |t by cha|racters.|
|000032a0| 20 20 53 69 6e 63 65 20 | 65 71 75 69 76 61 6c 65 | Since |equivale|
|000032b0| 6e 63 65 20 63 6c 61 73 | 73 65 73 20 61 72 65 20 |nce clas|ses are |
|000032c0| 69 6e 64 65 78 65 64 0a | 58 20 20 20 20 20 2a 20 |indexed.|X * |
|000032d0| 62 65 67 69 6e 6e 69 6e | 67 20 77 69 74 68 20 31 |beginnin|g with 1|
|000032e0| 2c 20 65 76 65 6e 20 69 | 66 20 74 68 65 20 73 63 |, even i|f the sc|
|000032f0| 61 6e 6e 65 72 20 61 63 | 63 65 70 74 73 20 4e 55 |anner ac|cepts NU|
|00003300| 4c 27 73 2c 20 74 68 69 | 73 0a 58 20 20 20 20 20 |L's, thi|s.X |
|00003310| 2a 20 6d 65 61 6e 73 20 | 74 68 61 74 20 28 73 69 |* means |that (si|
|00003320| 6e 63 65 20 65 76 65 72 | 79 20 63 68 61 72 61 63 |nce ever|y charac|
|00003330| 74 65 72 20 69 73 20 70 | 6f 74 65 6e 74 69 61 6c |ter is p|otential|
|00003340| 6c 79 20 69 6e 20 69 74 | 73 20 6f 77 6e 0a 58 20 |ly in it|s own.X |
|00003350| 20 20 20 20 2a 20 65 71 | 75 69 76 61 6c 65 6e 63 | * eq|uivalenc|
|00003360| 65 20 63 6c 61 73 73 29 | 20 74 68 65 73 65 20 61 |e class)| these a|
|00003370| 72 72 61 79 73 20 6d 75 | 73 74 20 68 61 76 65 20 |rrays mu|st have |
|00003380| 72 6f 6f 6d 20 66 6f 72 | 20 69 6e 64 69 63 65 73 |room for| indices|
|00003390| 0a 58 20 20 20 20 20 2a | 20 66 72 6f 6d 20 31 20 |.X *| from 1 |
|000033a0| 74 6f 20 43 53 49 5a 45 | 2c 20 73 6f 20 74 68 65 |to CSIZE|, so the|
|000033b0| 69 72 20 73 69 7a 65 20 | 6d 75 73 74 20 62 65 20 |ir size |must be |
|000033c0| 43 53 49 5a 45 20 2b 20 | 31 2e 0a 58 20 20 20 20 |CSIZE + |1..X |
|000033d0| 20 2a 2f 0a 58 20 20 20 | 20 69 6e 74 20 64 75 70 | */.X | int dup|
|000033e0| 6c 69 73 74 5b 43 53 49 | 5a 45 20 2b 20 31 5d 2c |list[CSI|ZE + 1],|
|000033f0| 20 73 74 61 74 65 5b 43 | 53 49 5a 45 20 2b 20 31 | state[C|SIZE + 1|
|00003400| 5d 3b 0a 58 20 20 20 20 | 69 6e 74 20 74 61 72 67 |];.X |int targ|
|00003410| 66 72 65 71 5b 43 53 49 | 5a 45 20 2b 20 31 5d 2c |freq[CSI|ZE + 1],|
|00003420| 20 74 61 72 67 73 74 61 | 74 65 5b 43 53 49 5a 45 | targsta|te[CSIZE|
|00003430| 20 2b 20 31 5d 3b 0a 58 | 0a 58 20 20 20 20 2f 2a | + 1];.X|.X /*|
|00003440| 20 74 68 69 73 20 69 73 | 20 73 6f 20 66 69 6e 64 | this is| so find|
|00003450| 5f 74 61 62 6c 65 5f 73 | 70 61 63 65 28 2e 2e 2e |_table_s|pace(...|
|00003460| 29 20 77 69 6c 6c 20 6b | 6e 6f 77 20 77 68 65 72 |) will k|now wher|
|00003470| 65 20 74 6f 20 73 74 61 | 72 74 20 6c 6f 6f 6b 69 |e to sta|rt looki|
|00003480| 6e 67 20 69 6e 0a 58 20 | 20 20 20 20 2a 20 63 68 |ng in.X | * ch|
|00003490| 6b 2f 6e 78 74 20 66 6f | 72 20 75 6e 75 73 65 64 |k/nxt fo|r unused|
|000034a0| 20 72 65 63 6f 72 64 73 | 20 66 6f 72 20 73 70 61 | records| for spa|
|000034b0| 63 65 20 74 6f 20 70 75 | 74 20 69 6e 20 74 68 65 |ce to pu|t in the|
|000034c0| 20 73 74 61 74 65 0a 58 | 20 20 20 20 20 2a 2f 0a | state.X| */.|
|000034d0| 58 20 20 20 20 69 66 20 | 28 20 66 75 6c 6c 73 70 |X if |( fullsp|
|000034e0| 64 20 29 0a 58 09 66 69 | 72 73 74 66 72 65 65 20 |d ).X.fi|rstfree |
|000034f0| 3d 20 30 3b 0a 58 0a 58 | 20 20 20 20 61 63 63 73 |= 0;.X.X| accs|
|00003500| 65 74 20 3d 20 61 6c 6c | 6f 63 61 74 65 5f 69 6e |et = all|ocate_in|
|00003510| 74 65 67 65 72 5f 61 72 | 72 61 79 28 20 6e 75 6d |teger_ar|ray( num|
|00003520| 5f 72 75 6c 65 73 20 2b | 20 31 20 29 3b 0a 58 20 |_rules +| 1 );.X |
|00003530| 20 20 20 6e 73 65 74 20 | 3d 20 61 6c 6c 6f 63 61 | nset |= alloca|
|00003540| 74 65 5f 69 6e 74 65 67 | 65 72 5f 61 72 72 61 79 |te_integ|er_array|
|00003550| 28 20 63 75 72 72 65 6e | 74 5f 6d 61 78 5f 64 66 |( curren|t_max_df|
|00003560| 61 5f 73 69 7a 65 20 29 | 3b 0a 58 0a 58 20 20 20 |a_size )|;.X.X |
|00003570| 20 2f 2a 20 74 68 65 20 | 22 74 6f 64 6f 22 20 71 | /* the |"todo" q|
|00003580| 75 65 75 65 20 69 73 20 | 72 65 70 72 65 73 65 6e |ueue is |represen|
|00003590| 74 65 64 20 62 79 20 74 | 68 65 20 68 65 61 64 2c |ted by t|he head,|
|000035a0| 20 77 68 69 63 68 20 69 | 73 20 74 68 65 20 44 46 | which i|s the DF|
|000035b0| 41 0a 58 20 20 20 20 20 | 2a 20 73 74 61 74 65 20 |A.X |* state |
|000035c0| 63 75 72 72 65 6e 74 6c | 79 20 62 65 69 6e 67 20 |currentl|y being |
|000035d0| 70 72 6f 63 65 73 73 65 | 64 2c 20 61 6e 64 20 74 |processe|d, and t|
|000035e0| 68 65 20 22 6e 65 78 74 | 22 2c 20 77 68 69 63 68 |he "next|", which|
|000035f0| 20 69 73 20 74 68 65 0a | 58 20 20 20 20 20 2a 20 | is the.|X * |
|00003600| 6e 65 78 74 20 44 46 41 | 20 73 74 61 74 65 20 6e |next DFA| state n|
|00003610| 75 6d 62 65 72 20 61 76 | 61 69 6c 61 62 6c 65 20 |umber av|ailable |
|00003620| 28 6e 6f 74 20 69 6e 20 | 75 73 65 29 2e 20 20 57 |(not in |use). W|
|00003630| 65 20 64 65 70 65 6e 64 | 20 6f 6e 20 74 68 65 0a |e depend| on the.|
|00003640| 58 20 20 20 20 20 2a 20 | 66 61 63 74 20 74 68 61 |X * |fact tha|
|00003650| 74 20 73 6e 73 74 6f 64 | 73 28 29 20 72 65 74 75 |t snstod|s() retu|
|00003660| 72 6e 73 20 44 46 41 27 | 73 20 5c 69 6e 20 69 6e |rns DFA'|s \in in|
|00003670| 63 72 65 61 73 69 6e 67 | 20 6f 72 64 65 72 2f 2c |creasing| order/,|
|00003680| 20 61 6e 64 20 74 68 75 | 73 0a 58 20 20 20 20 20 | and thu|s.X |
|00003690| 2a 20 6e 65 65 64 20 6f | 6e 6c 79 20 6b 6e 6f 77 |* need o|nly know|
|000036a0| 20 74 68 65 20 62 6f 75 | 6e 64 73 20 6f 66 20 74 | the bou|nds of t|
|000036b0| 68 65 20 64 66 61 73 20 | 74 6f 20 62 65 20 70 72 |he dfas |to be pr|
|000036c0| 6f 63 65 73 73 65 64 2e | 0a 58 20 20 20 20 20 2a |ocessed.|.X *|
|000036d0| 2f 0a 58 20 20 20 20 74 | 6f 64 6f 5f 68 65 61 64 |/.X t|odo_head|
|000036e0| 20 3d 20 74 6f 64 6f 5f | 6e 65 78 74 20 3d 20 30 | = todo_|next = 0|
|000036f0| 3b 0a 58 0a 58 20 20 20 | 20 66 6f 72 20 28 20 69 |;.X.X | for ( i|
|00003700| 20 3d 20 30 3b 20 69 20 | 3c 3d 20 63 73 69 7a 65 | = 0; i |<= csize|
|00003710| 3b 20 2b 2b 69 20 29 0a | 58 09 7b 0a 58 09 64 75 |; ++i ).|X.{.X.du|
|00003720| 70 6c 69 73 74 5b 69 5d | 20 3d 20 4e 49 4c 3b 0a |plist[i]| = NIL;.|
|00003730| 58 09 73 79 6d 6c 69 73 | 74 5b 69 5d 20 3d 20 66 |X.symlis|t[i] = f|
|00003740| 61 6c 73 65 3b 0a 58 09 | 7d 0a 58 0a 58 20 20 20 |alse;.X.|}.X.X |
|00003750| 20 66 6f 72 20 28 20 69 | 20 3d 20 30 3b 20 69 20 | for ( i| = 0; i |
|00003760| 3c 3d 20 6e 75 6d 5f 72 | 75 6c 65 73 3b 20 2b 2b |<= num_r|ules; ++|
|00003770| 69 20 29 0a 58 09 61 63 | 63 73 65 74 5b 69 5d 20 |i ).X.ac|cset[i] |
|00003780| 3d 20 4e 49 4c 3b 0a 58 | 0a 58 20 20 20 20 69 66 |= NIL;.X|.X if|
|00003790| 20 28 20 74 72 61 63 65 | 20 29 0a 58 09 7b 0a 58 | ( trace| ).X.{.X|
|000037a0| 09 64 75 6d 70 6e 66 61 | 28 20 73 63 73 65 74 5b |.dumpnfa|( scset[|
|000037b0| 31 5d 20 29 3b 0a 58 09 | 66 70 75 74 73 28 20 22 |1] );.X.|fputs( "|
|000037c0| 5c 6e 5c 6e 44 46 41 20 | 44 75 6d 70 3a 5c 6e 5c |\n\nDFA |Dump:\n\|
|000037d0| 6e 22 2c 20 73 74 64 65 | 72 72 20 29 3b 0a 58 09 |n", stde|rr );.X.|
|000037e0| 7d 0a 58 0a 58 20 20 20 | 20 69 6e 69 74 74 62 6c |}.X.X | inittbl|
|000037f0| 28 29 3b 0a 58 0a 58 20 | 20 20 20 2f 2a 20 63 68 |();.X.X | /* ch|
|00003800| 65 63 6b 20 74 6f 20 73 | 65 65 20 77 68 65 74 68 |eck to s|ee wheth|
|00003810| 65 72 20 77 65 20 73 68 | 6f 75 6c 64 20 62 75 69 |er we sh|ould bui|
|00003820| 6c 64 20 61 20 73 65 70 | 61 72 61 74 65 20 74 61 |ld a sep|arate ta|
|00003830| 62 6c 65 20 66 6f 72 20 | 74 72 61 6e 73 69 74 69 |ble for |transiti|
|00003840| 6f 6e 73 0a 58 20 20 20 | 20 20 2a 20 6f 6e 20 4e |ons.X | * on N|
|00003850| 55 4c 20 63 68 61 72 61 | 63 74 65 72 73 2e 20 20 |UL chara|cters. |
|00003860| 57 65 20 64 6f 6e 27 74 | 20 64 6f 20 74 68 69 73 |We don't| do this|
|00003870| 20 66 6f 72 20 66 75 6c | 6c 2d 73 70 65 65 64 20 | for ful|l-speed |
|00003880| 28 2d 46 29 20 73 63 61 | 6e 6e 65 72 73 2c 0a 58 |(-F) sca|nners,.X|
|00003890| 20 20 20 20 20 2a 20 73 | 69 6e 63 65 20 66 6f 72 | * s|ince for|
|000038a0| 20 74 68 65 6d 20 77 65 | 20 64 6f 6e 27 74 20 68 | them we| don't h|
|000038b0| 61 76 65 20 61 20 73 69 | 6d 70 6c 65 20 73 74 61 |ave a si|mple sta|
|000038c0| 74 65 20 6e 75 6d 62 65 | 72 20 6c 79 69 6e 67 20 |te numbe|r lying |
|000038d0| 61 72 6f 75 6e 64 20 77 | 69 74 68 0a 58 20 20 20 |around w|ith.X |
|000038e0| 20 20 2a 20 77 68 69 63 | 68 20 74 6f 20 69 6e 64 | * whic|h to ind|
|000038f0| 65 78 20 74 68 65 20 74 | 61 62 6c 65 2e 20 20 57 |ex the t|able. W|
|00003900| 65 20 61 6c 73 6f 20 64 | 6f 6e 27 74 20 62 6f 74 |e also d|on't bot|
|00003910| 68 65 72 20 64 6f 69 6e | 67 20 69 74 20 66 6f 72 |her doin|g it for|
|00003920| 20 73 63 61 6e 6e 65 72 | 73 0a 58 20 20 20 20 20 | scanner|s.X |
|00003930| 2a 20 75 6e 6c 65 73 73 | 20 28 31 29 20 4e 55 4c |* unless| (1) NUL|
|00003940| 20 69 73 20 69 6e 20 69 | 74 73 20 6f 77 6e 20 65 | is in i|ts own e|
|00003950| 71 75 69 76 61 6c 65 6e | 63 65 20 63 6c 61 73 73 |quivalen|ce class|
|00003960| 20 28 69 6e 64 69 63 61 | 74 65 64 20 62 79 20 61 | (indica|ted by a|
|00003970| 0a 58 20 20 20 20 20 2a | 20 70 6f 73 69 74 69 76 |.X *| positiv|
|00003980| 65 20 76 61 6c 75 65 20 | 6f 66 20 65 63 67 72 6f |e value |of ecgro|
|00003990| 75 70 5b 4e 55 4c 5d 29 | 2c 20 28 32 29 20 4e 55 |up[NUL])|, (2) NU|
|000039a0| 4c 27 73 20 65 71 75 69 | 6c 76 61 6c 65 6e 63 65 |L's equi|lvalence|
|000039b0| 20 63 6c 61 73 73 20 69 | 73 0a 58 20 20 20 20 20 | class i|s.X |
|000039c0| 2a 20 74 68 65 20 6c 61 | 73 74 20 65 71 75 69 76 |* the la|st equiv|
|000039d0| 61 6c 65 6e 63 65 20 63 | 6c 61 73 73 2c 20 61 6e |alence c|lass, an|
|000039e0| 64 20 28 33 29 20 74 68 | 65 20 6e 75 6d 62 65 72 |d (3) th|e number|
|000039f0| 20 6f 66 20 65 71 75 69 | 76 61 6c 65 6e 63 65 20 | of equi|valence |
|00003a00| 63 6c 61 73 73 65 73 0a | 58 20 20 20 20 20 2a 20 |classes.|X * |
|00003a10| 69 73 20 74 68 65 20 73 | 61 6d 65 20 61 73 20 74 |is the s|ame as t|
|00003a20| 68 65 20 6e 75 6d 62 65 | 72 20 6f 66 20 63 68 61 |he numbe|r of cha|
|00003a30| 72 61 63 74 65 72 73 2e | 20 20 54 68 69 73 20 6c |racters.| This l|
|00003a40| 61 74 74 65 72 20 63 61 | 73 65 20 63 6f 6d 65 73 |atter ca|se comes|
|00003a50| 20 61 62 6f 75 74 0a 58 | 20 20 20 20 20 2a 20 77 | about.X| * w|
|00003a60| 68 65 6e 20 75 73 65 65 | 63 73 20 69 73 20 66 61 |hen usee|cs is fa|
|00003a70| 6c 73 65 20 6f 72 20 77 | 68 65 6e 20 69 74 73 20 |lse or w|hen its |
|00003a80| 74 72 75 65 20 62 75 74 | 20 65 76 65 72 79 20 63 |true but| every c|
|00003a90| 68 61 72 61 63 74 65 72 | 20 73 74 69 6c 6c 0a 58 |haracter| still.X|
|00003aa0| 20 20 20 20 20 2a 20 6d | 61 6e 61 67 65 73 20 74 | * m|anages t|
|00003ab0| 6f 20 6c 61 6e 64 20 69 | 6e 20 69 74 73 20 6f 77 |o land i|n its ow|
|00003ac0| 6e 20 63 6c 61 73 73 20 | 28 75 6e 6c 69 6b 65 6c |n class |(unlikel|
|00003ad0| 79 2c 20 62 75 74 20 69 | 74 27 73 20 63 68 65 61 |y, but i|t's chea|
|00003ae0| 70 20 74 6f 20 63 68 65 | 63 6b 0a 58 20 20 20 20 |p to che|ck.X |
|00003af0| 20 2a 20 66 6f 72 29 2e | 20 20 49 66 20 61 6c 6c | * for).| If all|
|00003b00| 20 74 68 65 73 65 20 74 | 68 69 6e 67 73 20 61 72 | these t|hings ar|
|00003b10| 65 20 74 72 75 65 20 74 | 68 65 6e 20 74 68 65 20 |e true t|hen the |
|00003b20| 63 68 61 72 61 63 74 65 | 72 20 63 6f 64 65 20 6e |characte|r code n|
|00003b30| 65 65 64 65 64 0a 58 20 | 20 20 20 20 2a 20 74 6f |eeded.X | * to|
|00003b40| 20 72 65 70 72 65 73 65 | 6e 74 20 4e 55 4c 27 73 | represe|nt NUL's|
|00003b50| 20 65 71 75 69 76 61 6c | 65 6e 63 65 20 63 6c 61 | equival|ence cla|
|00003b60| 73 73 20 66 6f 72 20 69 | 6e 64 65 78 69 6e 67 20 |ss for i|ndexing |
|00003b70| 74 68 65 20 74 61 62 6c | 65 73 20 69 73 0a 58 20 |the tabl|es is.X |
|00003b80| 20 20 20 20 2a 20 67 6f | 69 6e 67 20 74 6f 20 74 | * go|ing to t|
|00003b90| 61 6b 65 20 6f 6e 65 20 | 6d 6f 72 65 20 62 69 74 |ake one |more bit|
|00003ba0| 20 74 68 61 6e 20 74 68 | 65 20 6e 75 6d 62 65 72 | than th|e number|
|00003bb0| 20 6f 66 20 63 68 61 72 | 61 63 74 65 72 73 2c 20 | of char|acters, |
|00003bc0| 61 6e 64 20 74 68 65 72 | 65 66 6f 72 65 0a 58 20 |and ther|efore.X |
|00003bd0| 20 20 20 20 2a 20 77 65 | 20 77 6f 6e 27 74 20 62 | * we| won't b|
|00003be0| 65 20 61 73 73 75 72 65 | 64 20 6f 66 20 62 65 69 |e assure|d of bei|
|00003bf0| 6e 67 20 61 62 6c 65 20 | 74 6f 20 66 69 74 20 69 |ng able |to fit i|
|00003c00| 74 20 69 6e 74 6f 20 61 | 20 59 59 5f 43 48 41 52 |t into a| YY_CHAR|
|00003c10| 20 76 61 72 69 61 62 6c | 65 2e 0a 58 20 20 20 20 | variabl|e..X |
|00003c20| 20 2a 20 54 68 69 73 20 | 72 75 6c 65 73 20 6f 75 | * This |rules ou|
|00003c30| 74 20 73 74 6f 72 69 6e | 67 20 74 68 65 20 74 72 |t storin|g the tr|
|00003c40| 61 6e 73 69 74 69 6f 6e | 73 20 69 6e 20 61 20 63 |ansition|s in a c|
|00003c50| 6f 6d 70 72 65 73 73 65 | 64 20 74 61 62 6c 65 2c |ompresse|d table,|
|00003c60| 20 73 69 6e 63 65 0a 58 | 20 20 20 20 20 2a 20 74 | since.X| * t|
|00003c70| 68 65 20 63 6f 64 65 20 | 66 6f 72 20 69 6e 74 65 |he code |for inte|
|00003c80| 72 70 72 65 74 69 6e 67 | 20 74 68 65 6d 20 75 73 |rpreting| them us|
|00003c90| 65 73 20 61 20 59 59 5f | 43 48 41 52 20 76 61 72 |es a YY_|CHAR var|
|00003ca0| 69 61 62 6c 65 20 28 70 | 65 72 68 61 70 73 20 69 |iable (p|erhaps i|
|00003cb0| 74 0a 58 20 20 20 20 20 | 2a 20 73 68 6f 75 6c 64 |t.X |* should|
|00003cc0| 20 6a 75 73 74 20 75 73 | 65 20 61 6e 20 69 6e 74 | just us|e an int|
|00003cd0| 65 67 65 72 2c 20 74 68 | 6f 75 67 68 3b 20 74 68 |eger, th|ough; th|
|00003ce0| 69 73 20 69 73 20 77 6f | 72 74 68 20 70 6f 6e 64 |is is wo|rth pond|
|00003cf0| 65 72 69 6e 67 20 2e 2e | 2e 20 23 23 23 29 2e 0a |ering ..|. ###)..|
|00003d00| 58 20 20 20 20 20 2a 0a | 58 20 20 20 20 20 2a 20 |X *.|X * |
|00003d10| 46 69 6e 61 6c 6c 79 2c | 20 66 6f 72 20 66 75 6c |Finally,| for ful|
|00003d20| 6c 20 74 61 62 6c 65 73 | 2c 20 77 65 20 77 61 6e |l tables|, we wan|
|00003d30| 74 20 74 68 65 20 6e 75 | 6d 62 65 72 20 6f 66 20 |t the nu|mber of |
|00003d40| 65 6e 74 72 69 65 73 20 | 69 6e 20 74 68 65 0a 58 |entries |in the.X|
|00003d50| 20 20 20 20 20 2a 20 74 | 61 62 6c 65 20 74 6f 20 | * t|able to |
|00003d60| 62 65 20 61 20 70 6f 77 | 65 72 20 6f 66 20 74 77 |be a pow|er of tw|
|00003d70| 6f 20 73 6f 20 74 68 65 | 20 61 72 72 61 79 20 72 |o so the| array r|
|00003d80| 65 66 65 72 65 6e 63 65 | 73 20 67 6f 20 66 61 73 |eference|s go fas|
|00003d90| 74 20 28 69 74 0a 58 20 | 20 20 20 20 2a 20 77 69 |t (it.X | * wi|
|00003da0| 6c 6c 20 6a 75 73 74 20 | 74 61 6b 65 20 61 20 73 |ll just |take a s|
|00003db0| 68 69 66 74 20 74 6f 20 | 63 6f 6d 70 75 74 65 20 |hift to |compute |
|00003dc0| 74 68 65 20 6d 61 6a 6f | 72 20 69 6e 64 65 78 29 |the majo|r index)|
|00003dd0| 2e 20 20 49 66 20 65 6e | 63 6f 64 69 6e 67 0a 58 |. If en|coding.X|
|00003de0| 20 20 20 20 20 2a 20 4e | 55 4c 27 73 20 74 72 61 | * N|UL's tra|
|00003df0| 6e 73 69 74 69 6f 6e 73 | 20 69 6e 20 74 68 65 20 |nsitions| in the |
|00003e00| 74 61 62 6c 65 20 77 69 | 6c 6c 20 73 70 6f 69 6c |table wi|ll spoil|
|00003e10| 20 74 68 69 73 2c 20 77 | 65 20 67 69 76 65 20 69 | this, w|e give i|
|00003e20| 74 20 69 74 73 0a 58 20 | 20 20 20 20 2a 20 6f 77 |t its.X | * ow|
|00003e30| 6e 20 74 61 62 6c 65 20 | 28 6e 6f 74 65 20 74 68 |n table |(note th|
|00003e40| 61 74 20 74 68 69 73 20 | 77 69 6c 6c 20 62 65 20 |at this |will be |
|00003e50| 74 68 65 20 63 61 73 65 | 20 69 66 20 77 65 27 72 |the case| if we'r|
|00003e60| 65 20 6e 6f 74 20 75 73 | 69 6e 67 0a 58 20 20 20 |e not us|ing.X |
|00003e70| 20 20 2a 20 65 71 75 69 | 76 61 6c 65 6e 63 65 20 | * equi|valence |
|00003e80| 63 6c 61 73 73 65 73 29 | 2e 0a 58 20 20 20 20 20 |classes)|..X |
|00003e90| 2a 2f 0a 58 0a 58 20 20 | 20 20 2f 2a 20 6e 6f 74 |*/.X.X | /* not|
|00003ea0| 65 20 74 68 61 74 20 74 | 68 65 20 74 65 73 74 20 |e that t|he test |
|00003eb0| 66 6f 72 20 65 63 67 72 | 6f 75 70 5b 30 5d 20 3d |for ecgr|oup[0] =|
|00003ec0| 3d 20 6e 75 6d 65 63 73 | 20 62 65 6c 6f 77 20 61 |= numecs| below a|
|00003ed0| 63 63 6f 6d 70 6c 69 73 | 68 65 73 0a 58 20 20 20 |ccomplis|hes.X |
|00003ee0| 20 20 2a 20 62 6f 74 68 | 20 28 31 29 20 61 6e 64 | * both| (1) and|
|00003ef0| 20 28 32 29 20 61 62 6f | 76 65 0a 58 20 20 20 20 | (2) abo|ve.X |
|00003f00| 20 2a 2f 0a 58 20 20 20 | 20 69 66 20 28 20 21 20 | */.X | if ( ! |
|00003f10| 66 75 6c 6c 73 70 64 20 | 26 26 20 65 63 67 72 6f |fullspd |&& ecgro|
|00003f20| 75 70 5b 30 5d 20 3d 3d | 20 6e 75 6d 65 63 73 20 |up[0] ==| numecs |
|00003f30| 29 0a 58 09 7b 20 2f 2a | 20 4e 55 4c 20 69 73 20 |).X.{ /*| NUL is |
|00003f40| 61 6c 6f 6e 65 20 69 6e | 20 69 74 73 20 65 71 75 |alone in| its equ|
|00003f50| 69 76 61 6c 65 6e 63 65 | 20 63 6c 61 73 73 2c 20 |ivalence| class, |
|00003f60| 77 68 69 63 68 20 69 73 | 20 74 68 65 20 6c 61 73 |which is| the las|
|00003f70| 74 20 6f 6e 65 20 2a 2f | 0a 58 09 69 6e 74 20 75 |t one */|.X.int u|
|00003f80| 73 65 5f 4e 55 4c 5f 74 | 61 62 6c 65 20 3d 20 28 |se_NUL_t|able = (|
|00003f90| 6e 75 6d 65 63 73 20 3d | 3d 20 63 73 69 7a 65 29 |numecs =|= csize)|
|00003fa0| 3b 0a 58 0a 58 09 69 66 | 20 28 20 66 75 6c 6c 74 |;.X.X.if| ( fullt|
|00003fb0| 62 6c 20 26 26 20 21 20 | 75 73 65 5f 4e 55 4c 5f |bl && ! |use_NUL_|
|00003fc0| 74 61 62 6c 65 20 29 0a | 58 09 20 20 20 20 7b 20 |table ).|X. { |
|00003fd0| 2f 2a 20 77 65 20 73 74 | 69 6c 6c 20 6d 61 79 20 |/* we st|ill may |
|00003fe0| 77 61 6e 74 20 74 6f 20 | 75 73 65 20 74 68 65 20 |want to |use the |
|00003ff0| 74 61 62 6c 65 20 69 66 | 20 6e 75 6d 65 63 73 20 |table if| numecs |
|00004000| 69 73 20 61 20 70 6f 77 | 65 72 20 6f 66 20 32 20 |is a pow|er of 2 |
|00004010| 2a 2f 0a 58 09 20 20 20 | 20 69 6e 74 20 70 6f 77 |*/.X. | int pow|
|00004020| 65 72 5f 6f 66 5f 74 77 | 6f 3b 0a 58 0a 58 09 20 |er_of_tw|o;.X.X. |
|00004030| 20 20 20 66 6f 72 20 28 | 20 70 6f 77 65 72 5f 6f | for (| power_o|
|00004040| 66 5f 74 77 6f 20 3d 20 | 31 3b 20 70 6f 77 65 72 |f_two = |1; power|
|00004050| 5f 6f 66 5f 74 77 6f 20 | 3c 3d 20 63 73 69 7a 65 |_of_two |<= csize|
|00004060| 3b 20 70 6f 77 65 72 5f | 6f 66 5f 74 77 6f 20 2a |; power_|of_two *|
|00004070| 3d 20 32 20 29 0a 58 09 | 09 69 66 20 28 20 6e 75 |= 2 ).X.|.if ( nu|
|00004080| 6d 65 63 73 20 3d 3d 20 | 70 6f 77 65 72 5f 6f 66 |mecs == |power_of|
|00004090| 5f 74 77 6f 20 29 0a 58 | 09 09 20 20 20 20 7b 0a |_two ).X|.. {.|
|000040a0| 58 09 09 20 20 20 20 75 | 73 65 5f 4e 55 4c 5f 74 |X.. u|se_NUL_t|
|000040b0| 61 62 6c 65 20 3d 20 74 | 72 75 65 3b 0a 58 09 09 |able = t|rue;.X..|
|000040c0| 20 20 20 20 62 72 65 61 | 6b 3b 0a 58 09 09 20 20 | brea|k;.X.. |
|000040d0| 20 20 7d 0a 58 09 20 20 | 20 20 7d 0a 58 0a 58 09 | }.X. | }.X.X.|
|000040e0| 69 66 20 28 20 75 73 65 | 5f 4e 55 4c 5f 74 61 62 |if ( use|_NUL_tab|
|000040f0| 6c 65 20 29 0a 58 09 20 | 20 20 20 6e 75 6c 74 72 |le ).X. | nultr|
|00004100| 61 6e 73 20 3d 20 61 6c | 6c 6f 63 61 74 65 5f 69 |ans = al|locate_i|
|00004110| 6e 74 65 67 65 72 5f 61 | 72 72 61 79 28 20 63 75 |nteger_a|rray( cu|
|00004120| 72 72 65 6e 74 5f 6d 61 | 78 5f 64 66 61 73 20 29 |rrent_ma|x_dfas )|
|00004130| 3b 0a 58 09 20 20 20 20 | 2f 2a 20 66 72 6f 6d 20 |;.X. |/* from |
|00004140| 6e 6f 77 20 6f 6e 2c 20 | 6e 75 6c 74 72 61 6e 73 |now on, |nultrans|
|00004150| 20 21 3d 20 6e 69 6c 20 | 69 6e 64 69 63 61 74 65 | != nil |indicate|
|00004160| 73 20 74 68 61 74 20 77 | 65 27 72 65 0a 58 09 20 |s that w|e're.X. |
|00004170| 20 20 20 20 2a 20 73 61 | 76 69 6e 67 20 6e 75 6c | * sa|ving nul|
|00004180| 6c 20 74 72 61 6e 73 69 | 74 69 6f 6e 73 20 66 6f |l transi|tions fo|
|00004190| 72 20 6c 61 74 65 72 2c | 20 73 65 70 61 72 61 74 |r later,| separat|
|000041a0| 65 20 65 6e 63 6f 64 69 | 6e 67 0a 58 09 20 20 20 |e encodi|ng.X. |
|000041b0| 20 20 2a 2f 0a 58 09 7d | 0a 58 0a 58 0a 58 20 20 | */.X.}|.X.X.X |
|000041c0| 20 20 69 66 20 28 20 66 | 75 6c 6c 73 70 64 20 29 | if ( f|ullspd )|
|000041d0| 0a 58 09 7b 0a 58 09 66 | 6f 72 20 28 20 69 20 3d |.X.{.X.f|or ( i =|
|000041e0| 20 30 3b 20 69 20 3c 3d | 20 6e 75 6d 65 63 73 3b | 0; i <=| numecs;|
|000041f0| 20 2b 2b 69 20 29 0a 58 | 09 20 20 20 20 73 74 61 | ++i ).X|. sta|
|00004200| 74 65 5b 69 5d 20 3d 20 | 30 3b 0a 58 09 70 6c 61 |te[i] = |0;.X.pla|
|00004210| 63 65 5f 73 74 61 74 65 | 28 20 73 74 61 74 65 2c |ce_state|( state,|
|00004220| 20 30 2c 20 30 20 29 3b | 0a 58 09 7d 0a 58 0a 58 | 0, 0 );|.X.}.X.X|
|00004230| 20 20 20 20 65 6c 73 65 | 20 69 66 20 28 20 66 75 | else| if ( fu|
|00004240| 6c 6c 74 62 6c 20 29 0a | 58 09 7b 0a 58 09 69 66 |lltbl ).|X.{.X.if|
|00004250| 20 28 20 6e 75 6c 74 72 | 61 6e 73 20 29 0a 58 09 | ( nultr|ans ).X.|
|00004260| 20 20 20 20 2f 2a 20 77 | 65 20 77 6f 6e 27 74 20 | /* w|e won't |
|00004270| 62 65 20 69 6e 63 6c 75 | 64 69 6e 67 20 4e 55 4c |be inclu|ding NUL|
|00004280| 27 73 20 74 72 61 6e 73 | 69 74 69 6f 6e 73 20 69 |'s trans|itions i|
|00004290| 6e 20 74 68 65 20 74 61 | 62 6c 65 2c 0a 58 09 20 |n the ta|ble,.X. |
|000042a0| 20 20 20 20 2a 20 73 6f | 20 62 75 69 6c 64 20 69 | * so| build i|
|000042b0| 74 20 66 6f 72 20 65 6e | 74 72 69 65 73 20 66 72 |t for en|tries fr|
|000042c0| 6f 6d 20 30 20 2e 2e 20 | 6e 75 6d 65 63 73 20 2d |om 0 .. |numecs -|
|000042d0| 20 31 0a 58 09 20 20 20 | 20 20 2a 2f 0a 58 09 20 | 1.X. | */.X. |
|000042e0| 20 20 20 6e 75 6d 5f 66 | 75 6c 6c 5f 74 61 62 6c | num_f|ull_tabl|
|000042f0| 65 5f 72 6f 77 73 20 3d | 20 6e 75 6d 65 63 73 3b |e_rows =| numecs;|
|00004300| 0a 58 0a 58 09 65 6c 73 | 65 0a 58 09 20 20 20 20 |.X.X.els|e.X. |
|00004310| 2f 2a 20 74 61 6b 65 20 | 69 6e 74 6f 20 61 63 63 |/* take |into acc|
|00004320| 6f 75 6e 74 20 74 68 65 | 20 66 61 63 74 20 74 68 |ount the| fact th|
|00004330| 61 74 20 77 65 27 6c 6c | 20 62 65 20 69 6e 63 6c |at we'll| be incl|
|00004340| 75 64 69 6e 67 0a 58 09 | 20 20 20 20 20 2a 20 74 |uding.X.| * t|
|00004350| 68 65 20 4e 55 4c 20 65 | 6e 74 72 69 65 73 20 69 |he NUL e|ntries i|
|00004360| 6e 20 74 68 65 20 74 72 | 61 6e 73 69 74 69 6f 6e |n the tr|ansition|
|00004370| 20 74 61 62 6c 65 2e 20 | 20 42 75 69 6c 64 20 69 | table. | Build i|
|00004380| 74 0a 58 09 20 20 20 20 | 20 2a 20 66 72 6f 6d 20 |t.X. | * from |
|00004390| 30 20 2e 2e 20 6e 75 6d | 65 63 73 2e 0a 58 09 20 |0 .. num|ecs..X. |
|000043a0| 20 20 20 20 2a 2f 0a 58 | 09 20 20 20 20 6e 75 6d | */.X|. num|
|000043b0| 5f 66 75 6c 6c 5f 74 61 | 62 6c 65 5f 72 6f 77 73 |_full_ta|ble_rows|
|000043c0| 20 3d 20 6e 75 6d 65 63 | 73 20 2b 20 31 3b 0a 58 | = numec|s + 1;.X|
|000043d0| 0a 58 09 2f 2a 20 64 65 | 63 6c 61 72 65 20 69 74 |.X./* de|clare it|
|000043e0| 20 22 73 68 6f 72 74 22 | 20 62 65 63 61 75 73 65 | "short"| because|
|000043f0| 20 69 74 27 73 20 61 20 | 72 65 61 6c 20 6c 6f 6e | it's a |real lon|
|00004400| 67 2d 73 68 6f 74 20 74 | 68 61 74 20 74 68 61 74 |g-shot t|hat that|
|00004410| 0a 58 09 20 2a 20 77 6f | 6e 27 74 20 62 65 20 6c |.X. * wo|n't be l|
|00004420| 61 72 67 65 20 65 6e 6f | 75 67 68 2e 0a 58 09 20 |arge eno|ugh..X. |
|00004430| 2a 2f 0a 58 09 70 72 69 | 6e 74 66 28 20 22 73 74 |*/.X.pri|ntf( "st|
|00004440| 61 74 69 63 20 73 68 6f | 72 74 20 69 6e 74 20 79 |atic sho|rt int y|
|00004450| 79 5f 6e 78 74 5b 5d 5b | 25 64 5d 20 3d 5c 6e 20 |y_nxt[][|%d] =\n |
|00004460| 20 20 20 7b 5c 6e 22 2c | 0a 58 09 09 2f 2a 20 27 | {\n",|.X../* '|
|00004470| 7d 27 20 73 6f 20 76 69 | 20 64 6f 65 73 6e 27 74 |}' so vi| doesn't|
|00004480| 20 67 65 74 20 74 6f 6f | 20 63 6f 6e 66 75 73 65 | get too| confuse|
|00004490| 64 20 2a 2f 0a 58 09 09 | 6e 75 6d 5f 66 75 6c 6c |d */.X..|num_full|
|000044a0| 5f 74 61 62 6c 65 5f 72 | 6f 77 73 20 29 3b 0a 58 |_table_r|ows );.X|
|000044b0| 0a 58 09 2f 2a 20 67 65 | 6e 65 72 61 74 65 20 30 |.X./* ge|nerate 0|
|000044c0| 20 65 6e 74 72 69 65 73 | 20 66 6f 72 20 73 74 61 | entries| for sta|
|000044d0| 74 65 20 23 30 20 2a 2f | 0a 58 09 66 6f 72 20 28 |te #0 */|.X.for (|
|000044e0| 20 69 20 3d 20 30 3b 20 | 69 20 3c 20 6e 75 6d 5f | i = 0; |i < num_|
|000044f0| 66 75 6c 6c 5f 74 61 62 | 6c 65 5f 72 6f 77 73 3b |full_tab|le_rows;|
|00004500| 20 2b 2b 69 20 29 0a 58 | 09 20 20 20 20 6d 6b 32 | ++i ).X|. mk2|
|00004510| 64 61 74 61 28 20 30 20 | 29 3b 0a 58 0a 58 09 2f |data( 0 |);.X.X./|
|00004520| 2a 20 66 6f 72 63 65 20 | 27 2c 27 20 61 6e 64 20 |* force |',' and |
|00004530| 64 61 74 61 66 6c 75 73 | 68 28 29 20 6e 65 78 74 |dataflus|h() next|
|00004540| 20 63 61 6c 6c 20 74 6f | 20 6d 6b 32 64 61 74 61 | call to| mk2data|
|00004550| 20 2a 2f 0a 58 09 64 61 | 74 61 70 6f 73 20 3d 20 | */.X.da|tapos = |
|00004560| 4e 55 4d 44 41 54 41 49 | 54 45 4d 53 3b 0a 58 0a |NUMDATAI|TEMS;.X.|
|00004570| 58 09 2f 2a 20 66 6f 72 | 63 65 20 65 78 74 72 61 |X./* for|ce extra|
|00004580| 20 62 6c 61 6e 6b 20 6c | 69 6e 65 20 6e 65 78 74 | blank l|ine next|
|00004590| 20 64 61 74 61 66 6c 75 | 73 68 28 29 20 2a 2f 0a | dataflu|sh() */.|
|000045a0| 58 09 64 61 74 61 6c 69 | 6e 65 20 3d 20 4e 55 4d |X.datali|ne = NUM|
|000045b0| 44 41 54 41 4c 49 4e 45 | 53 3b 0a 58 09 7d 0a 58 |DATALINE|S;.X.}.X|
|000045c0| 0a 58 20 20 20 20 2f 2a | 20 63 72 65 61 74 65 20 |.X /*| create |
|000045d0| 74 68 65 20 66 69 72 73 | 74 20 73 74 61 74 65 73 |the firs|t states|
|000045e0| 20 2a 2f 0a 58 0a 58 20 | 20 20 20 6e 75 6d 5f 73 | */.X.X | num_s|
|000045f0| 74 61 72 74 5f 73 74 61 | 74 65 73 20 3d 20 6c 61 |tart_sta|tes = la|
|00004600| 73 74 73 63 20 2a 20 32 | 3b 0a 58 0a 58 20 20 20 |stsc * 2|;.X.X |
|00004610| 20 66 6f 72 20 28 20 69 | 20 3d 20 31 3b 20 69 20 | for ( i| = 1; i |
|00004620| 3c 3d 20 6e 75 6d 5f 73 | 74 61 72 74 5f 73 74 61 |<= num_s|tart_sta|
|00004630| 74 65 73 3b 20 2b 2b 69 | 20 29 0a 58 09 7b 0a 58 |tes; ++i| ).X.{.X|
|00004640| 09 6e 75 6d 73 74 61 74 | 65 73 20 3d 20 31 3b 0a |.numstat|es = 1;.|
|00004650| 58 0a 58 09 2f 2a 20 66 | 6f 72 20 65 61 63 68 20 |X.X./* f|or each |
|00004660| 73 74 61 72 74 20 63 6f | 6e 64 69 74 69 6f 6e 2c |start co|ndition,|
|00004670| 20 6d 61 6b 65 20 6f 6e | 65 20 73 74 61 74 65 20 | make on|e state |
|00004680| 66 6f 72 20 74 68 65 20 | 63 61 73 65 20 77 68 65 |for the |case whe|
|00004690| 6e 0a 58 09 20 2a 20 77 | 65 27 72 65 20 61 74 20 |n.X. * w|e're at |
|000046a0| 74 68 65 20 62 65 67 69 | 6e 6e 69 6e 67 20 6f 66 |the begi|nning of|
|000046b0| 20 74 68 65 20 6c 69 6e | 65 20 28 74 68 65 20 27 | the lin|e (the '|
|000046c0| 25 27 20 6f 70 65 72 61 | 74 6f 72 29 20 61 6e 64 |%' opera|tor) and|
|000046d0| 0a 58 09 20 2a 20 6f 6e | 65 20 66 6f 72 20 74 68 |.X. * on|e for th|
|000046e0| 65 20 63 61 73 65 20 77 | 68 65 6e 20 77 65 27 72 |e case w|hen we'r|
|000046f0| 65 20 6e 6f 74 0a 58 09 | 20 2a 2f 0a 58 09 69 66 |e not.X.| */.X.if|
|00004700| 20 28 20 69 20 25 20 32 | 20 3d 3d 20 31 20 29 0a | ( i % 2| == 1 ).|
|00004710| 58 09 20 20 20 20 6e 73 | 65 74 5b 6e 75 6d 73 74 |X. ns|et[numst|
|00004720| 61 74 65 73 5d 20 3d 20 | 73 63 73 65 74 5b 28 69 |ates] = |scset[(i|
|00004730| 20 2f 20 32 29 20 2b 20 | 31 5d 3b 0a 58 09 65 6c | / 2) + |1];.X.el|
|00004740| 73 65 0a 58 09 20 20 20 | 20 6e 73 65 74 5b 6e 75 |se.X. | nset[nu|
|00004750| 6d 73 74 61 74 65 73 5d | 20 3d 20 6d 6b 62 72 61 |mstates]| = mkbra|
|00004760| 6e 63 68 28 20 73 63 62 | 6f 6c 5b 69 20 2f 20 32 |nch( scb|ol[i / 2|
|00004770| 5d 2c 20 73 63 73 65 74 | 5b 69 20 2f 20 32 5d 20 |], scset|[i / 2] |
|00004780| 29 3b 0a 58 0a 58 09 6e | 73 65 74 20 3d 20 65 70 |);.X.X.n|set = ep|
|00004790| 73 63 6c 6f 73 75 72 65 | 28 20 6e 73 65 74 2c 20 |sclosure|( nset, |
|000047a0| 26 6e 75 6d 73 74 61 74 | 65 73 2c 20 61 63 63 73 |&numstat|es, accs|
|000047b0| 65 74 2c 20 26 6e 61 63 | 63 2c 20 26 68 61 73 68 |et, &nac|c, &hash|
|000047c0| 76 61 6c 20 29 3b 0a 58 | 0a 58 09 69 66 20 28 20 |val );.X|.X.if ( |
|000047d0| 73 6e 73 74 6f 64 73 28 | 20 6e 73 65 74 2c 20 6e |snstods(| nset, n|
|000047e0| 75 6d 73 74 61 74 65 73 | 2c 20 61 63 63 73 65 74 |umstates|, accset|
|000047f0| 2c 20 6e 61 63 63 2c 20 | 68 61 73 68 76 61 6c 2c |, nacc, |hashval,|
|00004800| 20 26 64 73 20 29 20 29 | 0a 58 09 20 20 20 20 7b | &ds ) )|.X. {|
|00004810| 0a 58 09 20 20 20 20 6e | 75 6d 61 73 20 2b 3d 20 |.X. n|umas += |
|00004820| 6e 61 63 63 3b 0a 58 09 | 20 20 20 20 74 6f 74 6e |nacc;.X.| totn|
|00004830| 73 74 20 2b 3d 20 6e 75 | 6d 73 74 61 74 65 73 3b |st += nu|mstates;|
|00004840| 0a 58 09 20 20 20 20 2b | 2b 74 6f 64 6f 5f 6e 65 |.X. +|+todo_ne|
|00004850| 78 74 3b 0a 58 0a 58 09 | 20 20 20 20 69 66 20 28 |xt;.X.X.| if (|
|00004860| 20 76 61 72 69 61 62 6c | 65 5f 74 72 61 69 6c 69 | variabl|e_traili|
|00004870| 6e 67 5f 63 6f 6e 74 65 | 78 74 5f 72 75 6c 65 73 |ng_conte|xt_rules|
|00004880| 20 26 26 20 6e 61 63 63 | 20 3e 20 30 20 29 0a 58 | && nacc| > 0 ).X|
|00004890| 09 09 63 68 65 63 6b 5f | 74 72 61 69 6c 69 6e 67 |..check_|trailing|
|000048a0| 5f 63 6f 6e 74 65 78 74 | 28 20 6e 73 65 74 2c 20 |_context|( nset, |
|000048b0| 6e 75 6d 73 74 61 74 65 | 73 2c 20 61 63 63 73 65 |numstate|s, accse|
|000048c0| 74 2c 20 6e 61 63 63 20 | 29 3b 0a 58 09 20 20 20 |t, nacc |);.X. |
|000048d0| 20 7d 0a 58 09 7d 0a 58 | 0a 58 20 20 20 20 69 66 | }.X.}.X|.X if|
|000048e0| 20 28 20 21 20 66 75 6c | 6c 73 70 64 20 29 0a 58 | ( ! ful|lspd ).X|
|000048f0| 09 7b 0a 58 09 69 66 20 | 28 20 21 20 73 6e 73 74 |.{.X.if |( ! snst|
|00004900| 6f 64 73 28 20 6e 73 65 | 74 2c 20 30 2c 20 61 63 |ods( nse|t, 0, ac|
|00004910| 63 73 65 74 2c 20 30 2c | 20 30 2c 20 26 65 6e 64 |cset, 0,| 0, &end|
|00004920| 5f 6f 66 5f 62 75 66 66 | 65 72 5f 73 74 61 74 65 |_of_buff|er_state|
|00004930| 20 29 20 29 0a 58 09 20 | 20 20 20 66 6c 65 78 66 | ) ).X. | flexf|
|00004940| 61 74 61 6c 28 20 22 63 | 6f 75 6c 64 20 6e 6f 74 |atal( "c|ould not|
|00004950| 20 63 72 65 61 74 65 20 | 75 6e 69 71 75 65 20 65 | create |unique e|
|00004960| 6e 64 2d 6f 66 2d 62 75 | 66 66 65 72 20 73 74 61 |nd-of-bu|ffer sta|
|00004970| 74 65 22 20 29 3b 0a 58 | 0a 58 09 2b 2b 6e 75 6d |te" );.X|.X.++num|
|00004980| 61 73 3b 0a 58 09 2b 2b | 6e 75 6d 5f 73 74 61 72 |as;.X.++|num_star|
|00004990| 74 5f 73 74 61 74 65 73 | 3b 0a 58 09 2b 2b 74 6f |t_states|;.X.++to|
|000049a0| 64 6f 5f 6e 65 78 74 3b | 0a 58 09 7d 0a 58 0a 58 |do_next;|.X.}.X.X|
|000049b0| 20 20 20 20 77 68 69 6c | 65 20 28 20 74 6f 64 6f | whil|e ( todo|
|000049c0| 5f 68 65 61 64 20 3c 20 | 74 6f 64 6f 5f 6e 65 78 |_head < |todo_nex|
|000049d0| 74 20 29 0a 58 09 7b 0a | 58 09 74 61 72 67 70 74 |t ).X.{.|X.targpt|
|000049e0| 72 20 3d 20 30 3b 0a 58 | 09 74 6f 74 61 6c 74 72 |r = 0;.X|.totaltr|
|000049f0| 61 6e 73 20 3d 20 30 3b | 0a 58 0a 58 09 66 6f 72 |ans = 0;|.X.X.for|
|00004a00| 20 28 20 69 20 3d 20 31 | 3b 20 69 20 3c 3d 20 6e | ( i = 1|; i <= n|
|00004a10| 75 6d 65 63 73 3b 20 2b | 2b 69 20 29 0a 58 09 20 |umecs; +|+i ).X. |
|00004a20| 20 20 20 73 74 61 74 65 | 5b 69 5d 20 3d 20 30 3b | state|[i] = 0;|
|00004a30| 0a 58 0a 58 09 64 73 20 | 3d 20 2b 2b 74 6f 64 6f |.X.X.ds |= ++todo|
|00004a40| 5f 68 65 61 64 3b 0a 58 | 0a 58 09 64 73 65 74 20 |_head;.X|.X.dset |
|00004a50| 3d 20 64 73 73 5b 64 73 | 5d 3b 0a 58 09 64 73 69 |= dss[ds|];.X.dsi|
|00004a60| 7a 65 20 3d 20 64 66 61 | 73 69 7a 5b 64 73 5d 3b |ze = dfa|siz[ds];|
|00004a70| 0a 58 0a 58 09 69 66 20 | 28 20 74 72 61 63 65 20 |.X.X.if |( trace |
|00004a80| 29 0a 58 09 20 20 20 20 | 66 70 72 69 6e 74 66 28 |).X. |fprintf(|
|00004a90| 20 73 74 64 65 72 72 2c | 20 22 73 74 61 74 65 20 | stderr,| "state |
|00004aa0| 23 20 25 64 3a 5c 6e 22 | 2c 20 64 73 20 29 3b 0a |# %d:\n"|, ds );.|
|00004ab0| 58 0a 58 09 73 79 6d 70 | 61 72 74 69 74 69 6f 6e |X.X.symp|artition|
|00004ac0| 28 20 64 73 65 74 2c 20 | 64 73 69 7a 65 2c 20 73 |( dset, |dsize, s|
|00004ad0| 79 6d 6c 69 73 74 2c 20 | 64 75 70 6c 69 73 74 20 |ymlist, |duplist |
|00004ae0| 29 3b 0a 58 0a 58 09 66 | 6f 72 20 28 20 73 79 6d |);.X.X.f|or ( sym|
|00004af0| 20 3d 20 31 3b 20 73 79 | 6d 20 3c 3d 20 6e 75 6d | = 1; sy|m <= num|
|00004b00| 65 63 73 3b 20 2b 2b 73 | 79 6d 20 29 0a 58 09 20 |ecs; ++s|ym ).X. |
|00004b10| 20 20 20 7b 0a 58 09 20 | 20 20 20 69 66 20 28 20 | {.X. | if ( |
|00004b20| 73 79 6d 6c 69 73 74 5b | 73 79 6d 5d 20 29 0a 58 |symlist[|sym] ).X|
|00004b30| 09 09 7b 0a 58 09 09 73 | 79 6d 6c 69 73 74 5b 73 |..{.X..s|ymlist[s|
|00004b40| 79 6d 5d 20 3d 20 30 3b | 0a 58 0a 58 09 09 69 66 |ym] = 0;|.X.X..if|
|00004b50| 20 28 20 64 75 70 6c 69 | 73 74 5b 73 79 6d 5d 20 | ( dupli|st[sym] |
|00004b60| 3d 3d 20 4e 49 4c 20 29 | 0a 58 09 09 20 20 20 20 |== NIL )|.X.. |
|00004b70| 7b 20 2f 2a 20 73 79 6d | 62 6f 6c 20 68 61 73 20 |{ /* sym|bol has |
|00004b80| 75 6e 69 71 75 65 20 6f | 75 74 2d 74 72 61 6e 73 |unique o|ut-trans|
|00004b90| 69 74 69 6f 6e 73 20 2a | 2f 0a 58 09 09 20 20 20 |itions *|/.X.. |
|00004ba0| 20 6e 75 6d 73 74 61 74 | 65 73 20 3d 20 73 79 6d | numstat|es = sym|
|00004bb0| 66 6f 6c 6c 6f 77 73 65 | 74 28 20 64 73 65 74 2c |followse|t( dset,|
|00004bc0| 20 64 73 69 7a 65 2c 20 | 73 79 6d 2c 20 6e 73 65 | dsize, |sym, nse|
|00004bd0| 74 20 29 3b 0a 58 09 09 | 20 20 20 20 6e 73 65 74 |t );.X..| nset|
|00004be0| 20 3d 20 65 70 73 63 6c | 6f 73 75 72 65 28 20 6e | = epscl|osure( n|
|00004bf0| 73 65 74 2c 20 26 6e 75 | 6d 73 74 61 74 65 73 2c |set, &nu|mstates,|
|00004c00| 20 61 63 63 73 65 74 2c | 0a 58 09 09 09 09 20 20 | accset,|.X.... |
|00004c10| 20 20 20 20 20 26 6e 61 | 63 63 2c 20 26 68 61 73 | &na|cc, &has|
|00004c20| 68 76 61 6c 20 29 3b 0a | 58 0a 58 09 09 20 20 20 |hval );.|X.X.. |
|00004c30| 20 69 66 20 28 20 73 6e | 73 74 6f 64 73 28 20 6e | if ( sn|stods( n|
|00004c40| 73 65 74 2c 20 6e 75 6d | 73 74 61 74 65 73 2c 20 |set, num|states, |
|00004c50| 61 63 63 73 65 74 2c 0a | 58 09 09 09 09 20 20 6e |accset,.|X.... n|
|00004c60| 61 63 63 2c 20 68 61 73 | 68 76 61 6c 2c 20 26 6e |acc, has|hval, &n|
|00004c70| 65 77 64 73 20 29 20 29 | 0a 58 09 09 09 7b 0a 58 |ewds ) )|.X...{.X|
|00004c80| 09 09 09 74 6f 74 6e 73 | 74 20 3d 20 74 6f 74 6e |...totns|t = totn|
|00004c90| 73 74 20 2b 20 6e 75 6d | 73 74 61 74 65 73 3b 0a |st + num|states;.|
|00004ca0| 58 09 09 09 2b 2b 74 6f | 64 6f 5f 6e 65 78 74 3b |X...++to|do_next;|
|00004cb0| 0a 58 09 09 09 6e 75 6d | 61 73 20 2b 3d 20 6e 61 |.X...num|as += na|
|00004cc0| 63 63 3b 0a 58 0a 58 09 | 09 09 69 66 20 28 20 76 |cc;.X.X.|..if ( v|
|00004cd0| 61 72 69 61 62 6c 65 5f | 74 72 61 69 6c 69 6e 67 |ariable_|trailing|
|00004ce0| 5f 63 6f 6e 74 65 78 74 | 5f 72 75 6c 65 73 20 26 |_context|_rules &|
|00004cf0| 26 20 6e 61 63 63 20 3e | 20 30 20 29 0a 58 09 09 |& nacc >| 0 ).X..|
|00004d00| 09 20 20 20 20 63 68 65 | 63 6b 5f 74 72 61 69 6c |. che|ck_trail|
|00004d10| 69 6e 67 5f 63 6f 6e 74 | 65 78 74 28 20 6e 73 65 |ing_cont|ext( nse|
|00004d20| 74 2c 20 6e 75 6d 73 74 | 61 74 65 73 2c 0a 58 09 |t, numst|ates,.X.|
|00004d30| 09 09 09 61 63 63 73 65 | 74 2c 20 6e 61 63 63 20 |...accse|t, nacc |
|00004d40| 29 3b 0a 58 09 09 09 7d | 0a 58 0a 58 09 09 20 20 |);.X...}|.X.X.. |
|00004d50| 20 20 73 74 61 74 65 5b | 73 79 6d 5d 20 3d 20 6e | state[|sym] = n|
|00004d60| 65 77 64 73 3b 0a 58 0a | 58 09 09 20 20 20 20 69 |ewds;.X.|X.. i|
|00004d70| 66 20 28 20 74 72 61 63 | 65 20 29 0a 58 09 09 09 |f ( trac|e ).X...|
|00004d80| 66 70 72 69 6e 74 66 28 | 20 73 74 64 65 72 72 2c |fprintf(| stderr,|
|00004d90| 20 22 5c 74 25 64 5c 74 | 25 64 5c 6e 22 2c 20 73 | "\t%d\t|%d\n", s|
|00004da0| 79 6d 2c 20 6e 65 77 64 | 73 20 29 3b 0a 58 0a 58 |ym, newd|s );.X.X|
|00004db0| 09 09 20 20 20 20 74 61 | 72 67 66 72 65 71 5b 2b |.. ta|rgfreq[+|
|00004dc0| 2b 74 61 72 67 70 74 72 | 5d 20 3d 20 31 3b 0a 58 |+targptr|] = 1;.X|
|00004dd0| 09 09 20 20 20 20 74 61 | 72 67 73 74 61 74 65 5b |.. ta|rgstate[|
|00004de0| 74 61 72 67 70 74 72 5d | 20 3d 20 6e 65 77 64 73 |targptr]| = newds|
|00004df0| 3b 0a 58 09 09 20 20 20 | 20 2b 2b 6e 75 6d 75 6e |;.X.. | ++numun|
|00004e00| 69 71 3b 0a 58 09 09 20 | 20 20 20 7d 0a 58 0a 58 |iq;.X.. | }.X.X|
|00004e10| 09 09 65 6c 73 65 0a 58 | 09 09 20 20 20 20 7b 0a |..else.X|.. {.|
|00004e20| 58 09 09 20 20 20 20 2f | 2a 20 73 79 6d 27 73 20 |X.. /|* sym's |
|00004e30| 65 71 75 69 76 61 6c 65 | 6e 63 65 20 63 6c 61 73 |equivale|nce clas|
|00004e40| 73 20 68 61 73 20 74 68 | 65 20 73 61 6d 65 20 74 |s has th|e same t|
|00004e50| 72 61 6e 73 69 74 69 6f | 6e 73 0a 58 09 09 20 20 |ransitio|ns.X.. |
|00004e60| 20 20 20 2a 20 61 73 20 | 64 75 70 6c 69 73 74 28 | * as |duplist(|
|00004e70| 73 79 6d 29 27 73 20 65 | 71 75 69 76 61 6c 65 6e |sym)'s e|quivalen|
|00004e80| 63 65 20 63 6c 61 73 73 | 0a 58 09 09 20 20 20 20 |ce class|.X.. |
|00004e90| 20 2a 2f 0a 58 09 09 20 | 20 20 20 74 61 72 67 20 | */.X.. | targ |
|00004ea0| 3d 20 73 74 61 74 65 5b | 64 75 70 6c 69 73 74 5b |= state[|duplist[|
|00004eb0| 73 79 6d 5d 5d 3b 0a 58 | 09 09 20 20 20 20 73 74 |sym]];.X|.. st|
|00004ec0| 61 74 65 5b 73 79 6d 5d | 20 3d 20 74 61 72 67 3b |ate[sym]| = targ;|
|00004ed0| 0a 58 0a 58 09 09 20 20 | 20 20 69 66 20 28 20 74 |.X.X.. | if ( t|
|00004ee0| 72 61 63 65 20 29 0a 58 | 09 09 09 66 70 72 69 6e |race ).X|...fprin|
|00004ef0| 74 66 28 20 73 74 64 65 | 72 72 2c 20 22 5c 74 25 |tf( stde|rr, "\t%|
|00004f00| 64 5c 74 25 64 5c 6e 22 | 2c 20 73 79 6d 2c 20 74 |d\t%d\n"|, sym, t|
|00004f10| 61 72 67 20 29 3b 0a 58 | 0a 58 09 09 20 20 20 20 |arg );.X|.X.. |
|00004f20| 2f 2a 20 75 70 64 61 74 | 65 20 66 72 65 71 75 65 |/* updat|e freque|
|00004f30| 6e 63 79 20 63 6f 75 6e | 74 20 66 6f 72 20 64 65 |ncy coun|t for de|
|00004f40| 73 74 69 6e 61 74 69 6f | 6e 20 73 74 61 74 65 20 |stinatio|n state |
|00004f50| 2a 2f 0a 58 0a 58 09 09 | 20 20 20 20 69 20 3d 20 |*/.X.X..| i = |
|00004f60| 30 3b 0a 58 09 09 20 20 | 20 20 77 68 69 6c 65 20 |0;.X.. | while |
|00004f70| 28 20 74 61 72 67 73 74 | 61 74 65 5b 2b 2b 69 5d |( targst|ate[++i]|
|00004f80| 20 21 3d 20 74 61 72 67 | 20 29 0a 58 09 09 09 3b | != targ| ).X...;|
|00004f90| 0a 58 0a 58 09 09 20 20 | 20 20 2b 2b 74 61 72 67 |.X.X.. | ++targ|
|00004fa0| 66 72 65 71 5b 69 5d 3b | 0a 58 09 09 20 20 20 20 |freq[i];|.X.. |
|00004fb0| 2b 2b 6e 75 6d 64 75 70 | 3b 0a 58 09 09 20 20 20 |++numdup|;.X.. |
|00004fc0| 20 7d 0a 58 0a 58 09 09 | 2b 2b 74 6f 74 61 6c 74 | }.X.X..|++totalt|
|00004fd0| 72 61 6e 73 3b 0a 58 09 | 09 64 75 70 6c 69 73 74 |rans;.X.|.duplist|
|00004fe0| 5b 73 79 6d 5d 20 3d 20 | 4e 49 4c 3b 0a 58 09 09 |[sym] = |NIL;.X..|
|00004ff0| 7d 0a 58 09 20 20 20 20 | 7d 0a 58 0a 58 09 6e 75 |}.X. |}.X.X.nu|
|00005000| 6d 73 6e 70 61 69 72 73 | 20 3d 20 6e 75 6d 73 6e |msnpairs| = numsn|
|00005010| 70 61 69 72 73 20 2b 20 | 74 6f 74 61 6c 74 72 61 |pairs + |totaltra|
|00005020| 6e 73 3b 0a 58 0a 58 09 | 69 66 20 28 20 63 61 73 |ns;.X.X.|if ( cas|
|00005030| 65 69 6e 73 20 26 26 20 | 21 20 75 73 65 65 63 73 |eins && |! useecs|
|00005040| 20 29 0a 58 09 20 20 20 | 20 7b 0a 58 09 20 20 20 | ).X. | {.X. |
|00005050| 20 72 65 67 69 73 74 65 | 72 20 69 6e 74 20 6a 3b | registe|r int j;|
|00005060| 0a 58 0a 58 09 20 20 20 | 20 66 6f 72 20 28 20 69 |.X.X. | for ( i|
|00005070| 20 3d 20 27 41 27 2c 20 | 6a 20 3d 20 27 61 27 3b | = 'A', |j = 'a';|
|00005080| 20 69 20 3c 3d 20 27 5a | 27 3b 20 2b 2b 69 2c 20 | i <= 'Z|'; ++i, |
|00005090| 2b 2b 6a 20 29 0a 58 09 | 09 73 74 61 74 65 5b 69 |++j ).X.|.state[i|
|000050a0| 5d 20 3d 20 73 74 61 74 | 65 5b 6a 5d 3b 0a 58 09 |] = stat|e[j];.X.|
|000050b0| 20 20 20 20 7d 0a 58 0a | 58 09 69 66 20 28 20 64 | }.X.|X.if ( d|
|000050c0| 73 20 3e 20 6e 75 6d 5f | 73 74 61 72 74 5f 73 74 |s > num_|start_st|
|000050d0| 61 74 65 73 20 29 0a 58 | 09 20 20 20 20 63 68 65 |ates ).X|. che|
|000050e0| 63 6b 5f 66 6f 72 5f 62 | 61 63 6b 74 72 61 63 6b |ck_for_b|acktrack|
|000050f0| 69 6e 67 28 20 64 73 2c | 20 73 74 61 74 65 20 29 |ing( ds,| state )|
|00005100| 3b 0a 58 0a 58 09 69 66 | 20 28 20 6e 75 6c 74 72 |;.X.X.if| ( nultr|
|00005110| 61 6e 73 20 29 0a 58 09 | 20 20 20 20 7b 0a 58 09 |ans ).X.| {.X.|
|00005120| 20 20 20 20 6e 75 6c 74 | 72 61 6e 73 5b 64 73 5d | nult|rans[ds]|
|00005130| 20 3d 20 73 74 61 74 65 | 5b 4e 55 4c 5f 65 63 5d | = state|[NUL_ec]|
|00005140| 3b 0a 58 09 20 20 20 20 | 73 74 61 74 65 5b 4e 55 |;.X. |state[NU|
|00005150| 4c 5f 65 63 5d 20 3d 20 | 30 3b 09 2f 2a 20 72 65 |L_ec] = |0;./* re|
|00005160| 6d 6f 76 65 20 74 72 61 | 6e 73 69 74 69 6f 6e 20 |move tra|nsition |
|00005170| 2a 2f 0a 58 09 20 20 20 | 20 7d 0a 58 0a 58 09 69 |*/.X. | }.X.X.i|
|00005180| 66 20 28 20 66 75 6c 6c | 74 62 6c 20 29 0a 58 09 |f ( full|tbl ).X.|
|00005190| 20 20 20 20 7b 0a 58 09 | 20 20 20 20 2f 2a 20 73 | {.X.| /* s|
|000051a0| 75 70 70 6c 79 20 61 72 | 72 61 79 27 73 20 30 2d |upply ar|ray's 0-|
|000051b0| 65 6c 65 6d 65 6e 74 20 | 2a 2f 0a 58 09 20 20 20 |element |*/.X. |
|000051c0| 20 69 66 20 28 20 64 73 | 20 3d 3d 20 65 6e 64 5f | if ( ds| == end_|
|000051d0| 6f 66 5f 62 75 66 66 65 | 72 5f 73 74 61 74 65 20 |of_buffe|r_state |
|000051e0| 29 0a 58 09 09 6d 6b 32 | 64 61 74 61 28 20 2d 65 |).X..mk2|data( -e|
|000051f0| 6e 64 5f 6f 66 5f 62 75 | 66 66 65 72 5f 73 74 61 |nd_of_bu|ffer_sta|
|00005200| 74 65 20 29 3b 0a 58 09 | 20 20 20 20 65 6c 73 65 |te );.X.| else|
|00005210| 0a 58 09 09 6d 6b 32 64 | 61 74 61 28 20 65 6e 64 |.X..mk2d|ata( end|
|00005220| 5f 6f 66 5f 62 75 66 66 | 65 72 5f 73 74 61 74 65 |_of_buff|er_state|
|00005230| 20 29 3b 0a 58 0a 58 09 | 20 20 20 20 66 6f 72 20 | );.X.X.| for |
|00005240| 28 20 69 20 3d 20 31 3b | 20 69 20 3c 20 6e 75 6d |( i = 1;| i < num|
|00005250| 5f 66 75 6c 6c 5f 74 61 | 62 6c 65 5f 72 6f 77 73 |_full_ta|ble_rows|
|00005260| 3b 20 2b 2b 69 20 29 0a | 58 09 09 2f 2a 20 6a 61 |; ++i ).|X../* ja|
|00005270| 6d 73 20 61 72 65 20 6d | 61 72 6b 65 64 20 62 79 |ms are m|arked by|
|00005280| 20 6e 65 67 61 74 69 76 | 65 20 6f 66 20 73 74 61 | negativ|e of sta|
|00005290| 74 65 20 6e 75 6d 62 65 | 72 20 2a 2f 0a 58 09 09 |te numbe|r */.X..|
|000052a0| 6d 6b 32 64 61 74 61 28 | 20 73 74 61 74 65 5b 69 |mk2data(| state[i|
|000052b0| 5d 20 3f 20 73 74 61 74 | 65 5b 69 5d 20 3a 20 2d |] ? stat|e[i] : -|
|000052c0| 64 73 20 29 3b 0a 58 0a | 58 09 20 20 20 20 2f 2a |ds );.X.|X. /*|
|000052d0| 20 66 6f 72 63 65 20 27 | 2c 27 20 61 6e 64 20 64 | force '|,' and d|
|000052e0| 61 74 61 66 6c 75 73 68 | 28 29 20 6e 65 78 74 20 |ataflush|() next |
|000052f0| 63 61 6c 6c 20 74 6f 20 | 6d 6b 32 64 61 74 61 20 |call to |mk2data |
|00005300| 2a 2f 0a 58 09 20 20 20 | 20 64 61 74 61 70 6f 73 |*/.X. | datapos|
|00005310| 20 3d 20 4e 55 4d 44 41 | 54 41 49 54 45 4d 53 3b | = NUMDA|TAITEMS;|
|00005320| 0a 58 0a 58 09 20 20 20 | 20 2f 2a 20 66 6f 72 63 |.X.X. | /* forc|
|00005330| 65 20 65 78 74 72 61 20 | 62 6c 61 6e 6b 20 6c 69 |e extra |blank li|
|00005340| 6e 65 20 6e 65 78 74 20 | 64 61 74 61 66 6c 75 73 |ne next |dataflus|
|00005350| 68 28 29 20 2a 2f 0a 58 | 09 20 20 20 20 64 61 74 |h() */.X|. dat|
|00005360| 61 6c 69 6e 65 20 3d 20 | 4e 55 4d 44 41 54 41 4c |aline = |NUMDATAL|
|00005370| 49 4e 45 53 3b 0a 58 09 | 20 20 20 20 7d 0a 58 0a |INES;.X.| }.X.|
|00005380| 58 20 20 20 20 20 20 20 | 20 65 6c 73 65 20 69 66 |X | else if|
|00005390| 20 28 20 66 75 6c 6c 73 | 70 64 20 29 0a 58 09 20 | ( fulls|pd ).X. |
|000053a0| 20 20 20 70 6c 61 63 65 | 5f 73 74 61 74 65 28 20 | place|_state( |
|000053b0| 73 74 61 74 65 2c 20 64 | 73 2c 20 74 6f 74 61 6c |state, d|s, total|
|000053c0| 74 72 61 6e 73 20 29 3b | 0a 58 0a 58 09 65 6c 73 |trans );|.X.X.els|
|000053d0| 65 20 69 66 20 28 20 64 | 73 20 3d 3d 20 65 6e 64 |e if ( d|s == end|
|000053e0| 5f 6f 66 5f 62 75 66 66 | 65 72 5f 73 74 61 74 65 |_of_buff|er_state|
|000053f0| 20 29 0a 58 09 20 20 20 | 20 2f 2a 20 73 70 65 63 | ).X. | /* spec|
|00005400| 69 61 6c 20 63 61 73 65 | 20 74 68 69 73 20 73 74 |ial case| this st|
|00005410| 61 74 65 20 74 6f 20 6d | 61 6b 65 20 73 75 72 65 |ate to m|ake sure|
|00005420| 20 69 74 20 64 6f 65 73 | 20 77 68 61 74 20 69 74 | it does| what it|
|00005430| 27 73 0a 58 09 20 20 20 | 20 20 2a 20 73 75 70 70 |'s.X. | * supp|
|00005440| 6f 73 65 64 20 74 6f 2c | 20 69 2e 65 2e 2c 20 6a |osed to,| i.e., j|
|00005450| 61 6d 20 6f 6e 20 65 6e | 64 2d 6f 66 2d 62 75 66 |am on en|d-of-buf|
|00005460| 66 65 72 0a 58 09 20 20 | 20 20 20 2a 2f 0a 58 09 |fer.X. | */.X.|
|00005470| 20 20 20 20 73 74 61 63 | 6b 31 28 20 64 73 2c 20 | stac|k1( ds, |
|00005480| 30 2c 20 30 2c 20 4a 41 | 4d 53 54 41 54 45 20 29 |0, 0, JA|MSTATE )|
|00005490| 3b 0a 58 0a 58 09 65 6c | 73 65 20 2f 2a 20 6e 6f |;.X.X.el|se /* no|
|000054a0| 72 6d 61 6c 2c 20 63 6f | 6d 70 72 65 73 73 65 64 |rmal, co|mpressed|
|000054b0| 20 73 74 61 74 65 20 2a | 2f 0a 58 09 20 20 20 20 | state *|/.X. |
|000054c0| 7b 0a 58 09 20 20 20 20 | 2f 2a 20 64 65 74 65 72 |{.X. |/* deter|
|000054d0| 6d 69 6e 65 20 77 68 69 | 63 68 20 64 65 73 74 69 |mine whi|ch desti|
|000054e0| 6e 61 74 69 6f 6e 20 73 | 74 61 74 65 20 69 73 20 |nation s|tate is |
|000054f0| 74 68 65 20 6d 6f 73 74 | 20 63 6f 6d 6d 6f 6e 2c |the most| common,|
|00005500| 20 61 6e 64 0a 58 09 20 | 20 20 20 20 2a 20 68 6f | and.X. | * ho|
|00005510| 77 20 6d 61 6e 79 20 74 | 72 61 6e 73 69 74 69 6f |w many t|ransitio|
|00005520| 6e 73 20 74 6f 20 69 74 | 20 74 68 65 72 65 20 61 |ns to it| there a|
|00005530| 72 65 0a 58 09 20 20 20 | 20 20 2a 2f 0a 58 0a 58 |re.X. | */.X.X|
|00005540| 09 20 20 20 20 63 6f 6d | 66 72 65 71 20 3d 20 30 |. com|freq = 0|
|00005550| 3b 0a 58 09 20 20 20 20 | 63 6f 6d 73 74 61 74 65 |;.X. |comstate|
|00005560| 20 3d 20 30 3b 0a 58 0a | 58 09 20 20 20 20 66 6f | = 0;.X.|X. fo|
|00005570| 72 20 28 20 69 20 3d 20 | 31 3b 20 69 20 3c 3d 20 |r ( i = |1; i <= |
|00005580| 74 61 72 67 70 74 72 3b | 20 2b 2b 69 20 29 0a 58 |targptr;| ++i ).X|
|00005590| 09 09 69 66 20 28 20 74 | 61 72 67 66 72 65 71 5b |..if ( t|argfreq[|
|000055a0| 69 5d 20 3e 20 63 6f 6d | 66 72 65 71 20 29 0a 58 |i] > com|freq ).X|
|000055b0| 09 09 20 20 20 20 7b 0a | 58 09 09 20 20 20 20 63 |.. {.|X.. c|
|000055c0| 6f 6d 66 72 65 71 20 3d | 20 74 61 72 67 66 72 65 |omfreq =| targfre|
|000055d0| 71 5b 69 5d 3b 0a 58 09 | 09 20 20 20 20 63 6f 6d |q[i];.X.|. com|
|000055e0| 73 74 61 74 65 20 3d 20 | 74 61 72 67 73 74 61 74 |state = |targstat|
|000055f0| 65 5b 69 5d 3b 0a 58 09 | 09 20 20 20 20 7d 0a 58 |e[i];.X.|. }.X|
|00005600| 0a 58 09 20 20 20 20 62 | 6c 64 74 62 6c 28 20 73 |.X. b|ldtbl( s|
|00005610| 74 61 74 65 2c 20 64 73 | 2c 20 74 6f 74 61 6c 74 |tate, ds|, totalt|
|00005620| 72 61 6e 73 2c 20 63 6f | 6d 73 74 61 74 65 2c 20 |rans, co|mstate, |
|00005630| 63 6f 6d 66 72 65 71 20 | 29 3b 0a 58 09 20 20 20 |comfreq |);.X. |
|00005640| 20 7d 0a 58 09 7d 0a 58 | 0a 58 20 20 20 20 69 66 | }.X.}.X|.X if|
|00005650| 20 28 20 66 75 6c 6c 74 | 62 6c 20 29 0a 58 09 64 | ( fullt|bl ).X.d|
|00005660| 61 74 61 65 6e 64 28 29 | 3b 0a 58 0a 58 20 20 20 |ataend()|;.X.X |
|00005670| 20 65 6c 73 65 20 69 66 | 20 28 20 21 20 66 75 6c | else if| ( ! ful|
|00005680| 6c 73 70 64 20 29 0a 58 | 09 7b 0a 58 09 63 6d 70 |lspd ).X|.{.X.cmp|
|00005690| 74 6d 70 73 28 29 3b 20 | 20 2f 2a 20 63 72 65 61 |tmps(); | /* crea|
|000056a0| 74 65 20 63 6f 6d 70 72 | 65 73 73 65 64 20 74 65 |te compr|essed te|
|000056b0| 6d 70 6c 61 74 65 20 65 | 6e 74 72 69 65 73 20 2a |mplate e|ntries *|
|000056c0| 2f 0a 58 0a 58 09 2f 2a | 20 63 72 65 61 74 65 20 |/.X.X./*| create |
|000056d0| 74 61 62 6c 65 73 20 66 | 6f 72 20 61 6c 6c 20 74 |tables f|or all t|
|000056e0| 68 65 20 73 74 61 74 65 | 73 20 77 69 74 68 20 6f |he state|s with o|
|000056f0| 6e 6c 79 20 6f 6e 65 20 | 6f 75 74 2d 74 72 61 6e |nly one |out-tran|
|00005700| 73 69 74 69 6f 6e 20 2a | 2f 0a 58 09 77 68 69 6c |sition *|/.X.whil|
|00005710| 65 20 28 20 6f 6e 65 73 | 70 20 3e 20 30 20 29 0a |e ( ones|p > 0 ).|
|00005720| 58 09 20 20 20 20 7b 0a | 58 09 20 20 20 20 6d 6b |X. {.|X. mk|
|00005730| 31 74 62 6c 28 20 6f 6e | 65 73 74 61 74 65 5b 6f |1tbl( on|estate[o|
|00005740| 6e 65 73 70 5d 2c 20 6f | 6e 65 73 79 6d 5b 6f 6e |nesp], o|nesym[on|
|00005750| 65 73 70 5d 2c 20 6f 6e | 65 6e 65 78 74 5b 6f 6e |esp], on|enext[on|
|00005760| 65 73 70 5d 2c 0a 58 09 | 09 20 20 20 20 6f 6e 65 |esp],.X.|. one|
|00005770| 64 65 66 5b 6f 6e 65 73 | 70 5d 20 29 3b 0a 58 09 |def[ones|p] );.X.|
|00005780| 20 20 20 20 2d 2d 6f 6e | 65 73 70 3b 0a 58 09 20 | --on|esp;.X. |
|00005790| 20 20 20 7d 0a 58 0a 58 | 09 6d 6b 64 65 66 74 62 | }.X.X|.mkdeftb|
|000057a0| 6c 28 29 3b 0a 58 09 7d | 0a 58 20 20 20 20 7d 0a |l();.X.}|.X }.|
|000057b0| 58 0a 58 0a 58 2f 2a 20 | 73 6e 73 74 6f 64 73 20 |X.X.X/* |snstods |
|000057c0| 2d 20 63 6f 6e 76 65 72 | 74 73 20 61 20 73 65 74 |- conver|ts a set|
|000057d0| 20 6f 66 20 6e 64 66 61 | 20 73 74 61 74 65 73 20 | of ndfa| states |
|000057e0| 69 6e 74 6f 20 61 20 64 | 66 61 20 73 74 61 74 65 |into a d|fa state|
|000057f0| 0a 58 20 2a 0a 58 20 2a | 20 73 79 6e 6f 70 73 69 |.X *.X *| synopsi|
|00005800| 73 0a 58 20 2a 20 20 20 | 20 69 6e 74 20 73 6e 73 |s.X * | int sns|
|00005810| 5b 6e 75 6d 73 74 61 74 | 65 73 5d 2c 20 6e 75 6d |[numstat|es], num|
|00005820| 73 74 61 74 65 73 2c 20 | 6e 65 77 64 73 2c 20 61 |states, |newds, a|
|00005830| 63 63 73 65 74 5b 6e 75 | 6d 5f 72 75 6c 65 73 20 |ccset[nu|m_rules |
|00005840| 2b 20 31 5d 2c 20 6e 61 | 63 63 2c 20 68 61 73 68 |+ 1], na|cc, hash|
|00005850| 76 61 6c 3b 0a 58 20 2a | 20 20 20 20 69 6e 74 20 |val;.X *| int |
|00005860| 73 6e 73 74 6f 64 73 28 | 29 3b 0a 58 20 2a 20 20 |snstods(|);.X * |
|00005870| 20 20 69 73 5f 6e 65 77 | 5f 73 74 61 74 65 20 3d | is_new|_state =|
|00005880| 20 73 6e 73 74 6f 64 73 | 28 20 73 6e 73 2c 20 6e | snstods|( sns, n|
|00005890| 75 6d 73 74 61 74 65 73 | 2c 20 61 63 63 73 65 74 |umstates|, accset|
|000058a0| 2c 20 6e 61 63 63 2c 20 | 68 61 73 68 76 61 6c 2c |, nacc, |hashval,|
|000058b0| 20 26 6e 65 77 64 73 20 | 29 3b 0a 58 20 2a 0a 58 | &newds |);.X *.X|
|000058c0| 20 2a 20 6f 6e 20 72 65 | 74 75 72 6e 2c 20 74 68 | * on re|turn, th|
|000058d0| 65 20 64 66 61 20 73 74 | 61 74 65 20 6e 75 6d 62 |e dfa st|ate numb|
|000058e0| 65 72 20 69 73 20 69 6e | 20 6e 65 77 64 73 2e 0a |er is in| newds..|
|000058f0| 58 20 2a 2f 0a 58 0a 58 | 69 6e 74 20 73 6e 73 74 |X */.X.X|int snst|
|00005900| 6f 64 73 28 20 73 6e 73 | 2c 20 6e 75 6d 73 74 61 |ods( sns|, numsta|
|00005910| 74 65 73 2c 20 61 63 63 | 73 65 74 2c 20 6e 61 63 |tes, acc|set, nac|
|00005920| 63 2c 20 68 61 73 68 76 | 61 6c 2c 20 6e 65 77 64 |c, hashv|al, newd|
|00005930| 73 5f 61 64 64 72 20 29 | 0a 58 69 6e 74 20 73 6e |s_addr )|.Xint sn|
|00005940| 73 5b 5d 2c 20 6e 75 6d | 73 74 61 74 65 73 2c 20 |s[], num|states, |
|00005950| 61 63 63 73 65 74 5b 5d | 2c 20 6e 61 63 63 2c 20 |accset[]|, nacc, |
|00005960| 68 61 73 68 76 61 6c 2c | 20 2a 6e 65 77 64 73 5f |hashval,| *newds_|
|00005970| 61 64 64 72 3b 0a 58 0a | 58 20 20 20 20 7b 0a 58 |addr;.X.|X {.X|
|00005980| 20 20 20 20 69 6e 74 20 | 64 69 64 73 6f 72 74 20 | int |didsort |
|00005990| 3d 20 30 3b 0a 58 20 20 | 20 20 72 65 67 69 73 74 |= 0;.X | regist|
|000059a0| 65 72 20 69 6e 74 20 69 | 2c 20 6a 3b 0a 58 20 20 |er int i|, j;.X |
|000059b0| 20 20 69 6e 74 20 6e 65 | 77 64 73 2c 20 2a 6f 6c | int ne|wds, *ol|
|000059c0| 64 73 6e 73 3b 0a 58 0a | 58 20 20 20 20 66 6f 72 |dsns;.X.|X for|
|000059d0| 20 28 20 69 20 3d 20 31 | 3b 20 69 20 3c 3d 20 6c | ( i = 1|; i <= l|
|000059e0| 61 73 74 64 66 61 3b 20 | 2b 2b 69 20 29 0a 58 09 |astdfa; |++i ).X.|
|000059f0| 69 66 20 28 20 68 61 73 | 68 76 61 6c 20 3d 3d 20 |if ( has|hval == |
|00005a00| 64 68 61 73 68 5b 69 5d | 20 29 0a 58 09 20 20 20 |dhash[i]| ).X. |
|00005a10| 20 7b 0a 58 09 20 20 20 | 20 69 66 20 28 20 6e 75 | {.X. | if ( nu|
|00005a20| 6d 73 74 61 74 65 73 20 | 3d 3d 20 64 66 61 73 69 |mstates |== dfasi|
|00005a30| 7a 5b 69 5d 20 29 0a 58 | 09 09 7b 0a 58 09 09 6f |z[i] ).X|..{.X..o|
|00005a40| 6c 64 73 6e 73 20 3d 20 | 64 73 73 5b 69 5d 3b 0a |ldsns = |dss[i];.|
|00005a50| 58 0a 58 09 09 69 66 20 | 28 20 21 20 64 69 64 73 |X.X..if |( ! dids|
|00005a60| 6f 72 74 20 29 0a 58 09 | 09 20 20 20 20 7b 0a 58 |ort ).X.|. {.X|
|00005a70| 09 09 20 20 20 20 2f 2a | 20 77 65 20 73 6f 72 74 |.. /*| we sort|
|00005a80| 20 74 68 65 20 73 74 61 | 74 65 73 20 69 6e 20 73 | the sta|tes in s|
|00005a90| 6e 73 20 73 6f 20 77 65 | 20 63 61 6e 20 63 6f 6d |ns so we| can com|
|00005aa0| 70 61 72 65 20 69 74 20 | 74 6f 0a 58 09 09 20 20 |pare it |to.X.. |
|00005ab0| 20 20 20 2a 20 6f 6c 64 | 73 6e 73 20 71 75 69 63 | * old|sns quic|
|00005ac0| 6b 6c 79 2e 20 20 77 65 | 20 75 73 65 20 62 75 62 |kly. we| use bub|
|00005ad0| 62 6c 65 20 62 65 63 61 | 75 73 65 20 74 68 65 72 |ble beca|use ther|
|00005ae0| 65 20 70 72 6f 62 61 62 | 6c 79 0a 58 09 09 20 20 |e probab|ly.X.. |
|00005af0| 20 20 20 2a 20 61 72 65 | 6e 27 74 20 76 65 72 79 | * are|n't very|
|00005b00| 20 6d 61 6e 79 20 73 74 | 61 74 65 73 0a 58 09 09 | many st|ates.X..|
|00005b10| 20 20 20 20 20 2a 2f 0a | 58 09 09 20 20 20 20 62 | */.|X.. b|
|00005b20| 75 62 62 6c 65 28 20 73 | 6e 73 2c 20 6e 75 6d 73 |ubble( s|ns, nums|
|00005b30| 74 61 74 65 73 20 29 3b | 0a 58 09 09 20 20 20 20 |tates );|.X.. |
|00005b40| 64 69 64 73 6f 72 74 20 | 3d 20 31 3b 0a 58 09 09 |didsort |= 1;.X..|
|00005b50| 20 20 20 20 7d 0a 58 0a | 58 09 09 66 6f 72 20 28 | }.X.|X..for (|
|00005b60| 20 6a 20 3d 20 31 3b 20 | 6a 20 3c 3d 20 6e 75 6d | j = 1; |j <= num|
|00005b70| 73 74 61 74 65 73 3b 20 | 2b 2b 6a 20 29 0a 58 09 |states; |++j ).X.|
|00005b80| 09 20 20 20 20 69 66 20 | 28 20 73 6e 73 5b 6a 5d |. if |( sns[j]|
|00005b90| 20 21 3d 20 6f 6c 64 73 | 6e 73 5b 6a 5d 20 29 0a | != olds|ns[j] ).|
|00005ba0| 58 09 09 09 62 72 65 61 | 6b 3b 0a 58 0a 58 09 09 |X...brea|k;.X.X..|
|00005bb0| 69 66 20 28 20 6a 20 3e | 20 6e 75 6d 73 74 61 74 |if ( j >| numstat|
|00005bc0| 65 73 20 29 0a 58 09 09 | 20 20 20 20 7b 0a 58 09 |es ).X..| {.X.|
|00005bd0| 09 20 20 20 20 2b 2b 64 | 66 61 65 71 6c 3b 0a 58 |. ++d|faeql;.X|
|00005be0| 09 09 20 20 20 20 2a 6e | 65 77 64 73 5f 61 64 64 |.. *n|ewds_add|
|00005bf0| 72 20 3d 20 69 3b 0a 58 | 09 09 20 20 20 20 72 65 |r = i;.X|.. re|
|00005c00| 74 75 72 6e 20 28 20 30 | 20 29 3b 0a 58 09 09 20 |turn ( 0| );.X.. |
|00005c10| 20 20 20 7d 0a 58 0a 58 | 09 09 2b 2b 68 73 68 63 | }.X.X|..++hshc|
|00005c20| 6f 6c 3b 0a 58 09 09 7d | 0a 58 0a 58 09 20 20 20 |ol;.X..}|.X.X. |
|00005c30| 20 65 6c 73 65 0a 58 09 | 09 2b 2b 68 73 68 73 61 | else.X.|.++hshsa|
|00005c40| 76 65 3b 0a 58 09 20 20 | 20 20 7d 0a 58 0a 58 20 |ve;.X. | }.X.X |
|00005c50| 20 20 20 2f 2a 20 6d 61 | 6b 65 20 61 20 6e 65 77 | /* ma|ke a new|
|00005c60| 20 64 66 61 20 2a 2f 0a | 58 0a 58 20 20 20 20 69 | dfa */.|X.X i|
|00005c70| 66 20 28 20 2b 2b 6c 61 | 73 74 64 66 61 20 3e 3d |f ( ++la|stdfa >=|
|00005c80| 20 63 75 72 72 65 6e 74 | 5f 6d 61 78 5f 64 66 61 | current|_max_dfa|
|00005c90| 73 20 29 0a 58 09 69 6e | 63 72 65 61 73 65 5f 6d |s ).X.in|crease_m|
|00005ca0| 61 78 5f 64 66 61 73 28 | 29 3b 0a 58 0a 58 20 20 |ax_dfas(|);.X.X |
|00005cb0| 20 20 6e 65 77 64 73 20 | 3d 20 6c 61 73 74 64 66 | newds |= lastdf|
|00005cc0| 61 3b 0a 58 0a 58 20 20 | 20 20 64 73 73 5b 6e 65 |a;.X.X | dss[ne|
|00005cd0| 77 64 73 5d 20 3d 20 28 | 69 6e 74 20 2a 29 20 6d |wds] = (|int *) m|
|00005ce0| 61 6c 6c 6f 63 28 20 28 | 75 6e 73 69 67 6e 65 64 |alloc( (|unsigned|
|00005cf0| 29 20 28 28 6e 75 6d 73 | 74 61 74 65 73 20 2b 20 |) ((nums|tates + |
|00005d00| 31 29 20 2a 20 73 69 7a | 65 6f 66 28 20 69 6e 74 |1) * siz|eof( int|
|00005d10| 20 29 29 20 29 3b 0a 58 | 0a 58 20 20 20 20 69 66 | )) );.X|.X if|
|00005d20| 20 28 20 21 20 64 73 73 | 5b 6e 65 77 64 73 5d 20 | ( ! dss|[newds] |
|00005d30| 29 0a 58 09 66 6c 65 78 | 66 61 74 61 6c 28 20 22 |).X.flex|fatal( "|
|00005d40| 64 79 6e 61 6d 69 63 20 | 6d 65 6d 6f 72 79 20 66 |dynamic |memory f|
|00005d50| 61 69 6c 75 72 65 20 69 | 6e 20 73 6e 73 74 6f 64 |ailure i|n snstod|
|00005d60| 73 28 29 22 20 29 3b 0a | 58 0a 58 20 20 20 20 2f |s()" );.|X.X /|
|00005d70| 2a 20 69 66 20 77 65 20 | 68 61 76 65 6e 27 74 20 |* if we |haven't |
|00005d80| 61 6c 72 65 61 64 79 20 | 73 6f 72 74 65 64 20 74 |already |sorted t|
|00005d90| 68 65 20 73 74 61 74 65 | 73 20 69 6e 20 73 6e 73 |he state|s in sns|
|00005da0| 2c 20 77 65 20 64 6f 20 | 73 6f 20 6e 6f 77 2c 20 |, we do |so now, |
|00005db0| 73 6f 20 74 68 61 74 0a | 58 20 20 20 20 20 2a 20 |so that.|X * |
|00005dc0| 66 75 74 75 72 65 20 63 | 6f 6d 70 61 72 69 73 6f |future c|ompariso|
|00005dd0| 6e 73 20 77 69 74 68 20 | 69 74 20 63 61 6e 20 62 |ns with |it can b|
|00005de0| 65 20 6d 61 64 65 20 71 | 75 69 63 6b 6c 79 0a 58 |e made q|uickly.X|
|00005df0| 20 20 20 20 20 2a 2f 0a | 58 0a 58 20 20 20 20 69 | */.|X.X i|
|00005e00| 66 20 28 20 21 20 64 69 | 64 73 6f 72 74 20 29 0a |f ( ! di|dsort ).|
|00005e10| 58 09 62 75 62 62 6c 65 | 28 20 73 6e 73 2c 20 6e |X.bubble|( sns, n|
|00005e20| 75 6d 73 74 61 74 65 73 | 20 29 3b 0a 58 0a 58 20 |umstates| );.X.X |
|00005e30| 20 20 20 66 6f 72 20 28 | 20 69 20 3d 20 31 3b 20 | for (| i = 1; |
|00005e40| 69 20 3c 3d 20 6e 75 6d | 73 74 61 74 65 73 3b 20 |i <= num|states; |
|00005e50| 2b 2b 69 20 29 0a 58 09 | 64 73 73 5b 6e 65 77 64 |++i ).X.|dss[newd|
|00005e60| 73 5d 5b 69 5d 20 3d 20 | 73 6e 73 5b 69 5d 3b 0a |s][i] = |sns[i];.|
|00005e70| 58 0a 58 20 20 20 20 64 | 66 61 73 69 7a 5b 6e 65 |X.X d|fasiz[ne|
|00005e80| 77 64 73 5d 20 3d 20 6e | 75 6d 73 74 61 74 65 73 |wds] = n|umstates|
|00005e90| 3b 0a 58 20 20 20 20 64 | 68 61 73 68 5b 6e 65 77 |;.X d|hash[new|
|00005ea0| 64 73 5d 20 3d 20 68 61 | 73 68 76 61 6c 3b 0a 58 |ds] = ha|shval;.X|
|00005eb0| 0a 58 20 20 20 20 69 66 | 20 28 20 6e 61 63 63 20 |.X if| ( nacc |
|00005ec0| 3d 3d 20 30 20 29 0a 58 | 09 7b 0a 58 09 69 66 20 |== 0 ).X|.{.X.if |
|00005ed0| 28 20 72 65 6a 65 63 74 | 20 29 0a 58 09 20 20 20 |( reject| ).X. |
|00005ee0| 20 64 66 61 61 63 63 5b | 6e 65 77 64 73 5d 2e 64 | dfaacc[|newds].d|
|00005ef0| 66 61 61 63 63 5f 73 65 | 74 20 3d 20 28 69 6e 74 |faacc_se|t = (int|
|00005f00| 20 2a 29 20 30 3b 0a 58 | 09 65 6c 73 65 0a 58 09 | *) 0;.X|.else.X.|
|00005f10| 20 20 20 20 64 66 61 61 | 63 63 5b 6e 65 77 64 73 | dfaa|cc[newds|
|00005f20| 5d 2e 64 66 61 61 63 63 | 5f 73 74 61 74 65 20 3d |].dfaacc|_state =|
|00005f30| 20 30 3b 0a 58 0a 58 09 | 61 63 63 73 69 7a 5b 6e | 0;.X.X.|accsiz[n|
|00005f40| 65 77 64 73 5d 20 3d 20 | 30 3b 0a 58 09 7d 0a 58 |ewds] = |0;.X.}.X|
|00005f50| 0a 58 20 20 20 20 65 6c | 73 65 20 69 66 20 28 20 |.X el|se if ( |
|00005f60| 72 65 6a 65 63 74 20 29 | 0a 58 09 7b 0a 58 09 2f |reject )|.X.{.X./|
|00005f70| 2a 20 77 65 20 73 6f 72 | 74 20 74 68 65 20 61 63 |* we sor|t the ac|
|00005f80| 63 65 70 74 69 6e 67 20 | 73 65 74 20 69 6e 20 69 |cepting |set in i|
|00005f90| 6e 63 72 65 61 73 69 6e | 67 20 6f 72 64 65 72 20 |ncreasin|g order |
|00005fa0| 73 6f 20 74 68 65 20 64 | 69 73 61 6d 62 69 67 75 |so the d|isambigu|
|00005fb0| 61 74 69 6e 67 0a 58 09 | 20 2a 20 72 75 6c 65 20 |ating.X.| * rule |
|00005fc0| 74 68 61 74 20 74 68 65 | 20 66 69 72 73 74 20 72 |that the| first r|
|00005fd0| 75 6c 65 20 6c 69 73 74 | 65 64 20 69 73 20 63 6f |ule list|ed is co|
|00005fe0| 6e 73 69 64 65 72 65 64 | 20 6d 61 74 63 68 20 69 |nsidered| match i|
|00005ff0| 6e 20 74 68 65 20 65 76 | 65 6e 74 20 6f 66 0a 58 |n the ev|ent of.X|
|00006000| 09 20 2a 20 74 69 65 73 | 20 77 69 6c 6c 20 77 6f |. * ties| will wo|
|00006010| 72 6b 2e 20 20 57 65 20 | 75 73 65 20 61 20 62 75 |rk. We |use a bu|
|00006020| 62 62 6c 65 20 73 6f 72 | 74 20 73 69 6e 63 65 20 |bble sor|t since |
|00006030| 74 68 65 20 6c 69 73 74 | 20 69 73 20 70 72 6f 62 |the list| is prob|
|00006040| 61 62 6c 79 0a 58 09 20 | 2a 20 71 75 69 74 65 20 |ably.X. |* quite |
|00006050| 73 6d 61 6c 6c 2e 0a 58 | 09 20 2a 2f 0a 58 0a 58 |small..X|. */.X.X|
|00006060| 09 62 75 62 62 6c 65 28 | 20 61 63 63 73 65 74 2c |.bubble(| accset,|
|00006070| 20 6e 61 63 63 20 29 3b | 0a 58 0a 58 09 64 66 61 | nacc );|.X.X.dfa|
|00006080| 61 63 63 5b 6e 65 77 64 | 73 5d 2e 64 66 61 61 63 |acc[newd|s].dfaac|
|00006090| 63 5f 73 65 74 20 3d 0a | 58 09 20 20 20 20 28 69 |c_set =.|X. (i|
|000060a0| 6e 74 20 2a 29 20 6d 61 | 6c 6c 6f 63 28 20 28 75 |nt *) ma|lloc( (u|
|000060b0| 6e 73 69 67 6e 65 64 29 | 20 28 28 6e 61 63 63 20 |nsigned)| ((nacc |
|000060c0| 2b 20 31 29 20 2a 20 73 | 69 7a 65 6f 66 28 20 69 |+ 1) * s|izeof( i|
|000060d0| 6e 74 20 29 29 20 29 3b | 0a 58 0a 58 09 69 66 20 |nt )) );|.X.X.if |
|000060e0| 28 20 21 20 64 66 61 61 | 63 63 5b 6e 65 77 64 73 |( ! dfaa|cc[newds|
|000060f0| 5d 2e 64 66 61 61 63 63 | 5f 73 65 74 20 29 0a 58 |].dfaacc|_set ).X|
|00006100| 09 20 20 20 20 66 6c 65 | 78 66 61 74 61 6c 28 20 |. fle|xfatal( |
|00006110| 22 64 79 6e 61 6d 69 63 | 20 6d 65 6d 6f 72 79 20 |"dynamic| memory |
|00006120| 66 61 69 6c 75 72 65 20 | 69 6e 20 73 6e 73 74 6f |failure |in snsto|
|00006130| 64 73 28 29 22 20 29 3b | 0a 58 0a 58 09 2f 2a 20 |ds()" );|.X.X./* |
|00006140| 73 61 76 65 20 74 68 65 | 20 61 63 63 65 70 74 69 |save the| accepti|
|00006150| 6e 67 20 73 65 74 20 66 | 6f 72 20 6c 61 74 65 72 |ng set f|or later|
|00006160| 20 2a 2f 0a 58 09 66 6f | 72 20 28 20 69 20 3d 20 | */.X.fo|r ( i = |
|00006170| 31 3b 20 69 20 3c 3d 20 | 6e 61 63 63 3b 20 2b 2b |1; i <= |nacc; ++|
|00006180| 69 20 29 0a 58 09 20 20 | 20 20 64 66 61 61 63 63 |i ).X. | dfaacc|
|00006190| 5b 6e 65 77 64 73 5d 2e | 64 66 61 61 63 63 5f 73 |[newds].|dfaacc_s|
|000061a0| 65 74 5b 69 5d 20 3d 20 | 61 63 63 73 65 74 5b 69 |et[i] = |accset[i|
|000061b0| 5d 3b 0a 58 0a 58 09 61 | 63 63 73 69 7a 5b 6e 65 |];.X.X.a|ccsiz[ne|
|000061c0| 77 64 73 5d 20 3d 20 6e | 61 63 63 3b 0a 58 09 7d |wds] = n|acc;.X.}|
|000061d0| 0a 58 0a 58 20 20 20 20 | 65 6c 73 65 0a 58 09 7b |.X.X |else.X.{|
|000061e0| 20 2f 2a 20 66 69 6e 64 | 20 6c 6f 77 65 73 74 20 | /* find| lowest |
|000061f0| 6e 75 6d 62 65 72 65 64 | 20 72 75 6c 65 20 73 6f |numbered| rule so|
|00006200| 20 74 68 65 20 64 69 73 | 61 6d 62 69 67 75 61 74 | the dis|ambiguat|
|00006210| 69 6e 67 20 72 75 6c 65 | 20 77 69 6c 6c 20 77 6f |ing rule| will wo|
|00006220| 72 6b 20 2a 2f 0a 58 09 | 6a 20 3d 20 6e 75 6d 5f |rk */.X.|j = num_|
|00006230| 72 75 6c 65 73 20 2b 20 | 31 3b 0a 58 0a 58 09 66 |rules + |1;.X.X.f|
|00006240| 6f 72 20 28 20 69 20 3d | 20 31 3b 20 69 20 3c 3d |or ( i =| 1; i <=|
|00006250| 20 6e 61 63 63 3b 20 2b | 2b 69 20 29 0a 58 09 20 | nacc; +|+i ).X. |
|00006260| 20 20 20 69 66 20 28 20 | 61 63 63 73 65 74 5b 69 | if ( |accset[i|
|00006270| 5d 20 3c 20 6a 20 29 0a | 58 09 09 6a 20 3d 20 61 |] < j ).|X..j = a|
|00006280| 63 63 73 65 74 5b 69 5d | 3b 0a 58 0a 58 09 64 66 |ccset[i]|;.X.X.df|
|00006290| 61 61 63 63 5b 6e 65 77 | 64 73 5d 2e 64 66 61 61 |aacc[new|ds].dfaa|
|000062a0| 63 63 5f 73 74 61 74 65 | 20 3d 20 6a 3b 0a 58 09 |cc_state| = j;.X.|
|000062b0| 7d 0a 58 0a 58 20 20 20 | 20 2a 6e 65 77 64 73 5f |}.X.X | *newds_|
|000062c0| 61 64 64 72 20 3d 20 6e | 65 77 64 73 3b 0a 58 0a |addr = n|ewds;.X.|
|000062d0| 58 20 20 20 20 72 65 74 | 75 72 6e 20 28 20 31 20 |X ret|urn ( 1 |
|000062e0| 29 3b 0a 58 20 20 20 20 | 7d 0a 58 0a 58 0a 58 2f |);.X |}.X.X.X/|
|000062f0| 2a 20 73 79 6d 66 6f 6c | 6c 6f 77 73 65 74 20 2d |* symfol|lowset -|
|00006300| 20 66 6f 6c 6c 6f 77 20 | 74 68 65 20 73 79 6d 62 | follow |the symb|
|00006310| 6f 6c 20 74 72 61 6e 73 | 69 74 69 6f 6e 73 20 6f |ol trans|itions o|
|00006320| 6e 65 20 73 74 65 70 0a | 58 20 2a 0a 58 20 2a 20 |ne step.|X *.X * |
|00006330| 73 79 6e 6f 70 73 69 73 | 0a 58 20 2a 20 20 20 20 |synopsis|.X * |
|00006340| 69 6e 74 20 64 73 5b 63 | 75 72 72 65 6e 74 5f 6d |int ds[c|urrent_m|
|00006350| 61 78 5f 64 66 61 5f 73 | 69 7a 65 5d 2c 20 64 73 |ax_dfa_s|ize], ds|
|00006360| 69 7a 65 2c 20 74 72 61 | 6e 73 73 79 6d 3b 0a 58 |ize, tra|nssym;.X|
|00006370| 20 2a 20 20 20 20 69 6e | 74 20 6e 73 65 74 5b 63 | * in|t nset[c|
|00006380| 75 72 72 65 6e 74 5f 6d | 61 78 5f 64 66 61 5f 73 |urrent_m|ax_dfa_s|
|00006390| 69 7a 65 5d 2c 20 6e 75 | 6d 73 74 61 74 65 73 3b |ize], nu|mstates;|
|000063a0| 0a 58 20 2a 20 20 20 20 | 6e 75 6d 73 74 61 74 65 |.X * |numstate|
|000063b0| 73 20 3d 20 73 79 6d 66 | 6f 6c 6c 6f 77 73 65 74 |s = symf|ollowset|
|000063c0| 28 20 64 73 2c 20 64 73 | 69 7a 65 2c 20 74 72 61 |( ds, ds|ize, tra|
|000063d0| 6e 73 73 79 6d 2c 20 6e | 73 65 74 20 29 3b 0a 58 |nssym, n|set );.X|
|000063e0| 20 2a 2f 0a 58 0a 58 69 | 6e 74 20 73 79 6d 66 6f | */.X.Xi|nt symfo|
|000063f0| 6c 6c 6f 77 73 65 74 28 | 20 64 73 2c 20 64 73 69 |llowset(| ds, dsi|
+--------+-------------------------+-------------------------+--------+--------+
Only 25.0 KB of data is shown above.
