Gramática sin contexto que describe expresiones regulares?

Question

Estoy tratando de escribir un motor de expresiones regulares. Me gustaría escribir un analizador de descenso recursivo a mano. ¿Qué aspecto tendría una gramática sin contexto sin recurrencia para el lenguaje de expresiones regulares (no los lenguajes que pueden describirse mediante expresiones regulares)? ¿Sería más fácil volver a factorizar el azúcar sintáctico, es decir, cambiar a+ a aa*? ¡Gracias por adelantado!

Answer 1

recursividad Izquierda:

Expression = Expression '|' Sequence 
      | Sequence 
      ; 

Sequence = Sequence Repetition 
     | <empty> 
     ; 

recursividad Derecha:

Expression = Sequence '|' Expression 
      | Sequence 
      ; 

Sequence = Repetition Sequence 
     | <empty> 
     ; 

ambiguo formulario:

Expression = Expression '|' Expression 
      | Sequence 
      ; 

Sequence = Sequence Sequence 
     | Repetition 
     | <empty> 
     ; 

Answer 2

El artículo de la wikipedia en Left Recursion da bastante buena información sobre cómo llevarlo a cabo.

Answer 3

Se podría buscar en el source code for Plan 9 grep. El archivo grep.y tiene una gramática yacc (LALR (1) si recuerdo correctamente) para expresiones regulares. Es posible que pueda comenzar desde la gramática de yacc y volver a escribirla para el análisis de descenso recursivo.