[Bug 24769] SVG Path BNF is ambigious

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