I see that modern SW basically dominated by recursive descent parsers. These parsers try grammar production and back track to an alternative one in case of failure. Suppose BNF is

program = (declaration)* "begin" (statement)*
declaration = type_declaration | variable_declaration | function_declaration
type_declaration = "range" name "to" name | "enum" (name)*
variable_declaration = name ":" type_name
statement = ...

and suppose that user has entered user entered "range 10 to '15'" when declaration expected. The parser has failed to match the first type pattern but it also failed to match other alternatives and declarations and failed to parse the program. How do you recover? Should you track the "best match", which would be location of the "range 10 to '15'" and look for keywords met afterwards or what? Which mechanisms are used in practice, in popular parser combinators and generators like JavaCC?

  • $\begingroup$ "I see that modern SW basically dominated by recursive descent parsers" -- really? My impression was that most real-world parsers in compilers used LR variants. $\endgroup$ – Raphael Jan 13 '16 at 15:12
  • 2
    $\begingroup$ You are asking lots of questions. Please restrict yourself to one per post. $\endgroup$ – Raphael Jan 13 '16 at 15:13
  • $\begingroup$ @Raphael Which many questions? $\endgroup$ – Valentin Tihomirov Jan 13 '16 at 15:19
  • 2
    $\begingroup$ I count five. "How do you recover?", "Does my idea make sense?", plus three reference requests (which we are probably not the right site for) in the last sentence. $\endgroup$ – Raphael Jan 13 '16 at 15:20
  • $\begingroup$ As you seem interested in PEG and not if CFG, arxiv.org/pdf/1405.6646.pdf seems relevant. $\endgroup$ – AProgrammer Jan 13 '16 at 19:33

One (crude) technique is to just discard input until a synchronizing token is found, one that could legally follow what we were trying to match, and which is unlikely to be omitted by the user. Like e.g. ';' in languages like Pascal or C.

Another is to add productions for typical errors in some constructs, e.g. handle a b as if it was a * b in case of expressions in a compiler for newbies.

| cite | improve this answer | |
  • $\begingroup$ Can you explain what are we trying to match? Your sync token is mine keyword, as I understand. I have presented a demo grammar. Suppose that ; must follow every declaration and statement. How can you find what can follow the ; and exploit it automatically in PEG, which simply tries every alternative and says "nothing was found to match the program" if you make a slight error? $\endgroup$ – Valentin Tihomirov Jan 13 '16 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.