5 ms·

It might be nice for us less formally-trained persons to include a small description of what an LR(1) parser is. I tried looking it up wikipedia, but the articl

It might be nice for us less formally-trained persons to include a small description of what an LR(1) parser is. I tried looking it up wikipedia, but the article isn't that clear either IMHO.

ChuckMcM 11y ago
Here is a reasonable link - http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst...
- e12e 11y ago
  Thank you. I found that to be a perfect refresher before reading the article in this story. Does anyone know if there's a plan to move rusts own parser to a rust native tool? Now it apparently uses antlr4 along with some custom rust code: https://github.com/rust-lang/rust/tree/master/src/grammar https://github.com/rust-lang/rust/tree/master/src/grammar
  - kzrdude 11y ago
    That's just an alternative implementation of rust's grammar for verification purposes. Rust's parser is entirely hand coded inside rustc (in Rust).
    - e12e 11y ago
      Ah, I thought that was something new. I remember reading something about a manual parser a while back. Thank you for clarifying. Would there be a benefit to moving from hand coded to something like parent project for rustc? IIRC the rationale for hand-coding the parser was mostly speed (and a wish to avoid external (to rust) dependencies)?
      - kzrdude 11y ago
        Seeing this bug filed today (rather interesting/weird breaking change needed to fix it), it seems plain sanity should prefer a generated parser. https://github.com/rust-lang/rust/issues/28777 https://github.com/rust-lang/rust/issues/28777 I'm not a compiler hacker, so I don't know how to weigh it really though.
wfunction 11y ago
I literally took a compiler class just to learn what LR parsing is, and I had to spend an additional ~6 months of my free time just to write an LR parser generator that I found intellectually satisfying and didn't leave question marks in my brain. In other words, it's not something I expect you can read a couple sentences about and hope to understand well...
cynicalkane 11y ago
I find LR parsers to be conceptually simple--they're the same idea as recurisve descent parsers with the optimization that the many stack frames that result from "recursively descending" are bundled up into a single stack frame, corresponding to an 'item set' that contains every parse item that you might recursively descend into. You do not actually add a stack frame until you consume a token of input and "call" the next item set based on what token of input it was. So, if you have an item X that might call rules Y and Z, instead you have an item set {X, Y, Z}. This has the additional advantage that arbitrary left-recursion is handled naturally, since you're discarding the 'call graph' between rules when you build these sets. To deal with the compressed stack frames that you've now built, you construct a goto table for each item set that tells you what to do based on what item has been returned to you, from the observation that only certain items could have 'called' certain other rules in the first place. Finally, you add lookahead to your goto tables so that, in case of ambiguity, you can peek ahead to the next token and make your decision that way. This will not solve all ambiguity but it solves most cases in practice. This is a very hand-wavy description, but I hope it is useful if you decide to look further into the Wikipedia article. Unfortunately I have never seen a complete description of an LR(1) parser that takes the conceptual approach, and I don't have time to write one here.
- wfunction 11y ago
  Sorry, but I find this more confusing than anything. I would explain it more in terms of nondeterministic parsing (i.e. delaying the choice of the production rather than picking the production immediately) or in terms of "bottom-up" parsing (going from the string to the start symbol rather than the other way around). That said, it's way easier to understand what it should be doing than it is to understand it well enough to write one yourself.
barrkel 11y ago
The main contrast is with LL. LL(1) is trivially parsed with recursive descent; you start with the root production in the grammar, and you never need more than one token of lookahead to figure out which alternate to parse next. This maps naturally to turning productions into functions and alternation choices into switches on the next token. The parse tree is built from the top down, like a pre-order traversal, because the current production is chosen before the constituent productions and terminals are parsed. LR parsers build the tree from the bottom up. Productions / terminals get pushed onto a stack (shift) until there's enough information to decide what parent production to use, and children are popped off and replaced with the parent (reduce). The tree gets built post-order; the parents are built after the children are already built. The hard bit is figuring out whether the productions on the stack are enough to compose a parent rule or not. LR parser generators figure out a state machine for making shift / reduce decisions quickly.

It might be nice for us less formally-trained persons to include a small description of what an LR(1) parser is. I tried looking it up wikipedia, but the article isn't that clear either IMHO.

ChuckMcM 11y ago

Here is a reasonable link - http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demystified.html http://blog.reverberate.org/2013/07/ll-and-lr-parsing-demyst...

e12e 11y ago
Thank you. I found that to be a perfect refresher before reading the article in this story. Does anyone know if there's a plan to move rusts own parser to a rust native tool? Now it apparently uses antlr4 along with some custom rust code: https://github.com/rust-lang/rust/tree/master/src/grammar https://github.com/rust-lang/rust/tree/master/src/grammar
- kzrdude 11y ago
  That's just an alternative implementation of rust's grammar for verification purposes. Rust's parser is entirely hand coded inside rustc (in Rust).
  - e12e 11y ago
    Ah, I thought that was something new. I remember reading something about a manual parser a while back. Thank you for clarifying. Would there be a benefit to moving from hand coded to something like parent project for rustc? IIRC the rationale for hand-coding the parser was mostly speed (and a wish to avoid external (to rust) dependencies)?
    - kzrdude 11y ago
      Seeing this bug filed today (rather interesting/weird breaking change needed to fix it), it seems plain sanity should prefer a generated parser. https://github.com/rust-lang/rust/issues/28777 https://github.com/rust-lang/rust/issues/28777 I'm not a compiler hacker, so I don't know how to weigh it really though.

wfunction 11y ago

I literally took a compiler class just to learn what LR parsing is, and I had to spend an additional ~6 months of my free time just to write an LR parser generator that I found intellectually satisfying and didn't leave question marks in my brain. In other words, it's not something I expect you can read a couple sentences about and hope to understand well...

cynicalkane 11y ago

I find LR parsers to be conceptually simple--they're the same idea as recurisve descent parsers with the optimization that the many stack frames that result from "recursively descending" are bundled up into a single stack frame, corresponding to an 'item set' that contains every parse item that you might recursively descend into. You do not actually add a stack frame until you consume a token of input and "call" the next item set based on what token of input it was. So, if you have an item X that might call rules Y and Z, instead you have an item set {X, Y, Z}. This has the additional advantage that arbitrary left-recursion is handled naturally, since you're discarding the 'call graph' between rules when you build these sets. To deal with the compressed stack frames that you've now built, you construct a goto table for each item set that tells you what to do based on what item has been returned to you, from the observation that only certain items could have 'called' certain other rules in the first place. Finally, you add lookahead to your goto tables so that, in case of ambiguity, you can peek ahead to the next token and make your decision that way. This will not solve all ambiguity but it solves most cases in practice. This is a very hand-wavy description, but I hope it is useful if you decide to look further into the Wikipedia article. Unfortunately I have never seen a complete description of an LR(1) parser that takes the conceptual approach, and I don't have time to write one here.

wfunction 11y ago
Sorry, but I find this more confusing than anything. I would explain it more in terms of nondeterministic parsing (i.e. delaying the choice of the production rather than picking the production immediately) or in terms of "bottom-up" parsing (going from the string to the start symbol rather than the other way around). That said, it's way easier to understand what it should be doing than it is to understand it well enough to write one yourself.

barrkel 11y ago

The main contrast is with LL. LL(1) is trivially parsed with recursive descent; you start with the root production in the grammar, and you never need more than one token of lookahead to figure out which alternate to parse next. This maps naturally to turning productions into functions and alternation choices into switches on the next token. The parse tree is built from the top down, like a pre-order traversal, because the current production is chosen before the constituent productions and terminals are parsed. LR parsers build the tree from the bottom up. Productions / terminals get pushed onto a stack (shift) until there's enough information to decide what parent production to use, and children are popped off and replaced with the parent (reduce). The tree gets built post-order; the parents are built after the children are already built. The hard bit is figuring out whether the productions on the stack are enough to compose a parent rule or not. LR parser generators figure out a state machine for making shift / reduce decisions quickly.