Q: About ALAN's Parser & Lexer Generators

[tajmone]

@thoni56, In #12 you mentioned

The character sets used are actually generated by the scanner generator ("lexem parser generator") that is part of the legacy compiler-compiler toolset that is used to generate the scanner (and parser) for the Alan compiler.

I've been trying to find info about this compiler-compiler tool, but couldn't find anything by searching "lexem parser generator". I noticed that in the generated files pmParse.c and smScan.c it mentions the tools "ParserMaker" and "ScannerMaker", but couldn't find anything for those either on Google.

Not much luck with Wikipedia's page Comparison of parser generators either.

Could you provide me with more info about this toolset and its author, and a link to its website (if still in existence) or some place where its original codebase can still be found?

I would have liked to add to our Wiki (here) a page with some info about it, since its part of the required tools to build ALAN, and because these tools are now old and not easy to find info about.

Is this compiler-compiler tool (which I believe you've had to modify in order to adapt it to the latest changes) included in this repository? i.e. how would someone wanting to update the ALAN grammar and parser/lexer have to go about it? (I'm guessing he/she would need access to the same parser/lexer generator tools).

Thanks.

[thoni56]

Yes, and I think I have mentioned before that those are legacy tools from a suite that I and my colleagues at my previous company, SoftLab (not the German one), built in the 90's. It was of course proprietary at the time. It introduced modern parsing and compiling techniques for the Ericsson telephone exchange language Plex and shrank compile-times to a tenth of what it was previously. It has been said that the reduction of CPU-time alone, over a year, paid for the project cost. It was also used at a handful of our other clients.

But as that company after some intricate turn of events ended up as a part of Ericsson, and the tool probably hasn't been used during the last decades (but who knows how long the maintain these things...) I made it public after a few decades at https://github.com/thoni56/ToolMaker. With the disclaimer that if anyone objects to it being available, I'll take it down.

Actually, as usually, if you know what to Google for you can find a few matches.

Documentation? There is none. I always kept a personal copy of the source, and as it was vital to building Alan. Also building Alan on multiple platforms, sometimes made me also take ToolMake with me to that platform, although not strictly necessary. Unfortunately, the documentation was lost, or I never had a copy, and I have not been able to track down someone who had a copy, not even at Ericsson, where some of my old colleagues still work (unless they are retired nowadays...).

Is this compiler-compiler tool (which I believe you've had to modify in order to adapt it to the latest changes) included in this repository? i.e. how would someone wanting to update the ALAN grammar and parser/lexer have to go about it? (I'm guessing he/she would need access to the same parser/lexer generator tools).

You never need to modify the tools. It is only if the language grammar changes, or there are changes to the internal form that must be handled when the AST is built that the tool is needed. But, yes, if that happens, you need a working ToolMaker kit installed. But the use of it is all handled by the Makefiles, and I doubt that there will ever be such radical changes that you can't wing it by mimicing what's already there.

One concern that I have (not much, but a little) is that the grammar might at some point change so that the parser generator of ToolMaker, aptly named ParserMaker, cannot handle it. ParserMaker only handles LALR-grammars, although there are some means to tweak the parsing rules so a larger set of grammars can be handled (which is already done at a few places).

And of course I've been toying with converting to other parser generators multiple times over the years. That's why you see fragments of CoCo and ANTLR grammars in the compiler directory. Feeble attempts have so far resulted in nothing, as the work would be quite large and the value at this time very low. A lot would have to change as most of the compiler toolkits handle a lot of things differently. What's cool about ToolMaker is that many things already exist and integrate easily with each other, such as source positions, error messages, listing files, interface to scanner/lexer/tokenizer etc. etc. ParserMaker also has the worlds first back-tracking error-recovery logic, it was actually the doctoral work by one of my then colleagues, also former professor, Kenth Ericson (no relation to the company ;-).

With all that background it might not come as a surprise that my recommendation is to no go down that rabbit hole ;-)

But it is good that you asked the question (I will move this to a discussion, rather than an issue). In that way this answer is saved for posterity until someone does that wiki-page write-up.

[tajmone]

ALAN Compiler Wiki Page Added

I've added a new Alan Compiler page in the Wiki, which currently tries to gather in one place all info about the compiler, from basic stuff like differences between the CLI and GUI version, to links to ALAN Manual sections on how to use it, up to where to find its source code and info about ToolMaker being the parser generator.

If the page will every grow in size, we might consider splitting it into different pages, but since there isn't yet much in terms of contents I think it should be fine to keep al info packed under one page, for the time being.

And of course I've been toying with converting to other parser generators multiple times over the years. That's why you see fragments of CoCo and ANTLR grammars in the compiler directory. Feeble attempts have so far resulted in nothing,

I always wondered why there were so many different ALAN grammars. Initially I though that each grammar was being used with a different parser generator on different platforms, but now I seem to understand that many of these grammars are just left over from experiment. Is that so?

Which would then be the correct grammar file, i.e. the one actually used to build the parser?

Now that I'm starting to focus a bit more, my guess would be that:

• alan.pmk — source grammar for Parser generator.
• alan.prod — EBNF grammar auto-generated by Parser generator? (i.e. as reference doc)
• alan.lmk — source grammar for Lexer generator.
• alan.tmk — something to do with Tokens generator?
• alan.smk — ???
• alan.atg — ANTLR experiment grammar leftover???
• alan.g — other experiment grammar leftover???
• alan.coco — Cocoa/MacOSX experiment grammar leftover???

[thoni56]

I've added a new Alan Compiler page in the Wiki, which currently tries to gather in one place all info about the compiler, from basic stuff like differences between the CLI and GUI version, to links to ALAN Manual sections on how to use it, up to where to find its source code and info about ToolMaker being the parser generator.

Thanks.

Which would then be the correct grammar file, i.e. the one actually used to build the parser?

Now that I'm starting to focus a bit more, my guess would be that:

Good guesses:

• alan.pmk — source grammar for Parser generator.

Yes, this is the grammar file that is feed to ParserMaker to generate the parser for the Alan language.

• alan.prod — EBNF grammar auto-generated by Parser generator? (i.e. as reference doc)

Yes. It is auto-generated when the grammar file changes using some simple sed magic in compiler/Makefile.tm, which does the heavy lifting when generating the whole scanner/parser/lister shebang.

To be really nit-picking here, that is not EBNF, but plain BNF since ParserMaker converts EBNF rules to BNF before generating the parser, but also before printing the grammar. So you will find grammar non-terminals here that are not in the actual EBNF source in alan.pmk, but are the result of expanding the EBNF extensions to BNF.

• alan.lmk — source grammar for Lexer generator.

No, this is actually the configuration file for ListerMaker, the "lister module" generator of ToolMaker. The lister handles creating listings on screen and in files, marking errors using source positions etc. etc. The configuration file contains apart from a few other options, all compiler message templates.

• alan.tmk — something to do with Tokens generator?

This is the "top level" config file for the ToolMaker suite. In it you can define common options such as target language, but also define how ToolMaker should interface with the source position definition of your sources.

• alan.smk — ???

This is the configuration file for ScannerMaker, the scanner/lexer generator. So here you find the low level token constructs as well as handling of include (import) files, comments etc.

• alan.atg — ANTLR experiment grammar leftover???
• alan.g — other experiment grammar leftover???

Both files are automagically created from alan.prod when alan.pmk (the grammar file) has changed.
alan.g is actually the ANTLR file and alan.atg is the CoCo/R version.
Both these are in sync with the current Alan grammar.

The CoCo/R file is just not an experiment because it is also drives the incremental parser in AlanIDE, since that has to be in Java, which ToolMaker does not support.

• alan.coco — Cocoa/MacOSX experiment grammar leftover???

I think this is the version of the alan.prod at the point where the current AlanIDE CoCo/R grammar was taken. Since the grammars are attributed grammars (or has semantic actions) just converting the grammar is just the start. Depending on your need the grammar has to be ameded with the correct statements to, e.g., build an AST, print some output. These can not be converted between parsers, and would be wrong anyway.

You can find the running CoCo/R parser in AlanIDE here.

[thoni56]

What I failed to mention was that all the ToolMaker tool are, as many other such tools, built around a configuration/definition file that is read by the tool which then uses some kind of template or macro language to generate the actual compilable source. (That source is, in the Alan/ToolMaker case in the compiler subdirectory with names like lmList.[ch], pmPaSema.c etc.)

The "skeletons" are located in the lib directory of the ToolMaker sources. They are written using a ToolMaker unique macro language processed by imp. The language is as powerful as M4.

imp is linked into the binaries of all the tools, so you don't need to understand it or run ot, but you can run it stand-alone. You can also generate just the "tables" (= macro definitions) using options to most, if not all, of the ToolMaker tools, if you are interested or need to tweak them.

That was actually what I had to, or the Makefiles, for years when Alan supported the charsets we have talked about elsewhere. The ScannerMaker was run three times to generate three different scanning tables, one for each of the supported charsets, and then the "skeleton" was also tweaked to switch between them. Good riddens!