LL(1) and common-heads...

p8uu@jupiter.sun.csd.unb.ca (Saulnier)
28 Dec 1995 11:58:38 -0500

          From comp.compilers

Related articles
LL(1) and common-heads... p8uu@jupiter.sun.csd.unb.ca (1995-12-28)
Re: LL(1) common head. ask@csa.iisc.ernet.in (Kanhere Abhay) (1995-12-30)
LL(1) and common-heads... deakjahn@ludens.elte.hu (Gabor DEAK JAHN) (1995-12-30)
Re: LL(1) and common-heads... mparks@oz.net (1996-01-12)
Re: LL(1) and common-heads... d.sand@ix.netcom.com (1996-01-14)
Re: LL(1) and common-heads... Osman.Buyukisik@ae.ge.com (U-E59264-Osman Buyukisik) (1996-01-15)
| List of all articles for this month |

From: p8uu@jupiter.sun.csd.unb.ca (Saulnier)
Newsgroups: comp.compilers
Date: 28 Dec 1995 11:58:38 -0500
Organization: University of New Brunswick, Fredericton, NB, Canada
Keywords: assembler, parse

Hi all, I've written an actual assembler for this new OS that
a bunch of us are trying to get off the ground (originally from
r.g.p.). Anyhow, the assembler works fine, but I'm not using any
parsing algorithms like LL(1) or SLR. I was wondering if it would be
of any use writing it using LL(1). Or would anyone suggest a better
algorithm?


Ok, so I've started writing the grammar for a LL(1) parser,
and I've come into a problem. Common heads that are driving me nuts.
BTW, I'm using LL(1) because I've already implemented it before and I
understand it very well.


Here's the problem:
ADM16 -> "[" ADM16_1 "]"
ADM16_1 -> "EAX"
ADM16_1 -> BASE
BASE -> "EAX"
BASE -> "EBX"
BASE -> "EDX"
...


So there's 2 ways to encode "[eax]" addressing mode. But BASE
by itself is a valid addressing mode too which is also used in other
productions.


Now, I know I could fiddle with it all day until it finally
went away, but here's what I was wondering. With LL(1), the m-table
isn't supposed to have multiple entries, right! I was wondering, why
not? This is because the parser wouldn't know what production to go
to right? Well, why not create extra stacks for each extra entry.
Whenever one of the stacks (if more than one exists) goes to an empty
entry, you would delete that stack because it's not the valid
production(s). You would continue until only one stack is left. Now,
you would execute all the action routines that you stored in the queue
associated with the remaining stack. You could not execute these
action routines before because there were more than one valid
production earlier on.
If there is more than one stack remainding when it returns to
the point on the stack where it split, it would simply take the first
stack as the correct one (this here would solve my problem because
higher productions would have higher priorities).


Anybody understand what I mean or am I on another planet?
BTW, I really don't care how hard it would be to implement. Linked
lists are really easy for me.




----------------------------------------------------------------------------
                                            Cleo Saulnier p8uu@unb.ca
--


Post a followup to this message

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