Sat, 31 Oct 1992 00:21:47 GMT

Related articles |
---|

Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-26) |

Re: Grammar Algebra? wand@dec5120z.ccs.northeastern.edu (1992-10-27) |

Re: Grammar Algebra? hallpwcd@ucunix.san.uc.EDU (1992-10-31) |

Re: Grammar Algebra? jan@klikspaan.si.hhs.nl (1992-11-02) |

re: Grammar Algebra? keithc@dcs.qmw.ac.uk (Keith Clarke) (1992-11-02) |

Re: Grammar Algebra? hdev@dutiaj.twi.tudelft.nl (1992-11-03) |

Re: Grammar Algebra? Peter.Breuer@prg.oxford.ac.uk (1992-11-04) |

Newsgroups: | comp.compilers |

From: | hallpwcd@ucunix.san.uc.EDU (Phillip W. Hall) |

Organization: | Compilers Central |

Date: | Sat, 31 Oct 1992 00:21:47 GMT |

References: | 92-10-102 92-10-099 |

Keywords: | parse, theory, comment |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.