Tue, 17 Nov 1992 23:59:47 GMT

Related articles |
---|

re: Grammar Algebras? mareb@levels.unisa.edu.au (1992-11-17) |

Newsgroups: | comp.compilers |

From: | mareb@levels.unisa.edu.au |

Organization: | University of South Australia |

Date: | Tue, 17 Nov 1992 23:59:47 GMT |

Keywords: | parse, theory |

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

--

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.