9

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?.

Community
  • 1
  • 1
Giovanni Funchal
  • 8,934
  • 13
  • 61
  • 110

2 Answers2

8

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.

Joachim Sauer
  • 302,674
  • 57
  • 556
  • 614
Mirek Kratochvil
  • 742
  • 6
  • 3
  • FYI your comment on (parens) is incorrect. Old Fortran had parens .. but with a limit of 3 deep. – Yttrill Dec 24 '11 at 04:51
  • 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. – ashgromnies Mar 09 '16 at 01:48
  • 3
    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. – Palle Aug 11 '17 at 09:32
  • @Palle 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. – KeksArmee Jan 30 '18 at 15:03
  • 3
    @KeksArmee 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. – Palle Jan 30 '18 at 18:41
0

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+)*
Zhang Ruichong
  • 1
  • 2