8

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,618
  • 12
  • 60
  • 107

1 Answers1

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
  • 291,719
  • 55
  • 540
  • 600
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