Grammar
Let’s start with the top structure of the grammar. In this section, we’ll build the grammar and get a peek at the generated code. It’s a good opportunity to show features and provide guidance. We’ll implement the listener for the generated code in the next section, once the grammar is fully defined.
Since we’re covering both top-down LL(1) parsers and bottom-up LALR parsers, and since the differences in the interface aren’t big, we’ll indicate what’s specific to one type or the other with those annotations:
- LL for LL(1) parsers.
- *LR for LALR and future bottom-up parsers. All bottom-up parsers behave the same: LALR, LR, IELR, SLR, and so on. They only differ by the content of their parsing table.
The top level is a succession of four groups:
- definitions (
"def")def GRAMMAR_FILENAME = "example.lg"; def PARSER_FILENAME = "parser.rs"; def INDENT = 4; - lexer specifications (
"lexer")lexer { combined: GRAMMAR_FILENAME, output: PARSER_FILENAME ["example_lexer"] } - parser specifications (
"parser")parser { output: PARSER_FILENAME ["example_parser"] } - general options (
"options")options { libs: { "super::user_types::*" }, indent: INDENT }
The definitions contain zero or more items that all have the same format, so it’s pretty simple. We want to be able to use constants in the rest of the file for any type of value, like a string literal (filename or tag name), an integer literal (indent level), and other parameters we’ll discover as we come across all the options.
The lexer, parser, and general options contain a list of comma-separated options between brackets. We’ll see the inner content when we tackle those rules.
In the rest of this section, we’ll introduce the basic grammar patterns by applying them on the configuration file example.
Optional Items
How are the four top-level items organized? They could either follow one another in the order shown above, or there could just be a repetition of those items in no particular order. The latter would offer more flexibility, but we’ll choose the former because it’s cleaner and easier to manage. We’ll just have to tell in which order they come and which parts are optional.
The start nonterminal, that we’re naming config, lists the four parts:
config:
definitions
lexer
parser
options
;
lexer is mandatory, but parser and options are optional: we can require only a lexer or the whole lexer + parser + wrapper code. Since Lexigram offers a few elements of syntactic sugar for optional and repetitive items, such as α?, α*, and α+, we can use that to make the definition of parser and options optional: (we have omitted the actual content of the grammatical rules for now)
definitions: …;
lexer: …;
parser: (…)?;
options: (…)?;
Alternatively, we could have made parser and options optional in the top rule, but it’s not ideal to have a string of optional symbols; e.g.
config: definitions lexer parser? options?;
Let’s compare how both forms are translated to understand the potential issue.
The first task of Lexigram is to normalize the rules, transforming
α?toα | ε.α*to a new nonterminalx, wherex -> α x | εfor LL(1),x -> x α | εfor LALR.α+to a new nonterminalx, wherex -> α x | αfor LL(1),x -> x α | αfor LALR.
where
αstands for a string of symbolsεis the symbol for “empty”- the actual nonterminal’s name isn’t
x, but a unique name derived from the rule’s name
Consequently, our first formulation of the rules is transformed into the final productions below:
// normalization: config -> definitions lexer parser options definitions -> … lexer -> … parser -> … parser -> ε options -> … options -> ε
parser and options have an empty alternative, which is fine. It’s reflected directly in the listener trait methods as two variants of an enum context type, so the user knows immediately whether the option is used or not in parser and options. We’ll see an example of such an enum shortly.
Now, let’s examine the alternative form:
config:
definitions
lexer
parser?
options?
;
definitions: …;
lexer: …;
parser: …;
options: …;
Each of those ? would split the original production of config when it’s normalized, ending up as a list of all the possible combinations:
// normalization: config -> definitions lexer parser options config -> definitions lexer parser config -> definitions lexer options config -> definitions lexer
It’s not too long, but it’s cumbersome. Also, we’d have eight alternatives if the lexer specs were also optional.
In the case of LL, it’s not all: those alternatives would need to be left-factorized because of the common left-hand symbols.1
// LL left factorization: config -> definitions lexer config_1 . config_1 -> parser config_2 . config_1 -> options . config_1 -> ε . config_2 -> options . config_2 -> ε
Left factorization is hidden from the user in the listener interface, fortunately, but it creates more nonterminals and increases the size of the parsing table, requiring more memory and work from the parser.
The user implementation of the listener would list all the combinations, as shown below with the match on the enum variants we mentioned earlier. It’s possible to work with that, but it’s annoying to handle the repetitions, especially if the nonterminal values for definitions, lexer, parser, and options must be processed.
// user-code template:
impl ConfigListener for Listener {
fn exit_config(&mut self, ctx: CtxConfig) -> SynConfig {
match ctx {
// config -> definitions lexer parser options
CtxConfig::V1 { definitions, lexer, parser, options } => {}
// config -> definitions lexer parser
CtxConfig::V2 { definitions, lexer, parser } => {}
// config -> definitions lexer options
CtxConfig::V3 { definitions, lexer, options } => {}
// config -> definitions lexer
CtxConfig::V4 { definitions, lexer } => {}
}
SynConfig()
}
// ...
}
If we compare the initial and alternative forms:
- For 2 optional items out of 4, we get 7 productions vs 10.
- For 3 optional items out of 4, we get 8 productions vs 16.
The take-away is that you shouldn’t use several ? in the same alternative, since the desugaring makes it grow exponentially when it’s distributed:
x: α? β? γ?;
becomes
x -> (α | ε) (β | ε) (γ | ε) -> α β γ | α β | α γ | α | β γ | β | γ | ε
However, it’s perfectly fine to use ? in separate alternatives because it adds only a single ε after normalization:
x: α? | β? | γ?;
becomes
x -> α | β | γ | ε
Grammar Loops: Recursive Rules
Now that we have config, let’s see the secondary nonterminals, starting with definitions.
Each definition has the syntax below, where we give a temporary definition for value:
// lexicon
…
Id : [a-zA-Z][a-zA-Z_0-9]*;
NumLiteral : [0-9]+;
StrLiteral : '"' Char+ '"';
// grammar
…
definition : 'def' Id '=' value ';';
value : NumLiteral | StrLiteral | Id;
But how can we express 0 or more repetitions of definition? It’s time to see the different ways of iterating over grammar “loops”.
Right Recursion
The right recursion is the only recursive rule allowed in top-down grammars. It’s also allowed in bottom-up grammars, which support left and right recursions without requiring any transformation.
If we use this rule for definitions, where the missing symbols on the right of | simply means “empty”:
definitions: 'def' Id '=' value ';' definitions | ;
Since the syntax is recursive, we need an alternative to end the recursion: here, we use an empty production because definitions can be empty.
No transformation is required here, so the alternatives remain the same for the parser:
definitions -> 'def' Id '=' value ';' definitions definitions -> ε
The listener interface provides the following methods:
// user-code template:
impl ConfigListener for Listener {
// LL only
fn init_definitions(&mut self) {}
fn exit_definitions(&mut self, ctx: CtxDefinitions) -> SynDefinitions {
match ctx {
// definitions -> "def" Id "=" value ";" definitions
CtxDefinitions::V1 { id, value, definitions } => {}
// definitions -> ε
CtxDefinitions::V2 => {}
}
SynDefinitions()
}
// ...
}
At first glance, this looks fine. It’s simple and it has the advantage of not requiring any transformation, but there is a catch! Since it’s a right-recursive rule, the listener will receive the items in reverse order. Why is that?
Let’s consider the following input, which has three definitions:
def a = 0;
def b = 1;
def c = 2;
The reductions are performed as follows:
definitions
─────┬─────
│ z
─────────────────────┴──────────────────────
"def" Id("a") "=" value("0") ";" definitions
─────┬─────
│ y
─────────────────────┴──────────────────────
"def" Id("b") "=" value("1") ";" definitions
─────┬─────
│ x
─────────────────────┴──────────────────────
"def" Id("c") "=" value("2") ";" definitions
─────┬─────
│ w
─┴─
ε
Each exit_definitions(…) method is called only after all the symbols have been entirely parsed in the production, including the definitions nonterminal at the end. So the first definitions to be reduced is ε, then the one above, and so on.
The successive calls are, if we simplify the notation:
- LL only:
init_definitions() exit_definitions(CtxDefinitions::V2), returns theSynDefinitionsvaluewexit_definitions(CtxDefinitions::V1 { id: "c", value: "2", definitions: w })returnsxexit_definitions(CtxDefinitions::V1 { id: "b", value: "1", definitions: x })returnsyexit_definitions(CtxDefinitions::V1 { id: "a", value: "0", definitions: y })returnsz
And the value of definitions in exit_config(…), once it’s called, will be z.
If we accumulated the values in a vector, we would ultimately get the items in reverse order, unless we used a VecDeque to push the items in front. It could also be annoying if we wanted to check that an indentifier hadn’t already been declared before. And if an identifier was the same as another one (def c = a), we’d need another pass to resolve it.
A potential concern with iterations arises when post-processing is required. Since we don’t have any way of knowing when exit_definitions(…) is called for the last time, any post-processing must be done anywhere definitions is used. In our case, it’s used only once in exit_config(…), but if it was used in several productions, we’d have to call a post-processing method from each one of them. If we add another instance later, we must also remember to do the same. Alternatively, we could use an intermediate nonterminal to keep things tidier, but at a cost.
Another consequence, which isn’t obvious at first, is that each iteration stores a new SynDefinitions value in the wrapper stack and a new production symbol in the parser stack. Not only do you get the last item first, after the whole list has been processed by the parser, but it consumes more stack memory.
Right-recursive rules are simple and useful when you need to preserve that reverse order, but otherwise it’s not something you’ll want to use in a grammar very often.
Star *
We’ve already seen the syntactic sugar for repetitions of zero or more items: definition*. We can even put it directly into the definitions nonterminal:
definitions: ('def' Id '=' value ';')*;
For LL, Lexigram transforms it as follows:
definitions -> definitions_1 . definitions_1 -> "def" Id "=" value ";" definitions_1 . definitions_1 -> ε
For *LR, the transformation uses a left-recursive production. Bottom-up parsers support them natively, and it’s more efficient for what the wrapper has to do behind the scene to call the user listener methods:
definitions -> definitions_1 . definitions_1 -> definitions_1 "def" Id "=" value ";" . definitions_1 -> ε
In both cases, the generated listener interface hides that transformation by giving the end result once definitions is entirely parsed. There are no listener calls corresponding to the nonterminal definitions_1.
pub enum CtxDefinitions {
/// `definitions -> ("def" Id "=" value ";")*`
V1 { star: SynDefinitions1 },
}
pub struct SynDefinitions1(pub Vec<SynDefinitions1Item>);
pub struct SynDefinitions1Item { pub id: String, pub value: SynValue }
// user-code template:
impl ConfigListener for Listener {
fn exit_definitions(&mut self, ctx: CtxDefinitions) -> SynDefinitions {
// definitions -> ("def" Id "=" value ";")*
let CtxDefinitions::V1 { star } = ctx;
SynDefinitions()
}
// ...
}
The wrapper implements the glue logic to collect each item of the repetition and push it into a Vec<SynDefinitions1Item> list. When we implement exit_definitions(…), we get the star list containing all the collected (id, value) pairs. It’s often the most convenient way for small lists of items.
As we’ve already seen in the overview, fixed terminals that don’t hold any value, like "def", "=", and ";", are not given in context variants, so they’re not stored in that list, either.
If there are alternatives in the repetition, like x -> (α | β)*, the generated list type is an enum with the variants corresponding to the alternatives, so that each item can be either α or β. It can be very handy in simple situations, but it’s not to be abused. When the list item becomes too complex, another way to handle repetitions could be more optimal; we’ll see one later in the latency section.
LL technical considerations:
At this point, you might be wondering: isn’t the definitions_1 right-recursive? And didn’t we say that right recursions had downsides? Are we getting the items in reverse order?
Don’t worry. While it’s indeed technically right-recursive, the parser has several ways to interact with the listener and its own stack during the successive iterations. The original rule wasn’t meant as a right recursion, so Lexigram knows that the trailing definitions_1 of production 1 below doesn’t need to be known before using the items Id and value, unlike an original right-recursive rule.
0: definitions -> definitions_1 1: . definitions_1 -> "def" Id "=" value ";" definitions_1 2: . definitions_1 -> ε
Let’s see what happens in more detail:
- When the production 1 is predicted, the wrapper pushes an empty “loop” list on the value stack, for the repeated items that need to be collected.
- The production symbols are then parsed, and those that have a value are pushed on the wrapper stack; here,
Idandvalue. - When the
definitions_1symbol at the end of production 1 is met, it isn’t processed as a normal nonterminal to be derived (which would put another empty vector on the stack), but as a loop nonterminal. When wrapper receives a loop call for that nonterminal, it pops the values from their respective stack and pushes that as a new item into the list, which is now at the top of the value stack. - This process iterates until all the items have been parsed.
- When the loop is finished, production 0 is fully parsed, and the wrapper knows that the value of
definitions_1, which stands for the original*repetition, is at the top of the value stack.
Note
For the curious minds who know how top-down table-driven parsers work in general.
When a production like
definitions_1 -> "def" Id "=" value ";" definitions_1is predicted, the usual algorithm description tells us that the symbols on the right-hand side are put in reverse order on a stack. Here, it would pushdefinitions_1,";",value,"=",Id,"def". The parser would then pop the next symbol and, depending on its nature:
- if it’s a terminal, like
"def", it would check if the next token matches,- if it’s a nonterminal, like
value, it would predict, from the parsing table, which alternative of that nonterminal’s productions must be added onto the stack.Lexigram adds other symbols on the stack to call the wrapper:
- exit symbols for the nonterminals, so that the
exit_*(…)methods are called at the right time,- loop symbols to manage the iterations as we saw above,
- hook symbol to let the user intercept and modify specific tokens.
These symbols are shown in the log (“opcodes”).
In conclusion, the iterations of the parsing loop insert the items in the correct order, and nothing accumulates on the stacks. It’s more straightforward and not as resource-consuming.
The same mechanism is used in other types of iterations, like left-recursive rules and the low-latency * and + repetitions, which removes any concern of performance or memory footprint.
Plus +
For repetitions of one or more items, + can be used; the result is identical to * from the point of view of the listener implementation, except the name plus is used instead of star in the context variant.
definitions: ('def' Id '=' value ';')+;
What we don’t see in the listener trait is that the final grammar is slightly more complicated “internally”. The + is first normalized:
definitions -> definitions_1 . definitions_1 -> "def" Id "=" value ";" definitions_1 . definitions_1 -> "def" Id "=" value ";"
Since the productions begin with identical symbols, "def", Id, "=", and so on, this must be left-factorized, too:
definitions -> definitions_1 . definitions_1 -> "def" Id "=" value ";" definitions_2 . definitions_2 -> definitions_1 . definitions_2 -> ε
For a bottom-up parser, the transformed grammar is simpler and limited to the + normalization to a left-recursive rule:
definitions -> definitions_1 . definitions_1 -> definitions_1 "def" Id "=" value ";" . definitions_1 -> "def" Id "=" value ";"
Left Recursion
Let’s see how left recursion could be used for the definitions items.
As we saw in the LL(1) grammar limitations, left recursion is transformed into a right recursion. But, as we explained for the * repetition, the wrapper tweaks that right recursion to process the successive items in their incoming order, not in the reverse order like an original right-recursive rule would. So there is no performance impact to fear when using left-recursive rules in LL(1).
definitions:
definitions 'def' Id '=' value ';'
|
;
The transformed rules look identical to what we saw with the * repetition:
0: definitions -> definitions_1 1: . definitions_1 -> "def" Id "=" value ";" definitions_1 2: . definitions_1 -> ε
The rule doesn’t need to be modified:
0: definitions -> definitions "def" Id "=" value ";" 1: definitions -> ε
In both cases, the listener exposes context variants that show the original left-recursive production, and, unlike the * repetition, the wrapper calls the listener trait method at each iteration, leaving you the choice of the loop value type and how to use it.
// user-code template:
impl ConfigListener for Listener {
fn exit_definitions(&mut self, ctx: CtxDefinitions) -> SynDefinitions {
match ctx {
// definitions -> definitions "def" Id "=" value ";"
CtxDefinitions::V1 { definitions, id, value } => {}
// definitions -> ε
CtxDefinitions::V2 => {}
}
SynDefinitions()
}
// LL only
fn exitloop_definitions(&mut self, definitions: &mut SynDefinitions) {}
// ...
}
The same input is derived as follows:
definitions
─────┬─────
│ z
─────────────────────┴──────────────────────
definitions "def" Id("c") "=" value("2") ";"
─────┬─────
│ y
─────────────────────┴──────────────────────
definitions "def" Id("b") "=" value("1") ";"
─────┬─────
│ x
─────────────────────┴──────────────────────
definitions "def" Id("a") "=" value("0") ";"
─────┬─────
│ w
─┴─
ε
The successive calls are, in this case:
- LL:
init_definitions() exit_definitions(CtxDefinitions::V2), returns theSynDefinitionsvaluewexit_definitions(CtxDefinitions::V1 { id: "a", value: "0", definitions: w })returnsxexit_definitions(CtxDefinitions::V1 { id: "b", value: "1", definitions: x })returnsyexit_definitions(CtxDefinitions::V1 { id: "c", value: "2", definitions: y })returnsz- LL:
exitloop_definitions(&mut z)
And the value of definitions in exit_config(…), once it’s called, will be z.
As you can see above, LL benefits from a method called after the last iteration, exitloop_definitions(…). It’s easy to do thanks to the transformation in the grammar: when the alternative 2 is predicted on the last iteration, the wrapper calls the method. In comparison, this wasn’t possible in the case of a right-recursive rule because, when the loop finally exits, the parser must still make all the pending exit calls for the items on the stack. And since there is no separate nonterminal for the loop, it would make calling such an exitloop_*(…) method more complicated.
Unfortunately, it would be costlier to provide exitloop_definitions(…) for *LR, so it’s not available. The rule remains left-recursive in bottom-up parsers, so the situation is reversed: production 1 (with the empty symbol) is reduced first, then production 0 is reduced for each following iteration until the last one. When the end of the iterations comes up, the parser already has a definitions symbol ready on the stack and moves on immediately to the next part. Here, we could have added an initloop_definitions(…) method, but it would have been redundant with the call exit_definitions(CtxDefinitions::V2).
Left vs Right
Our need to encode the loop for definitions didn’t quite illustrate a subtlety between left and right recursion because we had an empty alternative. To remove any confusion and stress the difference between left and right, let’s introduce a non-empty alternative in each case.
Here is a right-recursive version that stops with an “end” terminal:
defs:
'def' Id '=' value ';' defs
| 'end' Id;
It corresponds to those productions (no transformation):
0: defs -> "def" Id "=" value ";" defs 1: defs -> "end" Id
It can parse an input that stops with “end”, since that’s the only admissible rightmost token in the original rule:
def a = 0;
def b = 1;
end loop
This would generate those successive calls:
- LL:
init_defs() exit_defs(CtxDefs::V2 { id: "loop" } -> xexit_defs(CtxDefs::V1 { id: "b", value: "1", defs: x }) -> yexit_defs(CtxDefs::V1 { id: "a", value: "0", defs: y }) -> z
And here is a left-recursive rule that starts with a “begin” terminal:
defs:
defs 'def' Id '=' value ';' // defs α
| 'begin' Id; // β
For an LL(1) parser, Lexigram must transform it into those productions:
0: defs -> "begin" Id defs_1 // β defs_1 1: . defs_1 -> "def" Id "=" value ";" defs_1 // α defs_1 2: . defs_1 -> ε // (loop end)
For an *LR parser, the productions aren’t modified:
0: defs -> defs 'def' Id '=' value ';' // defs α 1: defs -> 'begin' Id; // β
It can parse an input that starts with “begin”, since that’s the only admissible leftmost token in the original rule:
begin loop
def a = 0;
def b = 1;
This would generate those successive calls:
- LL:
init_defs() exit_defs(CtxDefs::V2 { id: "loop" }) -> xexit_defs(CtxDefs::V1 { id: "a", value: "0", defs: x }) -> yexit_defs(CtxDefs::V1 { id: "b", value: "1", defs: y }) -> z- LL:
exitloop_definitions(&mut z)
Latency
To close the loop, we’ll have a quick look at a variant of right recursion2 and */+ repetitions. We saw that those iterative constructs had a higher latency: the users gets a callback only after the whole rule is parsed. The right recursion puts everything in the stack until the last iteration, and only then starts calling the listener methods. Similarly, the * and + repetitions deliver the vector of collected items once the loop has ended.
Yet they provide useful alternatives to left recursion, by allowing independent terms at the end for the right recursion and a more natural grammar representation of repetitions. Wouldn’t it be worth having a way to get the loop items earlier?
That’s why the “low-latency” attribute was introduced.
In a low-latency right recursion, the rule has to be written as follows (the <L> can be placed anywhere in the recursive alternative):
definitions: 'def' Id '=' value ';' <L> definitions | ;
Lexigram doesn’t change the productions:
1: definitions -> "def" Id "=" value ";" definitions 2: definitions -> ε
But the listener methods do change:
// user-code template:
impl ConfigListener for Listener {
fn init_definitions(&mut self) -> SynDefinitions {
SynDefinitions(vec![])
}
fn exit_definitions(&mut self, acc: &mut SynDefinitions, ctx: CtxDefinitions) {
match ctx {
// definitions -> "def" Id "=" value ";" <L> definitions
CtxDefinitions::V1 { id, value } => {
acc.0.push((id, value));
}
// definitions -> ε
CtxDefinitions::V2 => {}
}
}
// ...
}
Now,
self.init_definitions()returns the initial value of the loop variable; for example, an empty vector.self.exit_definitions(acc, ctx)is called after parsing the independent term and each iteration.
At first, calling init_definitions(…), then exit_definitions(…) on the independent term may sound redundant, since both could provide the initial value, but they allow to separate the initialization of the nonterminal, before any part of it is parsed, and adjust it with the independent term if necessary. The other reason to do so is the mutable reference to the loop variable, acc, which is usually more efficient than moving its value at each iteration.
Since it’s a right recursion, there is still no way to know when it’s the last iteration, but now the data can be processed directly in the incoming order. The example of code above will provide a vector containing the items in the correct order. It would also allow you to check that Id hasn’t already been defined before and, if so, to return the appropriate error message. And it would allow you to use an already defined Id as value, without using a second pass.
The low-latency repetition is written a little differently, since the name of the loop nonterminal is given explicitly this time:
definitions: (<L=i_def> 'def' Id '=' value ';')*;
The resulting productions are the same, except maybe for the nonterminal name:
1: definitions -> i_def 2: . i_def -> "def" Id "=" value ";" i_def 3: . i_def -> ε
1: definitions -> i_def 2: . i_def -> i_def "def" Id "=" value ";" 3: . i_def -> ε
But the listener methods change, too:
// user-code template:
impl ConfigListener for Listener {
// LL only
fn init_definitions(&mut self) {}
fn exit_definitions(&mut self, ctx: CtxDefinitions) -> SynDefinitions {
// definitions -> (<L> "def" Id "=" value ";")*
let CtxDefinitions::V1 { star } = ctx;
SynDefinitions()
}
fn init_i_def(&mut self) -> SynIDef {
SynIDef(vec![])
}
fn exit_i_def(&mut self, acc: &mut SynIDef, ctx: CtxIDef) {
// `<L> "def" Id "=" value ";"` iteration in
// `definitions -> ( ►► <L> "def" Id "=" value ";" ◄◄ )*`
let CtxIDef::V1 { id, value } = ctx;
acc.0.push((id, value));
}
// LL only
fn exitloop_i_def(&mut self, acc: &mut SynIDef) {}
}
This variant allows you to define the type of the loop variable and to handle it directly.
self.init_i_def()is called before the first loop production is parsed to initialize the loop variable.self.exit_i_def(acc, ctx)is called after each iteration is parsed. Like the low-latency right recursion, it also uses a mutable reference to the loop variable instead of using a context and returning the new value.- LL:
self.exitloop_i_def(acc)is called after all the interations
There is no indication of the last iteration, but since there is an exit_definitions(…), it’s not really necessary; you can do any post-processing on star in that method if necessary.
Note
In the case of the
+repetition, there is an additional flag in the context that indicates the last iteration. Unlike the*repetition, it’s very easy to provide.CtxIDef::V1 { id: String, value: SynValue, last_iteration: bool } ^^^^^^^^^^^^^^
Finally, the low-latency attribute can also be used in the token-separated lists we saw earlier:
definitions: 'def' (<L=i_def> Id '=' value / ',')+ ';';
This concludes the quick tour of the art of loops with top-down and bottom-up parsers using Lexigram.
Considering definitions has no independent term, the * repetition, with or without <L>, seems a good way to handle that language element. The low-latency version offers the advantage of directly doing operations that would otherwise require post-processing the final vector or dictionary, so it may be the better choice here.
value & Recap
The value that our constants can represent are varied:
- string literals, for file names, tag names
- unsigned integer literals, for indentation levels
- boolean literals, to enable optional features like spans generation
- identifiers, if one constants equals another
- keywords like
stdoutwhich is a possible output code location
The grammar elements so far are as follows, where some details are not yet defined (the …). This time, we show the full lexicon definitions instead of a simplified grammar:
lexicon Config;
fragment EscChar : '\\' [nrt"\\];
fragment Char : EscChar | ~[\n\r\t"\\];
// punctuation and operators
Equal : '=';
Semicolon : ';';
// keywords
Def : 'def';
Lexer : 'lexer';
Options : 'options';
Parser : 'parser';
Stdout : 'stdout';
// variable terminals
BoolLiteral : 'false' | 'true';
Id : [a-zA-Z][a-zA-Z_0-9]*;
NumLiteral : [0-9]+;
StrLiteral : '"' Char+ '"';
SComment : '/*' .*? '*/' -> skip;
SLineComment : '//' ~[\r\n]* -> skip;
SWhiteSpace : [ \n\r\t]+ -> skip;
// -----------------------------------------------------------------------------
grammar Config;
config:
definitions
lexer
parser
options
;
definitions:
(<L=i_def> 'def' Id '=' value ';')* // any type
;
lexer:
'lexer' …
;
parser:
('parser' …)?
;
options:
('options' …)?
;
value:
BoolLiteral
| NumLiteral
| StrLiteral
| Id
| 'stdout'
;
A few comments on the lexicon:
- The
fragmentacts as an alias for lexical rules, or parts of lexical rules, that you intend to use multiple times or that you’d rather write separately for the sake of clarity. - The rules are expressed like simple regular expressions:
- Matching string literals are between single quotes:
'def'. - Sets of characters can be defined between square brackets (
[a-z]) or as ellipsis-separated characters ('a'..'z'). The dot.means any character at all. - An item can be negated with the prefix
~(normally used with character sets). - Items can be optional (
?) or repeated (*or+); non-greedy repetitions are noted*?and+?. - Escape codes can be used for usual characters:
\n,\r,\t,\\,\', and for UTF-8 codes:\u{3b5}.
- Matching string literals are between single quotes:
- The fixed keywords are defined before variable tokens like
Id, which could conflict with them. For example, “def” corresponds to both the definition ofDefandId. In that case, the first defined keyword prevails, which is what we want here. It means we can’t use “def” as anId, but that’s a usual limitation in programming languages. - The last three tokens have a
-> skipaction—everything after->is called an action.skipdiscards the token, so the parser will never receive it. In this case, we use that to discard all the comments and the white spaces and lines between the other tokens. It’s placed after everything so we’re sure those rules have the lowest priority.
The value productions are straightforward. The four first tokens are variable, so the parsed input is available in the context variants:
pub enum CtxValue {
V1 { boolliteral: String }, // value -> BoolLiteral
V2 { numliteral: String }, // value -> NumLiteral
V3 { strliteral: String }, // value -> StrLiteral
V4 { id: String }, // value -> Id
V5, // value -> "stdout"
}
pub trait ConfigListener {
// ...
fn init_value(&mut self) {}
fn exit_value(&mut self, ctx: CtxValue) -> SynValue;
}
lexer and parser
The lexer and the parser specifications are similar: they include, between brackets, one or more comma-separated options of the type:
combinedandinput: define the location of the lexicon; in the case ofcombined, it also contains the grammar.output: defines the location of the generated code.header: defines header(s) put in front of the generated code; e.g. inner attributes, comments, … (header: { "#![allow(unused)]", "#![cfg(tests)]" })indent: defines the indentation (indent: 4).
An input location is either
- a filename (
input: "config.l"). - a filename and the name of a tag between square brackets (
input: "config.lg" ["lexicon"]).
An output location can be either
- a filename or
stdout. - a filename or
stdout, and the name of a tag between square brackets.
Since both lexer and parser use the same types of options, we’ll use a common io_options rule to parse them.
It would be possible to force the grammar to accept either combined or input, and even to accept combined only for the lexer and not the parser, but it would complicate it significantly. It’s much easier to accept a list of any option and to verify them in the listener.
Similarly, we’ll use value for each argument, even if "indent" only accepts a number (or a constant Id holding a number) and "input" only accepts a string literal. Again, it’s easier to check the correct type in the listener than to surcharge the grammar.
Here are a few additions to the lexicon:
Colon : ':';
Comma : ',';
Lbracket : '{';
LSbracket : '[';
Rbracket : '}';
RSbracket : ']';
Combined : 'combined';
Headers : 'headers';
Indent : 'indent';
Input : 'input';
Output : 'output';
and to the grammar:
lexer:
'lexer' '{' io_options '}'
;
parser:
('parser' '{' io_options '}')?
;
io_options:
io_option (',' io_option)*
;
io_option:
'combined' ':' value tag_opt
| 'input' ':' value tag_opt
| 'output' ':' value tag_opt
| 'indent' ':' value
| 'headers' ':' '{' value (',' value)* '}'
;
tag_opt:
('[' value ']')?
;
The lexer part is simple:
pub enum CtxLexer {
/// `lexer -> "lexer" "{" io_options "}"`
V1 { io_options: SynIoOptions },
}
pub trait ConfigListener {
// ...
fn init_lexer(&mut self) {}
fn exit_lexer(&mut self, ctx: CtxLexer) -> SynLexer;
}
The parser part adds an alternative used when there is no parser (the listener methods are similar to the lexer’s):
pub enum CtxParser {
/// `parser -> "parser" "{" io_options "}"`
V1 { io_options: SynIoOptions },
/// `parser -> ε`
V2,
}
Similar context variants are used for the optional content of tag_opt.
Token-separated items
It’s cumbersome to have to repeat io_option in the io_options rule just because the separator , isn’t before the first item:
io_options: io_option (',' io_option)*;
^^^^^^^^^ ^^^^^^^^^
Here, it’s not too serious, but what if we had several items to repeat? To simplify frequent cases like this one, Lexigram offers an extended syntax when the repeated items are separated by one or several constant tokens3:
io_options: (io_option / ',')+;
It has the added advantage of collecting all the items in the loop variable, instead of presenting the first item separately and the rest in the loop variable. More information about this syntax can be found in the reference.
This syntax can be used with the <L> attribute like regular repetitions, too, and this is what we’ll choose for our grammar:
io_options: (<L=i_io_opt> io_option / ',')+;
The methods and their parameters remain the same as in normal repetitions:
pub enum CtxIoOptions {
/// `io_options -> (<L> io_option / ",")+`
V1 { plus: SynIIoOpt },
}
pub enum CtxIIoOpt {
/// `<L> io_option / ","` iteration in `io_options -> ( ►► <L> io_option / "," ◄◄ )+`
V1 { io_option: SynIoOption },
}
pub enum CtxIIoOpt {
/// `<L> "," io_option` iteration in
/// `io_options -> io_option ( ►► <L> "," io_option ◄◄ )*`
V1 { io_option: SynIoOption },
}
pub trait ConfigListener {
// ...
fn init_io_options(&mut self) {} // LL only
fn exit_io_options(&mut self, ctx: CtxIoOptions) -> SynIoOptions;
fn init_i_io_opt(&mut self, ctx: InitCtxIIoOpt) -> SynIIoOpt;
fn exit_i_io_opt(&mut self, acc: &mut SynIIoOpt, ctx: CtxIIoOpt);
fn exitloop_i_io_opt(&mut self, acc: &mut SynIIoOpt) {} // LL only
}
Since it’s an <L> loop, init_i_io_opt(…) returns the initial value of the accumulator, and each call to exit_i_io_opt(…) provides a mutable reference to it while it’s still on the stack. Removing the loop variable from the context is indeed more efficient than popping the accumulator from the stack, moving it into the context, then out again in the user’s implementation, and finally pushing the new returned value on the stack again.
We’ll do something similar in io_option, although without the <L> attribute this time:
io_option:
'combined' ':' value tag_opt
| 'input' ':' value tag_opt
| 'output' ':' value tag_opt
| 'indent' ':' value
| 'headers' ':' '{' (value / ',')+ '}' // string
;
pub enum CtxIoOption {
/// `io_option -> "combined" ":" value tag_opt`
V1 { value: SynValue, tag_opt: SynTagOpt },
/// `io_option -> "input" ":" value tag_opt`
V2 { value: SynValue, tag_opt: SynTagOpt },
/// `io_option -> "output" ":" value tag_opt`
V3 { value: SynValue, tag_opt: SynTagOpt },
/// `io_option -> "indent" ":" value`
V4 { value: SynValue },
/// `io_option -> "headers" ":" "{" (value / ",")+ "}"`
V5 { plus: SynIoOption1 },
}
pub enum CtxTagOpt {
/// `tag_opt -> "[" value "]"`
V1 { value: SynValue },
/// `tag_opt -> ε`
V2,
}
pub trait ConfigListener {
// ...
fn init_io_option(&mut self) {} // LL only
fn exit_io_option(&mut self, ctx: CtxIoOption) -> SynIoOption;
}
Since it’s a non-<L> repetition, the wrapper takes everything in charge to provide us with an ordered vector, as it would for a normal repetition. If we parse the following input:
headers: { "a", "b", "c" }
we get a vector vec![a, b, c] in star.0, where a is the SynValue for “a”, and so on.
options
The general options are different from the io_options of the lexer and the parser, although indent and headers are common. They include, between brackets, one or more comma-separated options:
headersandindent: define the headers and the indentation level for all the components; the syntax is the same as before.libs: defines extra bindings for the wrapper; e.g.libs: { "super::listener_types", "std::collections::HashMap" }nt-valuedefines which nonterminals hold a value of the typeSyn<nonterminal name>:nt-value: default: the nonterminals defined in the grammar and the<L>nonterminals hold a value (which is the default behaviour).nt-value: none: all the nonterminals are valueless. They’re not in the context variants, and there’s no value to return from theexit_*(…)methods. It’s a good option if all the values can easily be stored in the listener.nt-value: parents: only the nonterminals defined in the grammar hold a value. Any nonterminal generated from transformations like left recursion don’t hold any value.nt-value: set { "a", "b", "c" }: only nonterminalsa,b, andchold a value.
spans: followed by a boolean value
We need a few extra keywords in the lexicon:
Libs : 'libs';
NTValue : 'nt-value';
Spans : 'spans';
The main grammar rules follow a similar pattern to what we did for the lexer and parser:
options:
('options' '{' global_options '}')?
;
global_options:
(<L=i_global_opt> global_option / ',')+
;
global_option:
'headers' ':' '{' (value / ',')+ '}'
| 'indent' ':' value
| 'libs' ':' '{' (value / ',')+ '}'
| 'nt-value' ':' nt_value
| 'spans' ':' value
;
For global_options, and for "headers" and the "libs" in global_option, we’re using the same token-separated-items lists as before. Since there’s nothing new, we’re not going to look at the generated code, that we’ll see in the implementation section anyway.
The last nonterminal to define is nt_value. Here are the last keywords we need for the lexer:
Default : 'default';
None : 'none';
Parents : 'parents';
Set : 'set';
And here is the grammar part. We use value for the nonterminal names instead of Id because we want to avoid collisions with the existing keywords. For example, we wouldn’t be able to use nonterminal names like lexer and parser in that list, since the lexer wouldn’t identify them as Id, but as other tokens. There is a way around that with more advanced features of Lexigram, though, as you can see in the gen_typedef / typedef example.
nt_value:
'default'
| 'none'
| 'parents'
| 'set' '{' (value / ',')+ '}'
;
Final Grammar
// =============================================================================
// Lexicon
// -----------------------------------------------------------------------------
lexicon Config;
fragment ESC_CHAR : '\\' [nrt"\\];
fragment CHAR : ESC_CHAR | ~[\n\r\t"\\];
// punctuation and operators
Colon : ':';
Comma : ',';
Equal : '=';
Lbracket : '{';
LSbracket : '[';
Rbracket : '}';
RSbracket : ']';
Semicolon : ';';
// keywords
Combined : 'combined';
Def : 'def';
Default : 'default';
Headers : 'headers';
Indent : 'indent';
Input : 'input';
Lexer : 'lexer';
Libs : 'libs';
None : 'none';
NTValue : 'nt-value';
Options : 'options';
Output : 'output';
Parents : 'parents';
Parser : 'parser';
Set : 'set';
Spans : 'spans';
Stdout : 'stdout';
// variable terminals
BoolLiteral : 'false' | 'true';
Id : [a-zA-Z][a-zA-Z_0-9]*;
NumLiteral : [0-9]+;
StrLiteral : '"' CHAR+ '"';
SComment : '/*' .*? '*/' -> skip;
SLineComment : '//' ~[\r\n]* -> skip;
SWhiteSpace : [ \n\r\t]+ -> skip;
// =============================================================================
// Grammar
// -----------------------------------------------------------------------------
grammar Config;
config:
definitions
lexer
parser
options
;
definitions:
(<L=i_def> 'def' Id '=' value ';')*
;
lexer:
'lexer' '{' io_options '}'
;
parser:
('parser' '{' io_options '}')?
;
options:
('options' '{' global_options '}')?
;
io_options:
(<L=i_io_opt> io_option / ',')+
;
io_option:
'combined' ':' value tag_opt
| 'input' ':' value tag_opt
| 'output' ':' value tag_opt
| 'indent' ':' value
| 'headers' ':' '{' (value / ',')+ '}' // string
;
tag_opt:
('[' value ']')?
;
global_options:
(<L=i_global_opt> global_option / ',')+
;
global_option:
'headers' ':' '{' (value / ',')+ '}'
| 'indent' ':' value
| 'libs' ':' '{' (value / ',')+ '}'
| 'nt-value' ':' nt_value
| 'spans' ':' value
;
value:
BoolLiteral
| NumLiteral
| StrLiteral
| Id
| 'stdout'
;
nt_value:
'default'
| 'none'
| 'parents'
| 'set' '{' (value / ',')+ '}'
;