Path: csiph.com!weretis.net!feeder6.news.weretis.net!news.misty.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Roger L Costello Newsgroups: comp.compilers Subject: How can the speed of a scanner be independent of the number of rules? Date: Wed, 23 Mar 2022 18:49:39 +0000 Organization: Compilers Central Lines: 24 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <22-03-047@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="39843"; mail-complaints-to="abuse@iecc.com" Keywords: lex, question, comment Posted-Date: 23 Mar 2022 15:24:41 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com Content-Language: en-US Xref: csiph.com comp.compilers:2949 Hi Folks, On page 48 of the Flex manual [1] it says this amazing thing: Note that adding rules does not slow down the scanner! The speed of the scanner is independent of the number of rules or (modulo the considerations given at the beginning of this section) how complicated the rules are with regard to operators such as '*' and '|'. That is amazing! And counterintuitive. How can it possibly be that a scanner containing 1000 rules can operate as fast as a scanner containing 10 rules? Would you give some intuition to help me understand this, please? /Roger [1] https://epaperpress.com/lexandyacc/download/flex.pdf [Flex compiles the rules into a finite state machine. When the scanner runs, it just looks up each character it reads in the table for the current state to decide what to do. Creating the state tables for 1000 rules takes a lot longer than creating the tables for 10 rules, but that just happens once when you build the scanner, not when it's running. For more details on regular expressions and state machines, see any compiler textbook. It's one of the standrd topics. -John]