|
Home > Archive > Unix Programming > October 2006 > Yacc: Recursion and Empty rules.
You are viewing an archived Text-only version of the thread.
To view this thread in it's original format and/or if you want to reply to
this thread please [click here]
| Author |
Yacc: Recursion and Empty rules.
|
|
|
| Hi, I have two questions, but first, the code:
....
%%
start: items
items:
| items item
;
item: ITEM COMMAND ACTION
;
%%
....
Now this code i've pulled from the oriley lex & yacc book, after
studying the text for a while i still dont understand recursion and
empty right hand sides properly.
1) What is the behaviour of an empty rule? wouldnt it _ALLWAYS_ match
the token stream because yacc would not bother checking the other rules
if there is a empty rule ( the logic behind this idea is that if a rule
is empty, yacc will not bother checking the stack to reduce, so it will
return true no matter what the state and variables on the stack are. )
2) I'm not understanding how recursion works with yacc. If i had the
input stream ITEM COMMAND ACTION, when 'items' rule is evalulated,
would'nt it get stuck in a infite loop because it is self-referencing?
example of this concept: items -> evaluate first rule, first argument
is items, evalulate that, and were back at items again, in a infite
loop. How does yacc ever reach item when it gets stuck in a infite loop
before it can be evaluated?
Thanks in advance.
| |
| Pascal Bourguignon 2006-10-14, 1:20 pm |
| "escii" <escii@hotmail.com> writes:
> Hi, I have two questions, but first, the code:
>
> ...
> %%
>
> start: items
>
> items:
> | items item
> ;
>
> item: ITEM COMMAND ACTION
> ;
> %%
> ...
>
> Now this code i've pulled from the oriley lex & yacc book, after
> studying the text for a while i still dont understand recursion and
> empty right hand sides properly.
>
> 1) What is the behaviour of an empty rule? wouldnt it _ALLWAYS_ match
> the token stream because yacc would not bother checking the other rules
> if there is a empty rule ( the logic behind this idea is that if a rule
> is empty, yacc will not bother checking the stack to reduce, so it will
> return true no matter what the state and variables on the stack are. )
There is an additionnal implicit token added to the start rule:
start : items $EOF$ ;
and this token is implicitely added to the input stream:
ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
Therefore, if we derivate the empty items rule:
start --> items $EOF$ --> $EOF$ ;
we can see that this cannot match the input tokens. So we backtrack
and try to derivate the items : items item ; rule:
start --> items item $EOF$
and then we try the items -> ; and item -> ITEM COMMAND ACTION ; rules:
start --> items item ITEM COMMAND ACTION $EOF$
--> items ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
and there, we see that to match the input stream of tokens, the only
choice is to derivate the empty rule for items:
start --> items item ITEM COMMAND ACTION $EOF$
--> items ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
--> ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
MATCH!
So the parse tree is:
start --> items --> items --> items --> (empty)
| | |
| | item --> ITEM COMMAND ACTION
| |
| item --> ITEM COMMAND ACTION
$EOF$
> 2) I'm not understanding how recursion works with yacc. If i had the
> input stream ITEM COMMAND ACTION, when 'items' rule is evalulated,
> would'nt it get stuck in a infite loop because it is self-referencing?
It could, if there was no limit. For example, if you use the grammar
to _generate_ sentenses. You have an infinitite language.
> example of this concept: items -> evaluate first rule, first argument
> is items, evalulate that, and were back at items again, in a infite
> loop.
Yes, this is what you do when you _generate_ the sentences.
> How does yacc ever reach item when it gets stuck in a infite loop
> before it can be evaluated?
It uses the constraints implied by the input stream of tokens to
choose the right rule.
--
__Pascal Bourguignon__ http://www.informatimago.com/
"Logiciels libres : nourris au code source sans farine animale."
| |
|
|
Pascal Bourguignon wrote:
> "escii" <escii@hotmail.com> writes:
>
> There is an additionnal implicit token added to the start rule:
>
> start : items $EOF$ ;
>
> and this token is implicitely added to the input stream:
>
> ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
>
> Therefore, if we derivate the empty items rule:
>
> start --> items $EOF$ --> $EOF$ ;
>
> we can see that this cannot match the input tokens. So we backtrack
> and try to derivate the items : items item ; rule:
>
> start --> items item $EOF$
>
> and then we try the items -> ; and item -> ITEM COMMAND ACTION ; rules:
>
> start --> items item ITEM COMMAND ACTION $EOF$
> --> items ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
>
> and there, we see that to match the input stream of tokens, the only
> choice is to derivate the empty rule for items:
>
> start --> items item ITEM COMMAND ACTION $EOF$
> --> items ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
> --> ITEM COMMAND ACTION ITEM COMMAND ACTION $EOF$
> MATCH!
>
> So the parse tree is:
>
> start --> items --> items --> items --> (empty)
> | | |
> | | item --> ITEM COMMAND ACTION
> | |
> | item --> ITEM COMMAND ACTION
> $EOF$
>
>
>
> It could, if there was no limit. For example, if you use the grammar
> to _generate_ sentenses. You have an infinitite language.
>
>
> Yes, this is what you do when you _generate_ the sentences.
>
>
> It uses the constraints implied by the input stream of tokens to
> choose the right rule.
>
>
> --
> __Pascal Bourguignon__ http://www.informatimago.com/
>
> "Logiciels libres : nourris au code source sans farine animale."
Ah! Thank you, another very informitive answer from pascal!
|
|
|
|
|