HP-42S Compiler for Niklaus Wirth's PL/0 Language

[robve]

(02-18-2024 11:42 AM)floppy Wrote:  prolog.
a prolog interpreter for lisp https://www.metalevel.at/lisprolog/

Thanks for sharing. I like these kind of projects very much, that are a little different than the usual PL projects.

Here's a lazy functional language interpreter written in Prolog: Husky (disclaimer: which I wrote in the 90s).

On the topic of Lisp: a lua-to-lisp transpiler with the transpiler written in lex and yacc (actually, RE/flex and Bison, but that's just about the same). RE/flex does a lot more than lex (and flex) though, to make lexical analysis easier to specify and implement in C++.

Pick what you like:

• lex/yacc (and proper variants) produce critical warnings and details to help correct lexical and grammatical issues, yacc and bison cover a wide range of LR grammars
• recursive descent (for LL grammars) is generally only used for parsing small languages (class project PL are typically small, also PL/0 and Pascal are not that large), although C# was entirely written in R-D, which is not trivial
• ANTLR is OK (but it is essentially R-D for LL grammars with some tweaks)
• not so much heard of, but historically relevant: Prolog DCG to quickly implement recursive descent parsers
• PEGs are great and a good choice
• operator-precedence grammars for expressions (e.g. algebraic expressions, also Prolog is mostly an OP grammar), covers a subset of LR(1) and are very easy to implement as a general driver engine with a table that is modifiable at parsing time (like Prolog) to change/define operator precedence/associativity on the fly
  

Deterministic context-free LR(1) (LALR) grammars are far more common than LL. LL requires a rewrite to remove left recursion and also to explicitly deal with (or remove) ambiguity. PEGs originate from LL parsing (i.e. top down) but take a different approach to resolve some issues with LL.

The list of tools and choices is extensive and covers a wide range of PL to implement a parser.

A hand-written R-D parser for a tiny PL is fun and nice to implement too, especially if the grammar is already defined as a R-D grammar (LL, top down) and was tested, so you're not getting stuck in a long rinse-repeat cycle of testing and tweaking the grammar/parser. It is often a good choice to implement parsing on embedded devices and yesteryears 8-bit systems.

- Rob