Re: LL(1) common head.

p8uu@jupiter.sun.csd.unb.ca writes:


> Here's the problem:
> ADM16 -> "[" ADM16_1 "]"
> ADM16_1 -> "EAX"
> ADM16_1 -> BASE
> BASE -> "EAX"
> BASE -> "EBX"
> BASE -> "EDX"
> ...
How about grammar that says .


<ADM16> -> '[' <ADM_16_1 ']'
<ADM_16_1> -> 'EAX'
| <BASE1>
<BASE_1> -> 'EBX' | 'EDX' ... /* no 'EAX' here */
<BASE> -> 'EAX' | <BASE_1>


  I hope I've understood your problem properly.
[ It seems simple Hence I have doubt whether I have fully grasped
    the problem :-/ ]


> 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?
Correct.
> Well, why not create extra stacks for each extra entry ....


I believe 'm-table' refers to the parser goto-table (ie.goto next
state). I assume what you mean to say is that for each input token,
make a move on each alternate ( that is possible) by storing possible
actions on a queue. When rhs of a production is completely matched use
the actions queued up in queue order. Remove all other alternate
stacks temporarily created. This would have exponential time/space
requirement.


What you are proposing is similar to a nondeterministic(ND) pda (push
down automaton) which would be higly inefficient time+space wise.
Hence deterministic LL(k) parsers (based on D-PDA)are used. These
require that with lookahead of (only k as compared to conceptually
unbounded-variable lookaheads in NDPDA) k-symbols next production to
apply can be deterministically known.


                                                                                                                              - Abhay


WWW : http://www.csa.iisc.ernet.in/~ask Voice : 0091-080-3092451
----------------------------------------------------------------------
Abhay Kanhere. research student,Indian Institute of Science, Bangalore
--

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