5 ms·
Parsing computer languages is an entirely self-inflicted problem. You can easily design a language so it doesn't require any parsing techniques that were not kn
by kazinator 3y ago
Parsing computer languages is an entirely self-inflicted problem. You can easily design a language so it doesn't require any parsing techniques that were not known and practical in 1965, and it will greatly benefit the readability also.
- amelius 3y agoEnd-comment
- lgas 3y ago)
- loevborg 3y agoDo you mean lisp? If yes I agree
- Legend2440 3y agoBut I don't want to be able to parse only highly restricted languages. I want to be able to parse anything, including natural language or even non-languages like raw audio. My brain can do it, why can't my computer?
- reissbaker 3y agoYour computer can do it, if it has a beefy enough Nvidia card. That's what LLMs are for! Grammar-based parsing for natural language isn't anywhere close to working, sadly, and may never be.
- deathanatos 3y agoYou've never had an LLM misinterpret what you correctly wrote? (… I have.)
- deleted 3y ago[deleted]
- throwbadubadu 3y agoYes, never do humans misunderstand each other, or instructions are not clear to everyone and totally unambiguous, and luckily no language has pure differentiation of meaning by intonation, and, and.. and...
- thfuran 3y agoYeah, natural languages don't have a specification or canonical parser implementation, so they cannot be reliably parsed.
- Legend2440 3y agoThey don't have a short parser. They can be parsed, it just requires a huge amount of priors and world knowledge. Rule-based parsers are too simple.
- thfuran 3y agoNo, they cannot be reliably parsed. There is no unambiguously correct parsing for many (or, arguably, any) strings. Two people could say the same thing in the same context and mean different things by it. You can't even definitively say whether what they said/wrote is valid English. Sure, there are strings most would agree are and strings most would agree aren't, but even taking consensus opinion as the source of truth, most isn't all, and there's no universally agreed upon threshold for acceptance.
- dkjaudyeqooe 3y agoThis is entirely the case. Given a sensible grammar stated in a sensible way, it's very easy to write a nice recursive decent parser. They are fast and easy to maintain. It doesn't limit the expressiveness of your grammar unduly. Both GCC and LLVM implement recursive decent parsers for their C compilers. Parser generators are an abomination inflicted upon us by academia, solving a non problem, and poorly.
- derriz 3y agoAgree completely. Having used a bunch of parser generators (Antlr and bison most extensively) and written a parser combinator library, I came to the conclusion that they're a complete waste of time for practical applications. A hand-written recursive descent parser (with an embedded Pratt parser to handle expressions/operators) solves all the problems that parser generators struggle with. The big/tricky "issue" mentioned in the article - composing or embedding one parser in another - is a complete non-issue with recursive-descent - it's just a function call. Other basic features of parsing: informative/useful error messages, recovery (i.e. don't just blow up with the first error), seamless integration with the rest of the host language, remain issues with all parser generators but are simply not issues with recursive descent. And that's before you consider non-functional advantages of recursive-descent: debuggability, no change/additions to the build system, fewer/zero dependencies, no requirement to learn a complex DSL, etc.
- dkjaudyeqooe 3y ago> handle expressions/operators Precedence climbing is a natural and efficient way to parse expressions in a recursive decent parser. It's used by Clang in LLVM. https://eli.thegreenplace.net/2012/08/02/parsing-expressions-by-precedence-climbing https://eli.thegreenplace.net/2012/08/02/parsing-expressions...
- Guthur 3y agoMake them all s-expr with prefix notation solves even that generally, correct?
- 3y ago
- wittystick 3y ago[dead]
- LgWoodenBadger 3y agoJust like email addresses. The specification/rfc/whatever could have defined a reg-ex that determines a valid address, instead of the essential impossibility we have today.
- paulddraper 3y ago> and it will greatly benefit the readability also This is the controversial part, Lisp aficionados to the contrary.
- kazinator 3y agoPeople are misunderstanding my original comment. You can parse quite a lot more than Lisp with techniques from 1965.
- paulddraper 3y agoPeople would misunderstand you less if you made yourself better understood. Like using a hyperlink to code example.
- trealira 3y agoYou can search for parsing techniques that were available and practical in 1965: recursive descent, the shunting yard algorithm, and operator precedence parsing[0]. LR(k) parsing was described by Knuth in 1965, but I don't think it was considered practical yet due to the memory required by LR(1) tables. [0]: 1963 operator precedence description: https://dl.acm.org/doi/10.1145/321172.321179 https://dl.acm.org/doi/10.1145/321172.321179