Re: LL(1) common head.

Kanhere Abhay <>
30 Dec 1995 00:54:11 -0500

          From comp.compilers

Related articles
LL(1) and common-heads... (1995-12-28)
Re: LL(1) common head. (Kanhere Abhay) (1995-12-30)
| List of all articles for this month |

From: Kanhere Abhay <>
Newsgroups: comp.compilers
Date: 30 Dec 1995 00:54:11 -0500
Organization: Compilers Central
References: 95-12-143
Keywords: assembler, parse 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?
> 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

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 : Voice : 0091-080-3092451
Abhay Kanhere. research student,Indian Institute of Science, Bangalore

Post a followup to this message

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