Grammatica context-free che descrive le espressioni regolari?

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!Grammatica context-free che descrive le espressioni regolari?

fonte

2009-06-10 wkf

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> 
     ;

fonte

2009-06-11 02:23:35

Proprio sull'uomo; hai risposto a tutte le mie domande questa sera. Grazie! – wkf

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

fonte

2009-06-10 20:55:55

Non è che ho bisogno di ridimensionare una grammatica con ricorsione a sinistra, ma piuttosto che sto cercando di capire come dovrebbe essere la grammatica in generale. Mentre ho letto molto su di loro, in realtà non ho mai usato una grammatica context-free 'in the wild', per così dire. – wkf

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.

fonte

2011-01-03 18:39:24

Grammatica context-free che descrive le espressioni regolari?

risposta

Problemi correlati