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

Hans-Peter Diettrich <DrDiettrich1@aol.com>
Sun, 26 Aug 2007 19:36:08 +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: Hans-Peter Diettrich <DrDiettrich1@aol.com>
Newsgroups: comp.compilers,comp.theory
Date: Sun, 26 Aug 2007 19:36:08 +0200
Organization: Compilers Central
References: 07-08-071
Keywords: parse, theory

Chris F Clark wrote:


> 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?


Typical (BNF...) grammars are equivalent to NFA's, so this kind of
automaton IMO is only another, still more formal, reflection of the
input. For certain grammars a DFA can be constructed, from the NFA,
which also could be constructed immediately, when the user would
rephrase his input accordingly. It's only more convenient, when the user
can leave all automizeable tasks to his tools...


DoDi


Post a followup to this message

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