Help with providing good error messages to the user

[Elias-Graf]

I'm trying to write a parser for the following code:

(metric 
    :foo "bar"
    :label "123"
    :value 1
    "hello, world!"
    (bar))

For that, I have the following parsers:

pub WidgetCall: Spanned<WidgetCall> = {
    <l:@L> "(" <name:Symbol> <args:WidgetCallArg*> <children:WidgetCallChild*> ")" <r:@R> => {
        (l, WidgetCall::new(name, args, children), r).into()
    },
};

pub WidgetCallArg: WidgetCallArg = {
    ":" <name:Symbol> <value:Atom> => WidgetCallArg::new(name, value),
};

pub WidgetCallChild: WidgetCallChild = {
    Atom => <>.into(),
    WidgetCall => <>.into(),
};

The main goal, I'm pursuing for the parser, is to provide rich error message, currently for the WidgetCallArg. I would like that almost any way an arg is provided, there should be a message, telling you, what you are missing. E.g. missing the colon, missing the argument name, or the value.

Adding a rule like this:

pub WidgetCallArg: WidgetCallArg = {
    ":" <name:Symbol> <value:Atom> => WidgetCallArg::new(name, value),
    ":" <name:Symbol> => todo!("missing arg"),
};

It is problematic, because the program now can't decide if the next atom should be the argument, or the WidgetCallChild (which can also just be an atom).

So I've tried to work around this, by saying "you can't have children if the value of the argument is missing". Translating to the following code:

pub WidgetCall: Spanned<WidgetCall> = {
    <l:@L> "(" <name:Symbol> <args:WidgetCallArg*> <children:WidgetCallChild*> ")" <r:@R> => {
        (l, WidgetCall::new(name, args, children), r).into()
    },
    <l:@L>
    "("
    <name:Symbol>
    <mut args:WidgetCallArg*>
    <arg_trail:WidgetCallArgMissingValue>
    ")"
    <r:@R> => {
        args.push(arg_trail);
        (l, WidgetCall::new(name, args, Vec::new()), r).into()
    },
};

The problem with this is obvious, first, the parser does not work if there are any children. Second, the missing value detection only works on the last argument.

I've tried working around this for quite a long time now, but I only get more issues with ambiguous grammars and multiple productions. What would be the best way to solve something like this?

Runnable code (including some tests): Elias-Graf/rotten-potato@45056f7

I've also considered making the error reporting part of a post-processing step. Although I'd really prefer not to, since it's syntax, and it would make interpreting the AST generally more complicated. But even then, as long as I make the atom in the argument optional, I will run into the same problem as far as I'm concerned.

[yannham]

I think I have a hard time understanding, even as humans, how one can distinguish between both cases. Let's say you remove the 1 from your example, you get:

(metric 
    :foo "bar"
    :label "123"
    :value
    "hello, world!"
    (bar))

But this can be interpreted as :value being "hello, world!" (just reformatting to make it clearer):

(metric 
    :foo "bar"
    :label "123"
    :value "hello, world!"
    (bar))

Do you have one or more examples of the kind of errors that you'd like to catch (missing value for an argument) ? With the corresponding source?

[Elias-Graf]

Yes, I was afraid of something like this. Given that I currently would prefer not to switch the parsing framework, how would that "Proto-Grammar" look like? I still have the issue, that there are potentially two consecutive, optional atoms. Or am I missing something, because I'm tunnel visioning on my specific use-case?

[yannham]

The proto-AST doesn't have to be very complicated. There are probably many other possible designs, but here is how I would go about it as a first try:

1. Have a separate lexeme/token for argument name like :foo. Otherwise, unless you use a very specific LALRPOP setup, writing something like ":" <Symbol> will both match : foo and :foo because LALRPOP ignores whitespaces between tokens, so you won't be able to give nice error messages for missing parameter name. Let's call it this token (uncreatively) ColonSymbol. Let's also say that you require at least one character after the starting :, to differentiate it from the single colon (it's just a convention - I think it could work as well to merge the colon in the same token as an empty parameter name, if you don't use the colon elsewhere).
2. Create an enum that can hold all proto-widget call items, that is

   enum WidgetArgItem {
     Name(String),
     ValueOrChild(YourAstType),
   }

3. Create a corresponding rule for such items, that should now be unambiguous for the parser. You can already handle a missing parameter name without post-processing:

   pub WidgetArgItem: WidgetArgItem = {
     ColonSymbol => WidgetArgItem::Name(<>),
     <Atom | WidgetCall> => WidgetArgItem::ValueOrChild(<>),     
     ":" =>? Err(ParseError::User {
         error: MyError::MissingParamName,
     }),
   };
   

4. Parse arguments simply as a list of items, and then post-process:

   pub WidgetCall: Spanned<WidgetCall> = {
       "(" <name:Symbol> <args: WidgetArgItem*> ")" =>? {
           WidgetCall::from_items(name, args).map_err(|error| ParseError::User {error})
       },
   };
   

In this case, from_items would be fallible function returning Result<WidgetCall, E> that can do the second stage parsing, which I think here would be to make sure that the vector of items starts with (a potentially empty) prefix of alternating Name and ValueOrChilds, and then a sequence of ValueOrChild, and put that in your WidgetCall structure. You can look at the fallible action section of the book to see how to make custom errors that can be embedded in LALRPOP parse errors as I do here.

There are probably multiple ways of going about this, and I might have overlooked the specifics of your case that would entail a bit of tweaking. But hopefully this conveys the general idea.

[yannham]

(So, to answer your initial question, while "proto-AST" can sound like a whole different AST, here it would just be a short-lived Vec<Param name or atom or widget call> with no constraints on their particular order that is converted away to the real AST directly in the WidgetCall rule and thus would be invisible from the outside otherwise)

[Elias-Graf]

So essentially just throwing everything a widget can contain into a single parser, and check order and validity, not using grammar? I think I'm going to try this, but it also feels like it is removing a lot of the value, of having a "grammar-framework" in the first place.

The Section I wrote before, I think, I realized what you meant:

I don't think I can follow. The enum: WidgetArgItem, might be a value or a child? If we take a look back at the original grammar I posted:

pub WidgetCall: Spanned<WidgetCall> = {
    <l:@L> "(" <name:Symbol> <args:WidgetCallArg*> <children:WidgetCallChild*> ")" <r:@R> => {
        (l, WidgetCall::new(name, args, children), r).into()
    },
};

The arguments and children are two different consecutive structures, not something interlaced. What I tried to ask in my previous question, was essentially, how to write a parser that has:

<arg:WidgetCallArg> <child:WidgetCallChild>

When arg might be an Atom?, and child might be an Atom?, we would have Atom? Atom?, thus the parser wouldn't be able to decide if it should reduce to an arg, or shift to a child.

[yannham]

So essentially just throwing everything a widget can contain into a single parser, and check order and validity, not using grammar? I think I'm going to try this, but it also feels like it is removing a lot of the value, of having a "grammar-framework" in the first place.

Well, the grammar is still useful for parsing e.g. nested widget calls, parentheses, basic values. I would say there's just part of the grammar that is indeed offloaded to post-processing step.

In general, LALR parsers (and more generally generated parsers) are one trade-off in the design space. They are good at getting a grammar up and running quickly, at making the grammar "easy" to read (to map to and from an EBNF formal description, for example), and at making this grammar simple/easy to extend (as well as handling some other aspects such as precedence which isn't trivial in e.g. a basic handwritten recursive descent parser). They are reasonably fast. You can also write your parser in a left recursive style, which is much more natural.

However, LALR parsers aren't magical. It' more difficult to give very nice and specialized error messages (well, depends compared to what --but I think this is fair to say when compared to recursive descent parsers). They aren't necessarily always the fastest solution. I believe a number of mainstream language implementations use recursive descent parsing once the grammar is stable enough precisely to give nice error messages.

All in all, I think if widget stuff is just one part of your grammar, with many other rules that don't need such post-processing, this is still worth it. Or if you plan to experiment a bit with the syntax, extending or changing things along the way. On the other hand, if your grammar is small (mostly widget calls), fixed, and error messages are really important for you, then maybe LALRPOP is a bit superfluous, and you could do as much by just lexing and post-processing, or by using another parsing framework which is particularly good at error messages.

P.S: another possible technique would be to separate the fast and happy path, that is the source is valid input, and the error path. For example it's not hard to include error recovery in a LALRPOP parser with the special rule !, so that instead of erroring out, you can embed a special Error node in your AST. Doing so, you could keep your parser simple, without caring about error messages but focusing just on describing the grammar (no rule to match invalid widget arguments). Then, if you find an error node (that you would store with position information) in place of widget arguments for example, you could re-run a special, different rule, or even just an entirely different lexer that don't need to use the LALRPOP parser at all and can try to say something smart about the error. That would keep the main LALRPOP grammar clean, at least, but would probably lead to more code.