JDT Core Programmer Guide/ECJ/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.
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):
->is ambiguous wrt the two single tokens
- 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
yieldmust 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).
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.
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
- define a per-workspace String Substitution "JIKESPG" pointing to the location where jikespg is installed
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
- 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.
- 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
- MatchLocatorParser: used during Java Search to provide input to the MatchLocator (which refines index matches into resolved java matches).