Syntax and formal grammar of a formal language

Question

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!

Answer 1

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.

Answer 2

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, instead of the term grammatical, we use the term syntactically valid. The issue remains the same: we can express things that conform to the structure of a language but still don't make sense.

For instance, take this C program:

#include <stdio.h>
int main(int argc, char* argv[]) { int i = 4; printf("%d\n", j); }

This is a valid C program, except that it uses an undeclared variable, j. Most compilers will throw an error and refuse to compile the program.

However, the syntax of programming languages is usually described by means of context-free grammars, which are incapable of requiring all variables in a program to be declared prior to use. Hence, any context-free grammar for C will accept this program.

Is it syntactically valid?

Many practitioners will say: yes,

• syntax is defined by a grammar;
• look, here's this grammar for C;
• the program conforms to the grammar, so it is syntactically valid;
• the problem of j being undefined is not a syntactical problem, but a semantical one.

Other practitioners will say: no,

• a grammar is only a first approximation of syntactic validity;
• j being undefined clearly makes the program invalid, and we can see that at compile time, without running it;
• hence, it is a syntactical issue, even when a context-free grammar doesn't detect it.

A second example:

#include <stdio.h>
int main(int argc, char *argv[]) { int i; printf("%d\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 this is a syntactically valid C program that isn't meaningful. Some may use a compiler that defines its behavior by always initializing undefined variables and say this program is perfectly valid, syntactically and semantically.

Instead of using context-fee grammars, we can describe syntax using more powerful techniques, such as attribute grammars or two-level grammars, which can require all variables to be declared, or initialized, prior to use. With respect to such a grammar, these two C programs will be ungrammatical. However, writing grammars to capture this correctly is not easy, and checking whether a given program conforms to a given grammar using such a technique is hard or even undecidable. As a result, such techniques aren't popular today.