Which programming languages have a regular grammar?

Question

I'm curious about which (if any) real-world programming languages have a regular grammar (i.e. the set of all syntactically correct programs is regular).

See also this question: What programming languages are context-free?.

Pelpel

As a practical matter, none of them. – Ava

Answer 1

Brainfuck and Whitespace and similars are certainly regular.

On the other side, any language that supports (parens) is not regular, as the automaton recognizing it would need a stack. And I don't really know many languages without (){}[] support that would do anything more than assembly.

Only real-worldy example that comes to mind and probably is regular is Forth.

Lettielettish

FYI your comment on (parens) is incorrect. Old Fortran had parens .. but with a limit of 3 deep. – Xenophanes

What is the relevance of regular languages in modern computing? Intuitively I would imagine that to implement something on circuits it would need to be a regular language, and machine code syntax seems like it would be regular. Is there any time in software that regular languages are useful? It seems I hardly ever use strict regular languages -- PCRE has "regular expression" in its name but isn't even strictly regular if I understand correctly. – Lothario

Brainfuck is not a regular language, as it allows nested loops where [ marks the beginning of a loop and ] marks the end. As these must match, brainfuck is not regular. – Shufu

@Shufu Depending on the implementation, brainfuck can be regular or not. You parse them as while{} statements or as push [ and pop+jmp/ret ] instructions. Technically, there is no need for the bracket count to match. – Mathematician

@Mathematician You are mixing up translation with actual parsing. Of course you can translate brainfuck to C using just simple replacement operations but to actually parse correct brainfuck, you need a parser that can handle at least context free grammars. You cannot express the set of all syntactically correct brainfuck programs using a regular grammar. – Shufu

Answer 2

The answer is YES. There are certainly programming languages with regular grammar!

The A=B programming language is a one instruction esolang which is regular.

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

Here is the regular expression that matches any such language:

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

In fact, it is possible to describe a Turing machine using regular language. Let the states of the Turing machine be called a, aa, aaa, etc, where a is the initial state. we can describe a Turing machine as follows, assuming the tape only contains 0, 1 and 2, where 0 is the blank symbol:

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

Deandreadeane