I think if schools want to give a taste of the parsing->execution flow, they should have students implement an NFA based regular expression engine. No fancy features like captures and named character classes, just the primitive operations will do.

Regular expression syntax is context-free anyways, so they could use grammars if they wanted. Then again, you have to wonder if all of this should be covered by a theory or PL class instead.