If you’re wanting to avoid choicepoints, then add a cut in this line:
items --> item, !, items.
(! is implemented in both DCG and non-DCG Prolog.)
The standard method of handling such situations is to have an end_of_file token that the tokenizer adds to the input that it passes to the parser. So this:
proto = [syntax] { import | package | option | topLevelDef | emptyStatement }
would be changed to
proto = [syntax] { import | package | option | topLevelDef | emptyStatement } end_of_file
(Not to be confused with end_of_file from read/1.)
You may wish to use sequence//2 in library(dcg/high_order).
?- phrase(sequence(digit, Digits), `123a`, `a`).
Digits = [49,50,51]
(warning: this leaves a choice-point)
Thanks.
This makes we think that I need to analyze the grammar and the grammar processing if I expect backtracking here or not.
I.e. if there is in fact a choice to be made given tokens to be seen later, including in subsequent rules that would be processed.
And only then i could with confidence cut here.
Thank you.
Sequence//2
Would make the DCG more readable – less “auxiliary” clauses.
It might be useful to read up on LL(1) parser theory (this is what a naïve DCG parser does) and also run your grammar through an LR(1) parser generator such as yacc.
and many links here: Parsing - Wikipedia
(I learned this stuff long ago, so I don’t have good recommendations for tutorials; Niklaus Wirth popularized LL(1) with PL360 and Pascal and there’s a description of it in one of his books.)
An interesting way of making both a parser and a generator is to use DCTG notation (as described in Abramson&Dahl Logic Grammars): Package: lang/prolog/code/syntax/dctg/ … this creates an implicit parse tree and a notation for walking it in either direction.
I once had a reversible grammar for C declarations that used this but it’s lost in my backups somewhere – it was considerably shorter than the code for cdecl that used yacc/flex.
BTW, tabling can help with left-recursion. There’s an old (out of date?) discussion here: Definite Clause Grammars and Tabling
https://www3.cs.stonybrook.edu/~warren/xsbbook/node23.html
(also in the XSB PDF manual)
although I think that the latest tabling implementation avoids some of the problems.
I am starting to find that this approach is actually very effective.
Typically, with the parse tree generated as an outcome of parsing, in order to generate an AST one needs to write a prolog parse tree traversal program that essentially mirrors the structure of the grammar and the DCG.
This program is in my case further complicated by the need to deal with many optionals.
The approach I am currently working on can be understood as “triggers” on leaf DCG nodes – with each trigger generating the leave node.
It turns out that this simplifies the program that asserts the AST – since now, only many fragmented trigger rules need to be created without regard to the rather complex AST structure.