[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
parser stack overflow with glr
From: 
Roger Casaponsa 
Subject: 
parser stack overflow with glr 
Date: 
Fri, 01 Jul 2005 00:50:46 +0200 
Useragent: 
Mozilla Thunderbird 1.0.2 (X11/20050419) 
Hi there,
I would like to share with you a doubt that I found while parsing with
Bison2.0a and glr option.
In some inputs, not that big, I've got a parser stack overflow error.
Firstly Id like to expose my doubts:
Doesn't Bison really empty the stacks until it comes back to
deterministic
operation while working with glr?
Could happened that bison doesn't return to deterministic operation
when it
must?
Analyzing the output:
Stack 0 Entering state 10
Reduced stack 0 by rule #183; action deferred. Now in state 8.
Stack 0 Entering state 8
Reading a token: Next token is token IDENTIFIER ()
Reduced stack 0 by rule #206; action deferred. Now in state 14.
Stack 0 Entering state 14
Splitting off stack 2 from 0.
Reduced stack 2 by rule #465; action deferred. Now in state 107.
Stack 2 Entering state 107
Splitting off stack 3 from 2.
Reduced stack 3 by rule #31; action deferred. Now in state 212.
Stack 3 Entering state 212
On stack 3, shifting token IDENTIFIER (), now in state #34
On stack 2, shifting token IDENTIFIER (), now in state #34
On stack 0, shifting token IDENTIFIER (), now in state #34
Stack 1 Entering state 615
Reduced stack 1 by rule #161; action deferred. Now in state 309.
Stack 1 Entering state 309
Reduced stack 1 by rule #314; action deferred. Now in state 310.
Stack 1 Entering state 310
Reduced stack 1 by rule #312; action deferred. Now in state 25.
Stack 1 Entering state 25
Reduced stack 1 by rule #188; action deferred. Now in state 10.
Stack 1 Entering state 10
Reduced stack 1 by rule #183; action deferred. Now in state 8.
Merging stack 1 into stack 0.
At the beginning there are only 2 opened stacks: stack 0 and stack 1.
First it deals with stack 0 and after reading the token identifier it
splits
it.
Then it deals with stack 1 and merges it with stack 0. Is there that
stack 1 is
in state 8. Ive supposed that this merge takes place when both stacks
(10) are
in the same state (8). If Im right, this should happen before the
splitting of
stack 0.
Here I drop you a diagram of the stacks:
stack 0 stack 1
. .
. .
. .
state 10 state 615
 
state 8 state 309
 
reading ident state 310
 
state 14 state 25
 
/ \ state 10
/ \ 
/ \ state 8
split / \ 
/ \ merging with
stack 0
/ stack 0
stack 2 
 
state 107

/\
split / \
/ \
/ \stack 2
stack 3 
 
state 212
So if Bison deals the stack 1 before splitting the stack 0 it will
return to
deterministic operation, empty the stacks and continue parsing the input.
Is that correct??
Thanks for all
Roger
[Prev in Thread] 
Current Thread 
[Next in Thread] 
 parser stack overflow with glr,
Roger Casaponsa <=