1

I've inserted the given context free grammar into the database using assert(....) If the grammar is something like

S-->a,S,b
S-->c

This grammar is inserted into the database. I have to write a dcg to generate sentences for the cfg in the database. For example if i define the dcg in this way myDcg('S',str), the 'S'(non terminal) should be called or substituted by aSb or c|d or so.

The problem is how can i call/substitute 'S' by facts from the database each time a non terminal('S') is encountered to generate sentences.

Hope you understood my question, if not i will try to edit the question.

Below(Sample code) is what i wanted to do exactly This is not dcg. 

myGrammar([], []):-!.

myGrammar([T|Rest], [T|Sentence]):-
          myGrammar(Rest, Sentence).

myGrammar([NT|Rest], Sentence):-
          grammar(NT, Rest1),
          append(Rest1,Rest, NewRest),
          myGrammar(NewRest, Sentence).

Whenever a terminal is encountered it should be printed out and when a non terminal is encountered it will backtrack.

false
  • 10,264
  • 13
  • 101
  • 209
Anil
  • 2,405
  • 6
  • 25
  • 28

2 Answers2

2

I assume that you started with Prolog recently. Yes, you can assert things into the database, but this isn't the common thing you do in the first place. You will want to use that feature much later when you feel safe with the base language.

What you typically do is to write a grammar into a file like myfirstgrammar.pl and then load that file into your Prolog system.

Please refer to this recent thread for details concerning the grammar.

Community
  • 1
  • 1
false
  • 10,264
  • 13
  • 101
  • 209
  • i've written the grammar in a text file and loaded that into my prolog system. I also asserted all the rules. But what my problem is, when i started writing the dcg for the context free grammar, i want to refer(backtracking) to the grammar inserted in the database whenever a non terminal is occurred. So my problem is how to backtrack and the dcg i'm trying to write is for any given cfg that is written in the text file. – Anil Dec 01 '11 at 16:58
  • There are things which somehow cannot work in your description: If you load the grammar into your Prolog system, you do not need to assert rules at all. So there is some misunderstanding on that level. Maybe show the file, and the exact command how you invoked your Prolog. ((It is a very frequent beginner error to believe that things have to be asserted first. But you simply load your file with some command...)) – false Dec 01 '11 at 17:03
  • sorry, i think i did not load the file but let me tell you what i have done. Initially i'm reading the text file containing the grammar. By tokenizing the grammar i've generated a list something like `[grammar('S',[a,'S',b]),grammar('S',[....]),..]`.Now i've tried to assert the whole list. Finally i have to write a dcg for the cfg grammar read from the text file. – Anil Dec 01 '11 at 18:07
  • so while writing the dcg, generally we backtrack whenever a non terminal is encountered and when a terminal is encountered it is printed out. Since i've asserted the rules, i have to use/call them while backtracking – Anil Dec 01 '11 at 18:09
  • Clearly: You are doing too much around the actual task! You don't need to tokenize the grammar! Just change it from `S-->a,S,b.` to `s --> [a],s,[b].` and then read the other thread how you can generate all sentences! – false Dec 01 '11 at 18:48
  • i've added some info to my ques..once check the sample code. In sample code, grammar(....) means the `[grammar('S',[a,'S',b]),grammar('S',[....]),..]`... how can i differentiate terminal and non terminal symbols? – Anil Dec 01 '11 at 21:36
  • what you said is right. i nee to change the cfg from `S-->a,S,b.` to `s --> [a],s,[b].` But what i did in my prog is i've read the grammar which is in this format `S --> a S b` and tokenized it into `grammar('S',[a,'S',b])` by removing spaces. I want to change it to something like grammar `('S',[[a],'S',[b]])` or `grammar('S',[t(a),nt('S'),t(b)])`. but how to differentiate terminals and non terminals to do that? – Anil Dec 02 '11 at 01:53
2

In your predicate mygrammar/2 there is a list of non-terminals and terminals in the first argument and a list of terminals in the second. It should probably succeed if the second argument is of the form of the first. So what you have here essentially is a meta interpreter for DCGs. A few suggestions:

Your tokenizer produces currently [grammar('S',[a,'S',b]),grammar('S',[....]),..]. Let it produce [grammar('S',[t(a),nt('S'),t(b)]),grammar('S',[....]),..] instead. In this manner it's evident what is a terminal and what is a non-terminal. And, oh, remove that !.

myGrammar([], []).
myGrammar([t(T)|Rest], [T|Sentence]):-
   myGrammar(Rest, Sentence).
myGrammar([nt(NT)|Rest], Sentence):-
   grammar(NT, Rest1),
   append(Rest1,Rest, NewRest),
   myGrammar(NewRest, Sentence).

DCGs, btw are a bit more general than this interpreter.

The actual classification between non-terminals and terminals has to be done by the tokenizer.

uppercasecode(C) :-
   between(0'A,0'Z,C).

lowercasecode(C) :-
   between(0'a,0'z,C).

If you are using chars (one-character atoms), you will use char_code(Char, Code) to convert between them.

Full Unicode support is still in its infancy. Its very tricky because of all those special cases for characters like Ⓐ which is upper case but still cannot be part of an identifier. But here is how you can do it in SWI currently.

uppercasecode(C) :-
   '$code_class'(C,upper),
   '$code_class'(C,id_start).

lowercasecode(C) :-
   '$code_class'(C,id_start),
   '$code_class'(C,id_continue),
   \+ '$code_class'(C,upper).

Update: In the meantime, there is char_type/2 and code_type/2 for this purpose.

uppercasecode(C) :-
   code_class(C, upper),
   code_class(C, prolog_var_start).
false
  • 10,264
  • 13
  • 101
  • 209
  • so how to use this. While tokenizing, should i check whether each term or character is an uppercase or lower case? – Anil Dec 02 '11 at 03:09
  • Yes indeed. That's the only way how you can distinguish terminals and non-terminals given your syntax. ((In DCGs, the distintion is made differently: lists like `[a]` but also "a" are terminals including the empty list `[]` which is the epsilon and everything else is a non-terminal)). – false Dec 02 '11 at 03:13
  • uppercase and lowercase worked fine...but what if the grammar is like `Sa-->a,Sa,b` how to check that. upper and lower cases are only for characters right. – Anil Dec 02 '11 at 19:56
  • by trying the sample code i've shown i'm running into infinite loop (ERROR: Out of local stack). How to control this. Also, with my code i'm generating a list which is infinite, instead of list i want to display all sentences in this format `Sentence=ab`, Sentence=aabb`, ...so on...so how to control the loop? – Anil Dec 04 '11 at 22:13
  • @ven w.r.t. loops. Please refer to my 1st answer. It contains a link to a grammar with exactly that issue. – false Dec 05 '11 at 21:22
  • i have something to ask once again. I've already said that i've asserted the whole list `[grammar('S',[a,'S',b]),grammar('S',[c]),grammar('S',[d])]` in the database...so when you ask `grammar('S',L)`. we get `L=[a,'S',b]; L=[c]; L=[d]...`And in my program whenever i come across a non terminal 'S' i should substitute `[a,'S',b] or [c] or [d]`...but everytime i'm able to replace 'S' only with `[a,'S',b]``....is there a way to substitute `[c] or [d]`...what i mean is whether i can call` [a,'S',b] or [c] or [d]` randomly rather calling only the first value`[a,'S',b]`? – Anil Dec 08 '11 at 19:45
  • @ven, you are still using extremely ambiguous notions that can only lead to second-guessing. Sometimes this works, often not. E.g. asserting a list... In many systems asserta([a]) produces an error. Why don't you do a Makefile or other reproducible way, so that it is possible to know what you actually meant... – false Dec 08 '11 at 23:24
  • ok...forget about everything...i just got an idea for my solution...just help me with this....i'll start with `lmd('S',Sentence)`. Initially `'S'` will be replaced with [a,'S',b]...i want to modify my code in this way....`lmd_([T|Rest],[T|Sentence]:-`when i come across `a` i want to add it to the second list `[a|sentence]`, when i come across 'S'.i want to skip it and jump to `b` and add it to the list again so that my first sentence will be `[a,b]`, Now i want to replace 'S' with again [a,'S',b] and the process continues...so that my solutions will be `[a,b],[a,a,b,b],[a,a,a,b,b,b]`. – Anil Dec 09 '11 at 17:16
  • how can i skip the non-terminal so that i can replace it again later with [a,'S',b]. – Anil Dec 09 '11 at 17:18
  • Evidently you are trying to find some alternate derivations. I suggest: Make a new question containing **all your current code** – false Dec 09 '11 at 17:19