Who are these errors for?

[osa1]

I've been using LALRPOP for many years. I understand LR(1) and LALR(1) in detail. I have my own LR(1) parser generator. I even studied the lane table algorithm, though I gave up before fully grasping it.

Yet I don't understand what exactly lalrpop errors are saying, other than the last few lines, in 10,000s of lines in total.

Consider this grammar, which is ~1,200 lines of lalrpop.

I get a shift/reduce conflict when I make this change:

diff --git a/src/parser.lalrpop b/src/parser.lalrpop
index 7103b05..9d804b4 100644
--- a/src/parser.lalrpop
+++ b/src/parser.lalrpop
@@ -261,6 +261,9 @@ Type: Type = {

     "row[" <alts:Sep<VariantAlt, ",">> <extension:RowExtension> "]" =>
         Type::Variant { alts, extension, is_row: true },
+
+    "(" Type ")" =>
+        todo!(),
 }

and lalrpop prints 41,190 lines of errors for it!

In the errors, there seems to be three parts.

The first part has an example that makes no sense:

src/parser.lalrpop:318:5: 318:47: Local ambiguity detected

  The problem arises after having observed the following symbols in the input:
    (<RecordTypeField> ",")+ "(" Type
  At that point, if the next token is a `")"`, then the parser can proceed in
  two different ways.

  First, the parser could execute the production at
  src/parser.lalrpop:318:5: 318:47, which would consume the top 1 token(s) from
  the stack and produce a `RecordTypeField`. This might then yield a parse tree
  like
    "(" Type                        ╷ RowExtension ")"
    │   ├─RecordTypeField───────────┤                │
    │   └─Sep<RecordTypeField, ",">─┘                │
    └─TypeNoFn───────────────────────────────────────┘

  Alternatively, the parser could shift the `")"` token and later use it to
  construct a `Type`. This might then yield a parse tree like
    (<RecordTypeField> ",")+ "("     Type    ")"
    │                        ├─Type────────────┤
    │                        └─RecordTypeField─┤
    └─Sep<RecordTypeField, ",">────────────────┘

  See the LALRPOP manual for advice on making your grammar LR(1).

In particular, "after having observed the following symbols" part makes no sense, because if you observed "(" Type then you can't reduce when the lookahead token is ")", you have to shift (lookahead as in LR(1) item lookahead). There are no productions that lets you reduce "(" Type.

Then there are 40,000+ lines of LR(1) states dumped. Clearly this part is useless, right? Or do we have a use case where you read 40,000 lines of LR(1) state dumps? Who are we dumping this information for?

Then the last part which is the only part that's actually useful:

src/parser.lalrpop:318:5: 318:47: Conflict detected

    when in this state:
  RecordTypeField = Type (*) [<snip>]
  Type = "(" Type (*) ")" [<snip>]

  and looking at a token `")"` we can reduce to a `RecordTypeField` but we can also shift

This explains the actual shift/reduce conflict.

This last part has the same location as the first part (parser.lalrpop:318:5).

It seems to me that if we could just print the first and last parts that would be enough. What is the other 40,000+ lines of errors for?

(As mentioned, I think the first part is buggy, but I'm assuming it can be fixed and then it would be helpful.)

[dburgener]

In particular, "after having observed the following symbols" part makes no sense, because if you observed "(" Type then you can't reduce when the lookahead token is ")", you have to shift (lookahead as in LR(1) item lookahead). There are no productions that lets you reduce "(" Type.

I of course don't know the weeds of your grammar, but I think this error is correct. You're not reducing "(" Type here, you're reducing just Type to a RecordTypeField, etc as described in the error, until eventually you could reduce to this production. The error looks clear to me, so if you're looking for improvement, I'd need specific things that you find confusing.

Then there are 40,000+ lines of LR(1) states dumped. Clearly this part is useless, right? Or do we have a use case where you read 40,000 lines of LR(1) state dumps? Who are we dumping this information for?

Yes, this is a bug. This is the tracking issue for it: #728

I fixed some of the cases (#926 and #938), but there are some tricky ones I haven't managed to figure out yet. The basic situation is that lalrpop believes it's found a real, useful error, but it fails to make a useful error message. In the absence of the useful error message it dumps what it calls "naive" errors. The linked PRs try to reduce naive errors down to only 1 naive error for each real error, but don't cover all the cases. In particular, if you have a shift/reduce conflict for which we failed to make a better error message, it's hard to say which shift/reduce naive error is the appropriate one to return - they're technically different conflicts since they involve different lookaheads. Ideally, we should be able to detect that they all stem from the same issue, and return one "real" error. I didn't actually look at your errors, but I suspect that your "real" errors in this instance are the same issue as the shift/reduce errors, but lalrpop can't figure that out right now, and we definitely want to avoid giving no errors when something went wrong.

In my experience, this seems to happen particularly with empty productions like you have here. I think something about that is tripping lalrpop up, but the error generation code is fairly involved and abstract and I haven't had the time to dig in enough to fix it cleanly. I think there are probably several related bugs in there.

So in short, yes, the 40k lines is an error, and we're aware of it, but developer time is always tight. If you're interested in digging in more and submitting a PR to fix it, I can do a more thorough write-up of where my investigation has gone so far. I've intended to do that a few times in the past anyways, but I haven't managed to make it happen.