- From: <bugzilla@jessica.w3.org>
- Date: Mon, 24 Feb 2014 18:21:54 +0000
- To: www-svg@w3.org
https://www.w3.org/Bugs/Public/show_bug.cgi?id=24769 --- Comment #1 from Joe Gregorio <jcgregorio@google.com> --- OK, so I think part of the problem here is my use of the ambiguous terms first-match vs longest-match. What we are really seeing here is a difference between a PEG (parsing expression grammar) and a CFG (context free grammar). http://en.wikipedia.org/wiki/Parsing_expression_grammar http://en.wikipedia.org/wiki/Context-free_grammar http://en.wikipedia.org/wiki/Comparison_of_parser_generators The BNF supplied is a valid CFG, parsers built for CFGs do backtracking, which is one way to handle the issue around the ambiguity in the "nonnegative-number" rule. The other way to handle it is to rearrange the grammar so that it is non-ambiguous. >From the page http://en.wikipedia.org/wiki/Parsing_expression_grammar: """Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.""" This isn't a theoretical problem, I am building a parser for SVG paths and as a start I copied the supplied BNF into a parser generator, unfortunately the parser generator I am using is a PEG and not a CFG parser generator: https://github.com/dmajda/pegjs#expression1--expression2----expressionn I am apparently not the only one to get tripped up by this, as this parser also has the same problem: https://www.npmjs.org/package/svg-path-parser If you change the following line in their example: , 'A25,35 -80 1,1 450,220 Z' to: , 'A25.0,35 -80 1,1 450,220 Z' then that parser will crash on what should be a valid path, since the 25 gets parsed as an"integer-constant" and leaves .0 on the input, which fails to parse as anything in the grammar. In this case I think the best solution is to rearrange the grammar slightly as suggested, as it makes it valid for both PEG and CFG. The alternative would be to add a sentence to the spec that the BNF is a CFG and not to be used in a PEG. -- You are receiving this mail because: You are the QA Contact for the bug.
Received on Monday, 24 February 2014 18:21:55 UTC