What is a formal programming language?

programming-languages formal-languages
Orjanp picture Orjanp · Apr 19, 2010 · Viewed 10.6k times · Source

What does it mean that a programming language is a formal programming language? And which languages are formal programming languages? And which are informal programming languages?

I haven't found a good explanation yet.

Answer

zoul picture zoul · Apr 19, 2010

Every programming language is a formal language, so that it does not make much sense to me to speak of a “formal programming language.” (Or does somebody know an informal programming language?)

Formal language is a language with mathematically precise construction rules. Or, more precisely, it’s a set of words over some alphabet. For example, if you take alphabet consisting of the letters a, b and c, a formal language over this alphabet could be a set {a, aa, aba, ca}. Of course such a language would not be very useful – the point is that with a decent set of construction rules you can create a language such as C or PostScript.

As for the “construction rules,” they could be a formal grammar (see grammar for CSS), a regular expression (see this gorgeous regex for e-mail addresses as defined by RFC 822), an automaton or a general algorithm.

If you feel you don’t understand the thing a tiny bit more, do not despair, for this is not a very good explanation :-) There’s a lot of thinking behind the concept of formal languages. I’d suggest that you try and digest the Wikipedia entry and look for more tutorials and books. It’s fun and you will learn a lot about the background of compilers, regular expressions, Turing machines and other wonders of digital mankind.

Related questions

What is a regular language?

I'm trying to understand the concept of languages levels (regular, context free, context sensitive, etc.). I can look this up easily, but all explanations I find are a load of symbols and talk about sets. I have two questions: Can …

Read More
Why do we need prefix, postfix notation

I know how each of them can be converted to one another but never really understood what their applications are. The usual infix operation is quite readable, but where does it fail which led to inception of prefix and postfix …

Read More
Strangest language feature

What is, in your opinion, the most surprising, weird, strange or really "WTF" language feature you have encountered? Please only one feature per answer.

Read More