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

Question

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

另请参阅这个问题：哪些编程语言是上下文无关的？.

Answer 1

Brainfuck 和 Whitespace 以及类似的内容肯定是常见的。

另一方面，任何支持（parens）的语言都不是常规的，因为识别它的自动机需要一个堆栈。我真的不知道有多少种语言没有 (){}[] 支持，除了汇编之外还能做任何事情。

唯一想到的现实世界的例子并且可能是常见的是Forth。

Answer 2

答案是肯定的。当然有具有规则语法的编程语言！

A=B 编程语言是一种规则的单指令 esolang。

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

这是匹配任何此类语言的正则表达式：

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

事实上，可以使用常规语言来描述图灵机。 让图灵机的状态称为

a

、

aa

、

aaa

等，其中

a

是初始状态。我们可以如下描述图灵机，假设磁带仅包含

0

和

1

：

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