Itamar Turner-Trauring itamarst

## shift_dfa.md

      
        
          
            
              
              1 file
            
          
          
            
              
              4 forks
            
          
          
            
              
              6 comments
            
          
          
            
              
              93 stars
            
          
        
        
          
              
          
          
            
                pervognsen
                / shift_dfa.md
            
            
              Last active
              January 27, 2024 19:54
            
              
                Shift-based DFAs
              
          
        
      
        
  
      
    A traditional table-based DFA implementation looks like this:
uint8_t table[NUM_STATES][256]

uint8_t run(const uint8_t *start, const uint8_t *end, uint8_t state) {
    for (const uint8_t *s = start; s != end; s++)
        state = table[state][*s];
    return state;
}