Tue, 8 Jan 2008 23:59:45 -0800 (PST)

Related articles |
---|

Formal grammar & syntax of formal languages sensorflo@gmail.com (Florian Kaufmann) (2008-01-06) |

Re: Formal grammar & syntax of formal languages wyrmwif@tsoft.org (SM Ryan) (2008-01-07) |

Re: Formal grammar & syntax of formal languages DrDiettrich1@aol.com (Hans-Peter Diettrich) (2008-01-07) |

Re: Formal grammar & syntax of formal languages mefrill@yandex.ru (mefrill) (2008-01-08) |

Re: Formal grammar & syntax of formal languages theochim@it.teithe.gr (2008-01-13) |

From: | mefrill <mefrill@yandex.ru> |

Newsgroups: | comp.compilers |

Date: | Tue, 8 Jan 2008 23:59:45 -0800 (PST) |

Organization: | Compilers Central |

References: | 08-01-007 |

Keywords: | parse, theory |

Posted-Date: | 09 Jan 2008 15:38:36 EST |

*> 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.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.