Parser Generator Reference
Gram is the part of Lexigram that generates a parser.
The parser consumes an input stream of tokens issued by the lexer and verifies that it can be generated by the grammar. During that process, the derivations let the parser call grammar-related trait methods, which allows the user to retrieve the correspondence between grammar elements (nonterminals and terminals) and the input text.
The grammar production rules are defined in a human-readable language described in this reference. Similarly to the lexer, the code of the “low-level” parser already exists in the lexigram-core crate; its main object is Parser. Gram takes a grammar and generates the data required by Parser and the source code that allows the user to interact with Parser while it parses the input.
The language used to describe the grammar is very similar to that of the ANTLR. However, the generated code is very different, since Lexigram generates either an LALR parser or a predictive, non-recursive LL(1) parser, not a recursive-descent, adaptive LL(*) parser.
Notation
We’re using the following conventions in the grammar:
- Terminals are written in upper camel case (since they come from the lexicon):
Colon,SymEof. - Nonterminals are written in lower snake case:
rule,rule_name. - We usually write each production alternative on one line, indented, with the
|in the first column:prod: prod_alt | prod '|' prod_alt ;
Those conventions are not enforced by Gram.
There are some differences between what is supported in top-down and bottom parsers. We’ll use the following notation to differentiate them:
- LL means LL(1) parser
- *LR means LALR and future bottom-up types of parsers
Main Concepts
The grammar defines the structure of the language to be parsed. From the grammar, Gram generates the source code of the parser, which comprises the following parts:
- The parsing table for a predictive top-down parser, the symbol table, and other data.
- The
build_parser()method that creates aParserinstance from those data—what we call the “low-level parser”. - The listener, a trait that the user must implement to interact with the
Parserinstance. - The wrapper, the connection between the
Parserinstance and the listener. - Optionally, a template of the nonterminal types, and a template of a basic listener implementation.
Grammar Structure
The grammar begins with a header that defines the name of the parser:
grammar LexiParser;
The rest of the grammar is a set of rules, where the first one defines the top level of the grammar.
Each rule defines a nonterminal, the name on the left-hand side of :. The productions on the right-hand side are a string of symbols, which are terminals defined in the lexicon, nonterminals defined in the grammar, and operators.
file:
header? file_item*
;
file_item:
option
| declaration
| rule
;
header:
'lexicon' Id ';'
;
declaration:
'mode' Id ';'
;
option:
'channels' '{' (Id / ',')+ '}'
;
// ...
A normalized grammar rule is made of one or several production alternatives. The only operator allowed in a normalized rule is the “or” symbol |, which separates the alternatives:
file_item:
option
| declaration
| rule
;
Gram accepts non-normalized grammars, where other operators can be used:
(and)for grouping items:message: ('Note' | 'Warning' | 'Error') Message;*and+for repetitions, and?for optional items:file: header? file_item*;/with+for token-separated repetitions (/and*for potentially empty repetitions isn’t supported):actions: (action / ',')+; // action ',' action ',' action ...<...>for attributes that guide the parser generation:<resolve> // resolve ambiguous rule expr: '-' expr | expr <R> '^' expr // right-associative | expr ('*' | <P> '/') expr // same precedence | expr ('+' | <P> '-') expr | Id | Num ;
The original grammar undergoes a series of transformations to obtain a normalized LL(1) grammar, before Gram generates the parsing table and the source code of the listener and the wrapper.
Listener
The listener is mainly a trait that declares methods for each rule. The user implements those trait methods with the actions that must be performed when the rules are processed during the parsing. To some extent, it corresponds to the source code written on the right-hand side of grammar rules in some parser generators like Yacc and Bison.
Each nonterminal (rule name) can be associated to a value of a user-defined type. The parser calls a trait method bound to each nonterminal once its rule has been fully parsed, and the user implementation code of the method returns the nonterminal value based on the given context, which includes the values of the rule items: other nonterminals and variable tokens like string and numerical literals.
As an example, let’s consider a simple lexicon and grammar. Id and Num are variable tokens representing an identifier name and a numerical value, respectively, and the grammar defines two rules for the nonterminals s and val:
// lexicon file
Equal : '='; // fixed token
Exit : 'exit'; // fixed token
Return : 'return'; // fixed token
Id : [a-z][a-z0-9]*; // variable token
Num : [1-9][0-9]*; // variable token
// grammar file
s:
Id '=' val
| 'exit'
| 'return' val
;
val:
Id
| Num
;
Init and Exit Methods
Gram generates the following listener trait, that the user must implement on a listener object:
pub trait TestListener {
// ...
fn init_s(&mut self) {} // LL only
fn exit_s(&mut self, ctx: CtxS) -> SynS;
fn init_val(&mut self) {} // LL only
fn exit_val(&mut self, ctx: CtxVal) -> SynVal;
}
It also generates the context types used in the callback methods:
pub enum CtxS {
/// `s -> Id "=" val`
V1 { id: String, val: SynVal },
/// `s -> "exit"`
V2,
/// `s -> "return" val`
V3 { val: SynVal },
}
pub enum CtxVal {
/// `val -> Id`
V1 { id: String },
/// `val -> Num`
V2 { num: String },
}
For simple rules like above, a call to the corresponding init method is made when the next production is determined by the parser; for example, if the "return" token is received when s is one of the potential next nonterminals, the rule s -> 'return' val is selected and the init_s(&mut self) method is called. It can be used to initialize any data before the rule is actually parsed, so before any sub-rule is triggered, like val. There are default empty implementations for the initialization methods, so they’re optional.
Important
Init methods are not supported in *LR parsers.
Unlike top-down parsers, bottom-up parsers determine which production to derive only once all its symbols have already been parsed, including other nonterminals. For instance, the
init_s(…)method could only be called right beforeexit_s(…), which makes it redundant. Besides, it would be called after the init and exit methods of all the nonterminals included in the production, likeval; this defeats its initialization purpose and could be very confusing.
A call to the corresponding exit method is made once the production has been entirely parsed, including all the nonterminals it contains (val in the same example). This call gives all the necessary information about what has been parsed in a context object, which specifies which rule alternative was parsed and the values of the relevant nonterminals and tokens. In the example above, the exit_s(&mut self, ctx: CtxS) method is called with ctx equals to CtxS::V3 { val }, val being the value of the nonterminal.
If the parsed text is “return 5”, the following calls are made:
if cfg!(LL) { // LL only
listener.init_s(); // "return" selected the rule `s -> Return val`
listener.init_val(); // "5" selected the rule `val -> Num`
}
let val = listener.exit_val(CtxVal::V2 { num: "5".to_string() });
let s = listener.exit_s(CtxS::V3 { val });
Each nonterminal can have a value, but it’s only optional. This choice is specified in the options given to Lexigram when it generates the parser source code. If the nonterminal s has a value, exit_s is generated with a return value of type SynS, this type being defined by the user. If s has no value, exit_s has no return value and the trait definition includes a default empty implementation:
fn exit_s(&mut self, ctx: CtxS) {}
If the --spans option was given (or OptionsBuilder::span_params(true) programmatically), an extra parameter gives to the exit methods the location of the symbols in the input stream. It can be used to pinpoint the location of custom error messages in the input stream, for instance:
fn exit_s(&mut self, ctx: CtxS, spans: Vec<PosSpan>) -> SynS;
fn exit_val(&mut self, ctx: CtxVal, spans: Vec<PosSpan>) -> SynVal;
Error Recovery Methods
pub trait TestListener {
// ...
fn drop_nt_value(&mut self, value: &EnumSynValue) {}
fn get_recovery_value(&mut self, nt: VarId, last_dropped: Option<EnumSynValue>, err_span: &PosSpan)
-> RecoveryNtValue { RecoveryNtValue::Abort }
fn syntax_error_recovered(&mut self) {}
// ...
}
When a syntax error is detected by the parser, it tries to resynchronize automatically by dropping some content, either in the stream or on its stack, or both. A few methods allow the user to get feedback and to control the process to some extent.
-
drop_nt_value(…)is called to warn the user when a nonterminal has been dropped. The content is given in argument. -
get_recovery_value(…)is called when a value must be invented for a nonterminal. For example, a syntax error was detected inside an expression, and the parser couldn’t make anything out so it dropped all the content of the expression and asks the user what value to return for the expression nonterminal.The value can be a neutral, default value, or a special value that marks the error, depending on how the user wants to manage it. If other nonterminals were dropped earlier, the last one is provided in argument; sometimes, that value can be used if it’s the same type of nonterminal.
-
syntax_error_recovered(…)is called once the parser has resynchronized after a syntax error.
Other General Methods
There are a few other methods that the parser calls in some circumstances:
pub trait TestListener {
fn check_abort_request(&self) -> Terminate { Terminate::None }
fn get_mut_log(&mut self) -> &mut impl Logger;
fn handle_msg(&mut self, span_opt: Option<&PosSpan>, msg: LogMsg) {
self.get_log_mut().add(msg);
}
fn intercept_token(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId { token }
fn hook(&mut self, token: TokenId, text: &str, span: &PosSpan) -> TokenId { token }
fn exit(&mut self, _s: SynS) {}
fn abort(&mut self, terminate: Terminate) {}
// ...
}
-
The
check_abort_request(…)method is called after each parser cycle through its table, so approximately after each call to another listener method (mainly init and exit methods). It can be used to abort the parsing if an irrecoverable error is detected; for example, ifNumcannot be parsed as a number orIdhasn’t been declared. ReturningTerminate::Abortrequests the parser to abort its parsing procedure immediately. It’s the user’s choice to use this request or to manage the errors in the listener, but it’s often easier to abort if there’s a risk that an error generates too many problems down the line.A simple way to use the abort request is to set an
abortflag in the listener object and to return its value in that method. If one of the exit methods detects a problem, it sets the flag before returning, which ensures the parsing won’t go any further.impl TestListener for MyTestListener { fn check_abort_request(&self) -> Terminate { if self.abort { Terminate::Abort } else { Terminate::None } } // ... }The listener can also request to end the parsing gracefully, without raising an abort error. It can be used if the listener detects the end of the relevant text to parse before the stream ends. For example, Lexigram uses that feature when the lexicon and the grammar are in a single stream: when the keyword
grammaris met, the lexicon parser concludes the parsing of its part and hands over the task to the grammar parser. This doesn’t cancel other errors like syntax errors, of course.To do that,
check_abort_requestmust returnTerminate::Conclude.Once the parsing has acknowledged the abort request, it calls the
abort(…)listener method, which can be used to do post-parsing clean-up and report the event in the log. Theterminateargument specifies the reason (Terminate::AbortorTerminate::Conclude).The
exit(…)method isn’t called in the event of an abort, even if it’sTerminate::Conclude, so you mustn’t forget to call any post-parsing or clean-up code from bothexit(…)andabort(…)if you’re using that feature. -
For practical reasons, the listener must own a log object, in which all the warnings and errors will be recorded. The
get_mut_log(&mut self)method returns a reference to that log object whenever the parser needs to record something.pub struct MyTestListener { log: BufLog, // ... } impl TestListener for MyTestListener { fn get_mut_log(&mut self) -> &mut impl Logger { &mut self.log } // ... } -
Related to the log is the
handle_msg(…)method, which allows to intercept the log messages issued by the low-level parser. The default implementation outputs those messages to tthe log, but it’s possible to modify the messages or even disable them.For example, the listener implementations of Lexigram use it to show the errors in the input file:
impl GramParserListener for GramListener<'_> { // ... fn handle_msg(&mut self, span_opt: Option<&PosSpan>, mut msg: LogMsg) { if let Some(span) = span_opt { if let Some(msg_text) = msg.get_inner_str_mut() { let text = self.annotate_text_ascii(&span); *msg_text = format!("{msg_text}\n\n{text}\n"); } } self.get_log_mut().add(msg); } // ... }Tip
The method
annotate_text_ascii(…)in the example above is a trait method that becomes available when the listener implements the traitlexigram_core::text_span::GetLine. It returns the lines that include the text inspan, emphasizing the relevant part:- ERROR : at 62:9-11, <L=fun_params> uses the rule nonterminal instead of a new one for the loop: | 62| Id (<L> Comma Id)* | | ^^^Another method,
annotate_text(…), uses ANSI colours to emphasize the relevant part. In the current version, Lexigram actually use one or the other depending on the command-line ANSI mode. -
The
intercept_token(…)andhook(…)methods allow the user to intercept tokens and change their value.intercept_token(&mut self, token: TokenId, text: &str, span: &PosSpan)allows the user to intercept any token and to change it before it’s used by the parser. Since it’s called for every token, it may have a performance impact.hook(&mut self, token: TokenId, text: &str, span: &PosSpan)is a lighter way to intercept only specific tokens in LL; in *LR, it is equivalent tointercept_token(…). This method is generated only if the hooks are declared in the lexicon.See the lexer reference for more details.
-
Finally, the
exit(&mut self, s: SynS)method is called once the top rule exits, and gives the value of its nonterminal, if it exists, as aSynStype. There is a default empty implementation, which makes it optional. It can be used to store the final result of the parsing in the listener object or to call any post-processing required at that level, like finalizing the AST tree.So the entire series of calls, if the parsed text is “return 5”, is actually closer to the following sequence:
if cfg!(LL) { // LL only listener.init_s(); // "return" selected the rule `s -> Return val` listener.init_val(); // "5" selected the rule `val -> Num` } let val = listener.exit_val(CtxVal::V2 { num: "5".to_string() }); if listener.check_abort_request() { return Err(ParserError::AbortRequest) } let s = listener.exit_s(CtxS::V3 { val }); if listener.check_abort_request() { return Err(ParserError::AbortRequest) }; listener.exit(s);
Wrapper
The wrapper is entirely implemented in the generated source code. It calls the listener methods and keeps track of the data: nonterminal / terminal values and position of the symbols in the original input text.
pub struct Wrapper<T> {
listener: T, // user's listener instance
stack: Vec<EnumSynValue>, // nonterminal values
stack_t: Vec<String>, // terminal values
stack_span: Vec<PosSpan>, // positions
// ...
}
impl<T: TestListener> Wrapper<T> {
pub fn new(listener: T, verbose: bool) -> Self {
Wrapper {
listener,
// ...
}
}
pub fn get_listener(&self) -> &T {
&self.listener
}
pub fn get_listener_mut(&mut self) -> &mut T {
&mut self.listener
}
pub fn give_listener(self) -> T {
self.listener
}
// ...
}
impl<T: TestListener> ListenerWrapper for Wrapper<T> {
fn switch(&mut self, call: Call, nt: VarId, alt_id: AltId, t_data: Option<Vec<String>>) {
// ...
match call {
Call::Enter => { // only generated for LL parsers
match nt {
0 => self.listener.init_s(), // s
1 => self.listener.init_val(), // val
_ => panic!("unexpected enter nonterminal id: {nt}")
}
}
Call::Exit => {
match alt_id {
0 | // s -> Id "=" val
1 | // s -> "exit"
2 => self.exit_s(alt_id), // s -> "return" val
3 | // val -> Id
4 => self.exit_val(alt_id), // val -> Num
_ => panic!("unexpected exit alternative id: {alt_id}")
}
}
// ...
}
}
}
The user must instantiate the wrapper and give it the listener before parsing the input. The listener can be given back later if necessary with wrapper.give_listener().
The top-level user parser can be summarized by the following steps:
pub fn parse(text: &str) -> Result<BufLog, BufLog> {
const VERBOSE_WRAPPER: bool = false;
// instantiates the lexer and low-level parser:
let mut lexer = build_lexer();
let mut parser = build_parser();
// instantiates the user listener and the wrapper:
let listener = MyTestListener::new();
let mut wrapper = Wrapper::new(listener, VERBOSE_WRAPPER);
// creates a stream from the input text and attaches it to the lexer:
let stream = CharReader::new(Cursor::new(text));
lexer.attach_stream(stream);
// passes the tokens from the lexer to the parser:
let tokens = self.lexer.tokens().keep_channel0();
// parses the tokens using the wrapper and the listener:
let result = self.parser.parse_stream(&mut wrapper, tokens);
// handles the results:
let MyTestListener { mut log, .. } = wrapper.give_listener();
if let Err(e) = result {
log.add_error(e.to_string());
}
if log.has_no_errors() {
Ok(log)
} else {
Err(log)
}
}
Nonterminal Values
Nonterminals have a value by default, though this isn’t mandatory. When a nonterminal has no value, its exit method doesn’t return a value and it’s not represented in the contexts of other nonterminals that include it.
For example, consider the following rules:
a -> b c | c
b -> Op c
c -> Id
where Op and Id are variable tokens that contain string data.
If a, b, and c have a value, the following code is generated:
pub enum CtxA {
/// `a -> b c`
V1 { b: SynB, c: SynC }, // <-- values of b and c
/// `a -> c`
V2 { c: SynC }, // <-- value of c
}
pub enum CtxB {
/// `b -> Op c`
V1 { op: String, c: SynC },
}
pub enum CtxC {
/// `c -> Id`
V1 { id: String },
}
pub trait TestListener {
// ... (other general methods)
// ... (init methods if an LL parser is generated)
fn exit_a(&mut self, ctx: CtxA) -> SynA;
fn exit_b(&mut self, ctx: CtxB) -> SynB;
fn exit_c(&mut self, ctx: CtxC) -> SynC;
}
As expected, the context given for the first alternative of a includes the data for the nonterminals b and c, with user-defined types SynB and SynC, while the second alternative only includes c. Similarly, CtxB includes a field for the c nonterminal.
If c has no value, the code becomes:
pub enum CtxA {
/// `a -> b c`
V1 { b: SynB }, // <-- value of b only
/// `a -> c`
V2, // <-- no value in the context
}
pub enum CtxB {
/// `b -> Op c`
V1 { op: String },
}
pub enum CtxC {
/// `c -> Id`
V1 { id: String },
}
pub trait TestListener {
// ... (other general methods)
// ... (init methods if an LL parser is generated)
fn exit_a(&mut self, ctx: CtxA) -> SynA;
fn exit_b(&mut self, ctx: CtxB) -> SynB;
fn exit_c(&mut self, _ctx: CtxC) {} // <-- no return value, but has default definition
}
The variant CtxA::V2 is empty since there is no data, but it still exists so that the user knows which alternative of the a rule was parsed.
The trait still allows for callbacks before and after c is parsed, but there is no return value. This also makes the implementation of exit_c optional, so a default empty definition is provided.
If both b and c have no value, the code becomes:
pub enum CtxA {
/// `a -> b c`
V1,
/// `a -> c`
V2,
}
pub enum CtxB {
/// `b -> Op c`
V1 { op: String },
}
pub enum CtxC {
/// `c -> Id`
V1 { id: String },
}
pub trait TestListener {
// ...
// ...
fn exit_a(&mut self, ctx: CtxA) -> SynA;
fn exit_b(&mut self, _ctx: CtxB) {}
fn exit_c(&mut self, _ctx: CtxC) {}
}
Here, all the variants of the CtxA context are empty. If a only had one alternative, the context would still have one empty variant, even though it carries no information at all. It would be generated to keep the API consistent, but it could be ignored entirely.
When a nonterminal has a value, the user must define its type. By default, the type name is Syn<nonterminal>, where <nonterminal> is the upper camel case of the nonterminal’s name. For example, a is associated to the SynA type, which can be a genuine type or an alias.
Finally, when Lexigram has to add new nonterminals in the grammar, it generates their types automatically in the code. A common example is the array type returned by a repetition, like SynA1 in Repetions With *.
Tip
An easy way to quickly test the integration of the generated parser is to make a first version where all the nonterminals have no value. The listener doesn’t require definitions for the nonterminal methods or their types, so that reduces the work to a minimum. Once everything compiles, the parser can be regenerated with the appropriate value properties.
However, it’s also possible to get a template of the implementation when the code is generated. It’s more convenient to copy this template the first time; it also includes the definition of all the nonterminal types as empty structs:
/// User-defined type for `a` #[derive(Debug, PartialEq)] pub struct SynA(); // ... struct Listener { log: BufLog, } impl TestListener for Listener { fn get_log_mut(&mut self) -> &mut impl Logger { &mut self.log } fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) { match ctx { CtxA::V1 { b, c } => {} CtxA::V2 { c } => {} } SynA() } // ... }If the template is added to the project repository, it allows to see how the basic implementation of the listener changes when the grammar is modified later. This makes updating the actual listener implementation much easier.
Grammar Transformations
When asked to generate a top-down parser, Lexigram accepts non-LL(1) grammars if it’s able to transform them into LL(1). It tries to provide some degree of transparency by not showing the transformation in the listener trait and types, but some patterns require specific listener calls.
For bottom-up parsers, there are fewer restrictions, so the only changes are due to “syntactic sugar”.
The transformations made by Lexigram are:
?operator:a: X?;becomesX | ε*operators:a: X*;becomesa -> a_1,a_1 -> X a_1 | ε+operators:a: X+;becomesa -> a_1,a_1 -> X a_1 | X
- left recursion:
a: a X | Y;becomesa -> Y a_1,a_1 -> X a_1 | εa: a X a | Y;and more complex ambiguities, typically used in expression parsing, are transformed with the Clarke method, which is detailed later
- left factorization:
a -> A B | A Cbecomesa -> A a_1,a_1 -> B | C
A few rules have two implementations: normal or low-latency (<L> attribute). Firstly, in the + and * repetitions:
a: X*;becomesa -> a_1,a_1 -> X a_1 | ε, but thea_1iterator nonterminal is not visible to the user. The generated code gathers all the values and puts them in the context of theexit_amethod.a: (<L=i> X)*;becomesa -> i,i -> X i | ε, as above, but a callback method is generated foriso that the user can manage the iterations manually, almost as if the user had written the transformed rules in the original grammar. Note that the iterator nonterminal is explicitly named by the user.- Similar transformations apply to
a -> X+anda -> (<L=i> X)+.
Secondly, in right-recursive rules:1
a: X a | Y;behaves as expected: since it’s right recursive, a text “XXY” is decomposed asa -> X (a -> X (a -> Y)). The firstexit_acall occurs on the end of the iterations, witha -> Y, and the next two calls backtrack on the 2nd “X” then on the first “X”. This means that the first call occurs after the parser has already parsed the entire sequence and put all the intermediate values on the stack, which it empties one element at a time when callingexit_a.a: X <L> a | Y;is offering a shortcut to avoid the latency of the normal behaviour, by callingexit_aon each newly found value, a little as if it was a left-recursive rule. The firstexit_acall occurs on the first “X”, the 2nd on the next “X”, and the last on the “Y”. It is then up to the user to rebuild the AST in the desired order.
The purpose of the <L> attribute is to offer the ability of parsing a potentially infinite stream without storing all the intermediate items, or to produce an immediate output before reaching the end of the sequence in the stream.
Repetitions With *
a: A B* C;
is transformed into
a -> A a_1 C
a_1 -> B a_1
a_1 -> ε
a -> A a_1 C
a_1 -> a_1 B
a_1 -> ε
The generated code is as follows:
pub enum CtxA {
/// `a -> A B* C`
V1 { a: String, star: SynA1, c: String },
}
pub struct SynA1(pub Vec<String>);
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
Sequence of the operations:
init_a(…)is called before the rule is parsed.
exit_a(…)is called aftera -> A B* Cis parsed. The repetition is available in thestarfield of thectx: CtxAargument. It wraps a vector containing all the parsed values.
Repetitions With +
a: A B+ C;
is transformed into
a -> A a_1 C
a_1 -> B a_2
a_2 -> a_1
a_2 -> ε
a -> A a_1 C
a_1 -> a_1 B
a_1 -> B
The generated code is very similar to the * repetition:
pub enum CtxA {
/// `a -> A B+ C`
V1 { a: String, plus: SynA1, c: String },
}
/// Computed `B+` array in `a -> A ►► B+ ◄◄ C`
pub struct SynA1(pub Vec<String>);
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
Token-Separated Items
A special case of the * repetition recognized by Lexigram is a list of identical items separated by one or several fixed tokens:
a: 'var' Id (Id / ',')+ ';';
is transformed into
a -> "var" Id a_1 ";"
a_1 -> "," Id a_1
a_1 -> ε
a -> "var" a_1 ";"
a_1 -> a_1 "," Id
a_1 -> Id
The generated code is as follows:
pub enum CtxA {
/// `a -> "var" Id ("," Id)* ";"`
V1 { star: SynA1 },
}
pub struct SynA1(pub Vec<String>);
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) -> SynA;
}
Repetitions With <L>*
a: A (<L=i> B)* C;
is transformed into
a -> A i C
i -> B i
i -> ε
a -> A i C
i -> i B
i -> ε
Note that the nonterminal used to represent the iterations must be defined by the user, since its type is user-defined (here, i of type SynI).
The generated code is as follows:
pub enum CtxA {
/// `a -> A (<L> B)* C`
V1 { a: String, star: SynI, c: String },
}
pub enum CtxI {
/// `<L> B` iteration in `a -> A ( ►► <L> B ◄◄ )* C`
V1 { b: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) -> SynA;
fn init_i(&mut self) -> SynI; // also generated in *LR (!)
fn exit_i(&mut self, acc: &mut SynI, ctx: CtxI, spans: Vec<PosSpan>);
fn exitloop_i(&mut self, acc: &mut SynI) {} // LL only
}
init_a(…)is called before the ruleais parsed.exitloop_i(…)is called after the last iteration. It can be used if the accumulator requires post-processing once the whole series has been parsed.2
init_i(…)is called before the ruleiis parsed for the first time. This is a good place to initialize the whole series; the method must return the accumulator variable that will be updated at each iteration.exit_i(…)is called after parsing each item of the repetition, if there are any items. It receives the current value of the accumulatoraccand the values of the parsed items in the context variant, hereb. The accumulator can be updated thanks to the mutable reference.
Repetitions With <L>+
a: A (<L=i> B)+ C;
is transformed into
a -> A i C
i -> B a_1
a_1 -> i
a_1 -> ε
a -> A i C
i -> i B
i -> B
The generated code is as follows:
pub enum CtxA {
/// `a -> A (<L> B)+ C`
V1 { a: String, plus: SynI, c: String },
}
pub enum CtxI {
/// `<L> B` iteration in `a -> A ( ►► <L> B ◄◄ )+ C`
V1 { b: String, last_iteration: bool },
}
pub enum CtxI {
/// `<L> B` iteration in `a -> A ( ►► <L> B ◄◄ )+ C`
V1 { b: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) -> SynA;
fn init_i(&mut self) -> SynI; // also generated in *LR (!)
fn exit_i(&mut self, acc: &mut SynI, ctx: CtxI, spans: Vec<PosSpan>);
}
The differences from a repetition with <L>* are:
exit_i(…)is sure to be called at least once.- The resulting field in the
CtxA::V1variant is namedplusinstead ofstar.
- A
last_iterationfield that flags the last iteration, when thea_1 -> εalternative is reached. - No
exitloop_i(…)method, which has been replaced by the flag above because the last iteration contains the same data as the previous iterations.
Token-Separated Items With <L>
A list of identical items separated by one or several fixed tokens is also recognized in a <L>* repetition:
a: 'var' (<L=i> Id / ',')* ';';
is transformed into
a -> "var" Id i ";"
i -> "," Id i
i -> ε
a -> "var" i ";"
i -> i "," Id
i -> Id
The generated code is as follows:
pub enum CtxA {
/// `a -> "var" Id (<L> "," Id)* ";"`
V1 { star: SynI },
}
pub enum InitCtxI {
/// value of `Id` before `<L> "," Id` iteration in
/// `a -> "var" Id ( ►► <L> "," Id ◄◄ )* ";"`
V1 { id: String },
}
pub enum CtxI {
/// `<L> "," Id` iteration in
/// `a -> "var" Id ( ►► <L> "," Id ◄◄ )* ";"`
V1 { id: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) -> SynA;
fn init_i(&mut self, ctx: InitCtxI, spans: Vec<PosSpan>) -> SynI;
fn exit_i(&mut self, acc: &mut SynI, ctx: CtxI, spans: Vec<PosSpan>);
fn exitloop_i(&mut self, acc: &mut SynI) {} // LL only
}
Right Recursion
expr: Id '.' expr | '(' Num ')';
Right-recursive rules don’t need to be modified. The generated code is as follows:
pub enum CtxExpr {
/// `expr -> Id "." expr`
V1 { id: String, expr: SynExpr },
/// `expr -> "(" Num ")"`
V2 { num: String },
}
pub trait TestListener {
// ...
fn init_expr(&mut self) {} // LL only
fn exit_expr(&mut self, ctx: CtxExpr) -> SynExpr;
}
init_expr(…)is called before the rule is parsed.
exit_expr(…)is called after each alternative is parsed.- The first time, it’s a non-recursive alternative; here,
expr -> "(" Num ")", with variantV2. It returns the initial value of the accumulator. - The following times, it’s a recursive alternative; here,
expr -> Id "." expr, with variantV1. It returns the updated accumulator.
- The first time, it’s a non-recursive alternative; here,
Since it’s right-recursive, it’s worth noting the Id values are given in reverse order. The following input:
Id0.Id1(5)
generates the following calls when it’s parsed:
init_expr()
exit_expr(ctx = CtxA::V2 { num: "5" }) -> xexit_expr(ctx = CtxA::V1 { id: "Id1", expr: x }) -> yexit_expr(ctx = CtxA::V1 { id: "Id0", expr: y }) -> z- (the production that includes
exprreceives the valuez)
Right Recursion With <L>
expr: <L> Id '.' expr | '(' Num ')';
The generated code is as follows:
pub enum CtxExpr {
/// `expr -> <L> Id "." expr`
V1 { id: String },
/// `expr -> "(" Num ")"`
V2 { num: String },
}
pub trait TestListener {
// ...
fn init_expr(&mut self) -> SynExpr;
fn exit_expr(&mut self, acc: &mut SynExpr, ctx: CtxExpr, spans: Vec<PosSpan>);
}
Contrary to the * and + repetitions, the user mustn’t define a name in the attribute, since there is no transformation adding another nonterminal.
Since this form uses an accumulator, it is necessary to initialize it with init_expr(…).
This <L> version gives the values in the incoming order. The following input:
Id0.Id1(5)
generates the following calls when it’s parsed:
init_expr() -> wexit_expr(*acc: w, ctx = CtxA::V1 { id: "Id0" }),*acc = xexit_expr(*acc: x, ctx = CtxA::V1 { id: "Id1" }),*acc = yexit_expr(*acc: z, ctx = CtxA::V2 { num: "5" }),*acc = z- (the production that includes
exprreceives the valuez)
Left Recursion
e: f | e '.' Id;
For top-down parsers, it is transformed into
e -> f e_1
e_1 -> "." Id e_1 | ε
Left-recursive rules don’t need to be modified for bottom-up parsers.
e -> f
e -> e "." Id
The generated code is as follows:
pub enum CtxE {
/// `e -> f`
V1 { f: SynF },
/// `e -> e "." Id`
V2 { e: SynE, id: String },
}
pub trait TestListener {
// ...
fn init_e(&mut self) {} // LL only
fn exit_e(&mut self, ctx: CtxE) -> SynE;
fn exitloop_e(&mut self, _e: &mut SynE) {} // LL only
}
This is similar to an <L> repetition, except the initialization part. The accumulator is not returned by init_e, but it’s created at the first iteration, when the rule matches a non-recursive alternative of the rule; in this case, e -> f.
init_e(…)is called before the rule is parsed.exitloop_e(…)is called after the last iteration. It can be used if the accumulator requires post-processing once the whole series has been parsed.
exit_e(…)is called after each alternative is parsed.- The first time, it’s a non-recursive alternative; here,
e -> f, with variantV1. It returns the initial value of the accumulator. - The following times, it’s a recursive alternative; here,
e -> e "." Id, with variantV2. It returns the updated accumulator.
- The first time, it’s a non-recursive alternative; here,
Left Factorization
a: A | A B | A B C | A B D | E;
which can be rewritten as
a: A (ε | B (ε | C | D)) | E
------------ a2
------------------- a1
is transformed for a top-down parser into
a -> A a_1
a -> E
a_1 -> B a_2
a_1 -> ε
a_2 -> C
a_2 -> D
a_2 -> ε
Bottom-up parsers don’t need to left-factorize rules.
The generated code is as follows:
pub enum CtxA {
/// `a -> A`
V1 { a: String },
/// `a -> A B`
V2 { a: String, b: String },
/// `a -> A B C`
V3 { a: String, b: String, c: String },
/// `a -> A B D`
V4 { a: String, b: String, d: String },
/// `a -> E`
V5 { e: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {}
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
Advanced Transformations
Ambiguous Left and Right Recursion
Rules that are both left- and right-recursive are ambiguous, since they don’t define the precedence nor the associativity. Such rules are usually met in expressions containing binary operators.
Lexigram determines the precedence from the order in which the operators are defined in the rule:
-
The alternatives defined first have higher precedence; in this example,
*has higher precedence than+expr: expr '*' expr | expr '+' expr | Num; -
The
<P>attribute indicates an operator with the same level of precedence as the previous one on its left. For example, it can be used in a rule likeexpr: expr '+' expr | <P> expr '-' expr | Id | Num;
(otherwise, + would have more priority than -, which would be semantically incorrect).
By default, binary operators are left-associative. The <R> attribute indicates a right-associative operator. For example,
expr: <R> expr '^' expr | expr '*' expr | expr '/' expr | Num
The attributes can be placed anywhere in the rule alternative, but we usually place them at the beginning to be consistent.
For top-down parsers, Lexigram automatically transforms those rules using the Clarke method, which preserves the precedence and left-/right-associativity. The same rule can contain binary and prefixed / suffixed unary operators (e.g. expr '+' expr, '-' expr and expr '?', respectively).
The rule
e: e '*' e | <R> e '!' e | e '+' e | Num;
is transformed into
e -> e_4 e_1
e_1 -> "*" e_4 e_1 | "!" e_2 e_1 | "+" e_2 e_1 | ε
e_2 -> e_4 e_3
e_3 -> "*" e_4 e_3 | "!" e_2 e_3 | ε
e_4 -> Num
For bottom-up parsers, Lexigram automatically removes the shift/reduce conflicts resulting from the ambiguities. However, since similar conflicts can occur for other reasons, ambiguous rules that need to be resolved must be preceded by the attribute <resolve>:
<resolve>
e: e '*' e | <R> e '!' e | e '+' e | Num;
Note
This attribute is ignored when a top-down parser is generated, so it’s good practice to put it there even if you’re targetting an LL(1) parser, in case you want to switch to an *LR parser later.
The rule doesn’t need to be modified:
e -> e '*' e
e -> e '!' e
e -> e '+' e
e -> Num;
The generated code is as follows:
pub enum CtxE {
/// `e -> e "*" e`
V1 { e: [SynE; 2] },
/// `e -> <R> e "!" e`
V2 { e: [SynE; 2] },
/// `e -> e "+" e`
V3 { e: [SynE; 2] },
/// `e -> Num`
V4 { num: String },
}
pub trait TestListener {
// ...
fn init_e(&mut self) {} // LL only
fn exit_e(&mut self, ctx: CtxE) -> SynE;
}
Since there are two identical symbols in the same alternatives, they are regrouped in an array e: [SynE; 2], where e[0] is the leftmost nonterminal and e[1] is the rightmost one.
The first call to exit_e(…) corresponds to the operator of highest precedence, and the last corresponds to the lowest precedence, so using the listener to build an abstract syntax tree of an expression is straightforward.
Repetitions of Longer Patterns
a: (b A b B A)+;
produces the following code:
pub enum CtxA {
/// `a -> (b A b B A)+`
V1 { plus: SynA1 },
}
/// Computed `(b A b B A)+` array in `a -> ►► (b A b B A)+ ◄◄ `
pub struct SynA1(pub Vec<SynA1Item>);
/// `b A b B A` item in `a -> ( ►► b A b B A ◄◄ )+`
pub struct SynA1Item { pub b: [SynB; 2], pub a: [String; 2], pub b1: String }
pub trait TestListener {
// ..
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
In comparison to the simple example of the * repetition, we see that the type of the items in the list, SynA1Item, is a struct rather than a string. Also, the same symbols have been regrouped in arrays:
-
b: [SynB; 2]for the two nonterminalsb.b[0]represents►► b ◄◄ A b B Aandb[1]representsb A ►► b ◄◄ B A. -
a: [String; 2]for the two tokensA(note that the field must be lowercase, despite representing a token), which contain a string.a[0]representsb ►► A ◄◄ b B Aanda[1]representsb A b B ►► A ◄◄.
Also, the token B is represented by b1, since the name b was already taken. The fields are in the same order as the first symbol they represent in the rule; here, b is first, A second, and B third. Their type is another indication that helps set them apart: the type of a token is a string, while a nonterminal has a custom type whose name begins by “Syn”, for synthesized.
It takes some getting used to, but it’s quite easy if you consider that
- the symbols holding a value are taken in their order of appearance in the alternative
- identical symbols are regrouped in arrays, with the index preserving the relative order in the alternative
- the field is the name of the symbol, transformed to lower snake case when necessary, and followed by a number if the name is already taken (symbol with the same name but a different case, or Rust keyword).
Nested Repetitions
a: (A (b ',')* ';')* C;
produces the following code:
pub enum CtxA {
/// `a -> (A (b ",")* ";")* C`
V1 { star: SynA2, c: String },
}
/// Computed `(b ",")*` array in `a -> (A ►► (b ",")* ◄◄ ";")* C`
pub struct SynA1(pub Vec<SynB>);
/// Computed `(A (b ",")* ";")*` array in `a -> ►► (A (b ",")* ";")* ◄◄ C`
pub struct SynA2(pub Vec<SynA2Item>);
/// `A (b ",")* ";"` item in `a -> ( ►► A (b ",")* ";" ◄◄ )* C`
pub struct SynA2Item { pub a: String, pub star: SynA1 }
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
When a repetition is nested in another, the resulting vector becomes a field of the outer repetition’s type. Here, SynA2Item::star of type SynA1 contains a Vec<SynB>, where SynB contains the only data of the inner loop, which is the nonterminal b. Each generated type has a doc comment that emphasizes the part of the original rule it represents between “►►” and “◄◄” arrows.
It’s also possible to nest any combination of non-<L> and <L> repetitions. The principle is always the same: non-<L> repetitions are represented by a Vec of values gathered automatically by the parser, and an <L> repetition is managed manually by the user through extra nonterminal init(…)/exit(…) methods and is represented by a user-defined type.
At some point, though, it’s preferable to split the grammar rule and avoid types that become too complex to manage.
Alternatives in Repetitions
a: A (B | b C b B C | E)* F;
produces the following code:
pub enum CtxA {
/// `a -> A (B | b C b B C | E)* F`
V1 { a: String, star: SynA1, f: String },
}
pub enum CtxB {
/// `b -> D`
V1 { d: String },
}
/// Computed `(B | b C b B C | E)*` array in `a -> A ►► (B | b C b B C | E)* ◄◄ F`
pub struct SynA1(pub Vec<SynA1Item>);
pub enum SynA1Item {
/// `B` item in `a -> A ( ►► B ◄◄ | b C b B C | E)* F`
V1 { b: String },
/// `b C b B C` item in `a -> A (B | ►► b C b B C ◄◄ | E)* F`
V2 { b: [SynB; 2], c: [String; 2], b1: String },
/// `E` item in `a -> A (B | b C b B C | ►► E ◄◄ )* F`
V3 { e: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA) -> SynA;
}
Since each iteration can be one of 3 strings of symbols, its type SynA1Item is an enum with 3 variants, each containing the corresponding data.
Alternatives in Repetitions with <L>
a: A (<L=i> (<L=j> b C b B C | D)* E | F)* G;
produces the following code:
pub enum CtxA {
/// `a -> A (<L> (<L> b C b B C | D)* E | F)* G`
V1 { a: String, star: SynI, g: String },
}
pub enum CtxI {
/// `<L> (<L> b C b B C | D)* E` iteration in `a -> A ( ►► <L> (<L> b C b B C | D)* E ◄◄ | F)* G`
V1 { star: SynJ, e: String },
/// `F` iteration in `a -> A (<L> (<L> b C b B C | D)* E | ►► F ◄◄ )* G`
V2 { f: String },
}
pub enum CtxJ {
/// `<L> b C b B C` iteration in `a -> A (<L> ( ►► <L> b C b B C ◄◄ | D)* E | F)* G`
V1 { b: [SynB; 2], c: [String; 2], b1: String },
/// `D` iteration in `a -> A (<L> (<L> b C b B C | ►► D ◄◄ )* E | F)* G`
V2 { d: String },
}
pub trait TestListener {
// ...
fn init_a(&mut self) {} // LL only
fn exit_a(&mut self, ctx: CtxA, spans: Vec<PosSpan>) -> SynA;
fn init_i(&mut self) -> SynI;
fn exit_i(&mut self, acc: &mut SynI, ctx: CtxI, spans: Vec<PosSpan>);
fn exitloop_i(&mut self, acc: &mut SynI) {} // LL only
fn init_j(&mut self) -> SynJ;
fn exit_j(&mut self, acc: &mut SynJ, ctx: CtxJ, spans: Vec<PosSpan>);
fn exitloop_j(&mut self, acc: &mut SynJ) {} // LL only
}
In case of <L> + repetitions, a last_iteration boolean field flags the last repetition instead of a exitloop_*(…) method call, as seen before.
Formal Grammar Definition
Here are the lexicon and the grammar of Gram, using the Lexigram syntax. Those files can be found in the repository, in the build-stage1 directory.
Gram’s Lexicon
lexicon GramLexer;
fragment COMMENT : '/*' .*? '*/';
fragment LINECOMMENT : '//' ~[\r\n]*;
fragment WHITESPACE : [ \n\r\t]+;
fragment ID : [a-zA-Z][a-zA-Z_0-9]*;
fragment HEX_DIGIT : [0-9a-fA-F];
fragment UNICODE_ESC : 'u{' HEX_DIGIT+ '}';
fragment ESC_CHAR : '\\' ([nrt'\\] | UNICODE_ESC);
fragment CHAR : ESC_CHAR | ~[\n\r\t'\\];
fragment STR_LITERAL : '\'' CHAR+ '\'';
Comment : COMMENT -> skip;
LineComment : LINECOMMENT -> skip;
WhiteSpace : WHITESPACE -> skip;
Colon : ':';
Lparen : '(';
Or : '|';
Plus : '+';
Question : '?';
Rparen : ')';
Semicolon : ';';
Sep : '/';
Star : '*';
StrLit : STR_LITERAL;
Grammar : 'grammar';
SymEof : 'EOF';
Lform : '<L' ('=' ID)? '>';
Rform : '<R>';
Pform : '<P>';
Greedy : '<G>';
ResolveTag : '<resolve>';
Id : ID;
Gram’s Grammar
grammar GramParser;
file: header rules;
header:
'grammar' Id ';'
;
rules:
rule
| rules rule
;
rule:
rule_name ':' prod 'EOF'? ';'
;
rule_name:
'<resolve>'? Id
;
prod:
prod_alt
| prod '|' prod_alt
;
prod_alt:
prod_factor*
;
prod_factor:
prod_atom ('+' | '*' | '?')?
;
prod_atom:
Id
| Lform
| '<R>'
| '<P>'
| '<G>'
| '(' prod ')'
| '/'
| StrLit
;
-
bottom-up parsers don’t support
<L>right-recurive rules. In a top-down parser, it’s easy to reschedule the call to the exit method of a right-recursive rule earlier by using a simple trick on the default algorithm, but supporting that in a bottom-up parser would require serious modifications to its algorithm and impact its performance. Using a left-recursive rule would be much better. ↩ -
Detecting when it’s the last iteration in a bottom-up parser would complixify the algorithm and make it less performant. ↩