I use the recursive descent parser for top-level constructs like :- and the Pratt parser (a generalization of precedence climbing) for everything else.
The Pratt parser is a surprisingly good fit for Prolog: I haven’t encountered any significant problems or situations that it can’t handle. I’m wondering if all of the core Prolog expression syntax can fit nicely into the Pratt parser model.
Thats a chicken egg question, given that Prolog comes
from parsing, and the work by Alain Colmerauer had in
his background first van Wijngaarden Grammars, and
then Q-Systems. The step to Prolog came in 1972,
while Pratt published his paper in POPL 1973. Sounds
la little queer to say it would be a fit for Prolog.
Although the Pratt paper also starts with reference
to Wijngaarden, and even Wirth. There was a generation
of researches struggling with language efforts such
as ALGOL and to give it lean parsers. The only trick
you need to know is how to eliminate left recursion
from your parser. So while a production rule on paper
might say in BNF, BNF itself advocated by Pratt:
<expr> ::= <expr> + <term>
<expr> ::= <term>
A Prologer will automatically think DCG and transform it:
expr(Y) --> term(X), expr_rest(X, Y).
expr_rest(X, T) --> "+", !, term(Y), expr_rest(X+Y, T).
expr_rest(X ,X) --> [].
The above shows the neat little trick to eliminate
the left recursion. Based on these ideas you can write
a full Prolog parser using an operator table. Its a little
bit like replacing foldl/4 by foldr/4 with an accumulator.
BTW: The difference lists underlying DCG in a 1972 document:
http://alain.colmerauer.free.fr/alcol/ArchivesPublications/HommeMachineFr/HoMa.pdf
Still the DCG answer might frustrate you, since you
are now facing a bootstrapping problem. You want
to writer a parser for your Prolog system.
And you don’t have your Prolog system yet, that
could run this parser. So to build your machine M_A,
you first need a machine M_B that helps you building it.
After some iteration you can become self hosting.
Self-hosting (compilers)
for example, a compile that can compile its own source code
https://en.wikipedia.org/wiki/Self-hosting_(compilers)
SWI-Prolog is the ideal machine M_B to help you
with M_A in the early stage ! Strangly Scryer Prolog didn’t
proceed this way. I don’t know why, some might judge
the self hosting too academic, others think its the ultimate
first test case for your compiler. Giving it its own source
as dog food ! Main benefit of a self hosting architecture,
it can often increase productivity , especially for porting tasks.
If you lookup the wikipage , the list of industry grade
compilers being self hosting, is quite long. Also once you
have a self hosting compiler, you can still go the other
way, back down from your high level language, and write
parts in assembly or in a more low level language.
Prolog can offer you an entry ticket for fast prototyping.
Wow, very interesting connection. Thanks
Should I try to develop a prolog interpreter using prolog? It seems like a nice coding exercise and milestone, but still I don’t understand how can it increase productivity
The 1972 Prolog used a syntax quite different from the current one. The latter was introduced some years later by Edinburgh Prolog.
The problem is people working in natural language processing (NLP)
consider operator parsing a rather trivial problem. Since many NLP
problems are solved with a lexicon, which is very close to an operator table.
When I mention Alain Colmerauer I was not talking about particular syntax
of a Prolog system. But about the parsing mechanism of definite clause
grammar (DCG), because the OP asked which parsing algorithms to use.
Amazingly DCG was already used by Alain Colmerauer in reference I gave.
When translated to SWI-Prolog noadays, his examples would still work, one
needs to find a way to map “suprimes” and “retarder” though. And when I look
at the date of the report it is from 1972. While Pratt promoted BNF in 1973
comming from a CGOL project. The difference between the Alain Colmerauer
report, and the Pratt report, the later highlights more parsing artificially created
languages, such as programming languages, and their operator problematic.
While the former demonstrated more a natural language processing
use case, like a query answering system, in the various traditions of
We can allow a lexicon to be a grammar rule book as well.
An operator declaration in Prolog:
:- op(500,yfx,+).
:- op(400,yfx,*).
Is then just a lexicon that has entries such as:
plus +:
An operator that appears in infix position, on level
500, expecting a level 500 expression X to the left,
and a 499 expression Y to the right, forming +(X,Y)
times *:
An operator that appears in infix position, on level
400, expecting a level 400 expression X to the left,
and a 399 expression Y to the right, forming *(X,Y)
The y in yfx leads to a nasty left recursion, refering from the production
rules on a certain level to the same production rules on the same
given level. So you have to read the lexicon and at the same time
have a solution in place that doesn’t send you into an infinite loop.
There are like a dozen methods around that can solve the left
recursion, and the accumulator trick I showed is only one such solution.
BTW: You find the level computation in various sources, like starting
with the DEC-10 Prolog manual page 78 in 1982, and a little more famous
was recently Tau Prolog in 2018 for compiling a document with the rules
behind the various oparator icons xfx, yfx, etc.., so as to help themselves,
and also some subsequent projects that tried to takle the problem. Unlike
most Prolog systems do it nowadays, Alain Colmerauer had it upside down,
starting with priority 1 and not with priority 1200:
