Questions tagged [dcg]

DCGs (Definite Clause Grammars) are a compact way to describe lists in Prolog.

Filter by
Sorted by
Tagged with
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 ...
vinicio's user avatar
  • 13
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 --&...
ggplot2's user avatar
  • 41
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: ...
René Chenard's user avatar
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 ...
Mehmet Gençdal's user avatar
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)...
Edgar's user avatar
  • 159
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)....
hakank's user avatar
  • 6,679
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,...
Name McChange's user avatar
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 ...
Selene Melo's user avatar
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 --> ...
Claude COULOMBE's user avatar
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 = "...
eguneys's user avatar
  • 6,102
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....] ...
madeofmistake's user avatar
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"...
Name McChange's user avatar
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 ...
TessellatingHeckler's user avatar
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 ...
Kingfisher's user avatar
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 ...
TheWorstHaskellProger's user avatar
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), ...
tmagnusson's user avatar
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 ...
Nobody's user avatar
  • 103
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 ...
Chr's user avatar
  • 11
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 ...
Nobody's user avatar
  • 103
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-...
izash's user avatar
  • 51
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: ...
Fabian Schneider's user avatar
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))...
cucucu's user avatar
  • 1
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), ...
Wendell Best's user avatar
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 ...
Ciro Pollio's user avatar
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 ...
Erik Germani's user avatar
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 ...
David Tonhofer's user avatar
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 ...
sten's user avatar
  • 7,148
-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) --...
sten's user avatar
  • 7,148
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, ...
Numbers123's user avatar
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) <=> ...
sten's user avatar
  • 7,148
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 ...
sten's user avatar
  • 7,148
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(...
Caspian Ahlberg's user avatar
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 ...
mlg556's user avatar
  • 419
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]) --&...
sten's user avatar
  • 7,148
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 ...
Caspian Ahlberg's user avatar
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)) --> ...
sten's user avatar
  • 7,148
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 --...
sten's user avatar
  • 7,148
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 ...
sten's user avatar
  • 7,148
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], ...
Caspian Ahlberg's user avatar
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([]) --> ...
user avatar
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 ...
user avatar
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 ...
ESM's user avatar
  • 175
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), ...
Nicholas Hubbard's user avatar
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 ...
Shahawn's user avatar
  • 31
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?) ?- ...
David Tonhofer's user avatar
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), "...
radrow's user avatar
  • 6,560
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 ...
YiLuo's user avatar
  • 107
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 ...
swaffelay's user avatar
  • 182
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:...
Meng Weng Wong's user avatar
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 ...
swaffelay's user avatar
  • 182

1
2 3 4 5
10