stuck in Antlr4.Runtime.Atn.ParserATNSimulator.Closure

[eugenelepekhin]

Hi,
I am getting parser stuck in huge recursive loop in function Antlr4.Runtime.Atn.ParserATNSimulator.Closure
My handwritten parser on the same file is working instantly.
How do I figure out what the problem is?
Thanks,
Eugene

[kaby76]

Please post your Antlr grammar and hand-written parser, and say which runtime are you using.

There could be various causes:

• You are not implementing the same grammar between Antlr and hand-written parser.
• You are not including the same semantic checks for the grammar between Antlr and hand-written parser.
• There's a bug in the Antlr runtime.

[eugenelepekhin]

My handwritten parser is at: https://github.com/eugenelepekhin/Fusion
The Antlr4 grammar in: https://github.com/eugenelepekhin/SyntaxTest
I thought I am using THE runtime. It is the one that in Antlr4.Runtime version 4.6.6.
Are there any other runtimes?
I am not sure you want to deal with lot of my code. So, for the handwritten parser there is a BNF file in the Doc folder. It probably easier to compare whit G4 files.

[kaby76]

There's a lot going on here. But, I tried to parse just a simple two-line macro. It illustrates the problem with exprList->expr->exprList-> ......

$ cat t0.txt

macro MultTest {
        LD32    A, r4
        LD32    B, r6
}

Kenne@DESKTOP-DL44R7B MINGW64 ~/issues/disc-4056/clean/Generated-CSharp
$ trparse t0.txt | trtree
CSharp 0 t0.txt success 0.0563383

( fusionProgram
  ( macro
    ( intertoken text:'\n' tt:-1
    )
    ( Macro
      (  text:'macro' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
    ) )
    ( macroName
      ( name
        ( intertoken text:' ' tt:-1
        )
        ( Identifier
          (  text:'MultTest' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
    ) ) ) )
    ( intertoken text:' ' tt:-1
    )
    ( Begin
      (  text:'{' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
    ) )
    ( macroBody
      ( exprList
        ( expr
          ( macroName
            ( name
              ( intertoken text:'\n\t' tt:-1
              )
              ( Identifier
                (  text:'LD32' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
          ) ) ) )
          ( arguments
            ( expr
              ( parameterName
                ( name
                  ( intertoken text:'\t' tt:-1
                  )
                  ( Identifier
                    (  text:'A' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
            ) ) ) ) )
            ( Comma
              (  text:',' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
            ) )
            ( expr
              ( macroName
                ( name
                  ( intertoken text:' ' tt:-1
                  )
                  ( Identifier
                    (  text:'r4' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
              ) ) ) )
              ( arguments
                ( expr
                  ( macroName
                    ( name
                      ( intertoken text:'\n\t' tt:-1
                      )
                      ( Identifier
                        (  text:'LD32' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
                  ) ) ) )
                  ( arguments
                    ( expr
                      ( parameterName
                        ( name
                          ( intertoken text:'\t' tt:-1
                          )
                          ( Identifier
                            (  text:'B' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
                    ) ) ) ) )
                    ( Comma
                      (  text:',' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
                    ) )
                    ( expr
                      ( parameterName
                        ( name
                          ( intertoken text:' ' tt:-1
                          )
                          ( Identifier
                            (  text:'r6' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
    ) ) ) ) ) ) ) ) ) ) ) ) )
    ( intertoken text:'\n' tt:-1
    )
    ( End
      (  text:'}' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
  ) ) )
  ( intertoken text:'\n' tt:-1
  )
  ( EOF
    (  text:'' tt:0 chnl:DEFAULT_TOKEN_CHANNEL
) ) )

The parser is not recognizing the end of an expr#Call. The entire string LD32 A, r4 LD32 B, r6 is one expr#Call. The Antlr grammar has an infamous anti-pattern of ambiguity that I've seen many times before. exprList can derive expr expr => Identifier Identifier, which conflicts with expr deriving macroName arguments => Identifier Identifer. The parser tries all possible combinations of expr#Call and exprList, reading ahead until it hits the label. (I wonder if Antlr can detect this pathological pattern and not "go down the rabbit hole" so to speak? I think it can.)

I don't know for sure how you force the automaton to break at the end of the expr#Call in the macro call, but it looks like you do that in your Fusion C# code with semantic information. The hand-written parser uses in SecondPass() semantic information of a predefined table of "macros" to not read too far. See this fetch, and count. Presumably in FirstPass() you build up a "macro table" given the file "CPU.inc.asm" which you don't provide, and use that on SecondPass() to disambiguate.

The grammar is not the same grammar rules because not only do you use two passes, the SecondPass() implements a precedence chain of rules to recognize an expression in the C# code (ParseExpression() calls ParseOr() calls ParseAnd(), etc.), where as you use Antlr's alt-based structure to recognize an expr. Your hand-written parser doesn't seem to implement the precedence the same way as what you gave Antlr.

You can fix this by writing your driver for Antlr in the same way: do two passes, with the first gathering macro definitions, and the second pass using semantic predicates to stop certain alts from happening. The semantic predicate MUST go at the beginning of the alt (just after the '|') because there is no such thing as backtracking in Antlr!! (Antlr is basically an NFA interpreter that keeps tack of many states the parse can be in.

You can probably then keep your expr relatively unchanged and fix the "stuck looping" by adding a semantic predicate.

I highly recommend that you use Intellij to debug your grammar. You can click on the parse tree "hierarchy" nodes and see what the parser decides. Unfortunately the moment you add a semantic predicate the tool starts to become useless because it does not evaluate the predicates.

Finally, use Antlr4BuildTasks and Antlr4.Runtime.Standard.

[eugenelepekhin]

I am actually doing two passes in Antlr version too. The language doesn't require macro to be defined before it get used. Plus, labels can be used before they are declared. So, the two passes are the only way.
In Antlr version I am trying to use the same grammar in both passes. The first pass collects all the macro definitions with all parameters and labels. The rest of the macro body can be parsed incorrectly in the first pass. In the second pass the parsing should build the correct parse tree.
I actually reduced the grammar to simplify reading. The call defined in expr is like this:

	| {IsMacro0()}? macroName			#Call
	| {IsMacroN()}? macroName arguments	#Call

and the predicates defined:

@parser::members {
	/*
	This section is working in two passes of the compiler.
	The predicates field is set only in second pass.
	So, for the first pass it treats all identifiers as macro calls with as many parameters as possible.
	That allows to parse through all the macro calls.
	On the second pass all the macros are known and parameters are declared.
	So, the correct value of IsMacro0 and IsMacroN can be calculated.
	*/
	public Predicates predicates = null;
	bool IsMacro0() => predicates != null && predicates.IsMacro0(CurrentToken.Text);
	bool IsMacroN() => predicates == null || predicates.IsMacroN(CurrentToken.Text);
}

So, as you can see in the first pass all the calls are favorite macro name with as many arguments as possible.

But now it seems me I will need to do two grammars for two passes.

[kaby76]

You can either have two grammars, one for each pass, or one that has symbol renaming so different rules with the same name don't clash. This is where I wish there were concepts of packages, classes, and access modifiers existed in grammars. But that's another story. In any case, your Antlr grammar can be easily fixed I think.

[KvanTTT]

Honestly, ANTLR generates code far from optimal, and a lot of optimizations can be applied. Also, the runtime also can be optimized.

[kaby76]

True, but the assumption that parsing will "work" just fine given an ambiguous grammar is probably wrong. I don't know if the grammar in this discussion is ambiguous, but many problems like these can be attributed to the fact that the grammar itself has problems. That's where I would look first, not Antlr.