Re: Grammar Algebra?

> Can anyone point to references concerning research on
> operations on grammars? For example: what does it mean to add,
> subtract, compose, or concatenate grammars?
>
>It certainly makes sense to perform these operations on languages, and
>then you can ask whether there is an algorithm which, given grammars G1
>and G2, will produce a grammar for (say) L(G1) - L(G2). This kind of
>thing should be in any elementary automata theory book.
>
>Or did you have something else in mind?


Well, yes. I should have better qualified my question. I have studied
basic automata and formal language theory, though I certainly am not a
theorist.


I am looking for different operators then the set theoretic manipulations
on languages. I am perhaps more interested in "engineering" approaches.


One email respondant mentioned that the concatenation operation appeared
useless. From my perspective it might be the most useful.


Suppose one wanted to formalize (the syntax of) a documentation system
which contains sections devoted to differemt purposes. Section 1 might be
an outline of system requirements. Section 2 might be devoted to
describing actual protocols used by cooperating proccesses, etc.


It might be reasonable to constrict each section to its own grammar, and
this would amount to concatenating a sentance from one grammar with a
sentance from another grammar.


So, I was sort of fishing for any ideas people have on ways of combining
and/or meshing grammars..


Phil
Philip Hall | internet: hallpwcd@ucunix.san.uc.edu
University of Cincinnati | UUCP: hall@dec254 (Cinti Milacron)
[It seems to me that the obvious way to concatenate two grammars is to
add a new rule `` root_concat ::= root_g1 root_g2 ''. Union should be
equally easy, give or take concerns about ambiguity. Intersection and
difference start to get interesting. -John]
--

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