News for hackers. Stuff that matters.
Re:From string to AST: parsing by ckok on Friday November 22, 2024 @08:56AM (#42213857)
I think this makes it sound a lot more difficult than it has to be, with the formal theory.

When it's really one of the most simple things if you divide it in parts and look at it from a tokenizer (string to list of tokens) and parser on top. Where the tokenizer can usually be very simple: a loop, large switch on the current character, where a choice is made on "what can this be", and making it into a formal token or error. Then a simple recursive parser that can almost be a 1 to 1 copy of the (E)BNF.

Re:From string to AST: parsing by jrop on Friday November 22, 2024 @09:13AM (#42213970)
I love writing parsers like this. Add in Pratt Parsing for operator precedence and writing parsers can be really easy.
Re:From string to AST: parsing by detourdog on Friday November 22, 2024 @10:04AM (#42214369)
I got the impression the author was trying to add higher level reasoning to the chosen term for string to AST parsing.

I felt that they were pointing out how the cognitive load of understanding is effected by word choice.

Re:From string to AST: parsing by antononcube on Friday November 22, 2024 @10:06AM (#42214382)
It seems you are describing how functional parsers (aka parser combinators) work.

(BTW, there is a "Parser combinators" section in the featured post/article.)

Re:From string to AST: parsing by marcosdumay on Friday November 22, 2024 @01:09PM (#42216058)
The bad news about those is that it's easy to mindlessly create a parser that runs on exponential time.

The good news is that this happens in the grammar definition. So once you define your language well, you don't have to watch for it anymore.

Re:From string to AST: parsing by antononcube on Friday November 22, 2024 @02:36PM (#42216739)
Insightful!

Do you know of any "large scale" research on this? I.e. analysis of multiple related projects and/or of "real life stories."

(I agree regardless.)

Re:From string to AST: parsing by marcosdumay on Friday November 22, 2024 @05:02PM (#42217732)
I don't know about any real-world study. But there are people complaining about it from time to time, and it's quite obvious from the theory.
Re:From string to AST: parsing by ckok on Saturday November 23, 2024 @01:30AM (#42219503)
I believe the proper term for what i am describing is a recursive descent parser. With which it is also quite doable to generate proper error handling and even recovery. Some form of this is used in almost every production language I think.

It has been years since I've written a proper parser but before that every time I had to write one I tried the latest and greatest first. ANTLR, coco/r, combinators. All the generated ones seemed to have a fatal flaw that hand writing didnt have. For example good error handling seemed almost impossible, very slow due to Infinite look ahead or they were almost impossible to debug to find an error in the input schema.

In the end hand crafting seems to be faster and simpler. Ymmv.

My point about the article was mostly that all the formal theory is nice but all it does is scare away people, while parsing is probably the simplest thing about writing a compiler.

Re:From string to AST: parsing by DemocracyFTW2 on Friday November 22, 2024 @10:48AM (#42214756)
IMHO it gets even better when you can use regular expressions and write a 'modal' parser where each mode is responsible for a certain sub-grammar, like string literals. JavaScript added the sticky flag (y) to make this even simpler.
Re:From string to AST: parsing by rurban on Sunday November 24, 2024 @09:47AM (#42228178)
It gets much worse. It's a huge anti-pattern to use regex within parsers.
Re:From string to AST: parsing by DemocracyFTW2 on Monday November 25, 2024 @02:41AM (#42234068)
why so?
Re:From string to AST: parsing by rurban on Monday November 25, 2024 @03:36AM (#42234360)
There are many explanations. The most famous one Rob Pike in his lexer talk 2011 https://youtu.be/HxaD_trXwRE?si=Q1B4mZ4Vo1Z2gRZq at 10.48

Or http://www.golangdevops.com/2019/03/07/halfpike-a-framework-...

Or several articles why you should not parse with regex, like https://stackoverflow.com/questions/1732348/regex-match-open...

Re:From string to AST: parsing by DemocracyFTW2 on Monday November 25, 2024 @04:13AM (#42234548)
I couldn't locate the part where Pike addresses regexes in his 50-minute talk.

The second piece seems to be about someone complaining about a dysfunctional and untidy software situation where incompetence led to the incorrect application of greedy regexes, producing wrong results.

The third one is the most famous rant against attempts to parse a language with symmetric bracing (start tags that must match end tags) with a single regex from a language that doesn't provide regexes with symmetric bracing support, that is of course doomed to fail.

None of these provide any argument against lexing with sticky regexes. For one thing, the rant against regexes being unable to match bracing elements is only valid for regex engines that don't provide extensions for brace matching, but many languages and extensions do (e.g. https://stackoverflow.com/a/15303160/7568091).

However this point is typically irrelevant because this is not about parsing, it's about lexing, but I realize this my fault because in the above I wrote write a 'modal' parser where I should've written write a 'modal' lexer.

In lexing you typically do not match braces, you just realize you've found a brace and emit an appropriate token. It's up to the downstream processing to see whether barce tokens are matching.

Re:From string to AST: parsing by joz1-k on Friday November 22, 2024 @04:15PM (#42217425)
I had exactly the same feeling as you after reading the article. And interestingly, all production parsers for all major languages are hand-written recursive descent parsers. On the other hand, if you inspect the actual code for these production parsers (even for newer languages like Swift, Scala, Kotlin, or Rust), the complexity and amount of code is still quite staggering.
Re:From string to AST: parsing by taeric on Friday November 22, 2024 @05:09PM (#42217771)
Isn't a large portion of the code to get friendlier messages for the user?
Re:From string to AST: parsing by joz1-k on Saturday November 23, 2024 @02:41AM (#42219697)
Yes, that explains a lot of the complexity. Another reason is type checking/inferring and making the AST detailed enough for code analysis tools, such as code hinting in IDEs.