Hacker News Reader

Comment by hardware2win | Hacker News Reader

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?

View on HN

+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!

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

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/

Shameless plug: 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").

> 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.

I dont think grammar theory is related to that.

Bigger factor seems to be strong standard library with safe string primitives

Aka NOT C.

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).

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.

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.

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!

Also error handling

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

Reply on news.ycombinator.com