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

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

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