antlr / antlr/antlr4

[Bug] C++ generated parser cannot parse file which Java generated parser can parse

Open
#2,147 5 comments 0 reactions 0 assignees View on GitHub
Dominant language
Java
Stars
19k
Forks
3.5k
PR merge metrics
No merged PRs in 30d

Description

We have the following case: (Antlr g4 grammar is at the bottom in a zip file)

- generate a Java parser based on a g4 file
- Java can parse the model correctly and takes about 5s
- generate a C++ parser based on a g4 file
- C++ cannot parse the model correctly and also takes about 7 min
- we also translated the C++ parser via Emscripten to WebAssembly (there we detected the bug) - does also not work

@mike-lischke: Is this issue known or are any parts of Antlr not supported in the C++ target?

(The rest is a copy from the ticket https://github.com/EmbeddedMontiArc/onlineIDE/issues/19,
all tests are taken by @0xJMR)

## Introduction
As the title fittingly describes, the questions of this issue can be sub-divided into those related to the performance and those related to the correctness of the parser. Let us tackle them one at a time.

## Performance
Performance measurements of the EmbeddedMontiArcMath parser for C++ have been performed on a system with the following specifications:

| Processor | Memory | Operating System |
| --- | --- | --- |
| Intel(R) Core(TM) i7-6500 CPU @ 2.50 GHz | 8.0 GB | Windows 10 x64 |

Furthermore, [SteeringAngleCalculator](https://github.com/EmbeddedMontiArc/EmbeddedMontiArcMath/blob/master/src/test/resources/simulator/SteeringAngleCalculator.emam) has been used as input and WebAssembly as well as C++ have been measured. Lastly, Google Chrome has been used as platform for the measurements of the WebAssembly module.

The amount of code for the test case has been kept to a bare minimum with only the necessary method calls to perform measurements on time, to perform the parsing of the model and to print some information. Compilation of the code has been performed with the highest optimization option enabled. Lastly, LL as well as SLL with LL fallback have been measured as prediction modes.

Measurements for the above described environment have yield the following results:

![c duration](https://user-images.githubusercontent.com/25683724/33638682-b81cd434-da27-11e7-9856-faf24fc2e532.PNG)
Figure 1. Time needed to parse the model with LL as prediction mode.
(C++ has parsing problems here where Java has no problem): https://github.com/EmbeddedMontiArc/EmbeddedMontiArcMath/blob/master/src/test/resources/simulator/SteeringAngleCalculator.emam#L17

![c duration sll](https://user-images.githubusercontent.com/25683724/33638738-ed5979cc-da27-11e7-9854-bbf392960947.PNG)
Figure 2. Time needed to parse the model with SLL and LL fallback as prediction mode.

Figure 1 shows us that parsing with LL prediction mode takes around 7 minutes to finish in C++. Figure 2, on the other hand, shows us that parsing with SLL with LL as fallback prediction mode takes around 5 minutes. Similar results have been measured in the case of WebAssembly.

## Correctness
A sharp eye might have already spotted that, even though the measurements have been performed on the same model, the two figures show different syntax errors. Furthermore, we know from the EmbeddedMontiArcMath parser for Java that the model should be correct. As a consequence, one can deduce that the parser is neither correct in C++ nor in WebAssembly for both LL and SLL with LL fallback.

## Conclusion
Either the current state of our grammars does not seem to be compatible with the current state of Antlr's C++ target or I have made a mistake during the implementation of the test case. For this reason, I have appended a ZIP archive holding the grammar for Antlr4 and the generated parser, lexer and listener files.

## Appendix
[EmbeddedMontiArcMathParser.zip](https://github.com/EmbeddedMontiArc/onlineIDE/files/1533496/EmbeddedMontiArcParser.zip)

The g4 grammar has been generated by MontiCore based on the grammars:
* https://github.com/EmbeddedMontiArc/EmbeddedMontiArcMath/blob/master/src/main/grammars/de/monticore/lang/embeddedmontiarc/EmbeddedMontiArcMath.mc4
* https://github.com/EmbeddedMontiArc/MontiMath/blob/master/src/main/grammars/de/monticore/lang/math/Math.mc4
* https://github.com/EmbeddedMontiArc/EmbeddedMontiArc/blob/master/src/main/grammars/de/monticore/lang/embeddedmontiarc/EmbeddedMontiArc.mc4

Contributor guide

Open the contributing guide

Research direction

Start with the EmbeddedMontiArcMath SteeringAngleCalculator.emam input, the linked grammar sources, and the attached EmbeddedMontiArcParser.zip. Reproduce parsing in the Java and C++ generated parsers using LL and SLL with LL fallback, then compare the syntax errors, completion time, and WebAssembly behavior. Done means identifying whether the discrepancy is in the grammar, the C++ target, or the test setup and documenting a confirmed correction or limitation.

Written by the indexing model from the issue text.

Assessment

Tech stack
cpp, java, wasm
Domain
compilers
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
35/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.