Re: Commonality in subset construction and LR set of items construction algorithms

torbenm@app-6.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Mon, 27 Aug 2007 10:56:16 +0200

          From comp.compilers

Related articles
Commonality in subset construction and LR set of items construction al cfc@shell01.TheWorld.com (Chris F Clark) (2007-08-24)
Re: Commonality in subset construction and LR set of items constructio anton@mips.complang.tuwien.ac.at (2007-08-25)
Re: Commonality in subset construction and LR set of items constructio schmitz@i3s.unice.fr (Sylvain Schmitz) (2007-08-25)
Re: Commonality in subset construction and LR set of items constructio DrDiettrich1@aol.com (Hans-Peter Diettrich) (2007-08-26)
Re: Commonality in subset construction and LR set of items constructio torbenm@app-6.diku.dk (2007-08-27)
| List of all articles for this month |

From: torbenm@app-6.diku.dk (Torben =?iso-8859-1?Q?=C6gidius?= Mogensen)
Newsgroups: comp.compilers,comp.theory
Date: Mon, 27 Aug 2007 10:56:16 +0200
Organization: Department of Computer Science, University of Copenhagen
References: 07-08-071 07-08-074
Keywords: parse, theory

anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:


> Chris F Clark <cfc@shell01.TheWorld.com> writes:
>>Recently the similarities between the subset construction algorithm to
>>transform an NFA into a DFA and the LR set of items construction
>>algorithm have been repeatedly thrust upon me, so much so that I have
>>a hard time as seeing them as anything but one algorithm.
>>
>>Is this similarity a well known fact that I just somehow didn't learn
>>or forgot?
>
> I learned it from a textbook (unfortunately I don't remember which
> one). I think this is not pointed out in most textbooks, though.


The similarity is very prominent in my compiler book (Basics of
Compiler Design), where the SLR construction is shown as creating an
NFA from the productions and then using the subset construction to
make a DFA (in tabular form), after which you add reduce actions to
accepting states.


Torben


Post a followup to this message

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