+- Sinisterly (https://sinister.ly)
+-- Forum: Coding (https://sinister.ly/Forum-Coding)
+--- Forum: Coding (https://sinister.ly/Forum-Coding--71)
+--- Thread: Language parsing (/Thread-Language-parsing)
Pages:
1
2
RE: Language parsing - phyrrus9 - 01-03-2017
Ok, I'm going to break this down into bits and pieces when I respond, but I believe you already know what my answer will be.
(01-03-2017, 08:33 AM)bitm0de Wrote: That code could be heavily cleaned up. You could group similar constructs that use the same grammar for expressions and create proper parsing tables to ease the process of using lexical analysis + parsing. Reduce the number of hardcoded numbers you're using, and make more appropriate macros, instead of:
Code:#define ERR() free(tmp); error = true; return 0;
Quote:So, I got bored the other dayWhile everything you said there is perfectly true, it wasn't within the scope of my project. This was simply a proof of concept that got thrown (and I mean that in the most generous sense) together in about an hour just to kill some time. Never expect code to look good the first time it's written, in fact, the only way to write good code is to do it all from scratch, then completely obliterate it and start over.
(01-03-2017, 08:33 AM)bitm0de Wrote: If you read up on why people use do{}while(0), you'll see many discussions on this. I don't know why a macro like ERR() should free stuff on the heap, and return 0 though, that's not really self-documenting, and the way it's written you restrict it from being placed in a lot of locations in code.
Macros are a fun tool. They have infinitely many purposes. One of which, is to implement a piece of code (no matter how ugly) in an elegant way that can be easily repeated. Why is it freeing that data? Because if it's allocated we need to free it, we can't just jump return and be done. Yes, a slightly better solution to this (and is used elsewhere) is by using goto, however when I wrote that piece I decided to go with that and that's what happened. It works, it doesn't matter that it looks messy in source, it works, don't question it. Also keep in mind that this was written with absolutely no planning other than a vague idea of a sample program that permutated itself in my head half a dozen times as it was being implemented.
(01-03-2017, 08:33 AM)bitm0de Wrote: I read through some of the other threads too but I didn't see any mention of LALR or LR(1) or any of the other common parsers. If anyone is really serious about programming they should look into how those work. Not only do they help you reduce boilerplate code if you implement them properly, but they're also far more scalable than the manual parsing you're doing on a 1-to-1 per syntax basis.
You're absolutely correct! We don't mention any other parsers, because the tutorials are specifically written with recursive descent in mind, that's stated at least three distinct times. I did, however in a reply (discussion about compiler theory) offer to write up more than one set of these tutorials with other methodologies. At this point, I feel like you're trying to show off, and that's fine, I really would love for you to share some of that knowledge you have. On the other hand, You're doing it in a way that's not exactly open to criticism or debate. You make many claims, however you don't give much insight beyond the fact that other methods exist.
(01-03-2017, 08:33 AM)bitm0de Wrote: As a sidenote, 512 being a multiple or power of 2 is not the best number for CPU cache performance. There's a good PDF somewhere written by someone that explains a few things about this number, but I'm sure you can find it with a simple google search. I would've just chosen a PAGE size personally.
I'm going to be honest with you, I really don't give a flying fuck how the CPU cache wants to handle this code. It's really unimportant since the only time that's going to really make any difference at all is on RISC architecture, low memory environments, or in an actual compiler theory class. Since this is none of those (and even if it were, CPU optimization is another topic for another time), I'm not going to pay any attention to it here. The goal of these threads isn't to make the best or most optimized language, it's simply to teach members one (of the many) methods of creating a functional programming language. On that note, I would love to read a writeup (or even co author one with you) on advanced program optimization if you're up to the task.
(01-03-2017, 08:33 AM)bitm0de Wrote: If you posted this on github I'm sure others could help you clean it up a bit too..
If I posted this on github I might as well quit my job and become a carnie. It wasn't meant to be clean, elegant, or even good. It was meant to kill time, and it did just that. Sharing it on the forum was simply a way of gauging interest for a proper tutorial (which is now in progress)
(01-03-2017, 08:33 AM)bitm0de Wrote: Real parsers aren't written like this because this will never scale. It is about tokens but you don't create any hierarchy of tokens anywhere in that code; no trees, just string manipulation and conversions.You're correct, and at the same time you are not correct.
You're right that real parsers aren't written this way, but this isn't a real parser, it's a proof of concept. I'm not going to repeat myself here.
You said there are no trees or a hierarchy, but you're wrong. See, even though I don't go into (really much of) any depth, there still is a small chain that everything follows, and the trees (albeit at most binary) are all held within call frames. There really isn't much of a sense building a tree and then going back through it when you've already had the chance, that's just poor craftsmanship and something to expect from a Java programmer.
On a more serious note, you seem like a really smart guy, and I'm glad to have had your input. Going further into the future I think that you have some extreme potential for sharing knowledge here (provided what you said wasn't just the speil from your CS101 class or random google searches), and I encourage you to do so. I also would love it if you stuck around through the remainder of the RDT tutorial series. I'm really looking for an interactive take on that one, so as time goes along share some of your optimizations and changes, you may either correct a mistake I've made or help another member learn something new. In either case, I gladly welcome it.
RE: Language parsing - bitm0de - 01-04-2017
Quote:only way to write good code is to do it all from scratch, then completely obliterate it and start over
Not true, and experienced developers would know this. In the software industry, code is typically refactored numerous times after the initial design is delegated to groups of people and a first draft has been written through code review processes which are part of most company's policies. Usually people have flowcharts or pseudocode before blindly writing code too. You make it sound like the *only* way is trial and error.
Quote:Yes, a slightly better solution to this (and is used elsewhere) is by using goto, however when I wrote that piece I decided to go with that and that's what happened. It works, it doesn't matter that it looks messy in source, it works, don't question it.
This is a terrible way of thinking and if you looked up the do-while (0) example like I suggested you would have probably not written such an adolescent response to be honest. I haven't provided further insight because I expect motivated learners to look things up like they normally would do after being pointed in the right direction.
I doubt you would have a good defense to explain why a macro with a name like ERR() should exist to free a random local on the heap not passed by macro arguments, set a global variable to true, and return 0 (which is usually an indication of success [unless you're writing ANSI C where you don't have _Bool]). This code looks like a mix of poor C++ and C however, so I'm not really sure what you were going for there, when in another function you duplicate the call to free(tmp) and introduce a layer of goto's to jump around the code in addition to it. Where's the balance and how is anyone supposed to follow your "PoC" when it looks like a bunch of mashed potatoes? :S
I won't expand on my mention of LR(1) and LALR parsers, and let those willing to really learn figure out why they were mentioned here. Personally I think they are much more useful, and lots of the mainstream languages use these.
Quote:You're absolutely correct! We don't mention any other parsers, because the tutorials are specifically written with recursive descent in mind, that's stated at least three distinct times.
The point of my post was to show that you explain the theory in an abstract way but you don't implement it right and claim that the code you have is a PoC; there's nothing recursive about your code that you claim shows the recursive descent method. Having functions and variable names that reflect letters you see in the diagrams you're posting does not count... I see way too many ugly dealbreakers in this code for it to be used as learning material though -- fclose(stdin), for loops that are used like while loops, bad use of macros, and lots of other things, with little to no consistency.
As for CPU cache, you would be wise to read up on it some more before making further discussion about it. I can tell you that people writing C++ syntax parsers definitely consider caching, and it's not because they only target RISC. There's a PhD thesis that concludes this about C++ grammar: "C++ grammar is ambiguous, context-dependent and potentially requires infinite lookahead to resolve some ambiguities" (http://www.computing.surrey.ac.uk/research/dsrg/fog/FogThesis.pdf)
If you're going to write a series, it should at least be correct.