Lazarus

Free Pascal => General => Topic started by: avra on September 14, 2018, 11:08:46 pm

Title: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 14, 2018, 11:08:46 pm
I wanted to make a starting point for anyone interested in doing it with FreePascal and Lazarus:

http://wiki.freepascal.org/Make_your_own_compiler,_interpreter,_parser,_or_expression_analyzer

Lex/Yacc and Gold are covered. Help is needed for AntLR, Coco-R or any other tool not on the list.

Feel free to update, expand and correct.

Have fun!    :D 8-) :D
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on September 14, 2018, 11:25:36 pm
Interesting. Maybe I can include information about SynFacilSyn wich is a highlighter and lexer, I have used in my compilers.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 15, 2018, 12:05:05 am
Interesting. Maybe I can include information about SynFacilSyn wich is a highlighter and lexer, I have used in my compilers.
Please do. I would appreciate if you follow the current layout: you add short info about SynFacilSyn on the main page, then if needed you add a separate page with all the SynFacilSyn details. Please let me know if you have a better proposal then this.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 15, 2018, 05:24:11 pm
Thank you marcov for adding fcl-passrc, fcl-xml, symbolic, and TFPExpressionParser to the wiki stub. I believe that those are specialized, not general tools. For example first is specialized for pascal sources, and second for XML files. Therefore maybe we should make 2 categories: General Tools, and Specialized Tools. If anyone has a better idea, please say so.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on September 15, 2018, 06:22:11 pm
Updated with SynFacilSyn information.  :)
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 15, 2018, 09:41:19 pm
Updated with SynFacilSyn information.
Thank you!
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 19, 2018, 04:50:13 pm
Just couldn't resist adding to wiki  :-[
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: marcov on September 19, 2018, 05:46:16 pm
Thank you marcov for adding fcl-passrc, fcl-xml, symbolic, and TFPExpressionParser to the wiki stub. I believe that those are specialized, not general tools. For example first is specialized for pascal sources, and second for XML files. Therefore maybe we should make 2 categories: General Tools, and Specialized Tools. If anyone has a better idea, please say so.

Parsing is only part of making a compiler. And LALR parsers only a part of that. Most commercial compilers have recursive descent parsers afaik.
And as said fcl-passrc is being used for a pascal-to-js compiler.

Maybe the title is simply wrong for what you had in mind.  Make a topic "parser generators" or so, move the parser generators there, and then link that on the "compiler creation" page?
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Leledumbo on September 19, 2018, 07:03:46 pm
You make me wanna finish my handcoded compiler tutorial, as what's currently covered in the wiki are all generated by tools instead of coded from scratch by hand (except the fpc packages, of course, those are nice handwritten ones).
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 20, 2018, 10:38:49 am
Parsing is only part of making a compiler. And LALR parsers only a part of that.
I am aware of that, but such parsers can be used for much more then just compilers....

Most commercial compilers have recursive descent parsers afaik.
Speed is probably the most important reason. Maybe wiki should mention that somewhere...

Maybe the title is simply wrong for what you had in mind.  Make a topic "parser generators" or so, move the parser generators there, and then link that on the "compiler creation" page?
I felt like such segregation would make too much distraction for already loose coupled wiki topics. That's why I wanted to make a single starting place, and that's why I called it a wiki stub. The idea was that when in the future anyone wants to know more about anything from the title we point him to this wiki as a first step. Anyway, I don't mind anyone changing a title or making any deeper reorganization. All improvements are welcome. Please give it any shape you think is better then current one. I started the wiki in the first place because I wanted to preserve and share some of my experience with GOLD Parser Builder. The rest was simply an extension to that.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 20, 2018, 10:56:07 am
You make me wanna finish my handcoded compiler tutorial
If you do then please add it to the wiki. I will be looking forward to take a look at it. I started with hand coding everything. Then lex/yacc. Then some GUI parser generators. I ended up with GOLD, which spoilt me with it's code and grammar separation, visual and step by step grammar testing and ambiquities finder capabilities, and running it's nice FreePascal engines with parsed tree output. It's not a runtime speed champ and has it's quirks, but it automates most of my work and for what I need is more then enough.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: marcov on September 20, 2018, 11:04:52 am
Speed is probably the most important reason.

Speed, but also backwards compatibility requirements with older versions can often more easily be handled in code then adapting the grammar which often leads to multiplication of rules for the related part.

Also error generation is said to be finer and more to the point (less syntax error, more naming the exact issue).

It is not that commercial compilers don't use grammars and generators. Just the flagship ones often do not.

I know a guy that did/does compiler work for a living (mostly delivering C compilers for new DSP parts with some extensions for the C), and they worked very topdown and grammar based, and proof generation etc.

But the whole feature set was signed off on before final implementation started, and rarely iterated.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 20, 2018, 12:04:04 pm
backwards compatibility requirements with older versions can often more easily be handled in code then adapting the grammar which often leads to multiplication of rules for the related part.
The more such shortcuts exist, the harder it is to publish complete BNF/EBNF grammar at the end. Many times you do have to put some things in code, but unfortunatelly sometimes that code is hard to translate back to formal grammar.

Btw, I have just updated the wiki with 'Let's build a compiler' PDF from your site.  ;)
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: marcov on September 20, 2018, 12:26:50 pm
Btw, I have just updated the wiki with 'Let's build a compiler' PDF from your site.  ;)

I didn't do it myself, because my site goes dark october 1st :-)
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 20, 2018, 03:58:46 pm
Btw, I have just updated the wiki with 'Let's build a compiler' PDF from your site.  ;)

I didn't do it myself, because my site goes dark october 1st :-)
I have just tried to make PDF attachment to wiki, but it is not allowed. Do you plan to preserve it on github/bitbucket alike repo, so I can link it from the wiki? I remember there were other nice PDFs on your site. It would be a shame to loose them.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Thaddy on September 20, 2018, 04:27:00 pm
I am on holiday but i can add some things next week.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 21, 2018, 12:20:39 am
I am on holiday but i can add some things next week.
Please do!   :)
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on September 21, 2018, 01:17:49 am
I think the best title for that WIki entry could be "Libraries for compiler, interpreter, parser, or expression analyzer". 
Then you can add information about TFPExpressionParser, and some links about "Make your own compiler".
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: valdir.marcos on September 21, 2018, 03:30:30 am
If the Wiki entry is about "Make your own compiler", shouldn't there be some information about the importance of also knowing Assembly Language?
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 21, 2018, 08:47:34 am
Btw, I have just updated the wiki with 'Let's build a compiler' PDF from your site.  ;)

I didn't do it myself, because my site goes dark october 1st :-)
Preserved on webarchive, and wiki link changed accordingly:
http://web.archive.org/web/20180107011717/http://www.stack.nl:80/~marcov/compiler.pdf

I think the best title for that WIki entry could be "Libraries for compiler, interpreter, parser, or expression analyzer". 
Then you can add information about TFPExpressionParser, and some links about "Make your own compiler".
GOLD, COCO-R and AntLR have their own IDE where for example you can write, test, single step and debug your grammar, find ambiquities, and generate skeleton application code in many programming languages. These are definetly not libraries, so title would not be appropriate. "Tools and libraries for compiler, interpreter, parser, or expression analyzer" came to my mind after that, but it would not justify links in whe wiki which have full tutorials how to make your own compiler. Therefore I am more for original title, which reflect more what is inside the wiki. However this is not carved in stone, and I wouldn't mind if someone changes it. I care more about the content and contributions that would expand it. There are many situations when for a simple forum question you get many wiki links in an answer, and that repeats over and over. I would like to have a single wiki stub for the whole topic, even if it means that current layout should be changed in the future and separate wiki subtopic pages should be made. That way, for question like how to build a compiler, how to build an interpreter, how to build a front end, how to build a back end, what is an AST, what is a BNF grammar, how to parse this and that, how to make an expression analyzer and similar - we just give this single link and user will expand his knowledge from there. I didn't feel like adding links to wikipedia articles about all the terms since that would probably be too much, but other web links (especially when related to FreePascal) should end there.

If the Wiki entry is about "Make your own compiler", shouldn't there be some information about the importance of also knowing Assembly Language?
At least one of the links shows how to write a compiler with assembler generator back end. But that is indirect info. Please add direct info about assembler importance if you feel like it.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: valdir.marcos on September 23, 2018, 12:18:30 am
If the Wiki entry is about "Make your own compiler", shouldn't there be some information about the importance of also knowing Assembly Language?
At least one of the links shows how to write a compiler with assembler generator back end. But that is indirect info. Please add direct info about assembler importance if you feel like it.
I was thinking about something deeper, but I'd better leave it alone.
I only did a minor edit about Coco/R.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: avra on September 23, 2018, 10:35:48 am
I only did a minor edit about Coco/R.
Thank you!
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on January 07, 2019, 07:43:35 pm
Hi. I'm starting to write some articles about creating compilers, using a simple example compiler for the x86 32 bits architecture.  :D

The challenge for the compiler example, will be to create it without any external library, just hand code routines, of FPC no objects, no class, no records, just using integers and strings.  :o

Only in spanish by now: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/ :-[
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Handoko on January 16, 2019, 04:27:35 pm
Only in spanish by now ...

Did you mean it will be available in English in the future?
I guess the answer is YES.
So I bookmarked the link and wait patiently. :)
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: valdir.marcos on January 16, 2019, 10:23:47 pm
Hi. I'm starting to write some articles about creating compilers, using a simple example compiler for the x86 32 bits architecture.  :D

The challenge for the compiler example, will be to create it without any external library, just hand code routines, of FPC no objects, no class, no records, just using integers and strings.  :o

Only in spanish by now: http://blog.pucp.edu.pe/blog/tito/2019/01/05/crea-tu-propio-compilador-casero-parte-1/ :-[
Excellent article!
I loved your "Yo no soy un dictador informático." :D

After this series on compilers, could you extend it to another series about assemblers and linkers?
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Trenatos on January 16, 2019, 10:48:05 pm
I just read the article using Google Translate (Not a bad job for auto-translation) and I'm bookmarking and will keep checking back  :)

I've been playing with Plex and Pyacc, but one of the big things missing for me (In general in these topics) is how to actually implement a simple compiler (Not an interpreter).
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: lucamar on January 16, 2019, 11:03:09 pm
I've been playing with Plex and Pyacc, but one of the big things missing for me (In general in these topics) is how to actually implement a simple compiler (Not an interpreter).

Jack Crenshaw's Let's build a compiler (https://compilers.iecc.com/crenshaw/) may interest you then. Although it's (unfortunately) unfinished.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Trenatos on January 16, 2019, 11:04:15 pm
I started reading it after a few chapters, seemed pretty solid though.

I'll pick it back up when I get some free time again
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on January 17, 2019, 05:58:54 am
Only in spanish by now ...

Did you mean it will be available in English in the future?
I guess the answer is YES.
So I bookmarked the link and wait patiently. :)

I hope to have time to translate but if someone can help it will be good. Fortunately the language created (I called it "Titan") is in english so it won't be a problem.

Excellent article!
I loved your "Yo no soy un dictador informático." :D
After this series on compilers, could you extend it to another series about assemblers and linkers?

Thanks. I've created assemblers but no real linkers. I will consider to write about it after finished some projects.

I just read the article using Google Translate (Not a bad job for auto-translation) and I'm bookmarking and will keep checking back  :)

I've been playing with Plex and Pyacc, but one of the big things missing for me (In general in these topics) is how to actually implement a simple compiler (Not an interpreter).
The compiler used as example in this articles, is very simple, without some library, because the idea is to make this a Self-hosting compiler. That's why I'm using just a simple Pascal syntax to create the compiler.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: valdir.marcos on January 21, 2019, 10:22:08 pm
Excellent article!
I loved your "Yo no soy un dictador informático." :D
After this series on compilers, could you extend it to another series about assemblers and linkers?
Thanks. I've created assemblers but no real linkers. I will consider to write about it after finished some projects.
Thanks.

In your opinion:
What are the best books about compilers or interpreters or assemblers or linkers?
Is there any new (last five or ten years) good books about compilers or interpreters or assemblers or linkers?
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Edson on January 22, 2019, 05:15:02 am
In your opinion:
What are the best books about compilers or interpreters or assemblers or linkers?
Is there any new (last five or ten years) good books about compilers or interpreters or assemblers or linkers?

Sorry. I don't read books about compilers a long time ago. I just remember some from Wirth, but nothing special. I read differents pages, documents, articles, and papers from the Web.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: 440bx on January 22, 2019, 05:43:34 am
In your opinion:
What are the best books about compilers or interpreters or assemblers or linkers?
Is there any new (last five or ten years) good books about compilers or interpreters or assemblers or linkers?
My favorite book about compilers is Per Brinch Hansen's "On pascal compilers".  IMO, it's probably the best book ever written on compilers.  It's the one book that truly aims to make the reader understand the techniques used to define and convert a language (usually high level) into a series of instructions.

There is little to nothing in it about assemblers and linkers but, if you want to truly understand how a language is defined (I should say, _one_ way of defining a language/grammar) and the foundation of going from grammar to low level instructions, I don't believe there is a better book.

Unfortunately, at least at this time, the prices people are asking for it are rather steep but, if sometime you can get it for a reasonable amount, I believe you'll be very pleased.

I should also note that it is an introductory text but it opens the door to easily _understand_ (instead of just learning) other techniques presented in more advanced books.

HTH.

Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: Trenatos on January 23, 2019, 02:48:31 pm
I've started playing with Plex/Pyacc again, I'll start adding pages as I go.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: JdeHaan on March 09, 2019, 07:38:55 am
For those interested, I published my hobby interpreter project on GitHub:

https://github.com/jdehaan2014/GearLanguage

It is a procedural object-oriented functional language, supporting anonymous functions. I wrote everything I coded from start to finish with explanations and sample Gear code in the accompanying document (pdf).

All comments are welcome.
Cheers!
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: MarkMLl on April 17, 2019, 01:18:26 pm
I've just tacked some stuff onto the end which includes a couple of useful links on the history of recursive descent etc. which I hope somebody finds interesting.

I admit that I take some of this rather personally, since at about the same time as I joined Burroughs a document appeared where the author (Richard Waychoff) claimed that he had invented recursive descent and virtual memory. I was very dismissive of this, feeling that it was a company man writing for company men, but 40 years on and with the benefit of various oral histories etc. I think he has a very good claim to precedence on both fronts.

MarkMLl
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: dtoffe on July 10, 2019, 01:58:44 am
For those interested, I published my hobby interpreter project on GitHub:

https://github.com/jdehaan2014/GearLanguage

Hi, looks interesting, a couple questions: What languages influenced your decisions ? Do you plan to add code generation ? Do you have a grammar document ?

Thanks,

Daniel
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: SymbolicFrank on July 14, 2019, 10:37:51 am
I'm also going to make my own Pascal compiler, but it's going to take a completely different approach, as it all has to run on a microcontroller.

Basically, my compile unit is a single statement and my source code unit is a single statement that is terminated by a semicolon. My first goal is to store the source in P-code format, to make it small. Then again, the most compact way to store the source code is probably as a compiled binary, with a limited amount of debug symbols.

So, my parsing will be done while editing the source code, one line at a time. The code generation will initially be JIT, when loading the code into memory. And later, if possible, the editor will use a disassembler to display and edit the source code.

If I finish the project, I'll update the wiki on how to do it.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: lucamar on July 14, 2019, 10:49:22 am
My first goal is to store the source in P-code format, to make it small. Then again, the most compact way to store the source code is probably as a compiled binary, with a limited amount of debug symbols.

You do know that P-Code is the compiled code, don't you? It's compiled for a virtual machine but it's compiled code. Like Java and the JVM.
Title: Re: Wiki stub: Make your own compiler, interpreter, parser, or expression analyzer
Post by: SymbolicFrank on July 14, 2019, 11:06:21 am
My first goal is to store the source in P-code format, to make it small. Then again, the most compact way to store the source code is probably as a compiled binary, with a limited amount of debug symbols.

You do know that P-Code is the compiled code, don't you? It's compiled for a virtual machine but it's compiled code. Like Java and the JVM.

Source code goes through multiple steps. First you tokenize it, then you parse it into a functional description. That parse tree is then analyzed (and optionally optimized), then code is generated and as the last step all the bits are linked together into an executable file.

The Sinclair computers immediately did the tokenizing. The QL also did some limited parsing and called the resulting format P-code.

Many systems compile to P-code and run that through an interpreter. Which is basically what a JVM does as well.

In short, it depends.