Re: Formal grammar & syntax of formal languages

> Is there a difference in meaning between the terms "formal grammar"
> and "syntax of a formal language"?


The situation is something like to an algorithm definition. Every man
knows intuitively what an algorithm is, but the problem is to form the
formal definition of this one. Thus, there are many different
definitions of notion of algorithm: Turing machine, recurcive
functions, Markov algorithm and so on. The syntax of the language is
someone what define how symbols of alphabet (that are just atomic
nonstructured notions in the language) are combined to each other to
construct the meaningful statements. There are many different formal
definitions of syntax - the formal grammars. Generally, a grammar is
the description of the language syntax. One can describe the syntax as
the process of generation of the language statemens, such grammars are
named as generative ones. The syntax relations here are described as
algorithm of statemens generation. Other way is to describe the
language syntax as a machine, which reads the statement and say "yes"
if one is correct and "no" in contrary case. This machine also must
implemets some algorithm, not generative grammar, but recognizing one.
Now the most popular way to define the language syntax is Chomsky
generative grammar, where the generation algorithm is defined as
someone named as "rules", that are in fact rewriting rules in Markov's
algorithm. However, the most inyteresting way to define a syntax is
not an algorithm, but immediate description of the syntax relations of
the language. The way to do this was proposed by soviet mathematician
Yuly Shreider in 60th of the last century. He described languages with
very symple grammar with so named neighborhoods defined for each
symbol of the language. This neighborhood grammar is not algorithm,
but only the passive description of syntax laws and it is local one
(define the neighborhood for the symbol, not the statement). The
proposition of Shreider was developed in works of Borschev and
Homyakov. They took a look on the statements as not only horisontal
texts of symbols (chains), but as some combinations of more complex
structures. For example, a tree (obvious tree structure in
programming) is a text (statement), chemical formula is a text and so
on. Borschev and Homyakov used instrument of formal theory to describe
neighborhoods of the symbols in such complex text structures. The
model of the such theory is the statement of the language. Natural
languages are completely described with this model as statement (text
of the natural language proposiotion) can be looked as the tree if one
build the syntax tree of the statement where the leaves are just the
symbols of the statement. Now, my work is to generate this approach
and I have defined all such complex structures as "syntax diagrams" -
graphes, that vertices are sighed by symbols of the grammar. The
neighborhoods are also such diagrams. The property to be close is the
topological one. So, I have defined the grammar as the topological
space, where elements of the space are syntax diagrams. The syntax
diagrams are nor the set, so the obvious way to define the topology
doesn't work here. But, it is possible to define the more general then
set "category of syntax diagrams" (cathegory in the sence of cathegory
theory) and define the Grothendick topology as the grammar on this.
So, the grammar here is just the topology :-).


Hope my long tirade help you,
Vladimir.

Return to the comp.compilers page.
Search the comp.compilers archives again.