
Preston Briggs pointed out to us that perfect hashing [248] for reserved words (also called keywords) can have a negative impact on scanner performance unless the table lookup knows that it uses a perfect hash. His argument is simple; if the scanner uses a perfect hash table to identify reserved words, then the failure mechanism in the perfect hash lookup is invoked for every identifier. (Presumably, identifiers are not reserved words.) In the worst case (an open addressing table that is full), the cost of these failures can be linear in the number of reserved words. Adding that cost to each lookup on an identifier could significantly increase the cost for those words.
The FORTRAN code in Figure 2.14 is taken from a talk given by F.K. Zadeck while he was a graduate student.
A more reasonable question might be: An alternate definition of reducibility is: "in a reducible graph, any stronglyconnected component (SCC) contains one node, h that dominates all other nodes in the SCC." Prove that this definition of reducibility is equivalent to the definition based on the transformations T1 and T2 in Section 9.4.1.