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

Question

我正在尝试编写一个正则表达式引擎。我想手写递归下降解析器。对于正则表达式语言（不是可以由正则表达式描述的语言），没有左递归的上下文无关文法会是什么样子？最简单的方法是重构语法糖，即将a+改为aa*吗？提前致谢！

- wkf

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

- Markus Jarderot

---

太好了，你今晚回答了我所有的问题。谢谢！ - wkf

Answer 2

你可以查看 Plan 9 grep 的源代码。文件 grep.y 中有一个 yacc（如果我没记错的话是 LALR(1)）语法用于正则表达式。你可以从 yacc 语法开始，并将其重写为递归下降分析。

- user208139

Answer 3

左递归的维基百科文章提供了如何实现这一点的相当不错的信息。

- Mark P Neyer

---

我并不需要重构一个带有左递归的语法，而是试图对语法的一般形式有所了解。虽然我已经阅读了很多关于它们的内容，但我从未真正使用过上下文无关文法。 - wkf