Looking for some explanation on how to interpret AmbiguityInfo

[bdw429s]

Cross-posted from here.

I'm delving into the parser profiling features, which I found referenced in this article on parser performance. I'm using the Java runtime 4.x. That article has some simple code for enabling profiling and then outputting the details (which I converted from Kotlin to Java). I'm specifically digging into some ambiguities in my grammar(s) for the sake of increasing performance and allowing SLL prediction. I understand at a high level what creates ambiguities, but I'm struggling a little to determine how to interpret the information in the AmbiguityInfo instances returned by the profiler. I've done a few hours of research on Google and in the source and came up mostly empty handed. I'm aware there are some nice IntelliJ tools, but I'm not using that IDE right now and would like to still develop an understanding of what the data means on my own outside of any particular tool.

So, looking at each AmbiguityInfo instance returned by the profiler, I can get

• the rule name via the decision property (which appears to be the same as the rule name in the containing DecisionInfo class)
• The start/stop index, which I can use to get the related source from the input tokenstream
• I'm not sure how to read fullCtx, or what it means in terms that I care about or if it's just telling me the predication mode I had configured, which is obviously information I already know.
• ambigAlts bitset is a bit of a mystery in terms of turning it into something meaningful. I understand at a high level it is meant to represent the alternatives that were ambiguous, but I don't know how to map the ints in the bitset back to the actual parts of the grammar they represent. Especially when the rue in question has no explicit alternatives (using a pipe). I mean, I get how a rule with no explicit alternatives but containing asterisks or pluses can have multiple paths through, I just don't know how to take the ambigAlts bit set and translate that to the specific portions of the grammar they represent.
• configs is just a huge amount of information that I can't get to make sense in a meaningful way. I'm not not clear if all the configs related directly to the ambiguity at hand, or if it's just everything the parser knew about at the time. I found a handy bit of code
  config.context.toStrings( parser, config.state.stateNumber )
  which appears to print out a rule stack for each config, but it's not clear which of these configs relate to the specific ambiguity or what to do with the information.

I have more specific examples I can share, and the grammars are open source so I don't mind sharing them as well, but I wanted to wait to get off in the deep weeds of that and just see if I could get some direction on how to interpret the ambiguity info classes in order to create some visualization tools for myself.

Thanks!

~Brad

[kaby76]

As I am still not completely clear on all this, too, I'll first start with "ambigAlts".

Yes, it is a bitset of the number alts that are in conflict. For example,

grammar Ambig;
start : x* EOF;

x
	: e ';'
	| ID '(' ')' ';'
	;

e
	: ID '(' ')'
	| INT
	;
ID: [a-z]+;
INT: [0-9]+;
WS: [ \n\t\r]+ -> channel(HIDDEN);

For rule 2 ("x"), there are two "alts": : e ';' ("alt 1") and | ID '(' ')' ';' ("alt 2"). Alts numbering positive integers.

However, alts can be nested, e.g., foo: bar | baz ('a' | 'b') zip;. As far as I know, the alts are numbered in an in-order DFS traversal.

As far as I know, there is nothing in the runtime API that gives the alternative from an alt number. In fact, there is nothing it seems to go from a NFA state number back to a position in the grammar. (I would like this in order to implement LR0 items.)

(Note: I'm trying to figure all this out because I offer a command-line toolkit to debug grammars. trperf implements the "performance" panel in the Intellij Antlr plugin in a command-line interface. This comes in handy with the usual Bash commands sort, uniq, column, etc. IDEs cannot be used in scripts to automate grammar debugging and refactoring.)

[bdw429s]

Thanks for confirming this @kaby76 . My original question still stands now-- how do I take the alts bitset given to me in an ambuitinfo instance and map it back to the specific parts of the decision states in the grammar so I can understand what specific parts of my rules are causing the ambiguity?

[kaby76]

Just in case others want to add profiling, here are some preliminary steps.

1. If you haven't written a driver with profiling, you'll need to set up the parser for profiling, in CSharp, Java, Cpp, Dart. The API does not exist for Go.JavaScript, TypeScript, Python3. I don't know about Swift because I don't have a development box for that. (Can't install on Windows as of 2 or 3 years ago.) It is implemented in Antlr4ng.

2. Run parse as you normally would.

3. After parse, get the DecisionInfo for each Decision number, and from that all the AmbiguityInfo. Note, for Decision for which ambiguity is not detected, the list of AmbiguityInfo is empty. The DecisionInfo contains information on getting the rule name. https://github.com/kaby76/Trash/blob/e41598cd497b1f8337e1129d81aab1de99fe17e8/src/trperf/Grun.cs#L270-L275

In AmbiguityInfo, the ambigAlts is an unsigned long, with the first "alt" numbered 1. There is no such thing as a "zeroth alt", so the least significant bit (0) should always be zero--in CSharp. (May depend on the implementation.)

For example, for the abb grammar, with input robdata.sys, you should see Decision 3 with one AmbiguityInfo.

	Name	Value	Type
◢	d.ambiguities[0]	configs = {[(51,1,[42 33 $]), (117,1,[107 53 42 33 $]), (120,1,[107 53 42 33 $]), (63,1,[56 42 33 $]), (39,1,[33 $]), (45,1,[33 $]), (39,2,[33 $]), (45,2,[33 $])]}	Antlr4.Runtime.Atn.AmbiguityInfo
	▶ configs	{[(51,1,[42 33 $]), (117,1,[107 53 42 33 $]), (120,1,[107 53 42 33 $]), (63,1,[56 42 33 $]), (39,1,[33 $]), (45,1,[33 $]), (39,2,[33 $]), (45,2,[33 $])]}	Antlr4.Runtime.Atn.ATNConfigSet
	▶ ambigAlts	{{1, 2}}	Antlr4.Runtime.Sharpen.BitSet
	decision	3	int
	fullCtx	true	bool
	▶ input	{Antlr4.Runtime.CommonTokenStream}	Antlr4.Runtime.ITokenStream {Antlr4.Runtime.CommonTokenStream}
	startIndex	148	int
	stopIndex	148	int

The Decision number "3" is state "s60" in the NFA. (parser.Atn.decisionToState[3] = 60.) State s60 is in Rule 3. parser.Atn.decisionToState[3].ruleIndex = 3. Rule "3" is named "dataList". (parser.RuleNames[parser.Atn.decisionToState[3].ruleIndex] = "dataList".) To confirm, look at the abbParser.dataList.dot file. Indeed, we see Decision 3 ("d=3"/state 60) with two out transitions, both epsilon. Note, they have to be epsilon transitions. (I read code in the runtime that makes this assumption.)

Working back to the original rule, it's not so clear cut where the Decision state maps to in the rule

dataList
    : (NEWLINE | declaration NEWLINE | procedure NEWLINE)*
    ;

As I mentioned, as far as I know, there is no parse tree representation of the grammar itself available in Parser, and no map from NFA state to a point in the parse tree. This makes it really inconvenient to map the Decision state back to the grammar without redoing Thompson's construction in entirety, exactly as done in the Antlr Tool. I have a Thompson Construction implementation for an Antlr grammar, but it does not duplicate all the nuances of the Tool's implementation. (I generate more states, and more epsilon transitions. And, if you annotate Thompson's Construction with a parse tree node in the grammar, you can reverse the nodes in the NFA back to a point exactly in the grammar.) But, for this rule, you "see" via the .dot graph that the Decision 3 is the one associated with the Kleene operator, not the '|'-operators.

For more info on dataList in grammar abb, see antlr/grammars-v4#4181.

[bdw429s]

Wow, great info! Some of this I had figured out, but much of it is new. I've been working on this ANTLR-powered project for a year now but just now getting into the guts of ANTLR and there is so many terms and concepts to research.

So, what I'm hearing you saying is that there is basically no actual direct way to translate the ambiguity info into the part of the rule causing the issue, which is unfortunate. I guess generating the dot graph and then analyzing that is helpful, but without anything to know what the ordinal alt numbers correspond to, I'm not quite sure what anyone does with them! I'm new-ish to ANTLR tho, so perhaps these are new features which haven't been fleshed out quite yet, nor tooling built around them?

And lest we spend all our time on the alts, I also had questions in my OP about how to interpret the full context flag as well as the configs which are still outstanding.

[kaby76]

I was thinking more about this today. While there doesn't seem there is a mapping from an NFA state to a point in a parse tree of the grammar itself, it might be possible to generate a grammar rule from the NFA. In most situations, we can recover the rule fron the NFA since it's just a regular expression of terminals and nonterminals. The problem is left recursion as it is converted to a kleene operator.

[kaby76]

"configs" is a collection of "closures" from a state. In the classic definition from graph theory, the transitive closure G* of a directed graph G is a graph that has an edge (u, v) whenever G has a directed path from u to v. In Antlr, we're especially interested in NFA states that have epsilon transitions (i.e., no input is required to move to the target state). Also, an NFA can "call" another NFA for another rule. In Antlr, the closure of an NFA state is a "config," which is a sequence of "calls" and "returns." It represents a DFA state.

The main issue with configs is that I don't think it is that useful in understanding ambiguity. You can use the state numbers in the config to show the rules for a possible derivation, but it doesn't show you the actual different parse trees possible. ParserInterpreter is code that can enumerate the different parse trees in an ambiguous parse. The main problem for me is that much of this code does not exists in the CSharp target.

[jimidle]

Basically though, you can read your rules left to right and count. But Box grammar is really only ambiguous because of keywords being allowed as identifiers. Brad - content out the keyword alt in the id rule.

…

On Wed, Sep 11, 2024 at 19:32 Ken Domino ***@***.***> wrote: "configs" is a collection of "closures" from a state. In the classic definition from graph theory, the transitive closure G* of a directed graph G is a graph that has an edge (u, v) whenever G has a directed path from u to v. In Antlr, we're especially interested in NFA states that have epsilon transitions (i.e., no input is required to move to the target state). Also, an NFA can "call" another NFA for another rule. In Antlr, the closure of an NFA state is a "config," which is a sequence of "calls" and "returns." It represents a DFA state. The main issue with configs is that I don't think it is that useful in understanding ambiguity. You can use the state numbers in the config to show the rules for a possible derivation, but it doesn't show you the actual different parse trees possible. ParserInterpreter <https://github.com/antlr/antlr4/blob/811b7fda58bd14d7f0abc496b6fd651dfa01ed97/runtime/Java/src/org/antlr/v4/runtime/ParserInterpreter.java> is code that can enumerate the different parse trees in an ambiguous parse <https://github.com/antlr/antlr4/blob/811b7fda58bd14d7f0abc496b6fd651dfa01ed97/tool/src/org/antlr/v4/tool/GrammarParserInterpreter.java#L200-L310>. The main problem for me is that much of this code does not exists in the CSharp target. — Reply to this email directly, view it on GitHub <#4693 (reply in thread)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/AAJ7TMC7KIAG4Z3SYGCP54TZWDVKLAVCNFSM6AAAAABN62KETSVHI2DSMVQWIX3LMV43URDJONRXK43TNFXW4Q3PNVWWK3TUHMYTANRSGA2TOMQ> . You are receiving this because you are subscribed to this thread.Message ID: ***@***.***>

[bdw429s]

Yep, reserved words as identifiers is certainly one of the sources of ambiguity. My quest here is not just to fix the issue, but to understand it so I can also fix less obvious ambiguities in the future :) I can confirm that just removing keywords as IDs (as well as prefixing components) was not enough to eliminate all ambiguities in the box grammar.

[kaby76]

I ported over Parr's ParserInterpreter and getAllPossibleParseTrees in Java to CSharp for Trash. ParserInterpreter in the CSharp runtime seems to differ in the beginning of VisitState(ATNState p) (CSharp vs Java), which causes the code in CSharp to not work. But, I don't need to update the CSharp runtime--and wait however long for it to be merged. Instead, I added the corrected codes to the templates used to generate a driver via trgen, with a rudimentary enumeration of all ambiguous parse trees (right now over all decisions!). But, I can now do trparse input-file.txt --ambig | trtree -a and display all parse trees for all ambiguities. I can then do a Bash diff to see where the parse trees differ. I don't need to write a PT diff because I can easily grab a tree via an XPath expression on the command line, then use Bash diff. For example, using java20.

$ trparse ../examples/Unicode.java --ambig | trxgrep ' /*[1]' | trtree -i > a1
CSharp 0 ../examples/Unicode.java success 0.6572988
09/13-15:14:00 ~/issues/g4-current/java/java20/Generated-CSharp
$ trparse ../examples/Unicode.java --ambig | trxgrep ' /*[2]' | trtree -i > a2
CSharp 0 ../examples/Unicode.java success 0.6656184
09/13-15:14:10 ~/issues/g4-current/java/java20/Generated-CSharp
$ diff a1 a2
76,80c76,80
<                      DOT
<                       "."
<                      packageName
<                       Identifier
<                        "out"
---
>                     DOT
>                      "."
>                     typeIdentifier
>                      Identifier
>                       "out"
09/13-15:14:14 ~/issues/g4-current/java/java20/Generated-CSharp
$

I might want to add a "trdiff" because diffing ambiguities in PTs should be grouped by a decision state.

[ericvergnaud]

I ported over Parr's ParserInterpreter and getAllPossibleParseTrees in Java to CSharp for Trash. ParserInterpreter in the CSharp runtime seems to differ in the beginning of VisitState(ATNState p) (CSharp vs Java), which causes the code in CSharp to not work. But, I don't need to update the CSharp runtime--and wait however long for it to be merged. Instead, I added the corrected codes to the templates used to generate a driver via trgen, with a rudimentary enumeration of all ambiguous parse trees (right now over all decisions!). But, I can now do trparse input-file.txt --ambig | trtree -a and display all parse trees for all ambiguities. I can then do a Bash diff to see where the parse trees differ. I don't need to write a PT diff because I can easily grab a tree via an XPath expression on the command line, then use Bash diff. For example, using java20.

$ trparse ../examples/Unicode.java --ambig | trxgrep ' /*[1]' | trtree -i > a1
CSharp 0 ../examples/Unicode.java success 0.6572988
09/13-15:14:00 ~/issues/g4-current/java/java20/Generated-CSharp
$ trparse ../examples/Unicode.java --ambig | trxgrep ' /*[2]' | trtree -i > a2
CSharp 0 ../examples/Unicode.java success 0.6656184
09/13-15:14:10 ~/issues/g4-current/java/java20/Generated-CSharp
$ diff a1 a2
76,80c76,80
<                      DOT
<                       "."
<                      packageName
<                       Identifier
<                        "out"
---
>                     DOT
>                      "."
>                     typeIdentifier
>                      Identifier
>                       "out"
09/13-15:14:14 ~/issues/g4-current/java/java20/Generated-CSharp
$

I might want to add a "trdiff" because diffing ambiguities in PTs should be grouped by a decision state.

Hey Ken, I`ll happily approve a PR that alignes the C# ParserInterpreter with the Java one !

[kaby76]

@ericvergnaud I'm going to go through Parr's ambig tree enumeration code more carefully before creating a PR. Also, the code might be best moved all into the runtime, rather than some of it in the runtime and some in the tool code.