Re: Beginner help with LALR(1) closure

Kent Rollins wrote:


> I'm using 'Compiler Design in C' [Holub]. I'm currently working
> on performing LALR(1) closure on LALR(1) states. I've got 2
> questions:


The kind of language contruct you are trying to avoid are the
ones that make LALR(1) grammars easier to write compared with
LL(1). If you change the grammar to eliminate left-recursion and
circular references, you will end with something close to a
LL(1) grammar (you need to do a left factoring too!!)


> 1. I've downloaded a few YACC-able grammars and I've noticed that
> they all have left-recusive grammars like (A) below. When I


> 2. How are circular references like the following handled when
> performing LALR(1) closure?


How to compute the LALR(1) closure:


s -> statement-list


statement-list -> statement
                                | statement-list statement


statement -> STAT
| statment2


statement2 -> STAT2




First, you have to compute the First(1) sets the every non-terminal.


1. First compute wich non-terminales can be empty; Do it by checking
if any of its RHS can be empty. Use a iteractive algorithm like this:


Mark all Non-Terminals as "Not null"
Repeat
Change = 0;
Foreach rule (S -> X1 X2 X3 .. Xn) && S is "not Null"
is_null = 1;
for (i=1..n)
if (X1 is "not null") is_null = 0;
end for
if (is_null) then
Mark S as "null"; Change=1;
end if
End For Each
Until Change=0;




2. After this, you can compute quite easy the First(1) set for your
grammar.




After this, you are ready to compute the closure(1) of your grammar:


1. Compute all the posible direct (non-term) derivations for each
Non-Terminal:


s *> s, statement-list, statement, statement2
statement-list *> statement-list, statement, statement2
statement *> statement statement2
statement2 *> statement2


2. Compute start (Set 0):


s -> . statement-list


CLOSURE (Finally!!!!)
This means that you have to "expand" statement-list. By using the
transitive closure compute in 1, this is very easy!! You will get:


s -> . statement-list
statement-list -> . statement
statement-list -> . statement-list statement
statement -> . STAT
statement -> . statement2
statement2 -> . STAT2


Now, compute all your posible "transitions" or "gotos" to create
another set, for example, goto(0,statement-list)


Set 1:
You will get:


statement-list -> statement-list . statement


"Expand" again using the transitive closure of "statement"


statement -> . STAT
statement -> . statement2
statement2 -> . STAT2


And so on.....


You will get the LR(0) Sets.


To get the LALR(1), you can compute the "lookaheads" from this sets
by "propagating" or "generating" them also using a iteractive
algoritm if it make a backward propagation. Also you can use
a more efficient one by just keeping the "dependences" between propaga-
tion and then do a topological sort to get the order of evaluation
(Try the iteractive method, is a lot simpler!!!)


Hope this helps, (I am happy that still remember this!!)


Frankie Arzu
Computer Science Department
Texas A&M University


P.S. You can take a look to the source code of my LL(1) compiler
generator "Coco/R for C++" that is available at
ftp://uvg.edu.gt/pub/coco (Ver 1.06 is the latest). There are
versions is C++, modula-2, pascal and oberon.
--

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