In a nutshell
Programming languages are composed of a syntax that represent the
program as strings of characters, and a semantics that is the intended
meaning of the program.
Formal languages are syntax without meaning. It is meant to study the
structure of sets of strings defined formally, without usually
attaching meaning to those strings.
Regular expression and other formalisms (such as Context-Free Grammars) are used to define formal languages, used as
syntactic component of programming and natural languages, i.e. to
represent sentences in a structured way. Other mechanisms are used to
relate that structure with the semantics of the programming languages.
Much here is considerably simplified, particularly regarding natural language.
With a lot more details
To answer your question we should start from the beginning. A language
in the usual sense is, informally, a means to convey information or
ideas. In a language, one usually distinguishes between syntax and
semantics. Semantics is what you want to talk/write about. the
information you want to convey. Syntax is the means you use to convey
it, i.e. a conventional representation that can be exchanged between
people, and now also between people and devices, or between devices
(computers).
Typically, you will use the word dog to convey the idea of a
dog. The word dog is made of three letters, or some equivalent
sound, and is intended to be the representation of some kind of
animal. The key idea is that communication is done through
representation of what is to be communicated. Representation
structures are usually called syntax, while what is represented is
called semantics. This goes more or less for natural language as well
as for programming languages.
Words are syntactic entities to represent more or less elementary
semantic concepts. But these elementary concepts have to be put
together in a variety of ways to give more complex meaning. We write
the dog to convey that we mean a specific dog, and the dog bites the cat to convey a more complex idea. But the way the words are
organized has to be fixed by rules, so that we can tell which of the
dog and the cat is actually biting the other.
So we have rules such as sentence -> subject verb complement that
are supposed to match sentences and tell us how the ideas associated
with each part are articulated. These rules are syntactic rules, since
they tell us how the representation of our message is to be organized.
The subject can itself be defined by a rule subject -> article noun, and so on.
The same is true in mathematics. You have mathematical expression
written with a very formal syntax. and the meaning of the expression
can be obtained by analyzing the syntactic structure. For example
$2x+1=23$, depending on context, may be read as an equation, stating
that if you take the double of $x$ and add $1$, it should be the same
as $23$. Some of the rules are:
equation -> expression "=" expression
expression -> expression "+" expression
expression -> number
The structure of programming languages is the same. Programming
languages are semantically specialized in expressing computations to
be performed, rather than expressing problems to be solved, proof of
theorems or friendly relations between animal. But that is the main
difference.
Representations used in syntax are usually strings of
characters, or of sounds for spoken languages. Semantics usually
belong to abstract domain, or possibly to reality, but still
abstracted in our thought processes, or to the behavioral domain of
devices. Communication entails encoding the information/idea into
syntax, which is transmitted and decoded by the receiver. The result
in then interpreted in whatever way by the receiver.
So what we see of the language is mostly syntax and its structure. The
example above are only one of the most common way to define syntactic
strings and their structural organization. There are others. For
a given language, some strings can be assigned a structure, and are
said to belong to the language, while others do not.
The same is true for words. Some sequences of letters (or sound) are
legitimate words, while other are not.
Formal languages are just syntax without semantics. They define with a
set of rule what sequences can be constructed, using the basic
elements of an alphabet. What the rules are can be very variable,
sometimes complex. But formal languages are used for many
mathematical purposes beyond linguistic communication, whether for
natural of for programming languages. The set of rules that define the
strings in a language is called a grammar. But there are many other
way to define languages.
In practice, a language is structured in two levels. The lexical level
defines words constructed from an alphabet of characters. The
syntactic level defines sentences, or programs constructed from an
alphabet of words (or more precisely of word families, so that it
remain a finite alphabet). This is necessarily somewhat simplified.
The structure of words is fairly simple in most language (programming
or natural) so that they are usually defined with what is usually
considered the simplest kind of formal language: the regular
languages. They can be defined with regular expressions (regexp), and are
fairly easily identified with programmed devices called finite state
automata. In the cases of programming languages, examples of a word are
an identifier, an integer, string, a real number, a reserved word such as if
or repeat, a punctuation symbol or an open parenthesis. Examples of
word families are identifier, string, integer.
The syntactic level is usually defined by a slightly more complex type
of formal language: the context-free languages, using the words as
alphabet. The rules we have seen above are context-free rules for
natural language. In the case of programming languages rules can be:
statement -> assignment
statement -> loop
loop -> "while" expression "do" statement
assignment -> "identifier" "=" expression
expression -> "identifier"
expression -> "integer"
expression -> expression "operator" expression
With such rules you can write:
while aaa /= bbb do aaa = aaa + bbb / 6 which is a statement.
And the way it was produced can be represented by a tree structure
called a parse tree or syntax tree (not complete here):
statement
|
_______________ loop _______________
/ / \ \
"while" expression "do" statement
__________|_________ |
/ | \ assignment
expression "operator" expression _______|_______
| | | / | \
"identifier" "/=" "identifier" "identifier" "=" expression
| | | |
aaa bbb aaa ... ...
The names appearing on the left of a rule are called non-terminals,
while the words are called also terminals, as they are in the alphabet
for the language (above the lexical level).
Non-terminal represent the different syntactic structures, that can be
used to compose a program.
Such rules are called context-free, because a non-terminal can
be replaced arbitrarily using any of the corresponding rules,
independently of the context in which it appears. The set of rules
defining the language is called a context-free grammar.
Actually there are restrictions on that, when identifiers have to be
first declared, or when an expression must satisfy type restrictions.
But such restriction may be considered as semantical, rather than
syntactical. Actually some professionals place them in what they call
static semantics.
Given any sentence, any program, the meaning of that sentence is
extracted by analyzing the structure given by the parse tree for this
sentence. Hence it is very important to develop algorithms, called
parsers, that can recover the tree structure corresponding to a
program, when given the program.
The parser is preceded by the lexical analyzer that recognize words,
and determine the family they belong to. Then the sequence of words,
or lexical elements, is given to the parser that retrieves the
underlying tree structure. From this structure the compiler can then
determine how to generate code, which his the semantic part of the
program processing on the compiler side.
The parser of a compiler can actually build a data structure
corresponding to the parse-tree and pass it to the later stages of the
compiling process, but it does not have to. Running the parsing
algorithm amount to developing a computational strategy to explore the
syntax-tree that is implicit in the program text. This syntax/parse
tree may or may not be explicited in the process, depending on
compilation strategy (number of stages). What is necessary though is
that there is ultimately at least one bottom-up exploration of the
parse-tree, whether explicited or left implicit in the computation
structure.
The reason for that, intuitively, is that a standard formal way to
define semantics associated to a syntactic tree structure is by means
of what is called a homomorphism. Do not fear the big word. The idea
is just to consider the the meaning of the whole is constructed from
the meaning of the parts, on the basis of the operator that connects
them
For example, the sentence the dog bites the cat can be analyzed with
the rule sentence -> subject verb complement. Knowing the meaning of
the 3 subtrees subject, verb, and complement, the rule that
composes them tells us that the subject is doing the action, and that
the cat is the one who is bitten.
This is only an intuitive explanation, but it can be formalized.
Semantics is constructed upward from the constituents. But this hides
a lot of complexity.
The internal working of a compiler can be decomposed into several
stages. The actual compiler may works stage by stages, using
intermediate representations. It may also merge some stages. This
depend on the technology used and on the complexity of the compiling
the language at hand.
