4 ms·

Formal languages / parsing theory is one of the most difficult for me to understand. No other theory feels so easy to get decent results in practice, yet so obs

Formal languages / parsing theory is one of the most difficult for me to understand. No other theory feels so easy to get decent results in practice, yet so obscure in theory. I have experience in writing parsers and small langs but whenever I have to approach all those theories behind parsers and grammar then Im lost I dont understand why would you want to approach those problems in such a way, or at least describe it in such a way that feels so out of touch with programming This theory is so unintuitive damn Idk maybe ive hurt myself by starting with those topics by practice instead of theory, but who knows?

antibasilisk 4y ago
I feel very much the same. When I want to parse a thing I know that all I need to do is turn it into a bunch of tokens and then gradually loop over all the tokens until I've reduced them into something that can't be reduced further, and that lets me do infix and all of that good stuff. I don't quite understand how to bridge the gap between that understanding and all the theory.
- flashgordon 4y ago
  Your TL;DR is true. But where the beauty of this theory shows up is as you start seeing different levels of complexity, ambiguity, practical considerations show up in grammars and their parsing!
  - tomcam 4y ago
    Also error handling
- thechao 4y ago
  When we taught parsing (formal language theory) we generally did so using a "Chomskian" hierarchy. In a trivial sense it would be something like: regex (finite automata; pushdown) -> context free (CYK; LL(1); LL(k)) -> Turing reduction crap. I think it did a huge disservice to our students. It completely elided probably the three most important strategies for parsing "in practice", in order: recursive descent (RD), Pratt, and Earley. The time it spent on algorithmic reduction was insufficient to teach students the practice of translating algorithms to simpler, but more efficient, forms (parametric algorithm design). I think it's because there's not a lot of formal "meat" on RD, Pratt, and Earley — the first two are engineering solutions, and the latter is too difficult for lower-division to do the proofs. Anyways, learn Pratt and RD. That's all you need, in practice.
flashgordon 4y ago
+1 But I found that it is also the most fun to understand. Even better - when you actually implement them from ground up (I did this in typescript literally by going through about 30-40 papers - it is public but am a bit scared to publicize them) the satisfaction is immense. You almost forget you have to go back to a dreadful day job the next day for a tiny second! And that second my friend can feel like an entire universe!
- autumn-antlers 4y ago
  Hi! I'd be really interested in checking out what you put together c: The personal site in my bio hasn't had an email address on it because I thought I'd have one running on my own domain by now, but I'll go stick a gmail address on there like right now in case you're willing share
  - flashgordon 4y ago
    Definitely. This is a lr parser playground i put together. Again very simple (I am not a ui person so pardon the cringe ui). Happy to share repo too (has lots of tests but need to put together documentation etc). I am even using this lr parser generator for a couple of my hobby apps for a couple of years. http://galorium.appspot.com/demos/playground/ http://galorium.appspot.com/demos/playground/
avgcorrection 4y ago
> I dont understand why would you want to approach those problems in such a way, or at least describe it in such a way that feels so out of touch with programming I don’t know. But the “langsec” (language security) branch of software security argues that a lot of security issues stem from insecure approaches to parsing. I don’t know how much the theory of parsing helps with that. But it can help you make sure that your grammar has certain properties.
- hardware2win 4y ago
  I dont think grammar theory is related to that. Bigger factor seems to be strong standard library with safe string primitives Aka NOT C.
  - peterfirefly 4y ago
    A lot of it has to do with having more than one parser for the same thing -- it's bad if they don't agree on the meaning of the input. That has everything to do with grammar theory (and with how clumsy parser generators are and with how brittle many hand-written parsers are and how often they don't quite implement the spec).
norswap 4y ago
Shameless plug: https://www.youtube.com/playlist?list=PLOech0kWpH8-njQpmSNGSiQBPUvl8v3IM https://www.youtube.com/playlist?list=PLOech0kWpH8-njQpmSNGS... The first half of the course is on parsing. I'm hoping I'm giving a lot of examples and there is some coding (using PEG, which is closer to "programmer intuition").
quikoa 4y ago
Perhaps you'd like to give recursive descent parsing a try, this is something I find quite usable: https://craftinginterpreters.com/parsing-expressions.html#recursive-descent-parsing https://craftinginterpreters.com/parsing-expressions.html#re...

antibasilisk 4y ago

I feel very much the same. When I want to parse a thing I know that all I need to do is turn it into a bunch of tokens and then gradually loop over all the tokens until I've reduced them into something that can't be reduced further, and that lets me do infix and all of that good stuff. I don't quite understand how to bridge the gap between that understanding and all the theory.

flashgordon 4y ago
Your TL;DR is true. But where the beauty of this theory shows up is as you start seeing different levels of complexity, ambiguity, practical considerations show up in grammars and their parsing!
- tomcam 4y ago
  Also error handling
thechao 4y ago
When we taught parsing (formal language theory) we generally did so using a "Chomskian" hierarchy. In a trivial sense it would be something like: regex (finite automata; pushdown) -> context free (CYK; LL(1); LL(k)) -> Turing reduction crap. I think it did a huge disservice to our students. It completely elided probably the three most important strategies for parsing "in practice", in order: recursive descent (RD), Pratt, and Earley. The time it spent on algorithmic reduction was insufficient to teach students the practice of translating algorithms to simpler, but more efficient, forms (parametric algorithm design). I think it's because there's not a lot of formal "meat" on RD, Pratt, and Earley — the first two are engineering solutions, and the latter is too difficult for lower-division to do the proofs. Anyways, learn Pratt and RD. That's all you need, in practice.

flashgordon 4y ago

+1 But I found that it is also the most fun to understand. Even better - when you actually implement them from ground up (I did this in typescript literally by going through about 30-40 papers - it is public but am a bit scared to publicize them) the satisfaction is immense. You almost forget you have to go back to a dreadful day job the next day for a tiny second! And that second my friend can feel like an entire universe!

autumn-antlers 4y ago
Hi! I'd be really interested in checking out what you put together c: The personal site in my bio hasn't had an email address on it because I thought I'd have one running on my own domain by now, but I'll go stick a gmail address on there like right now in case you're willing share
- flashgordon 4y ago
  Definitely. This is a lr parser playground i put together. Again very simple (I am not a ui person so pardon the cringe ui). Happy to share repo too (has lots of tests but need to put together documentation etc). I am even using this lr parser generator for a couple of my hobby apps for a couple of years. http://galorium.appspot.com/demos/playground/ http://galorium.appspot.com/demos/playground/

avgcorrection 4y ago

> I dont understand why would you want to approach those problems in such a way, or at least describe it in such a way that feels so out of touch with programming I don’t know. But the “langsec” (language security) branch of software security argues that a lot of security issues stem from insecure approaches to parsing. I don’t know how much the theory of parsing helps with that. But it can help you make sure that your grammar has certain properties.

hardware2win 4y ago
I dont think grammar theory is related to that. Bigger factor seems to be strong standard library with safe string primitives Aka NOT C.
- peterfirefly 4y ago
  A lot of it has to do with having more than one parser for the same thing -- it's bad if they don't agree on the meaning of the input. That has everything to do with grammar theory (and with how clumsy parser generators are and with how brittle many hand-written parsers are and how often they don't quite implement the spec).

norswap 4y ago

Shameless plug: https://www.youtube.com/playlist?list=PLOech0kWpH8-njQpmSNGSiQBPUvl8v3IM https://www.youtube.com/playlist?list=PLOech0kWpH8-njQpmSNGS... The first half of the course is on parsing. I'm hoping I'm giving a lot of examples and there is some coding (using PEG, which is closer to "programmer intuition").

quikoa 4y ago

Perhaps you'd like to give recursive descent parsing a try, this is something I find quite usable: https://craftinginterpreters.com/parsing-expressions.html#recursive-descent-parsing https://craftinginterpreters.com/parsing-expressions.html#re...