# Syntax and formal grammar of a formal language

For a formal language, I wonder what differences and relations are between its syntax and its formal grammar.

A formal grammar
is a set of formation rules that describe how to generate the strings that belong to the formal language.

Wikipedia says that syntax

is "the study of the principles and processes by which sentences are constructed in particular languages."

the term syntax is also used to refer directly to the rules and principles that govern the sentence structure of any individual language.

So I wonder if for a formal language, its syntax and its formal grammar the the same concept? Thanks!

• For my the syntax is the (underlying) structure of the strings in the language. A grammar is a way of describing that structure. – Hendrik Jan May 27 '14 at 8:30
• A formal language is syntax, so I don't understand what you are asking by "its syntax". Also, there are infinitely many grammars for any language. – Raphael May 27 '14 at 9:25
• You suggest that a language has only one grammar. This is not true in general. Given a language (that can be described by a grammar), there exist infinitely many different grammars to describe it. – reinierpost May 27 '14 at 10:50
• @HendrikJan: Thanks. What are "the (underlying) structure of the strings"? – Tim Jul 14 '14 at 1:38

Syntax is a very general term that encompasses the description and properties of physical representation of languages, i.e. of sets of sentences intended to convey ideas, concepts, meanings, etc. It is to be contrasted with semantics that is concerned with what is being conveyed.

Syntax is often thought of as structured sets of strings of symbols on a given alphabet (sentences), but that is the simpler form. Many syntaxes have a more complex structure, such as spoken natural language, signed language, graphical languages, musical scores, etc.

Syntax could be thought of as just a way to describe the set of legitimate representations, but it is usually expected to also associate structure with these representations. This structure is the scaffolding that is used to associate meaning (semantics) with a syntactic construct.

Grammars are a specific way to define these sets of sentences. There are other ways, such as automata (e.g. FA, PDA, TM), or string set expressions (regular expressions). Some types of grammars (Context-free in particular, but not the only one) are the preferred medium for expressing syntax as they are complex enough to provide structure allowing to express semantics with enough perspicuity, while remaining simple enough to be intellectually tractable.

Regular grammar, for example, do not provide enough structure and expressive power for general syntactic structure, but are often adequate for the structure of simpler semantics constituants (identifiers, numbers, morphological strcture of natural languages).

On the other hand, while context-sensitive languages can define more complex sets of sentences, the associated structure is usually too complex for deriving semantics from it in a simple enough way.

Context-free grammar are convenient because they associate a tree structure with sentences. This tree structure can be seen as an expression in a formal algebra, from which meaning can be derived by a convenient and well understoof mathematical tool: the homomorphism.

There are other ways of associating a tree structure with a sentence, for example by considering derivation trees with the structure (see mildly context-sensitive formalisms).

One could also define the syntax with automata, but this is much more computational and less perspicuous.

Denotational vs operational aspects

The preference for grammars over automata may also be related to the preference for denotational definitions over operational definition. Many grammars may be seen as more denotational as they may be read as equational definitions of syntactic structures. Though it may sometimes be disputed, denotational definitions are perceived as closer to the essence and mathematical properties of the defined entity, as giving a more perspicuous understanding, more appropriate for mathematical analysis, while operational semantics are more encumbered with technical computational or algorithmic details on the use of these entities.

Hence, it is common practice to prefer denotational definitions as reference, including for syntax. Operational tools (such as parsers) are then derived for practical computational work, and have to be proved equivalent.

Meta-language issues

Note that, when I say that a grammar "may be read as equational definitions of syntactic structures", I assume that the grammar itself is a sentence in a formal language (the language for writing grammar) and that this language may be assigned one or several semantics by appropriate means. Indeed, there is at least one well known standardized language for writing context-free grammars which is the Backus-Naur Form (BNF).

Actually, different semantics can often be associated with the same syntax, though they will often be in some mathematical relation, possibly isomorphic. This is in particular the topic of what is called "abstract interpretations" and "non standard interpretations" of languages.

Remark on the question

When answering the question, I did take the expression "formal language" in a general sense of language formally defined, as often used in mathematical context, with syntax and semantics. But the discussion is very much the same in the case of natural language.

Now it is possible that the question was intended only for the consideration of formal languages as simple sets of strings, as in formal language theory.

I would tend to think that this should not change much the answer, since even formal language theory often sees more in its formal languages than simple set of strings. This is typically the case when it makes a difference between strong and weak equivalence of grammars. Furthermore, a grammar is usually only one possible way to define the language and/or give it structure.

The terms syntax and grammar are ambiguous, but most commonly, they both refer to the structure of utterances in a language. (These terms are opposed to semantics, which refers to what the utterances mean.) Additionally, a grammar is a particular description of the structure of sentences of a particular language. This is true both in linguistics and in computer science.

In linguistics, we further have the term grammaticality, which is ambiguous, too: with respect to a particular language, a sentence is either said to be grammatical if it is valid (it belongs to the language; it may be uttered) or if it conforms to its grammar (it has the right structure). These are not the same things. Chomsky used the example

Colorless green ideas sleep furiously


of a sentence that is perfect English grammatically, but still would never be uttered, because it doesn't make sense. Most texts would take the second stance and classify such a sentence as grammatical.

In computer science, we don't use the term grammatical but syntactically valid for this notion. Here, we have the same issue: we can express things that conform to the structure of a language but still don't make sense. For instance, take the C programs

int main(int argc, char*[] argv) { int i = 4; printf(%s\n", j); }
int main(int argc, char *argv[]) { int i; printf(%s\n", i); }


The meaning of a C program is what it does when executed. In this case, the behavior is undefined, because the value of a variable is printed that is never set. Most would say that the second example is a syntactically valid C program that isn't meaningful. For the first example, I'm not sure whether everybody would agree that it is syntactically valid.

There is another subtlety: a particular grammar for a language (a description of its grammar) is not usually 100% accurate or complete - hence, grammaticality with respect to that grammar is not the same thing as grammaticality with respect to the language that the grammar tries to describe. For instance, if I use context-free grammars to describe English, I will never arrive at a 100% accurate and complete description of all the nuances of English syntax: the set of sentences described by my context-free grammar will never be the set of grammatical English sentences. Perfectly grammatical and sensible sentences may be missed by my grammar; perfectly ungrammatical sentences may be allowed by my grammar.

The same thing is true in computer science. Typically, when we describe the syntax of programming languages, we use context-free grammars to do so. Context-free grammars cannot describe the subtler aspects of validity - in particular, they cannot describe the requirement that variables must be defined prior to use. Context-free grammars for C will accept the above two programs.

However, using techniques such as attribute grammars or two-level grammars, we can provide grammars that include the requirement for all variables to be defined prior to use. With respect to such a grammar, these two C program will be ungrammatical. And even when a C compiler isn't based on such grammars, usually it supports detecting the error in the first program, and possibly the error in the second program too. So these programs are definitely invalid to C programmers and to tools that work with C programs.

But many texts I've seen on C and compiler construction would still classify even the first program as syntactically valid. So that term is often used to mean: valid according to the rules of some context-free grammar.

In formal language theory, there is no ambiguity: the terms syntax and grammaticality are avoided, and so is the generic term grammar, while a grammar unambiguously means: a particular way to describe the set of utterances that belong to a language.