re: Grammar Algebras?

Clearly you can't intersect CFGs - since the intersection may not be a
CFG. I have been playing with the intersection of CFGs lately for a couple
of reasons.


1. we wanted to know how to parse a^n b^n c^n d^n ... quickly. Since we
can parse a^n b^n c^m d^m ... in time O(N) {does anyone have a reference
to a published proof that LR(k) parsing is O(N)?} and a^* b^i c^i d^j e^j
... we just run two parsers in parallel (or serially) and if they both
succeed, the string is in the above CSL.


Perhaps we are lucky that CFLs are not closed under intersection!


Another observation is that this method of producing any type of grammar
for the above CSL is probably easier and more intuitive than trying to
produce a CSG. I find that it takes quite a bit of experience to be able
to work effectively with CFGs; I know very few people who can look at a
CSG and have much of a idea what it does and doesn't `say'.


2. a second reason for wanting to parse a^n b^n c^n ... is that people
keep asking me about parsing 2D syntax. Mostly they mean tables. I tell
them to just linearise their language and build a parser. If they have the
above problem, parse a^* b^* c^* and check the lengths with semantic
rules. So far, they've all been happy. The above trick is nice theory but
hasn't proven of much practical significance for me.


regards,
Bob Buckley


School of Computer and Information Science
University of South Australia
--

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