* Anyone who had read the src of lalr-scm?
@ 2013-12-06 10:30 康桥
2014-09-02 6:07 ` Thien-Thi Nguyen
0 siblings, 1 reply; 2+ messages in thread
From: 康桥 @ 2013-12-06 10:30 UTC (permalink / raw
To: guile-user
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)?
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: Anyone who had read the src of lalr-scm?
2013-12-06 10:30 Anyone who had read the src of lalr-scm? 康桥
@ 2014-09-02 6:07 ` Thien-Thi Nguyen
0 siblings, 0 replies; 2+ messages in thread
From: Thien-Thi Nguyen @ 2014-09-02 6:07 UTC (permalink / raw
To: 康桥; +Cc: guile-user
[-- Attachment #1: Type: text/plain, Size: 1073 bytes --]
() 康桥 <usakq12345@gmail.com>
() Fri, 06 Dec 2013 18:30:16 +0800
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?
At first glance it seems to be a standard fanout computation.
What do you mean by "know"? Are you looking for its name?
BTW, should we rewrite lalr-scm in a more scheme way(even to
make the process of parser generating slower)?
Why don't you go ahead and try, then post your findings?
--
Thien-Thi Nguyen
GPG key: 4C807502
(if you're human and you know it)
read my lisp: (responsep (questions 'technical)
(not (via 'mailing-list)))
=> nil
[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 197 bytes --]
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2014-09-02 6:07 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2013-12-06 10:30 Anyone who had read the src of lalr-scm? 康桥
2014-09-02 6:07 ` Thien-Thi Nguyen
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).