How to improve user experience in writing semantic actions

[jsinger67]

parol's approach to incorporating semantic user actions in grammar processing currently forces the
user to make a detour to the expanded grammar, a canonicalized version of the user's input grammar.

The applied canonicalization is necessary to be able to process the grammar efficiently by a parser.
Actually this is a technical requirement the user isn't necessarily aware of. And thus it is a
source of irritation.

A user actually wants to apply semantic actions to his initial input grammar. He doesn't even want
to know that there exists something like a transformed grammar.

This aspect was recognized in early stages of parol's development and should be addressed by new
features of parol. Thanks to Techcable for contributing a lot to
this idea. See also our discussion here

We took a look at some projects which dealt with similar problems like
ungrammar and
Oak.

As a result the idea was born to synthesize each semantic action of a transformed grammar so that it
structurally recreates the types of an abstract syntax tree the user expects.

Let's explain this with a short example.

A comma separated integer list grammar can be written like this:

%start List
%%
List: Num { "," Num };
Num: "0|[1-9][0-9]*";

The canonicalized version looks like this:

%start List
%%
List: Num ListList;
ListList: "," Num ListList;
ListList: ;
Num: "0|[1-9][0-9]*";

The interesting construct here is the repetition expression {...} and how it is transformed during
canonicalization:

p: a { r } b;

where a, r and b are arbitrary expressions, is transformed to

p: a R b;
R: r R;
R: ;

In our example r is actually "," Num, i.e. the expression between { and }, a is Num and b
is empty. R is a newly introduced non-terminal with one occurrence on the right-hand side of the
initial production and two productions where it forms the left-hand side.

The goal is now

• to deduce the type the user expects from the structure of our transformed grammar and
• to deduce semantic primitives that can be automatically generated.

Let's first detail the aspect of type deduction a bit.

Type deduction

In the example above the user may expect List to be of type

// List: Num { "," Num };
struct List {
    num: Num,
    list_list: Vec<ListList>,
}

// With further types:

type Num = Token;       // "0|[1-9][0-9]*"
type Comma = Token;     // ","

struct ListList {
    comma: Comma,
    num: Num,
}

Note that the names of the data types are fully deduced by the grammar's symbols and thus might be
surprising sometimes. But this can be addressed by further improvements. For instance we could
provide the opportunity to specify naming hints. But this is not subject of this paper.

The type of the vector in struct List could have been a tuple too but I decided to use structures
here for several reasons. The first one is that a struct could be constructed via builder pattern.
The second one is that a production has symbols with "names" (token names and non-terminal names)
that could be used to generate named struct members, freeing the user from needing to know the
order of the tuple's elements. The third reason is that it is easier to have a fixed mapping between
productions and their types of kind struct.

To be clear, what the user expects to be the type of a semantic action is the type of the parameter
that is provided to his semantic action for a certain productions. In our example he wants his
semantic action for production List: Num { "," Num }; to have this signature:
fn list(&mut self, arg: &List).

For the semantic actions we want to synthesize the case is the other way around.
A semantic action for production List: Num ListList; (taken from the transformed
grammar, known as expanded grammar) should have this signature:
fn list(&mut self, num: Num, list_list: ListList) -> List.
To transform the input argument tuple into the output form we need to generate sematic code.

Let me point to a detail of the signature shown here. The return type is actually unit, () or
even more correctly Result<()>. The value of output type List is actually outputted onto the
item stack for further processing in succeeding actions. This results from the way the parser calls
semantic actions. It doesn't pass the output of a certain action to the input of the next action.
They exchange values via the item stack only.

Now is the time to have a look at the semantic gap we have to fill in our generated actions.

Semantic content of the actions

All actions can be thought of functions that have input and output types. The semantic, i.e. the
code in the actions have at least one task. This task is to transform input values into a form that
represents the output value, resp. the output type. Some of the actions have additional tasks that
are defined by their position in the grammar. For instance "outer" actions, i.e. those that share
their names with the ones from the users grammar, have to call the related user's semantic actions
with the generated output type as argument.

fn list_0(
    &mut self,
    num_0: &ParseTreeStackEntry,
    _list_list_1: &ParseTreeStackEntry,
    parse_tree: &Tree<ParseTreeType>,
) -> Result<()> {
    let context = "list_0";

    // Transform the arguments into a value of the output type `List`

    // First take the token from the argument list:
    let num_0 = num_0.token(parse_tree)?.to_owned();

    // Next take the ListList form the item stack
    if let Some(ASTType::ListList(mut list_list_1)) = self.pop(context) {
        // Reverse the list's content
        list_list_1.reverse();

        // Build the output value with a builder
        let out_val = ListBuilder::default()
            .num_0(num_0)
            .list_list_1(list_list)
            .build()
            .into_diagnostic()?;

        // Call the user action with the built value
        self
            .user_grammar.list(&out_val)
            // Push the output value onto the item stack for further processing
            .and_then(|_| self.push(ASTType::List(out_val, context)))
    } else {
        Err(miette!(
            "{}: Expected 'Fac(Factor::NonTerminal)' on TOS.",
            context
        ))
    }
}

Function with this format we want to synthesize completely from the structure of the user grammar
and the expanded grammar.
This synthesis of actions and types should be optional and the old approach should be still usable
to support users that want to have full control over their language processing and who don't have
problems to handle with expanded grammar and semantic actions on it.

Currently some experiments are conducted to test the feasibility of this concept.
Further updates and details will be posted here.

Everyone is encouraged to contribute to this discussion.

[jsinger67]

As of version v0.6.0 the above described feature is available in parol. You simply have to enable the auto-generation in the builder or by setting the -g flag on the command line.
All semantic actions of the expanded grammar are generated for you in the form described above. Types that resemble the structure of your grammar are also generated for you.

So, forget about the expanded grammar 😉

Feedback is appreciated.
Have fun 👍