|
Error recovery merely tries to bring your parse in a valid state e.g. by adding error productions, error "repair" tries to convert the input into something that may be is not meant
by the writer of the program, but is valid.
Since you do kind of LR parsing, you are certain that what you have recognized is a valid
prefix. The "state" you are in when detecting the error gives all possibilities for an error free continuation. Add to each state such a symbol and you always can recover from the error
with a correct parse tree (although not necessarily the tree meant by the writer of the program)
(There are some cases where that does not work, where you have to do some form of state splitting as long as you do the simple forms like SLR or LALR)
Error recovery and repair was a popular topic in the late 70-ies and 80-ies, and dr Johannes Roehrich had a few good papers on it, Unfortunately these seem to be behind pay walls
|
|
|
|
|
I've got Dick Grune's book on it, and he gives it a pretty thorough treatment.
It's not really the parser that's not working
The parser is a pull-parser underneath and that handles errors okay.
The tree builder that uses the pull-parser gets confused though when there aren't the right number of right hand sides to satisfy a rule.
Real programmers use butterflies
|
|
|
|
|
Yeah, but then the state the parser is in is incorrect or - if you use a separate stack
for the building process, there is an inconsistency between the parse stack and the "semantics" stack
|
|
|
|
|
Yep, and I do have a separate step for the tree building.
The reason for the inconsistency is a rule/shift/reduce mismatch
Like if something is supposed to do
Shift a
Shift b
Shift c
Reduce D
but there's in error it might return this from the parse:
Shift a
#ERROR bc
and then there's an inconsistency, because the rule didn't match the number of shifts in this case (there should have been 3 followed by a reduce)
Real programmers use butterflies
|
|
|
|
|
Have you tried turning it off and back on again?
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Yes. 
Real programmers use butterflies
|
|
|
|
|
Hmm. Reformat your HDD and reinstall your algorithm from scratch?
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
just thinking a simple solution would be push markers onto the stack,
something goes wrong pop and discard till the marker is found.
markers would have a "safe here" with a number akin to the depth of the tree.
i.e. marker #1 at the beginning, #2 at the first branch, #3 at third...
- if it fails roll (pop) back to last marker
- but then need to decide: are we recovered [enough] here go back another level?
second part is hardest - sometimes an error shows 1 message and other times a whole page of subsequent and possibly incorrect/inappropriate messages - even the best compilers can do that.
(missing/extra quotes and close braces are common classics, fore sure they make FSM's run like bulls in a china shop.)
how far to roll back depends how blunt you want recovery, even then there's some things you just cant fix anymore.
already reduced input to handle for missing/extra right hands pushing "ok to here" markers should recover most.
after many otherwise intelligent sounding suggestions that achieved nothing the nice folks at Technet said the only solution was to low level format my hard disk then reinstall my signature. Sadly, this still didn't fix the issue!
|
|
|
|
|
The trouble is because it's bottom up I don't know how many to push until after the fact.
Real programmers use butterflies
|
|
|
|
|
hmmm, at every ite/item-group terminator (comma, semi, close brace/bracket...) - almost have to do it at syntax check and search forward backwards further back?/up?(??) for the markers.
?? going back forwards, no, forwards back, no, backwards up? no, ahead backwards ...
argggh, bottom up with a stack is which way really?
I give up! I'm the wrong person for this kitchen.
after many otherwise intelligent sounding suggestions that achieved nothing the nice folks at Technet said the only solution was to low level format my hard disk then reinstall my signature. Sadly, this still didn't fix the issue!
|
|
|
|
|
.NET "stacks" have a "Contains" method. Backwards or forwards, it's easy enough to "look ahead" (or behind). You can "see" as much as you want.
It was only in wine that he laid down no limit for himself, but he did not allow himself to be confused by it.
― Confucian Analects: Rules of Confucius about his food
|
|
|
|
|
Yeah, that's not the problem. The problem is with a bottom up parse I don't know what I'm looking for until after it's too late. The reason being is the tree is build from the leaves to the root.
So you get a series of tokens
a
b
c
and then a reduce rule
A-> a b c
Which finally tells you what you need to push and pop
But again, it's not until after, so
a
#ERROR bc
???
???
You don't even know what to reduce at that point. However assume you did.
a
#ERROR bc
A-> a b c
Error, not enough tokens in the input. Expecting 3, got 2.
Real programmers use butterflies
|
|
|
|
|
Make the leaves leafs the root, and the root the leaves leafs! Then flip! Problem solved! 
edit - doh!
|
|
|
|
|
well, i do already return multiple trees, but yeah no. =) I'm not flipping them
Real programmers use butterflies
|
|
|
|
|
More seriously, if I was to make a bottom-up parser, I would start with a 'statement' root node, and push the items into it as they get parsed. Once a 'statement was complete, I'd expect a single branch from that 'statement' node to a 'type of statement' node, from which a true tree would form.
|
|
|
|
|
I must be misunderstanding you because it seems like you're describing a top-down, not bottom up approach.
In the statement scenario you'd see like:
shift while
shift (
shift true
shift )
reduce WhileStart
reduce Statement
(not a real scenario, i made up the sequence there)
note how statement doesn't make it until the end after it has recognized the start of the while loop?
that's how bottom up works. If that's what you were describing then my mistake. 
Real programmers use butterflies
|
|
|
|
|
honey the codewitch wrote: shift while
shift (
shift true
shift )
reduce WhileStart
reduce Statement
Isn't that top-down?
My understanding was that bottom-up was like:
parse the ')' to a rparen and build a 'rparen' leaf
parse the 'true' and place it in the tree
parse the '(' to a lparen and insert it
... 'while' ...
reduce WhileStart
reduce Statement
So my approach would be to start with a blank statement at the beginning
add the rparen to it, so the tree is: Statement -> RParen
add the 'true' to it, so the tree is now: Statement -> True -> RParen
add the lparen to it, so: Statement -> LParen -> True -> RParen
the LParen can trigger a reduction at this step if you want
add the 'while': Statement -> While -> LParen -> True -> RParen
and reduce everything there if you want.
It would be a pretty straight tree in this case, but so be it. Maybe my understanding about top-down and bottom-up is incorrect.
|
|
|
|
|
No you got it, I just misunderstood you at first
Real programmers use butterflies
|
|
|
|
|
That's why parsers have some sort of synchronise system, when an error occurs they just eat tokens until they can get back to a safe state - simple ones just chew away until they hit a keyword.
|
|
|
|
|
I have that.
The issue is further downstream, and has to do with building the tree upward in the event of missing nodes (missing due to an error)
Edit: I should add, I've fixed it since. 
Real programmers use butterflies
|
|
|
|
|
Stupid person is confused, or amusing? (9)
|
|
|
|
|
I'm going to ignore musefan today, as I posted yesterdays.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
Very good.
And 88% is a pass where I come from 
|
|
|
|
|
|
Generally, I use either 26 or 29 (Welsh has some English doesn't, and vice versa) - but some are infrequent visitors to my screen.
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
