23
$\begingroup$

I've looked around the net for an answer to this question and it seems as if everybody implicitly knows the answer except me. Presumably this is because the only people who care are those who have had tertiary education on the subject. I, on the other hand, have been thrown in the deep end for a high school assignment.

My question is, how exactly are programming languages related to formal languages? Everywhere I read, something along the lines of "formal languages are used for defining the grammar of programming languages" is said.

Now from what I've been able to gather, a formal language is a series of production rules that apply to a specific set of symbols (the language's alphabet). These production rules define a set of transformations, such as:

b -> a

aaa->c

This can be applied such that:

abab->aaaa aaaa-> ca

Just as a side note, if we define that our formal language's alphabet as {a,b,c}, then a and b are non terminals and c is terminal as it can not be transformed (please correct me if I'm wrong about that).

So given all that, how on earth does this apply to programming languages? Often it is also stated that regex is used to parse a language in it's text form to ensure the grammar is correct. This makes sense. Then it is stated that regex are defined by formal languages. Regex return true or false (in my experience at least) depending on if the finite state automata that represents the regex reaches the goal point. As far as I can see, that has nothing to do with transformations*.

For the compiling of the program itself, I suppose a formal language would be able to transform code into consecutively lower level code, eventually reaching assembly via a complex set of rules, which the hardware could then understand.

So that's things from my confused point of view. There's probably a lot of things fundamentally wrong with what I have said, and that is why I'm asking for help.


*Unless you consider something like (a|b)*b*c->true to be a production rule, in which case the rule requires a finite state automata (ie: regex). This makes no sense as we just said that

$\endgroup$
  • 2
    $\begingroup$ You are confising formal grammars with formal languages. A grammar is a set of rewrite rules that describes a language. The language is the set of strings described by the grammar. So a grammar is an alternative to a regular expression: it is a way to describe a language. $\endgroup$ – reinierpost Oct 6 '14 at 16:29
  • $\begingroup$ @reinierpost You are completely right, after looking through the university lecture notes I got some of this information from, I see my mistake. $\endgroup$ – Zwander Oct 7 '14 at 4:40
  • $\begingroup$ I shared your confusion when I started out. Of course, grammars form a language too, and so do regular expressions. But formal language theory is devoted to studying how the syntax (form) of languages can be described, so it usually uses the term 'language' for what is being described, not what is describing it. $\endgroup$ – reinierpost Oct 7 '14 at 6:28
24
$\begingroup$

Whoever told you that regular expressions are used to parse code was spreading disinformation. Classically (I don't know to what extent this is true in modern compilers), the parsing of code – conversion of code from text to a syntax tree – is composed of two stages:

  1. Lexical analysis: Processes the raw text into chunks such as keywords, numerical constants, strings, identifiers and so on. This is classically implemented using some sort of finite state machine, similar in spirit to a deterministic finite automaton (DFA).

  2. Parser: Run after lexical analysis, and converts the raw text into an annotated syntax tree. The grammar of programming languages is (to first approximation) context-free (actually, one needs an even stricter subset), and this allows certain efficient algorithms to parse the lexified code into a syntax tree. This is similar to the problem of recognizing whether a given string belongs to some context-free grammar, the difference being that we also want the proof in the form of a syntax tree.

Grammars for programming languages are written as context-free grammars, and this representation is used by parser generators to construct fast parsers for them. A simple example would have some non-terminal STATEMENT and then rules of the form STATEMENT$\to$IF-STATEMENT, where IF-STATEMENT$\to$if CONDITION then BLOCK endif, or the like (where BLOCK$\to$STATEMENT|BLOCK;STATEMENT, for example). Usually these grammars are specified in Backus-Naur form (BNF).

The actual specifications of programming languages are not context-free. For example, a variable cannot appear if it hadn't been declared in many languages, and languages with strict typing might not allow you to assign an integer to a string variable. The parser's job is only to convert the raw code into a form which is easier to process.

I should mention that there are other approaches such as recursive descent parsing which doesn't actually generate a parse tree, but processes your code as it parses it. Although it doesn't bother to generate the tree, in all other respects it operates at the same level as described above.

$\endgroup$
  • $\begingroup$ Thank you for your reply, it certainly cleared a few things up. It also brought on a whole lot more questions. Should I append them to my question, or ask them here? $\endgroup$ – Zwander Oct 6 '14 at 3:22
  • 5
    $\begingroup$ @Zwander -- actually, neither. On this site, we want you to write one question per question. It's not a discussion forum: it's a question-and-answer site, and we want each question to be in a separate thread. If this answer raises a new question, then spend some time researching that follow-up question, and if you can't find an answer in any of the standard sources, post a new question. (But do make sure to look at standard resources first.) $\endgroup$ – D.W. Oct 6 '14 at 4:23
  • 1
    $\begingroup$ @D.W. Gotcha, cheers. $\endgroup$ – Zwander Oct 6 '14 at 4:46
  • 3
    $\begingroup$ The first of the two stages that you mention is usually done using regular expressions. The format of each token is usually given by a regular expression. Those regular expression are compiled into a single DFA, the DFA is then applied to the actual code. $\endgroup$ – kasperd Oct 6 '14 at 9:12
  • 2
    $\begingroup$ @Zwander Recursive descent parsing is just one parsing technique. It may or may not generate a parse-tree. In general, parsing algorithm amount to developing a computational strategy to explore the syntax-tree 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. $\endgroup$ – babou Oct 6 '14 at 12:33
12
$\begingroup$

This is some heavy stuff for a high school assignment.

Yuval Filmus's answer is really good, so this is more of a supplementary answer to clarify some of the points he made.

A formal language is a mathematical construction. Their use for programming languages is just one of many possible uses; in fact, linguist Noam Chomsky made significant contributions to the early theory of formal languages. He invented the Chomsky Hierarchy, which classifies formal languages into regular, context-free, etc. Formal languages are also applied in linguistics to describe the syntax of natural languages like English. Think of it like the real numbers: we can use the real numbers to describe both concrete things like the distance from Los Angeles to New York, and abstract things like the ratio of a circle's circumference to its diameter. Even though both of those things exist independently of the real numbers, the real numbers are a helpful system for describing them. Formal languages are a helpful system for describing both English and Python, because both have a similar structured format.

Formal languages are just manipulations of symbols; they don't say anything about what the symbols mean. Think of an algebra problem like $a + b + c = d$. That equation has no inherent meaning, but we can still manipulate the symbols according to the rules of algebra; for example, we can rewrite it as $a + b = d - c$, even though we have no idea what the symbols mean. A way of giving meaning to the symbols within a system is called the semantics (in both natural and programming languages). So we could interpret $a$, $b$, and $c$ as dollar amounts, for example, and then the equation has meaning.

Classically, a programming language will have two grammars: a lexical grammar and a syntactic grammar. The lexical grammar deals with characters such as letters, semicolons, braces, and parentheses. It's usually a regular grammar, so it can be expressed with regular expressions or a DFA or NFA. (There are proofs in formal language theory showing the three are equivalent in power—meaning they accept the same set of languages.) The lexing phase of the compiler or interpreter is sort of a mini interpreter for the regular language grammar. It reads the rules of the grammar, and following those rules, it lumps up individual characters into tokens. For example, if the language has an if statement that looks more or less like C's, the lexer might lump the characters i and f into the single token IF, then look for an opening parenthesis and output a token OPEN_PAREN, then handle whatever's between the parentheses, and then find the closing parenthesis and output a CLOSE_PAREN. When the lexer's done making tokens, it hands them over the parser, which determines if the tokens actually form valid statements of the programming language. So if you write ip a == b in Python, the lexer just does its best to guess what kind of token ip is (probably it would be taken for an identifier by most lexers), and passes it to the parser, which complains because you can't have an identifier in that position.

The parser implements the syntactic grammar, which is usually context-free, although as Yuval's answer mentions, most programming languages nowadays actually don't use the full abilities of context-free grammars to make parsing simpler and more efficient. Here's Python's syntactic grammar, written in a variant of Backus-Naur form, which is a slight variant of the $a \rightarrow b$ format in the OP. The Java language specification also has examples of Java's lexical and syntactic grammars.

Let's look at the grammar rules for Python's if statement. This is the rule:

if_stmt: 'if' test ':' suite ('elif' test ':' suite)* ['else' ':' suite]

That rule tells us how the parser will figure out if a string of tokens sent from the lexer is an if-statement. Any word in single quotes needs to appear, just like that, in the source code, so the parser will look for the plain word if. The parser will then try to match some tokens to the rule for test:

test: or_test ['if' or_test 'else' test] | lambdef

test is defined in terms of other rules in the grammar. Notice how test also includes itself in its definition; that's called a recursive definition. It's the big power of context-free languages that regular languages don't have, and it allows things like nested loops to be defined for programming language syntax.

If the parser manages to match some tokens to test, it will try to match a colon. If that succeeds, it will try to match some more tokens using the rule for suite. The section ('elif' test ':' suite)* means that we can have any number of repetitions of the literal text elif, followed by something that matches test, followed by a colon, followed by something that matches suite. We can also have zero repetitions; the asterisk at the end means "zero or as many as we want".

At the very end is ['else' ':' suite]. That part's enclosed in square brackets; that means we can have zero or one, but no more. To match this, the parser needs to match the literal text else, a colon, and then a suite. Here's the rule for a suite:

suite: simple_stmt | NEWLINE INDENT stmt+ DEDENT

It's basically a block in C-like languages. Since Python uses newlines and indentation to mean things, the lexer outputs NEWLINE, INDENT, and DEDENT tokens to tell the parser where a new line started, where the code started to be indented, and where it was returned to the outer level of indentation.

If any of these match attempts fail, the parser flags an error and stops. If the parsing of the whole program succeeds, the parser will usually have built a parse tree as Yuval covered in his answer, and possibly a symbol table and other data structures that store semantic information. If the language is statically typed, the compiler will walk the parse tree and look for type errors. It also walks the parse tree to generate low-level code (assembly language, Java bytecode, .Net Intermediate Language, or something similar) which is what actually runs.

As an exercise, I'd recommend taking the grammar of some programming language you're familiar with (again, Python, Java, and here's C#, Javascript, C) and try to hand-parse something simple, like maybe x = a + b; or if (True): print("Yay!"). If you're looking for something simpler, there's also a nice grammar for JSON, which basically covers just the syntax for object literals in Javascript (like {'a': 1, 'b': 2}). Good luck, this is brain-bending stuff but it turns out to be really interesting when you're not on some crazy deadline.

$\endgroup$
  • $\begingroup$ I know I'm not supposed to post "thanks" here, but cheers for taking the time to explain all of this. "This is some heavy stuff for a high school assignment." The intention of the assignment is to skim over the top and talk about regular expressions, but as an avid computer science student I wanted to get the whole picture. The whole topic is fascinating. $\endgroup$ – Zwander Oct 6 '14 at 7:57
  • 1
    $\begingroup$ @Zwander I just graduated college, and most of my electives were stuff like this. I remember being totally confused and yet totally absorbed. You might also like the papers on compiler design mentioned in this blog, or the books Introduction to the Theory of Computation, by Michael Sipser, and John C. Martin, Introduction to Languages and the Theory of Computation. You can find cheap used copies on Amazon. Both make formal language theory about as simple as it's gonna get. $\endgroup$ – tsleyson Oct 6 '14 at 8:12
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Awesome, very helpful. I understand that regex is used in the tokenization process (for example a string literal can be defined by "[^"]*" in its simplest form, ignoring escape chars etc), but is it also used in creating the syntax tree (Talking in terms of programming languages)? I presume not, as a finite state automata is, by definition finite. A syntax tree, even for a single if statement, can be theoretically infinite due to nesting. Therefore regex, being a a finite state automata can not be used for the purpose of generating a syntax tree. $\endgroup$ – Zwander Oct 7 '14 at 5:09
  • $\begingroup$ @Zwander thx 4 editing- Your example of regex is correct (I should have given some examples). BTW, Regex is also a language, with its own semantics in the world of sets of strings, and with a Context-Free (CF) syntax. It is used only for tokenisation of language string, at least for programming languages, not usually in defining the larger syntax used for the syntax trees, except as short hand in Extended BNF (EBNF). Adding Regex in some form to more complex formalisms does not change their expressive power in most cases. Your remarks about infinity are not quite correct. See next comment. $\endgroup$ – babou Oct 7 '14 at 8:03
  • $\begingroup$ @Zwander All formalisms (formal languages) are finitely described. That is a fundamental hypothesis. Even if you are interested in, say, CF grammar with an infinite number of rules, you have to give a finite description of that infinity of rules. Also infinity plays tricks on you (no space for that). An if statement is unbounded (arbitrarily large) but always finite. A finitely defined infinite if is a while. The difference between CF and regular is that CF controls/allows nesting (i.e. parenthetization) while regular does not. But both are finitely described and allow unbounded strings. $\endgroup$ – babou Oct 7 '14 at 8:18
  • 1
    $\begingroup$ @Zwander The formalism must be able to represent any well formed sentence (program), but only well formed sentences. To put it (too) simply, FSA cannot count unboundedly. So they cannot know how many parentheses have been opened that should be closed, or nest properly two different kinds of parentheses. Many linguistic structures have "hidden" parentheses. It is not simply a matter of syntax checking, but mainly implies that the appropriate tree structure cannot be expressed and built, from which to derive the semantics. Recovering some adequate tree structure requires doing the counting. $\endgroup$ – babou Oct 7 '14 at 9:33
  • 1
    $\begingroup$ @Zwander One remark that may be later useful to you is that trees can be linearized simply as string using parentheses. That is typically what you do when you fully parenthesize an arithmetic expression such as $(((A-B)+3)\times C)$ to make sure that each operator get the proper subtree (subexpression). There is a close relationship between pashdown stacks (see pushdown automata), context-free languages, and trees. $\endgroup$ – babou Oct 7 '14 at 10:58
2
$\begingroup$

A formal language is a set of words - where a word is a string of symbols from some alphabet.

This means that your coupling of the production rules and the formal language is too strong. It's not correct that the formal language is the production rules. Rather the production rules define the formal language. The formal language is the words that can be produced by the production rule. (This requires that the formal language is of the sort that can be defined by production rules, e.g. regular languages can be defined by a context free grammar)

So the regular language corresponding to the expression (a|b)*c*d is defined by the production rules;

S->ACd
A->
A->aA
A->bA
C->
C->cC

The words that these production rules generate from the starting symbol S is precisily those strings that the regular expression accepts.

$\endgroup$
2
$\begingroup$

There are significant differences. Chief among them, I would say, is that parsing real programming languages is all about handling syntax errors. With a formal language you'd just say "well it's not in the language", but a compiler that says that is not very useful - it should tell you what's wrong, and if it was a small error, ideally keep parsing so it can report more errors. A lot of research (and implementation effort) goes into that. So really you don't even care that much about the true/false result, you just want to analyse the structure of the input. Formal languages are used as a tool there, and there's a lot of overlap, but you're really solving a different problem.

Also, in most languages it has been chosen to not enforce certain things in the grammar, for example the example you mentioned, "a variable cannot appear if it hadn't been declared". That's typically a thing that would be completely ignored by the parser, and then caught in a separate analysis (semantic analysis) that looks at that sort of thing and isn't affected by considerations such as context-freeness. But not always - for example to parse C, the lexer hack is often used, and C++ is a famous example of a language that can not be parsed without simultaneously doing some serious semantic analysis (actually parsing C++ is undecidable, because templates are Turing complete). In simpler languages it tends to be split though, it's easier that way.

$\endgroup$
0
$\begingroup$

There is another relationship between regular expressions and programming languages which is to do with semantics. The basic control constructs of an imperative language are sequential composition (do A and then B), choice (do A or B), and repetition (do A again and again).

The same three ways of combining behaviours are found in regular expressions. Throw in subroutine calls and you have an analogy to EBNF.

So there is a lot of similarity between the algebra of regular expressions and the algebra of commands. This is explored in detail by Dijkstra in "The Unification of Three Calculi". It is also the basis of Milner's CCS, which provides an answer to the question: what if we add parallelism?

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.