Wed, 15 Aug 2018 20:48:12 -0700 (PDT)

Related articles |
---|

From: | woong.jun@gmail.com |

Newsgroups: | comp.compilers |

Date: | Wed, 15 Aug 2018 20:48:12 -0700 (PDT) |

Organization: | Compilers Central |

Keywords: | books, question |

The official errata for the book, Advanced Compiler Design and Implementation

by Steven Muchnik added, among other fixes, this line to the Tarjan's algorithm

to find maximal strongly connected components (SCCs) from a directed graph.

All_SCC U= {{Stack[1]}}

where I replaced with brackets an arrow to mean retrival of an element from a

sequence named Stack.

The full context (p.195) reads as

... some declarations and init code omitted...

for each x from node sets do

if Dfn(x) = 0 then

Strong_Components(x,Succ)

fi

od

All_SCC U= {{Stack[1]}}

The original paper has no such line and I failed to figure out when it is

necessary.

It seems to imply the stack has one node that should be added to the set of

SCCs, but AFAIK the stack should be empty when returning an initial call to

Strong_Components() above. What am I missing here, or is this another added bug

as ones for Tarjan's dominator algorithm?

Thanks in advance.

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.