471,616 Members | 1,949 Online
Bytes | Software Development & Data Engineering Community
Post +

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 471,616 software developers and data experts.

String Generation using Mask Parsing

Hello,

I am new to C and I am trying to write a few small applications to get
some hands-on practise! I am trying to write a random string
generator, based on a masked input. For example, given the string:
"AAANN" it would return a string containing 3 alphanumeric characters
followed by 3 digits. This part I have managed:)

I would now like to add some complexity to this, such as repetitions
and grouping. For example, I'd like to have masks similar to:
"AAN*10", which would return two alphanumeric chars followed by a
sequence of 10 numeric characters. However, the characters could be
grouped, such as: "A(AN)*10", which would now return an alphanumeric
character followed by a sequence of ten alternating alphanumeric/
numeric characters.

I'm not really sure where to start with this next step as I have
minimal experience. Any pointers in the right direction, or sample
code, would be appreciated.

Thanks in advance,
James.
Sep 21 '08 #1
6 3360
James Arnold wrote:
>
I am new to C and I am trying to write a few small applications
to get some hands-on practise! I am trying to write a random
string generator, based on a masked input. For example, given
the string: "AAANN" it would return a string containing 3
alphanumeric characters followed by 3 digits. This part I have
managed:)

I would now like to add some complexity to this, such as
repetitions and grouping. For example, I'd like to have masks
similar to: "AAN*10", which would return two alphanumeric chars
followed by a sequence of 10 numeric characters. However, the
characters could be grouped, such as: "A(AN)*10", which would
now return an alphanumeric character followed by a sequence of
ten alternating alphanumeric/ numeric characters.

I'm not really sure where to start with this next step as I
have minimal experience. Any pointers in the right direction,
or sample code, would be appreciated.
I think a study of regular expressions, as implemented in Unix and
Linux, would be instructive here.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.
Sep 21 '08 #2

"James Arnold" <ja****@gmail.comwrote in message
I am new to C and I am trying to write a few small applications to get
some hands-on practise! I am trying to write a random string
generator, based on a masked input. For example, given the string:
"AAANN" it would return a string containing 3 alphanumeric characters
followed by 3 digits. This part I have managed:)

I would now like to add some complexity to this, such as repetitions
and grouping. For example, I'd like to have masks similar to:
"AAN*10", which would return two alphanumeric chars followed by a
sequence of 10 numeric characters. However, the characters could be
grouped, such as: "A(AN)*10", which would now return an alphanumeric
character followed by a sequence of ten alternating alphanumeric/
numeric characters.

I'm not really sure where to start with this next step as I have
minimal experience. Any pointers in the right direction, or sample
code, would be appreciated.
It turns into a grammar parsing problem.

To understand parsing generally, you could do worse than to check out my
MinBasic project, on my website.

Basically you divide the input strem into "tokens". Here that step is simple
because most tokens are a single char - the excpetion is the embedded
integers. Then you keep one token of lookahead, and take actions. When you
hit a '(' you need to push a stack of strings. When you hit the matching ')'
you pop it, and look for the '*' and integer to multiply.
You don't actually need to manage the stack yourself. You have a function
char *alphanum() which returns a sequence of As and Ns. When you hit the '('
you call alphanum() recursively, duplicate the string the required number of
times, and append it to the mother alphanum().

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Sep 21 '08 #3
James Arnold wrote:
I would now like to add some complexity to this, such as repetitions
and grouping. For example, I'd like to have masks similar to:
"AAN*10", which would return two alphanumeric chars followed by a
sequence of 10 numeric characters. However, the characters could be
grouped, such as: "A(AN)*10", which would now return an alphanumeric
character followed by a sequence of ten alternating alphanumeric/
numeric characters.

I'm not really sure where to start with this next step as I have
minimal experience. Any pointers in the right direction, or sample
code, would be appreciated.

Thanks in advance,
James.
It's definitely worth it to have a look at how regular expressions work.
I might also suggest that you alter that syntax to be a little less
ambiguous, like putting the numeric values in braces {} so you can more
easily figure out where the number begins and ends.

After that, my suggestion would be to divide the program into two parts.
The first one would input a string like "AA(AN){10}" and expand it to
something like "AAANANANANANANANANANAN", which is really what you're
looking at. The second part of the program is essentially what you've
already written; it inputs that string and outputs the random one.

Hope this helps.

Trent
Sep 21 '08 #4
I think a study of regular expressions, as implemented in Unix and
Linux, would be instructive here.
I am already familiar with regluar expressions, but I was under the
impression they can't be used to match braces when nested? So if for
example I wanted to do A(A(N)*10)*5, regular expressions wouldn't be
appropriate?
It turns into a grammar parsing problem.
I have been looking at Lex/Yacc (well, Flex/Bison) and written a
grammar to handle what I would like. I've compiled it and managed to
get it to output the detected tokens, but it definitely seemed to be
overkill for such a small program. Currently I'm just iterating
through a string and switch()'ing on each character, which covers most
of the functionality I'd like. I figured there must be a way of
tracking nested depth and calling the parse routine recursively for
each matched group?
After that, my suggestion would be to divide the program into two parts.
The first one would input a string like "AA(AN){10}" and expand it to
something like "AAANANANANANANANANANAN", which is really what you're
looking at.
This is also something I had considered, but I want to be able to use
a range for a specified repetition, e.g. repeat between 5 to 10 times.
This is fine, but if I want to generate 50 different outcomes the full
mask would need to be expanded each time, rather than just the
repeated bit. Surely that is not going to be very efficient? :)

Thanks for the replies!
Sep 21 '08 #5

"James Arnold" <ja****@gmail.comwrote in message
This is also something I had considered, but I want to be able to use
a range for a specified repetition, e.g. repeat between 5 to 10 times.
This is fine, but if I want to generate 50 different outcomes the full
mask would need to be expanded each time, rather than just the
repeated bit. Surely that is not going to be very efficient? :)
Don't worry too much about efficiency.

Your code goes (skeleton)

char *alphanum()
{
char *answer;

set answer to emptystring;

while(1)
{
switch(gettoken())
{
case 'A': concatenate an 'A':
case 'N': concatenate an 'N':
case '(')
match '(');
sub = alphanum();
match(')');
match('*');
repetitions = integer();
for(i=0;i<repetitions;i++)
concatenate sub;
case ')':
return answer;
case 0:
return answer;
}
}
}

It won't run superfast, but it won't crawl.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

Sep 21 '08 #6

[You or your news reader is not adding attribution lines. This is not
a good idea and you should have a look to see if you can fix it.]

James Arnold <ja****@gmail.comwrites:
>I think a study of regular expressions, as implemented in Unix and
Linux, would be instructive here.

I am already familiar with regluar expressions, but I was under the
impression they can't be used to match braces when nested? So if for
example I wanted to do A(A(N)*10)*5, regular expressions wouldn't be
appropriate?
I think the suggestion was only that you could look at REs for how to
write your masks. You are right that REs won't be any good as way of
implementing this. For example, some REs use (abc){3,6} for 3 to 6
repeats of "abc" and you might one day want things like [aeiou] rather
than just A and N indicators.
>It turns into a grammar parsing problem.

I have been looking at Lex/Yacc (well, Flex/Bison) and written a
grammar to handle what I would like. I've compiled it and managed to
get it to output the detected tokens, but it definitely seemed to be
overkill for such a small program.
Agreed. You have at most brackets and a couple of operators. No
need for lex and yacc.
Currently I'm just iterating
through a string and switch()'ing on each character, which covers most
of the functionality I'd like. I figured there must be a way of
tracking nested depth and calling the parse routine recursively for
each matched group?
That's roughly what I'd do. In fact, I'd probably make what you call
the parse routine do the actual generation as well. The parsing will
be so simple that actually storing the parse in some form in probably
not needed.
> After that, my suggestion would be to divide the program into two parts.
The first one would input a string like "AA(AN){10}" and expand it to
something like "AAANANANANANANANANANAN", which is really what you're
looking at.

This is also something I had considered, but I want to be able to use
a range for a specified repetition, e.g. repeat between 5 to 10 times.
This is fine, but if I want to generate 50 different outcomes the full
mask would need to be expanded each time, rather than just the
repeated bit. Surely that is not going to be very efficient? :)
I agree. If you parse and generate on the fly, there is no need for
ether an intermediate mask or a stored parse tree.

--
Ben.
Sep 21 '08 #7

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

28 posts views Thread by David Rubin | last post: by
6 posts views Thread by Ian Gibbons | last post: by
23 posts views Thread by Nascimento | last post: by
20 posts views Thread by bubunia2000 | last post: by
6 posts views Thread by jmanion | last post: by
111 posts views Thread by Tonio Cartonio | last post: by
11 posts views Thread by Jacek Dziedzic | last post: by
reply views Thread by Mitchel Haas | last post: by
1 post views Thread by XIAOLAOHU | last post: by
reply views Thread by leo001 | last post: by
1 post views Thread by ZEDKYRIE | last post: by

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.