[css3] Grammar very slow due to numerous ambiguities

[kaby76]

See https://groups.google.com/g/antlr-discussion/c/8KQC7fwcXpQ

Using the latest ANTLR 4.13.2, with the official example repository's CSS3 grammar (https://github.com/antlr/grammars-v4/tree/master/css3), I generated a C++ parser to parse a simple CSS file of about 200 lines. Without adding any custom listener logic, on an M1 MacBook Pro, it takes 1 second for the first run! I'll consider that as a warm-up, but even after that, it takes 0.14 seconds each time! In contrast, my own homemade approach relying purely on string find only takes 0.002 seconds. Why is there such a performance difference? Is it because I'm using it incorrectly?

As with many of the grammars in the grammars-v4 repo, you never know what to expect.

The problem is that the css3 grammar is ambiguous. To debug the grammar, you can use "trperf" for a quick explanation of the ambiguity or "trparse --ambig" for a slow but detailed explanation of the ambiguity. These tools are from the Trash toolkit. https://github.com/kaby76/Trash. For "trparse --ambig", I had to pare down the input to a few hundred lines, otherwise it would take too long.

To name a few ambiguities, we have Decisions 55 in "ruleSet", 60 in "declaration", 98 in "fontFaceDeclaration", and 112 in "ws".

"ws" is particularly egregious because it is the most time-consuming expression. Using "trparse --ambig", and Bash diff, I found these rules to be a problem.

expr : term (operator_? term)* ;

term : number ws # knownTerm | percentage ws # knownTerm | dimension ws # knownTerm | String_ ws # knownTerm | UnicodeRange ws # knownTerm | ident ws # knownTerm | var_ # knownTerm | url ws # knownTerm | hexcolor # knownTerm | calc # knownTerm | function_ # knownTerm | unknownDimension ws # unknownTerm | dxImageTransform # badTerm ;

operator_ : '/' ws # goodOperator | Comma ws # goodOperator | Space ws # goodOperator | '=' ws # badOperator // IE filter and DXImageTransform function ;

For partial input

abbr[title] { border-bottom: 1px dotted; }

we see two parses for "1px",

examples/xxx.css.112: (expr (term (dimension (Dimension "1px")) (ws (Space " "))) (term (ident (Ident "dotted")) (ws))) examples/xxx.css.112: (expr (term (dimension (Dimension "1px")) (ws)) (operator_ (Space " ") (ws)) (term (ident (Ident "dotted")) (ws)))

(dotnet trparse -- --ambig examples/xxx.css | dotnet trxgrep -- ' //expr[.//Dimension[text()="1px"]]' | dotnet trtree -- -a)

A space should not be an operator!

Ken