Hi all. I am a college student, recently I became interested in parser generating algorithms. One of them is LALR(1).I took lalr-scm(which is mentioned in Guile Manual) as an example of the design of this kind of parser generators and studied its source code. However, I found the source code too little scheme.It seems that it was written by a programmer who had been familier with C or Pascal before, mainly because it relies heaviliy on side-effects, which we don't use much in functional programming languages. In spite of this, I read it almost all.I have found the part of computing itemsets, FOLLOW sets, etc.But I still leave one function not understand. It's function digraph in the macro lalr-parser in file lalr.scm. It seems that this function is trying to traverse a digraph and make each FOLLOW set corresponding a vertex in the digraph the union of it and the FOLLOW sets corrsponding the vertices which can be reached from the vectex I mentioned before.But I can't figure out what algorithm it uses.
Anyone who know this algorithm? BTW, should we rewrite lalr-scm in a more scheme way(even to make the process of parser generating slower)?
