哪些编程语言具有正则文法？

Question

我很好奇哪些（如果有的话）现实中的编程语言具有正则文法（即所有语法正确的程序集合是正则的）。

另请参见这个问题：哪些编程语言是上下文无关文法？。

- Giovanni Funchal

---

作为实际问题，它们中没有一个。 - Ira Baxter

Answer 1

Brainfuck和Whitespace等类似语言是确定性的。

另一方面，任何支持(括号)的语言都不是确定性的，因为识别它的自动机需要一个堆栈。而且我并不知道有多少不支持(){}[]的语言可以做更多的事情，除了汇编语言。

唯一能想到的现实例子并且可能是确定性的是Forth。

- Mirek Kratochvil

---

提醒您，您关于括号的评论是不正确的。旧版Fortran使用了括号，但是仅限于三层嵌套。 - Yttrill

正则语言在现代计算中的相关性是什么？直觉上，我想实现电路上的某些东西需要使用正则语言，并且机器码语法似乎也是正则的。在软件开发中有没有使用正则语言的情况？似乎我很少使用严格的正则语言 - 如果我理解正确，PCRE在其名称中具有“正则表达式”，但甚至不是严格的正则表达式。 - ashgromnies

Brainfuck 不是一种正则语言，因为它允许嵌套循环，其中 [ 表示循环的开始，] 表示循环的结束。由于这些符号必须匹配，所以 Brainfuck 不是正则语言。 - Palle

@Palle 根据实现方式，brainfuck 可能是正则的或者不是。你可以将它们解析为 while{} 语句或者推入 [ 和弹出+jmp/ret ] 指令。从技术上讲，括号计数没有必要匹配。 - KeksArmee

您混淆了翻译和实际解析。当然，您可以使用简单的替换操作将brainfuck翻译为C，但要正确解析brainfuck，您需要一个至少可以处理上下文无关文法的解析器。您不能使用正则文法表示所有语法上正确的brainfuck程序集合。 - Palle

Answer 2

答案是肯定的。确实有具有正则语法的编程语言！

A=B编程语言是一种只有一条指令的esolang，它是正则的。

https://esolangs.org/wiki/A%3DB

这是一个匹配任何这种语言的正则表达式。

((\(once\))?([^=()]+|\(start\)[^=()]+|\(end\)[^=()]+)=([^=()]*|\(start\)[^=()]*|\(end\)[^=()]*|\(return\)[^=()]*))*

事实上，可以使用常规语言来描述图灵机。假设图灵机的状态被称为a、aa、aaa等等，其中a是初始状态。我们可以如下描述一个图灵机，假设纸带上只包含0、1和2，其中0是空白符号：

([012]a+=[012][lr]a+)*

- Zhang Ruichong