Grammatica context-free che descrive le espressioni regolari?

Question

Sto provando a scrivere un motore di espressioni regolari. Mi piacerebbe scrivere un parser di discesa ricorsivo a mano. Come sarebbe una grammatica senza contesto senza ricorsione a sinistra per il linguaggio delle espressioni regolari (non le lingue che possono essere descritte dalle espressioni regolari)? Sarebbe più semplice ri-calcolare lo zucchero sintattico, cioè cambiare a+ a aa*? Grazie in anticipo!

Answer 1

ricorsione sinistra:

Expression = Expression '|' Sequence 
      | Sequence 
      ; 

Sequence = Sequence Repetition 
     | <empty> 
     ; 

ricorsione a destra:

Expression = Sequence '|' Expression 
      | Sequence 
      ; 

Sequence = Repetition Sequence 
     | <empty> 
     ; 

forma ambigua:

Expression = Expression '|' Expression 
      | Sequence 
      ; 

Sequence = Sequence Sequence 
     | Repetition 
     | <empty> 
     ; 

Answer 2

L'articolo di Wikipedia su Left Recursion fornisce informazioni piuttosto buone su come estrarlo.

Answer 3

Si potrebbe guardare il source code for Plan 9 grep. Il file grep.y ha una grammatica yacc (LALR (1) se ricordo correttamente) per le espressioni regolari. Potresti essere in grado di iniziare dalla grammatica yacc e riscriverlo per l'analisi della discesa ricorsiva.