Las expresiones regulares son todas aquellas que se pueden definir con un autómata finito no determinista (AFND)...
Viendo esto supongo que solo te puede servir un compilador simple como el del lenguaje micro y saber interpretar las BNF sintactica.
¿En serio? ¿Eres universitario y hablas de las Regex como algo... difícil y ...
Lo que tu planteas en realidad son meta expresiones regulares. Lo que el necesita es demostrar el uso de algo mas teorico. Por eso recomiendo un analizador lexico/sintactico.
Define un AFD y despues pasalo a C y listo.
Enviado desde mi LG-E610 mediante Tapatalk