Re: Help - partial parsing of C

al@nmt.edu (Al Stavely)
Fri, 24 Jan 92 19:13:54 GMT

          From comp.compilers
Related articles
Help - partial parsing of C dta@dcs.exeter.ac.uk (Daniel Tallis) (1992-01-20)
Re: Help - partial parsing of C e-sink@uiuc.edu (1992-01-22)
re: Help - partial parsing of C ohl@crunch.ikp.physik.th-darmstadt.de (1992-01-23)
Re: Help - partial parsing of C al@nmt.edu (1992-01-24)
| List of all articles for this month |
Newsgroups: comp.compilers
From: al@nmt.edu (Al Stavely)
Summary: look in this year's POPL proceedings
Keywords: C, parse
Organization: New Mexico Tech, USA
References: 92-01-086
Date: Fri, 24 Jan 92 19:13:54 GMT

The general problem was addressed (and solved) in a paper given at the
Principles of Programming Languages conference only this week (I just
returned from the conference). The paper is:


Joseph Bates and Alon Lavie
Recognizing Substrings of LR(k) Languages in Linear Time


What you need to do is replace the parse stack with a somewhat more
complicated data structure, and keep it updated so that it represents all
possible parse stacks for the substring that you have seen so far, in any
context in the language defined by the grammar. But the authors prove
that you still get linear-time performance if you do this cleverly.


The proceedings should be available from ACM soon, if they aren't already.
--
- Allan Stavely, New Mexico Tech, USA
--

Post a followup to this message

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