描述正則表達式的上下文無關文法？

Question

我想寫一個正則表達式引擎。我想用手寫一個遞歸下降解析器。對於正則表達式的語言（而不是正則表達式可以描述的語言）而言，無上下文遞歸的上下文無關文法是什麼樣的？重新分解語法糖是否最容易，即將a+更改爲aa*？提前致謝！

Answer 1

左遞歸：

Expression = Expression '|' Sequence 
      | Sequence 
      ; 

Sequence = Sequence Repetition 
     | <empty> 
     ; 

右遞歸：

Expression = Sequence '|' Expression 
      | Sequence 
      ; 

Sequence = Repetition Sequence 
     | <empty> 
     ; 

曖昧形式：

Expression = Expression '|' Expression 
      | Sequence 
      ; 

Sequence = Sequence Sequence 
     | Repetition 
     | <empty> 
     ; 

Answer 2

關於Left Recursion的維基百科文章給出了關於如何將其關閉的很好的信息。

Answer 3

你可以看看source code for Plan 9 grep。 grep.y文件有一個yacc（如果我正確記得，LALR（1））正則表達式的文法。您可能可以從yacc語法開始，並將其重寫爲遞歸下降解析。