I'm stumped and in the worst way.
-
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
-
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!
-
No, it is all bottom up. It recognizes things called viable prefixes using a state machine. When it recognizes a right hand side, it removes that from the stack and replaces it with the appropriate reduction.
Real programmers use butterflies
Tested a bit, and it seems you're right. But in a file with 500 rows, one well placed bracket renders 80 errors. Now factor in how many man years MS has poured into VS. The lady witch doth protest too much, methinks
Wrong is evil and must be defeated. - Jeff Ello
-
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
-
Yes, I want to continue. Could you imagine if C#'s compiler stopped at the first parse error? :-D
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
-
honey the codewitch wrote:
Could you imagine if C#'s compiler stopped at the first parse error?
Or the converse, which I encountered many years ago in PASCAL -- a forgotten semicolon would result it reams, and I mean REAMS of "missing ;" errors. Stupid parser.
Latest Articles:
Abusing Extension Methods, Null Continuation, and Null Coalescence OperatorsI am slightly surprised. The first compiler I tried to understand thoroughly was a Pascal compiler, and I was surprised by how great efforts it made to avoid repeated error messages. E.g. if a type declaration failed, it went on with a pseudo-type-object for that type name that allowed "any" operation. If a non-existing variable was referenced, it created the variable, of a similar forgiving pseudo-type. And so on - lots of tricks to avoid repeated and false errors. Sometimes we were frustrated by this strategy, as the "forgiving" strategy let other "real" errors pass by without an error message. This was in an age when compilation of even small projects could take minutes - it didn't take that large projects to cross the hour limit. Catching the maximum number of errors per compilation run was a quality measure of the compiler. It made perfectly sense to try to continue as far as possible after a compilation error. (And, with those compilation times, the make utility made far more sense than today!) Btw: LALR parsers (often referred to "bottom up parsers") is far better suited for going on after errors than recursive descent parser are. But in the golden years of Pascal, at least nine out of ten Pascal compilers were recursive. I guess that some of the few Pascal compilers in use today are bottom up, though.
-
I've got a coding problem that I don't know if there's a solution to and it's pretty important. This isn't a coding question. It's more of a rant. When a bottom up parser parses input it kind of does things backward. You get your inputs into the queue: 1. term a 2. term b 3. non-term C Then a reduce action with a rule 4. Reduce D-> a b C which tells me to pop C, b, a, and then push D, effectively "replacing" the first 3 entries with 1 entry from step 4 This is all well and good, except when there's errors in the input let's say there was an error parsing step 1 above - and the error recovery "ate" 2 and 3 leaving me with 1. error #ERROR Well even if i figured out to reduce to D (which i probably wouldn't) I have the wrong number of items on the stack. So my tree building fails. I've tried inserting artificial tokens. I've tried rule rewriting, nothing works. I don't have enough information at any given point to reconstruct what's left of the tree. :doh: So I can do a pull parse on it, but the tree can't be generated from the input. i get my info back with a class that works like XmlReader with the pull parser but there's no way to generate a hierarchy for it because the tree is built from the leaves to the root, and a corrupt subtree will corrupt its parents due to the stack issue - and that's IF you don't wind up ending early by trying to pop from an empty stack! :( This is my life right now. I never did solve this problem last time I encountered it either. EDIT: Woo I got it working somewhat
Real programmers use butterflies
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!
-
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
-
Yes. :-D
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!
-
Yeah, I ran into that valid point face-first when I was implementing an old parser last year. I had to redesign the whole thing
Real programmers use butterflies
-
I am slightly surprised. The first compiler I tried to understand thoroughly was a Pascal compiler, and I was surprised by how great efforts it made to avoid repeated error messages. E.g. if a type declaration failed, it went on with a pseudo-type-object for that type name that allowed "any" operation. If a non-existing variable was referenced, it created the variable, of a similar forgiving pseudo-type. And so on - lots of tricks to avoid repeated and false errors. Sometimes we were frustrated by this strategy, as the "forgiving" strategy let other "real" errors pass by without an error message. This was in an age when compilation of even small projects could take minutes - it didn't take that large projects to cross the hour limit. Catching the maximum number of errors per compilation run was a quality measure of the compiler. It made perfectly sense to try to continue as far as possible after a compilation error. (And, with those compilation times, the make utility made far more sense than today!) Btw: LALR parsers (often referred to "bottom up parsers") is far better suited for going on after errors than recursive descent parser are. But in the golden years of Pascal, at least nine out of ten Pascal compilers were recursive. I guess that some of the few Pascal compilers in use today are bottom up, though.
Yeah with LALR(1) is possible to do what recursive descent can't easily do in terms of error continuation. But it's way more difficult than with an LL class parser, at least in my experience. And then there's the stack issue, which is separate since it's building process is separate than the parse, but it relies on the parser to return the correct number of items or it fails badly stack-wise. I implemented an ad-hoc technique where in I stop popping when I encounter an error (better the stack has too many nodes than not enough)
Real programmers use butterflies
-
Tested a bit, and it seems you're right. But in a file with 500 rows, one well placed bracket renders 80 errors. Now factor in how many man years MS has poured into VS. The lady witch doth protest too much, methinks
Wrong is evil and must be defeated. - Jeff Ello
Yeah. What's interesting is a team at Microsoft Research reimplemented the C# front-end to use a GLR parser like the one I've made. It's not used in production though.
Real programmers use butterflies
-
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!
-
I've got a coding problem that I don't know if there's a solution to and it's pretty important. This isn't a coding question. It's more of a rant. When a bottom up parser parses input it kind of does things backward. You get your inputs into the queue: 1. term a 2. term b 3. non-term C Then a reduce action with a rule 4. Reduce D-> a b C which tells me to pop C, b, a, and then push D, effectively "replacing" the first 3 entries with 1 entry from step 4 This is all well and good, except when there's errors in the input let's say there was an error parsing step 1 above - and the error recovery "ate" 2 and 3 leaving me with 1. error #ERROR Well even if i figured out to reduce to D (which i probably wouldn't) I have the wrong number of items on the stack. So my tree building fails. I've tried inserting artificial tokens. I've tried rule rewriting, nothing works. I don't have enough information at any given point to reconstruct what's left of the tree. :doh: So I can do a pull parse on it, but the tree can't be generated from the input. i get my info back with a class that works like XmlReader with the pull parser but there's no way to generate a hierarchy for it because the tree is built from the leaves to the root, and a corrupt subtree will corrupt its parents due to the stack issue - and that's IF you don't wind up ending early by trying to pop from an empty stack! :( This is my life right now. I never did solve this problem last time I encountered it either. EDIT: Woo I got it working somewhat
Real programmers use butterflies
.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
-
.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
-
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! :laugh: :laugh: :laugh: edit - doh!
-
Make the leaves leafs the root, and the root the leaves leafs! Then flip! Problem solved! :laugh: :laugh: :laugh: edit - doh!
well, i do already return multiple trees, but yeah no. =) I'm not flipping them :laugh:
Real programmers use butterflies
-
well, i do already return multiple trees, but yeah no. =) I'm not flipping them :laugh:
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.
-
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
