Questions tagged [dcg]
DCGs (Definite Clause Grammars) are a compact way to describe lists in Prolog.
484
questions
1
vote
1
answer
183
views
Writing a DCG containing same string reversed
I am trying to write a dcg that accepts string of the form l0k, where l and k are strings over the alphabet {1, 2, 3} and l is k in reverse. What I have seems to work in that the first answer of a ...
3
votes
2
answers
215
views
Fibonacci using DCG
I am in the process of trying to create the fibonacci series using DCG in prolog. I have this for starters, however I have no idea why the code is not being carried out.
Here is the code below:
fib --&...
3
votes
5
answers
284
views
Sliding window method for pattern recognition in SWI-Prolog
I would like to find the most eloquent and efficient method, algorithmically speaking, to count occurrences of some patterns in SWI-Prolog.
For now, my solution uses DCG and looks like this:
...
1
vote
0
answers
52
views
How i can use DFS with a final state automata in Prolog?
I have a final state automata and i want to see all the patterns. This automata is about morphology of Turkish.
Turkish is an agglutinative language. I analyze words and and find their morphemes and ...
0
votes
1
answer
75
views
Termination of prolog query using using dcgs
Given the program
foo([]) --> [].
foo([Start|Rest]) --> alphanum(Start), foo(Rest).
alphanum(Ch) --> [Ch], { char_type(Ch, alnum) }.
How can I make the query length(I, 2), phrase(foo(C), I)...
4
votes
2
answers
242
views
Capture matching substrings from a DCG
Using regular expressions makes it quite easy to capture sub strings, e.g. the string "Jaco was an American bassist" matches this regular expression (PCRE2 syntax):
(?sm)^([Jj]aco).+(was|is)....
1
vote
3
answers
149
views
How to check how many elements you've already consumed in Prolog DCGs
Say I have these DCGs:
zorbs([H|T]) --> zorb(H), zorbs(T).
zorbs([]) --> [].
zorb(a) --> [1,2].
zorb(b) --> [3].
zorb(c) --> [6,1,2,2].
I can do this:
?- phrase(zorbs(X), [1,2,3,6,...
0
votes
2
answers
104
views
Free of context grammar in prolog - example
I'm studying free of context grammar using the functional language Prolog. I'm trying to solve this exercise, but I'm in trouble designing a grammar to recognize the language.
We know that the ...
0
votes
4
answers
113
views
How to replace a sequence of tokens in a DCG grammar in Prolog?
I would like to replace a sequence of tokens in a DCG grammar in Prolog. In other words replace the sequence or sublist A: [a,a,a,a] by the sublist B: [b].
chain --> ...
0
votes
2
answers
110
views
Match anything except if a negative rule matches
I have a rule that matches bc. When I encounter that in a string, I don't want to parse that string, otherwise parse anything else.
% Prolog
bc(B, C) --> [B, C], {
B = "b",
C = "...
1
vote
2
answers
103
views
run length encoding using DCGs
problem from: https://web.archive.org/web/20200718175929/http://www.pathwayslms.com/swipltuts/dcg/
Use a dcg to convert a sparse sequence like
[0,0,0,0,0,0,7,4,3,0,0,0,0,0,0,0,8,9,14,0,0,0,0....]
...
1
vote
1
answer
67
views
SWI Prolog PIO DCGs can't deal with null bytes
I have a file that is just the letter a. I can "parse" it with this DCG:
identity([]) --> [].
identity([H|T]) --> [H], identity(T).
?- phrase_from_file(identity(X), "jah.txt"...
0
votes
1
answer
67
views
DCG chain from facts, including "not seen before" condition
I am trying to solve the traditional path-finding puzzle using DCG notation. These are some connected numbers, and they make a chain from start to end. You can step between two numbers if there is a ...
1
vote
1
answer
61
views
Why do I need to duplicate my Prolog predicates in order to make my program work?
I am using SICStus Prolog 4.0.8 to write a program that parses a sentence in English and returns the syntactic tree, as well as a yes/no on whether the sentence is correct according to the programmed ...
2
votes
1
answer
114
views
How to deal with [a,b|c] format lists?
I created a simple parser for subset of Clojure language. For some reason it returns me a list in format [a,b,c|d], not in format [a,b,c,d]. Morover member(X, List) doesn't work with such format of ...
1
vote
1
answer
136
views
Left associative evaluation of a right recursive grammar in Prolog
I have an issue with evaluating a parsetree derived from a grammar. The parsetree is derived from this pice of code:
parse(block(LEFT_CURLY, STMTS, RIGHT_CURLY)) -->
left_curly(LEFT_CURLY),
...
0
votes
3
answers
145
views
How to program in Prolog a function that does operations on lists
How can I make a program in Prolog that contains n numbers of a and n numbers of b, it's important to note here that the number of a and b in the list must be equal, also the list must always start ...
1
vote
1
answer
70
views
Use expand_term/2 with file for dcg translation
I'm trying to "translate" a file that contains dcg's. in particular i am trying to transform all dcg into normal definite clauses using expand_term/2, however i would like to avoid manually ...
1
vote
2
answers
189
views
How to code a prolog program that does some operations on list
I want to program a list that uses only the characters {a, b}.
My objective is that Prolog returns true only if the list that the user enter contains n number of a, or at least one a but has to finish ...
1
vote
2
answers
130
views
Define a DCG in Prolog for bit strings practice problem
Before our Prolog final exam soon, I got some practice questions and I am stuck on one:
For each integer n > 0,
let Ln := {s ∈ {0, 1}+ | s ends in a string from 1(0 + 1)n−1}
be the set of bit-...
3
votes
3
answers
338
views
How to write this DCG more elegantly?
Playing around with DCGs and stubled upon the following problem:
I want to parse as well as produce an exact amount of spaces (" "). My trivial approach of simply doing this:
...
0
votes
0
answers
98
views
Natural Language processing with prolog error
I'm new to using prolog and I'm trying things to get a text parsed and translated in this way:
?- go.
|: All boys run.
s(np(det(all),noun(boys)),vp(verb(run)))
S = all(_4326, boy(_4326)->run(_4326))...
3
votes
3
answers
120
views
Writting grammar in prolog and can't get it to work correctly
This is for a class assignment, but I can't figure out how to fix my problem.
I wrote the following:
sentence(S0, S):- f(S0,S); t(S0, S1),n(S1, S2),t(S2, S).
f(S0, S):- termIf(S0, S1), pLeft(S1, S2), ...
1
vote
0
answers
64
views
How to use normal clauses converted from DCG Prolog one?
I know DCG is only a syntactic sugar , as prolog translate them in normal Clauses.
So, for instance,
palindrome --> [].
palindrome --> [_].
palindrome --> [X], palindrome, [X].
/* it is ...
0
votes
2
answers
123
views
Calling phrase/2 on a list of grammar rules, rather than a list of atoms
With a grammar like this:
as --> [].
as --> [a], as.
b(b(a)) --> as.
c(X) --> b(X).
phrase(b(X), [a, a]) & phrase(c(X), [a, a]) work no problem. Both return X = b(a)..
But is it ...
7
votes
4
answers
538
views
Should text-processing DCGs be written to handle codes or chars? Or both?
In Prolog, there are traditionally two ways of representing a sequence of characters:
As a list of chars, which are atoms of length 1.
As a list of codes, which are just integers. The integers are to ...
3
votes
2
answers
210
views
Threading state/context in DCG while parsing text
How to pass State (and change it when I need) around while parsing text !?
https://www.metalevel.at/prolog/dcg
the example is doing counting..
Don't know how I'm supposed to pass the initial State. Do ...
-1
votes
3
answers
102
views
DCG: hidden argument across all Rules?
.in DCG is there a way to have hidden argument i.e. argument is passed in the top rule , but I dont mention it in the rest of the rules , but i still have access to it.
S(Ctx,A,B) --> ...
R1(A) --...
0
votes
1
answer
207
views
Defining a DCG in Prolog for bit strings
Ahead of our Prolog exam next week, our lecturer has provided us with a number of practice questions, but I'm stumped for the following. Can anyone help?
For each integer n > 0,
let Ln := {s ∈ {0, ...
0
votes
1
answer
160
views
parsing with CHR (Constraint handling rules)
Trying to do sort of parsing with CHR (Constraint handling rules)
I come up with this (still learning)
w(the),w(X) <=> w([the,X]).
w(L),w(on),w(R) <=> w(on(L,R)).
w(L),w(is),w(R) <=> ...
0
votes
1
answer
57
views
Possible bug or omission
Possible bug OR I'm missing something obvious :
test(struct(X,Y)) --> X,[isa],Y.
When I try to use this rule I get an error.. and it was working the other day !!
The listing uses phrase() inside ...
1
vote
0
answers
65
views
Properly matching a set of tokens against my BASIC grammar
I am working on writing a BASIC interpreter in Prolog. DCGs are a little tricky, which is why I am having trouble here today.
Here is my grammar.
bool --> [true].
bool --> [false].
is_num_char(...
4
votes
5
answers
466
views
About building a list until it meets conditions
I wanted to solve "the giant cat army riddle" by Dan Finkel using Prolog.
Basically you start with [0], then you build this list by using one of three operations: adding 5, adding 7, or ...
3
votes
2
answers
74
views
matching 'connectors' and creating structure?
I'm trying to match and then convert to structure :
text1, connector, text2 ==> connector(text1,text2)
the following works, but seems too unwieldy and non-idiomatic :
p([]) --> [].
p([H|T]) --&...
3
votes
2
answers
138
views
How do I create a DCG rule inverse to another in Prolog?
I am writing a Commodore BASIC interpreter in Prolog, and I am writing some DCGs to parse it. I have verified the DCGs below to work except for the variable one. My goal is this: for anything which ...
1
vote
1
answer
71
views
Parsing list of items with DCG?
How do you parse string which is list of items f.e.
1,2,3,4
aa,b,ccc,ddd
Currently I do this (and is the comma) :
sub(X,Y) --> req(X), [and], req(Y).
sub(X) --> req(X).
req(on(X,Y)) --> ...
2
votes
1
answer
143
views
DCG : zero-or-more, zero-or-one , one-or-more occurrences?
In DCG how do you implement : zero-or-more, zero-or-one , one-or-more occurrences ?
I'm talking about the following in pseudo code :
sentence --> word+
float --> int+, ['.'], int+
nilORa --...
1
vote
0
answers
69
views
DCG encoding facts with lambdas in old Prologs?
Having the rule :
nx(X^dog(X)) --> [dog].
In old books the query for the above fact is :
?- nx(X^R).
but now I have to use :
?- phrase(nx(X^F),R).
F = dog(X),
R = [dog].
because it is encoded as ...
1
vote
1
answer
129
views
How do I construct a parse tree from a series of S-expression tokens in Prolog?
I'm curious about Prolog as a parser, so I'm making a little Lisp front-end. I have already made a tokenizer, which you can see here:
base_tokenize([], Buffer, [Buffer]).
base_tokenize([Char | Chars], ...
0
votes
1
answer
276
views
DCG reversing a string of binary bits
I want to write a (Prolog) DCG which takes in strings of the form a2rev(a) where a is a string of binary bits, e.g. 1012101, 001121100, 0111002001110. My idea was the following :
reverse([]) --> ...
4
votes
2
answers
120
views
Is there a way I can call non-terminal symbols recursively when working with a DCG in Prolog?
I have been trying to convert a section of Prolog code I created to represent a basic finite automaton into a DCG. Basically it ensures that an acceptable input would be one where the third last ...
0
votes
1
answer
116
views
Prolog: I keep getting errors when trying to compile a simple program
I'm trying to make a simple grammar parser that checks whether a specific sentence pattern is valid or not. the grammar rules are as follows:
terminals: circleplus, circleor, 1, 0
non-terminals: S; T
...
1
vote
4
answers
218
views
How can I make a time parsing predicate work in both directions?
Using SWI-Prolog I have made this simple predicate that relates a time that is in hh:mm format into a time term.
time_string(time(H,M), String) :-
number_string(H,Hour),
number_string(M,Min),
...
2
votes
1
answer
983
views
Creating a DCG capable of parsing trees in Prolog
I have to create a DCG in Prolog with the following features:
handle subject/object distinction
singular/plural distinction
capable of producing parse trees
make use of a separate lexicon
Here's the ...
0
votes
1
answer
58
views
Two DCG rules for `(ab)*`. Can it be one?
I want to generate or test strings obeying the Perl Regex (ab)*
The code below works perfectly well:
Generate
?- phrase_acceptable(Text,6).
Text = abababababab ;
false.
Test (or compress?)
?- ...
3
votes
1
answer
172
views
How to create a higher order DCG parser in Prolog?
I would like to have some more general parsers, like for example paren that would take a parser and wrap it with parentheses:
paren(Parser, Result) -->
"(", some_magic_dcg_call(Parser, Result), "...
1
vote
2
answers
148
views
matching patterns in matrix using prolog dcg
Is it possible with DCGs to extract some 2D list, such that it can be represented by a context free grammar
S -> [ A , B ]
A -> [0,0,0,0,0]
A -> NULL
B -> [1,1,1,1,1]
B -> NULL
for ...
1
vote
1
answer
101
views
dcg parsing in random order
I have some text files which I would like to parse, however the order of for exemple stop and start could be different. Stop could appear first or last, this is a dummy exemple as there are multiple ...
5
votes
1
answer
118
views
parsing and generating multi-level list structures with DCG
Suppose I call an "a-list" a list of zero or more "a"s:
% as = [a,a,a]
as --> [].
as --> [a], as.
Suppose I want to represent a "b-list”, a list of zero or more a-lists:...
1
vote
1
answer
145
views
parsing stdin with dcg
I am having some difficulties understanding how to parse some text from stdin to the desired variables using DCG.
Players: player1 & player2
Board : 3 moves
1A : player1
5D : player2
8Z : player1
...