ERROR CHECKING IMPLEMENTATION

Can you implement an error handling?

In case of error, we can be insert correct token and using synchronizing token method.
7-parsing-error.pdf

Can you help me to implement two methods for error recovery?

I need to:

insert function (insert token pag. 3)
synchronizing token (pag. 4).
Here you can find what I'm saying.
7-parsing-error.pdf

[digitalheir]

Eh. Are you a spam bot?

[digitalheir]

Oh OK my Android device wouldn't open the PDF so I thought it was a virus, but I can open it now. Let me see.

[digitalheir]

This is a very nice idea. A bit what I was getting at in #1 except I didn't put any thought in it. We could definitely implement this. You may be ableto hack ittogether using the postScan function.

The slides are about shift-reduce parsers. I can't offhand say how they compare to earley error handling and probabilities

[digitalheir]

Idea: implement a ParseIterator that performs the predict, scan, complete cycle based on the user-passed iterator and additionally contains a stack for tokens to insert or "delete" dynamically at runtime

A very nice idea! Congratulations!

[digitalheir]

I don't really understand yet how error handling should work for Earley parsers (and I don't really know about shift reduce parsers in general). Do you have any idea how this kind of error handling fits in with Earley parsing?

Like, is it when a certain token is scanned, but it can't advance any active states? That was my interpretation of it. But it can happen that the parser happily predicts, scans and completes, but only at the very end find out it can't actually make a sentence out of the states (ie. it can't complete the goal state). I don't really know how to take care of this except telling the user: hey, I tried to do this but it's not a sentence.

Is the synchronizing token idea something where you add rules to your grammar say: I know this is an error, and you deal with it in this way?

I'll need to read more about how to do this.

Based on what he says to the PDF, the error handling in the Earley parser can take place in this manner. Given a context-free grammar and an input string, the parser performs its prediction cycle, scanning and completion (the classic Earley parser).
Error handling is a qualcos most advanced in the sense that:

The user enters a string, the parser must say if the input string is properly generated by the grammar (if so it's all ok).
If the input string has some words (tokens) that do not belong to the grammar, the parser can be taken:

1. eliminate the wrong token (for example by replacing it with a label "#" to indicate that it is not recognized and therefore eliminated)

2. insert in place of the wrong token, another token more likely (symbol of production of the same head with the highest probability).
   If every symbol has the same probability, we must use directly synchonizing token method.

The token synchronizing technique is used when we can not handle the error situation.
A synchronizing token may be for example a sentence recognizer end as the dot ( ".").
If we can not correct the token, we arrive at a fixed point (synchronizing token), we throw it all away and start over.
If we able to correct the input string, print the correct string.

Do you understand what I mean?

[digitalheir]

If I understand correctly: when the parser reads a sentence left to right it might encounter a token E that it cannot understand. It will go into a kind of panic mode and back up until it get to a point where it can say "ignore all tokens from here, past E, up to the synchronizing token", and resume parsing.

It is difficult to determine where the point is from where the parser can resume parsing, but the presentation that you sent suggests that the user makes add rules to the grammar that specify what these points are.

So I will add a special type of <error> terminal which allows you to write "backup" rules in case something goes wrong. The parser will then act as if the predict phase predicted the backup rule.

Sum -> Num Plus Num
Plus -> +
Num -> 1
Num -> <error>

A sentence like 1 + 1 will then generate the following parse tree:

       Sum
 /      |     \
Num    Plus   Num
 |      |     |
1       +     1

And a sentence like 1 + 2 will then generate the following parse tree:

       Sum
 /      |     \
Num    Plus   Num
 |      |     |
1       +     <error>

I'm making some progress on this.

I've already implemented two kinds of simpler error handling in #7, in case of unknown tokens: either just drop the unknown token or make it have any terminal type, and I have a pretty good idea of how to implement these synchronizing tokens.

[digitalheir]

Then another point: how to insert? At what point do you decide you want to insert a token, and at what position will you insert the token?

Your source says

Burke-Fisher error repair tries every possible single-token insertion, deletion or replacement at every point in the input up to K tokens before the error is detected

That's pretty spicy, I don't know how useful this will be.