regex - 描述正则表达式的上下文无关语法？

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

您可以查看Plan 9 grep 的源代码。文件 grep.y 有一个正则表达式的 yacc（如果我没记错的话是 LALR(1)）语法。您也许可以从 yacc 语法开始，并重写它以进行递归下降解析。

Answer 3

关于左递归的维基百科文章提供了关于如何实现这一点的非常好的信息。