prologdcgleft-recursion

Prolog dcg generating all words from language


I'm trying to write some dcg grammar in prolog which will describe language of
a^nb^n n>=0
"",ab,aabb,aaabbb itd

All what I wrote is

s --> slowo.
slowo --> [a],slowo,[b],!.
slowo --> [].  

And its good as long as all I want to do is just check if word is correct, but how should dcg grammar look in prolog for ?-phrase(s,X) which will generate all words from my language?


Solution

  • If you're beginning with Prolog, try to avoid the use of !/0. You can generally do better without it.

    Here for example, your grammar could be written as follows:

    s --> [].
    s --> [a], s, [b].
    

    and queried as follows:

    ?- phrase(s, X).
    

    Note that prolog clauses are picked from left to right and top to bottom, so a rule written at the top of another one will be prioritized when the backtracking is involved.