5 ms·

Recursive descent is very different (if I understand correctly.) Some languages that can be parsed with a recursive ascent parser cannot be parsed by a recursiv

by swiley 9y ago

Recursive descent is very different (if I understand correctly.) Some languages that can be parsed with a recursive ascent parser cannot be parsed by a recursive descent parser.

tyingq 9y ago
Right. Was responding to "But recursive-descent, if you're going to use it, seems to cry out for tooling"
- barrkel 9y ago
  As I mentioned in an uncle comment, recursive descent permits localised hackery to switch parsing scheme or dynamically fix tricky context-specific grammar constructs, which argues against tooling. Tooling is still very useful for grammar validation though, and it's the way to go for ad hoc parsing of a simple or new language.
- rejschaap 9y ago
  That was a typo, he meant to say recursive-ascent needs tooling. Recursive-descent parsers can be hand-written quite easily.
barrkel 9y ago
Yes; left recursion. However in practice left recursion can usually be eliminated by adjusting the grammar. Other cases can be handled using various degrees of grammar action cleverness. And finally, recursive descent lends itself naturally to parsing a subset of the language using a different scheme; top down operator precedence for expressions to avoid lots of redundant recursion is a fine example.
- nnq 9y ago
  > can usually be eliminated by adjusting the grammar Never understood this backwards way of thinking. You first write/immagine the grammar that you want to write, whatever is most intuitive for you. Then you figure out what kind of parser your grammar needs. Why would one contort a grammar? I mean, even "contorting it to not be context-dependent" is already a limitation enough...
  - barrkel 9y ago
    Why would you let the grammar dictate the architecture of your compiler? Left recursion in things like expressions is completely trivial to eliminate. If you want to e.g. embed a DSL in a language, something that's really easy to do with recursive descent, it's worth spending 30 seconds or so to remove left recursion from your expression rules. Etc. > You first write/immagine the grammar that you want to write, whatever is most intuitive for you. IMO this is the road to hard to parse languages; if you genuinely advocate this path, you'll end up needing a GLR parser before you know it. I think it's much better to ensure your grammar is parseable with LL(1); not only is the tooling simpler, but the language will be less ambiguous for human users too. Follow the example of Pascal, not C++. This is what I'd advocate even for people doing hand-written recursive descent on a new language: validate your grammar with an LL(k) tool even if you don't use the generated parser. (You've ended up sounding a bit like Ira Baxter, who's often seen around the net selling his DMS toolkit. He has a strong self-interest in people writing complicated grammars, so that he can sell them his services...)
    - tom_mellior 9y ago
      > You've ended up sounding a bit like Ira Baxter Haha, I was thinking about him too. He does have a point, though, that on 2018 machines we might be able to afford parsing technology a bit more expensive than the 1970s approaches commonly used today.
    - nnq 9y ago
      > but the language will be less ambiguous for human users too I'd bet against this. The human brain works very differently, we always keeps something like "trees of contexts" in our head. And why would you thing left recursions is less intuitive to a human user than other kinds of recursion. > ended up sounding a bit like Ira Baxter Now I gotta take time and google who this guy is :P
  - daemin 9y ago
    For the most part you can apply some simple rules to transform the BNF notation from being left recursive to being right recursive. It's most useful when you have a right recursive language but are using yacc or bison for the parser.

by swiley 9y ago

Recursive descent is very different (if I understand correctly.) Some languages that can be parsed with a recursive ascent parser cannot be parsed by a recursive descent parser.

tyingq 9y ago

Right. Was responding to "But recursive-descent, if you're going to use it, seems to cry out for tooling"

barrkel 9y ago
As I mentioned in an uncle comment, recursive descent permits localised hackery to switch parsing scheme or dynamically fix tricky context-specific grammar constructs, which argues against tooling. Tooling is still very useful for grammar validation though, and it's the way to go for ad hoc parsing of a simple or new language.
rejschaap 9y ago
That was a typo, he meant to say recursive-ascent needs tooling. Recursive-descent parsers can be hand-written quite easily.

barrkel 9y ago

Yes; left recursion. However in practice left recursion can usually be eliminated by adjusting the grammar. Other cases can be handled using various degrees of grammar action cleverness. And finally, recursive descent lends itself naturally to parsing a subset of the language using a different scheme; top down operator precedence for expressions to avoid lots of redundant recursion is a fine example.

nnq 9y ago
> can usually be eliminated by adjusting the grammar Never understood this backwards way of thinking. You first write/immagine the grammar that you want to write, whatever is most intuitive for you. Then you figure out what kind of parser your grammar needs. Why would one contort a grammar? I mean, even "contorting it to not be context-dependent" is already a limitation enough...
- barrkel 9y ago
  Why would you let the grammar dictate the architecture of your compiler? Left recursion in things like expressions is completely trivial to eliminate. If you want to e.g. embed a DSL in a language, something that's really easy to do with recursive descent, it's worth spending 30 seconds or so to remove left recursion from your expression rules. Etc. > You first write/immagine the grammar that you want to write, whatever is most intuitive for you. IMO this is the road to hard to parse languages; if you genuinely advocate this path, you'll end up needing a GLR parser before you know it. I think it's much better to ensure your grammar is parseable with LL(1); not only is the tooling simpler, but the language will be less ambiguous for human users too. Follow the example of Pascal, not C++. This is what I'd advocate even for people doing hand-written recursive descent on a new language: validate your grammar with an LL(k) tool even if you don't use the generated parser. (You've ended up sounding a bit like Ira Baxter, who's often seen around the net selling his DMS toolkit. He has a strong self-interest in people writing complicated grammars, so that he can sell them his services...)
  - tom_mellior 9y ago
    > You've ended up sounding a bit like Ira Baxter Haha, I was thinking about him too. He does have a point, though, that on 2018 machines we might be able to afford parsing technology a bit more expensive than the 1970s approaches commonly used today.
  - nnq 9y ago
    > but the language will be less ambiguous for human users too I'd bet against this. The human brain works very differently, we always keeps something like "trees of contexts" in our head. And why would you thing left recursions is less intuitive to a human user than other kinds of recursion. > ended up sounding a bit like Ira Baxter Now I gotta take time and google who this guy is :P
- daemin 9y ago
  For the most part you can apply some simple rules to transform the BNF notation from being left recursive to being right recursive. It's most useful when you have a right recursive language but are using yacc or bison for the parser.