JDT Core Programmer Guide/ECJ/Parse

Parse

In classical compiler construction, the input text is tokenized by a Scanner. The resulting token stream is then fed into the Parser which creates the abstract syntax tree (AST). ECJ essentially follows this design, but in reality things are more complex, because the Java syntax is no longer amenable to a strict implementation of this approach.

Scanner

Responsibilities of the scanner:

• interpret input unicode
• recognize comments
  • recognize task tags within comments
• record line ends (for translation between linear offsets and line based positions)
• disambiguate tokens which depend on context. Some examples, why scanning needs more context than it should according to text books (cf. JLS §3.9):
  • token -> is ambiguous wrt the two single tokens - and >
  • restricted keywords are opportunistically recognized when this enables the parser to recognize a legal module declaration (inside the modular compilation unit "module-info.java").
  • restricted identifiers like var and yield must also be recognized by the scanner in certain contexts.

Two main concepts are used for token disambiguation:

• A VanguardParser, is a stripped-down parser that runs the parse automaton at a location of ambiguity to check if a specific goal can be reached using the remaining input. In particular, the VanguardParser does not produce any AST, and it does not really consume any input.
• The scanner keeps track of the current ScanContext in order to decide if a restricted keyword should be classified as a keyword or as an identifier.

To support the above, the scanner allows limited look ahead and the option to "unget" an erroneously consumed token (in order to allow re-classification).

Caveat
The above implies a few restrictions on the use of a scanner:

• many locations in JDT request partial scanning starting from a given context. If the input could possibly be a modular compilation unit, then the scanner needs to actually "parse" starting from the beginning of the text, in order to determine the ScanContext at the requested offset. This is done using ScanContextDetector which is a special VanguardParser.
• ...

Matters are further complicated in variant CompletionScanner as used for code completion.

Scanner itself is 100% handcoded, but ScannerHelper contains several tables for unicode handling. Olivier Thomann is the expert for unicode handling.

Scanner has a public variant, PublicScanner which must be updated after each relevant change in Scanner. PublicScanner shields clients from generated constants in interface TerminalTokens and maps those to stable constants in ITerminalSymbols.

Parser

Constituents of the parser:

• java.g is the grammar definition that is used by jikespg to create the following:
  • method Parser.consumeRule(int)
  • constants in interface TerminalTokens: every token detected by the scanner is represented using one of the constants in this interface. Constant names are composed of TokenName + the terminal name used in the grammar.
  • constants in interface ParserBasicInformation (used mostly by the parser automaton).

Generating the parser (see also bug 562044):

• install jikespg on your local machine
  • cf bug 562044#c17
  • cf github branch
• define a per-workspace String Substitution "JIKESPG" pointing to the location where jikespg is installed
• run scripts/build-parser.launch

Main parsing mechanism:

• the parser state is captured in various stacks, each of which is implementated by a pair of fields:
  • a field of an array type to contain the stack data
  • an int field representing the pointer to the current top element (initially -1 for: empty stack)
• method Parser.parse() contains the main loop of the parse automaton
• method Parser.consumeToken(int) generically records some information purely based on a token being consumed
• method Parser.consumeRule(int) (generated) dispatches into the individual consumeXYZ methods.
• each consume method may peek or pop elements from some stacks and push elements on one or more other stacks

Parsing modes

• in diet mode, any blocks like method bodies are skipped, which can later be filled in using dedicated methods like Parser.parse(MethodDeclaration,CompilationUnitDeclaration).
• fields Parser.methodRecoveryActivated and Parser.statementRecoveryActivated control whether or not attempts should be made to create AST despite syntax errors.

Upon any syntax error, syntax recovery happens using the following concepts:

• field Parser.currentElement holds a "recovered" element which wraps a possibly incomplete AST node
• each class below RecoveredElement models a node in the recovered tree, with generic functions for adding new child nodes etc.
• field Parser.lastCheckpoint marking a position up-to which parsing is considered "done". When hitting a syntax error, parsing will restart at the last checkpoint.
• method Parser.resumeOnSyntaxError() applies a number of heuristics to put the parser into a state where parsing can resume.

Peculiar parser rules
Grammar java.g contains a few unexpected rules:

• Rules starting with Invalid or invoking a method consumeInvalid... explicitly expect some common error situations, in order to provide specific error messages.
• Rules starting with Recovery are only invoked during syntax recovery, i.e., those may expect a valid Parser.currentElement.
• Rules of the shape ForceNoDiet ::= $empty are markers in the grammar, which do not correspond to any input text. Whenever the parser reaches such an empty non-terminal, a side effect is performed in the parser.
  • E.g.: EnumConstant ::= EnumConstantHeader ForceNoDiet ClassBody RestoreDiet ensures that the body of an enum constant is always parsed in non-diet mode.
  • Don't confuse such marker non-terminals with those rules terminating a recursion, like Argumentsopt ::= $empty

Parser Variants:

• DiagnoseParser: after detecting a syntax error, this parser heuristically tries several "repairs", and selects the repair with the smallest "distance" to the actual input. During this process, the parser automaton is repeatedly run, without producing any output, other then accept or reject.
• VanguardParser: as mentioned above, this parser is used for nested parse attempts in order to disambiguate certain tokens, that could be classified in different ways according to context.
• AssistParser with subclasses CompletionParser and SelectionParser: these parsers focus on a specific text location and implement incomplete parsing optimized for the task at hand.
  • See JDT Core Programmer Guide/Completion for complications in and around the CompletionParser
• CodeSnippetParser: parses incomplete code for the sake of evaluation
• CommentRecorderParser: used for created DOM AST
• SourceElementParser: used for building structure of Java Elements (see Java Model)
• IndexingParser: used for creating the JDT/Core index
• DocumentElementParser: used for creating the obsolete JDOM (packages org.eclipse.jdt.core.jdom, org.eclipse.jdt.internal.core.jdom).
• MatchLocatorParser: used during Java Search to provide input to the MatchLocator (which refines index matches into resolved java matches).

HOWTO: Grammar Changes

eg: Let us say you want to add a new statement, MyNewStatement. Grammar changes start with java.g - It should be a context free grammar since we use an LALR(1) parser You can add your MyNewStatement similar to that of EnhancedForStatement to the RHS of Statement, ie Statement -> MyNewStatement and then followed by the new rules (obeying the context free rule) with a few consumeMyNewStatement(), other consume* methods.

The parser generator jikespg is used to generate the parser from this grammar. You may want to take the latest bits of the jikespg from [1] since it contains a few bug fixes and then make. Additionally, the generation of parser has been made easier - ref [2]. If you want to look at the original documentation of how the parser is generated see [3].

Let us say, now you have the modified java.g and the jikespg parser ready. First run jikespg.exe java.g to check whether your grammar is LALR(1).

Assuming that it is, then you need to just run org.eclipse.jdt.core/scripts/build-parser.launch. In order to provide the path to jikespg you need to define a per-workspace String Substitution "JIKESPG", see also the usage notes inside build-parser.xml.

This would generate the files as described in [3], but what would interest you most would the Parser.java - here you will see your consumeMyNewStatement() and other consume* stubs inserted - both the method call as per the generated automata (which you should not touch) and the declaration - you would need to add code to the declaration, to reduce and possibly create a new AST Node.

The AST Node created would be the internal compiler AST Node and not the DOM AST node - they have similar/identical definitions - so you need to create something similar to org.eclipse.jdt.internal.compiler.ast.ForeachStatement, which is the enhanced for statement node of compiler AST - look at org.eclipse.jdt.internal.compiler.parser.consumeEnhancedForStatement() - internally, it creates a ForeachStatement - [we are not talking of DOM AST node - the conversion to the DOM AST Node EnhancedForStatement comes later in the ASTConverter method and is not relevant here - mentioning to avoid confusion]

The most tricky part about constructing new AST nodes is to correctly manage the various stacks of the parser. As a general rule, each consume method should consume all ast nodes mentioned on its RHS and replace them by one node representing the LHS. The first distinction to be made is between astStack and expressionStack. Less obvious is the use of intStack which is also modified inside consumeToken, e.g.

[1] https://github.com/jikespg/jikespg/tree/fixes-combined

[2] https://bugs.eclipse.org/bugs/show_bug.cgi?id=562044

[3] https://www.eclipse.org/jdt/core/howto/generate%20parser/generateParser.html

Note You can also run the jikespg separately and then bring the generated files. Once you get the files, set the env in Eclipse JIKESPG=JIKESPG_EXTERNAL to signal to the script to skip running the jikespg.