Network Intrusion Detection Systems (NIDS) are deployed to protect computer networks from malicious attacks. Proper evaluation of NIDS requires more scrutiny than the evaluation for general network appliances. This evaluation is commonly performed by sending pre-generated traffic through the NIDS. Unfortunately, this technique is often limited in diversity resulting in evaluations incapable of examining the complex data structures employed by NIDS. More sophisticated methods that generate workload directly from NIDS rules consume excessive resources and are incapable of running in real-time. This work proposes a novel approach to real-time workload generation for NIDS evaluation to improve evaluation diversity while maintaining much higher throughput. This work proposes a generative grammar which represents an optimized version of a context-free grammar derived from the set of strings matching to the given NIDS rule database. The grammar is memory-efficient and computationally light when generating workload. Experiments demonstrate that grammar-generated workloads exert an order of magnitude more effort on the target NIDS. Even better, this improved diversity comes at much smaller cost in memory and speeds four times faster than current approaches.