Context-free grammar in C

Question

I have an assignment to make a program in C that displays a number (n < 50) of valid, context-free grammar strings using the following context-free grammar:

S -> AA|0
A -> SS|1

I had few concepts of how to do it, but after analyzing them more and more, none of them were right.

For now, I'm planning to make an array and randomly change [..., A, ...] for [..., S, S, ...] or [..., 1, ...] until there are only 0s and 1s and then check whether the same thing was already randomly generated.

I'm still not convinced if that is the right approach, and I still don't know exactly how to do that or where to keep the final words because the basic form will be an array of chars of different length. Also, in C, is a two dimensional array of chars equal to an array of strings?

Does this make any sense, and is it a proper way to do it? Or am I missing something?

maybe you should list each of your questions separately, as string representation is not related to CFG — Grady Player, Nov 27 '13 at 16:28
Do you necessarily have to generate a string with only terminals? Or is e.g. `[A, S, S, 0, A, 1]` also a valid outcome? Because then you could just do a random number of steps. I'm not sure an array is the best structure, as steps may increase the length of the string. Does it have to be C, or is C++ allowed as well? If you are looking for solutions with only terminals, it may be worth proving what they look like first (e.g. you only get even numbers of consective `0`s and `1`s, or an `1` can only occur between two `0`s, etc) and use those rules to generate a result. — CompuChip, Nov 27 '13 at 16:29
Yes, it has to be all ones and zeros at the and. Yes, only in C. — pawel.ad, Nov 27 '13 at 17:30
I don't see anywhere in your specification that the program has to process the stated grammar. I could satisfy your stated requirements with some hardcoded `printf` calls that print manually computed strings that conform to the grammar. — Kaz, Nov 27 '13 at 23:35

Guilherme Bernal · Accepted Answer · 2013-11-27T17:54:11.347

2

You can simply make a random decision every time you need to decide on something. For example:

function A():
  if (50% random chance)
    return "1"
  else
    return concat(S(), S())

function S():
  if (50% random chance)
    return "0"
  else
    return concat(A(), A())

Calling S() multiple times give me these outputs:

"0"
"00110110100100101111010111111111001111101011100100011000000110101110000110101110
 10001000110001111100011000101011000001101111000110110011101010111111111011010011
 10000000101111100100011011010000000101000111110010001000101001100110100111111111
 1001010011"
"11"
"10010010101111010111101"

All valid strings for your grammar. Note that you may need to tweak a little the random chances. This sample has a high probability to generate very small strings like "11".

edited Nov 27 '13 at 17:54

answered Nov 27 '13 at 16:37

Guilherme Bernal

8,183
25
43

Is this really that simple? I'll definitely try that approach, thanks! – pawel.ad Nov 27 '13 at 17:32
This is a very nice solution, resembles the way you would do it in a functional language. It also generalizes quite well, I think. The downside is, it's maybe not very intuitive - especially a beginner would have trouble thinking of this (or maybe even understanding it). – CompuChip Nov 27 '13 at 17:34

score 0 · Answer 2 · answered Nov 27 '13 at 16:35

0

Try to think of the context-free grammar as a set of rules that allow you to generate new strings in a language. For example, the first rule:

S -> AA | 0

How could you generate a word S in this language? One way is with a function that generates, at random, either the string "0" or two A words, concatenated.

Similarly, to implement the second rule:

A -> SS | 1

write a function that generates, at random, either "1" or two S words concatenated.

answered Nov 27 '13 at 16:35

Tim Pierce

5,514
1
15
31

Yeah, I think that it is what @Guilherme Bernal did, and I like it a lot. – pawel.ad Nov 27 '13 at 17:25

score 0 · Answer 3 · edited May 23 '17 at 12:17

You asked several questions...
Regarding The question: BTW in C, is two dimensional array of chars equal to array of strings?

Yes.

Here are ways to declare arrays of strings, each example shows varying flexibility in terms of usage:

char **ArrayOfStrings;  //most flexible declaration - 
                        //pointer to pointer, can use `calloc()` or `malloc()` to create memory for
                        //any number of strings of any length (all strings will have same length)

or

char *ArrayOfStrings[10]; //somewhat flexible - 
                          //pointer to array of 10 strings, again can use  `c(m)alloc()` to allocate memory for 
                          //each string to have any lenth (all strings will have same length)

or

ArrayOfStrings[5][10]; //Not flexible - (but still very useful)
                       //2 dimensional array of 5 strings, each with space for up to 9 chars + '\0' 
                       //Note:  In C, by definition, strings must always be NULL terminated.

Note: Although each of these forms are valid, and very useful when used correctly, It is good to be aware there are differences in the way each will behave in practice. (read the link for a good discussion on that)

Context-free grammar in C

3 Answers3

Linked