sharwell / antlr4 Goto Github PK

View Code? Open in Web Editor NEW

This project forked from antlr/antlr4

16.0 16.0 7.0 62.39 MB

License: Other

Java 93.71% ANTLR 2.66% GAP 3.63%

antlr4's People

Contributors

Stargazers

Watchers

Forkers

jinminsik savaki johnwashburn weltond xueqian jmelnick-atlantis tanas7

antlr4's Issues

Reduce contention in DFA

In multithreaded parsing scenarios, contention in DFAState.getTarget and DFAState.setTarget can increase CPU usage dramatically, according to the following report.
http://stackoverflow.com/q/23120555/138304

The following image shows the performance improvement of the rm-contention branch as of commit 57a77e1. The test was performed with 20 threads on a machine with 4 cores + hyperthreading.

Implement support for NONCONFORMING_LR_RULE

Currently NONCONFORMING_LR_RULE is not enabled in the optimized fork because it prevented the indirect left recursion elimination feature from running.

Preserve DFAState cache for context-sensitive DFA when possible

When a DFA is made context sensitive and always_try_local_context is true, clearing the DFAState cache for the DFA will force the previously cached states to be recomputed.

Reduce memory overhead in getConflictingAlts

The current implementation of ParserATNSimulator.getConflictingAlts uses multiple maps for intermediate storage of configs. It may be possible to implement the method using an array sorted like ATNConfigSet.toString to improve performance.

Support runtime metadata for ATN nodes

It would be nice to be able to specify terminal options in the grammar which generate metadata information which is emitted as part of the serialized ATN, and can be examined at runtime. Such a feature would greatly aid tools like Xtext which rely on extended semantic information to perform actions at runtime.

Move parser action blocks to their own methods (similar to lexers)

In order to truly support an interpreter-only parsing algorithm, the interpreter will need the ability to directly execute grammar actions. The availability of an interpreted parsing mode is the ideal situation for advanced code-completion and other IDE features, with the current -Xforce-atn option to the ANTLR tool in place as a band-aid.

Provide more readable result for org.antlr.v4.runtime.TokenStream#getText(java.lang.Object, java.lang.Object)

Hi Sam(@sharwell),

   When I develop the new parser Parrot for Groovy programming language,

I find the text of tokens generated by antlr4 are a bit hard to read and ambiguous, e.g.

class X {a b

You can see, a and b are concatenated without any separtors:

Unexpected input: 'ab' at line: 1, column: 12

Currently org.antlr.v4.runtime.TokenStream#getText(java.lang.Object, java.lang.Object) is used.
Could you please provide more readable getText method? (e.g. remaining text of the hidden channel tokens) Or give me some hints to implement it by myself? Thanks in advance!

Optimize storage of the PredictionContext cache

The PredictionContext cache stores objects in a HashMap which does not use memory efficiently. A B-tree Set implementation would reduce the cache overhead by 90%.

@baseContext does not work

Hi Sam,

I find @baseContext does not work as expected: LambdaParametersContext does not extend StandardLambdaParametersContext. Could you have a look? Thanks in advance!

lambdaParameters
@baseContext{ standardLambdaParameters }
    :   LPAREN formalParameterList? RPAREN
    ;

standardLambdaParameters
    :   LPAREN formalParameterList? RPAREN
    |   variableDeclaratorId
    ;

    public static class LambdaParametersContext extends GroovyParserRuleContext {
    ...
    }

Imported parser grammar with left-recursive fails to build

This same issue persists in the C# side: antlr#670

...since the fix on the issue above doesn't seem to have been included yet. This commit appears to be the right fix, at least from what I read in the code: antlr@4f0f361

I have two lexer grammars (one inherits from the other), one parser grammar, and one combined and/or parser at the top. Whether I leave it combined or I set it to parser doesn't matter.

Error   38  Unknown build error: Exception in thread "main" java.util.NoSuchElementException: token index 26 out of range 0..20 Trilogy.Excel.Grammar
Error   39  Unknown build error:    at org.antlr.runtime.BufferedTokenStream.get(BufferedTokenStream.java:154)  Trilogy.Excel.Grammar
Error   40  Unknown build error:    at org.antlr.v4.parse.GrammarToken.getLine(GrammarToken.java:57)    Trilogy.Excel.Grammar
Error   41  Unknown build error:    at org.antlr.runtime.tree.CommonTreeNodeStream.hasPositionInformation(CommonTreeNodeStream.java:208)    Trilogy.Excel.Grammar
Error   42  Unknown build error:    at org.antlr.runtime.tree.CommonTreeNodeStream.remove(CommonTreeNodeStream.java:116)    Trilogy.Excel.Grammar
Error   43  Unknown build error:    at org.antlr.runtime.misc.LookaheadStream.consume(LookaheadStream.java:97)  Trilogy.Excel.Grammar
Error   44  Unknown build error:    at org.antlr.runtime.tree.TreeParser.matchAny(TreeParser.java:118)  Trilogy.Excel.Grammar
Error   45  Unknown build error:    at org.antlr.v4.parse.BlockSetTransformer.topdown(BlockSetTransformer.java:328) Trilogy.Excel.Grammar
Error   46  Unknown build error:    at org.antlr.v4.parse.BlockSetTransformer.topdown(BlockSetTransformer.java:24)  Trilogy.Excel.Grammar
Error   47  Unknown build error:    at org.antlr.runtime.tree.TreeRewriter$2.rule(TreeRewriter.java:111)    Trilogy.Excel.Grammar
Error   48  Unknown build error:    at org.antlr.runtime.tree.TreeRewriter.applyOnce(TreeRewriter.java:61)  Trilogy.Excel.Grammar
Error   49  Unknown build error:    at org.antlr.runtime.tree.TreeRewriter$1.pre(TreeRewriter.java:93)  Trilogy.Excel.Grammar
Error   50  Unknown build error:    at org.antlr.runtime.tree.TreeVisitor.visit(TreeVisitor.java:56)    Trilogy.Excel.Grammar
Error   51  Unknown build error:    at org.antlr.runtime.tree.TreeRewriter.downup(TreeRewriter.java:97) Trilogy.Excel.Grammar
Error   52  Unknown build error:    at org.antlr.runtime.tree.TreeRewriter.downup(TreeRewriter.java:86) Trilogy.Excel.Grammar
Error   53  Unknown build error:    at org.antlr.v4.tool.GrammarTransformPipeline.reduceBlocksToSets(GrammarTransformPipeline.java:89)  Trilogy.Excel.Grammar
Error   54  Unknown build error:    at org.antlr.v4.analysis.LeftRecursiveRuleTransformer.translateLeftRecursiveRule(LeftRecursiveRuleTransformer.java:148) Trilogy.Excel.Grammar
Error   55  Unknown build error:    at org.antlr.v4.analysis.LeftRecursiveRuleTransformer.translateLeftRecursiveRules(LeftRecursiveRuleTransformer.java:95) Trilogy.Excel.Grammar
Error   56  Unknown build error:    at org.antlr.v4.semantics.SemanticPipeline.process(SemanticPipeline.java:95)    Trilogy.Excel.Grammar
Error   57  Unknown build error:    at org.antlr.v4.Tool.processNonCombinedGrammar(Tool.java:397)   Trilogy.Excel.Grammar
Error   58  Unknown build error:    at org.antlr.v4.Tool.process(Tool.java:384) Trilogy.Excel.Grammar
Error   59  Unknown build error:    at org.antlr.v4.Tool.processGrammarsOnCommandLine(Tool.java:343)    Trilogy.Excel.Grammar
Error   60  Unknown build error:    at org.antlr.v4.CSharpTool.main(CSharpTool.java:59) Trilogy.Excel.Grammar

Implement eager pruning of shadowed configs

In local prediction, a config is shadowed if a higher-priority configuration (according to conflict resolution rules) consumes a superset of its potential inputs. Shadowing occurs in at least the following cases:

The local configuration (1, 1, [3]) accepts a superset of the inputs of (1, 1, [3 4]) since the invoking state 4 will be in the global follow of state 3.
The local configuration (1, 1, []) is ambiguous with the configuration (1, 2, []), but the former will always be chosen according to min-alts conflict resolution policy.
The local configuration (1, 1, []) is ambiguous with the configuration (1, 1, [], {1:0}?). The predicated config is shadowed by a containing unpredicated config. Note: pruning predicated configs is only valid if the rules for predicate resolution are changed from the "first true predicate" policy to a "minimum valid alt" policy.

Use factory methods to create parser context objects

In order to truly support an interpreter-only parsing algorithm, the interpreter will need the ability to construct context objects without resorting to reflection. The availability of an interpreted parsing mode is the ideal situation for advanced code-completion and other IDE features, with the current -Xforce-atn option to the ANTLR tool in place as a band-aid.

Integrate semantic predicate evaluation with the DFA

The result of semantic predicate evaluation can be incorporated into the DFA edge tables similar to the way full-context transitions are included. This will allow early evaluation of the predicates inside of execDFA, which opens the possibility of using predicate evaluation to reduce lookahead requirements.

Optimize storage of configs in the DFA

Memory consumed by the DFA cache is dominated by the ATNConfigSet associated with each DFAState. By storing a compressed form which can be used to reconstruct the actual ATNConfigSet in the event of ATN failover, memory usage could improve by over 85%.

RuleDependencyProcessor reports wrong element for multiple dependencies

In the following code, if the expected version is 0 then the error is reported for the first @RuleDependency annotation when it should be reported for the second.

@RuleDependencies({
    @RuleDependency(recognizer=MyParser.class, rule=RULE_myRule, version=0),
    @RuleDependency(recognizer=MyParser.class, rule=RULE_myRule, version=1),
})

Exception in thread "main" java.lang.NullPointerException
    at org.antlr.v4.codegen.model.RuleFunction.addContextDecl(RuleFunction.java:331)
    at org.antlr.v4.codegen.ParserFactory.tokenRef(ParserFactory.java:160)
    at org.antlr.v4.codegen.BlankOutputModelFactory.stringRef(BlankOutputModelFactory.java:88)
    at org.antlr.v4.codegen.OutputModelController.stringRef(OutputModelController.java:403)
    at org.antlr.v4.codegen.SourceGenTriggers.terminal(SourceGenTriggers.java:1581)
    at org.antlr.v4.codegen.SourceGenTriggers.atom(SourceGenTriggers.java:1307)
    at org.antlr.v4.codegen.SourceGenTriggers.blockSet(SourceGenTriggers.java:1066)
    at org.antlr.v4.codegen.SourceGenTriggers.atom(SourceGenTriggers.java:1327)
    at org.antlr.v4.codegen.SourceGenTriggers.labeledElement(SourceGenTriggers.java:828)
    at org.antlr.v4.codegen.SourceGenTriggers.element(SourceGenTriggers.java:594)
    at org.antlr.v4.codegen.SourceGenTriggers.alt(SourceGenTriggers.java:427)
    at org.antlr.v4.codegen.SourceGenTriggers.alternative(SourceGenTriggers.java:335)
    at org.antlr.v4.codegen.SourceGenTriggers.block(SourceGenTriggers.java:270)
    at org.antlr.v4.codegen.OutputModelController.buildNormalRuleFunction(OutputModelController.java:306)
    at org.antlr.v4.codegen.OutputModelController.buildRuleFunction(OutputModelController.java:193)
    at org.antlr.v4.codegen.OutputModelController.buildParserOutputModel(OutputModelController.java:119)
    at org.antlr.v4.codegen.CodeGenerator.generateParser(CodeGenerator.java:156)
    at org.antlr.v4.codegen.CodeGenPipeline.process(CodeGenPipeline.java:82)
    at org.antlr.v4.Tool.processNonCombinedGrammar(Tool.java:426)
    at org.antlr.v4.Tool.process(Tool.java:390)
    at org.antlr.v4.Tool.processGrammarsOnCommandLine(Tool.java:343)
    at org.antlr.v4.Tool.main(Tool.java:190)