Member Avatar for techno_weenie

I need to parse a file line by line and check if the line is in a valid BNF format and print it out if it is.

Below is my BNF grammar:
<line> ::= <program names><spaces><uids><spaces><dest IPs><spaces><ports>
<spaces> ::= <blank character> | <blank character><spaces>
<blank character> ::= ' ' | '\t'
<uids> ::= '*' | <alnumstring seq>
<alnumstring seq> ::= <alnumstring> | <alnumstring>','<alnumstring seq> | <alnumstring>','<spaces><alnumstring seq>
<program names> ::= '*' | <prog name seq>
<prog name seq> ::= <progstring> | <progstring>','<prog name seq> | <progstring>','<spaces><prog name seq>
<dest IPs> ::= '*' | <IP address seq>
<IP address seq> ::= <dest IP> | <dest IP>','<spaces><IP address seq> | <dest IP>','<IP address seq>
<dest ports> ::= '*' | <dest port seq>
<dest port seq> ::= <destination port> | <destination port>','<spaces><dest port seq> | <destination port>','<dest port seq>

Example of Valid Sentences:
/usr/bin/firefox * * 80, 443, 8080
/usr/bin/ssh * 147.188.195.15, 147.188.193.15, 147.188.193.16 22


I understand the structure of the BNF grammar however i'm unsure of how to put this into C code.

Would it be possible for somebody to give me a simple example of how to do this in c e.g.

<sentences> ::= <words><Punctuation>|<words><Punctuation><sentences>|<sentences><sentences>
<words> ::= <word> | <word><space><words>
<word> ::= <characters a-z>
<space> ::= ' '
<Punctuation> ::= <,>|<.>|<;>| etc...

testsentences = "Thank you for your help, I appreciate it."

Thanks,
Techno_weenie

  • 3 Contributors
  • 4 Replies
  • 130 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by IsharaComix
Member Avatar for IsharaComix

Well, this was probably a bad idea, but I went ahead and wrote you that example you asked for because I thought it would be fun. Needless to say, it's particularly trivial compared to what you're trying to do, but hopefully you can see the thought process that went behind it.

Basically, making the program for a grammar is about the same as making the grammar itself. You just need a way to validate each piece. Be sure to save your state before taking a branch, just in case that path failed. It's all just a big, tiered recursive process.

Play around with my example, see how it does its job, and especially note what happens at the recursive calls and at the base cases of the code. If there are any errors in it, don't blame me. I wrote it in 30 minutes at 22:30 the night before an exam.

Remember, the only reason I wrote this was because your problem was so interesting. Don't go thinking I do it for anyone who just asks for it. ;)

/*
   Simple BNF Grammar Example
   Written by Ishara Comix
   http://isharacomix.com
   
   I, the copyright holder of this work, hereby release it into the public 
   domain. This applies worldwide.

   In case this is not legally possible: I grant anyone the right to use this
   work for any purpose, without any conditions, unless such conditions are
   required by law.
*/

#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <ctype.h>

/* Function definitions. */
char *is_sentences( char *s );
char *is_words( char *s );
char *is_word( char *s );
char *is_punctuation( char *s );

/* Main method - driver. */
int main( int argc, char **argv )
{
    if ( argc < 2 )
    {
        printf("Usage: ./bnf \"<Sentences>\"\n");
        return EXIT_FAILURE;
    }
    
    /* The entire program is checking if our input is a sentences. */
    if ( is_sentences( argv[1] ) )
    {
        printf("Valid sentence.\n");
        return EXIT_SUCCESS;        /* Zero means success. */
    }
    else
    {
        printf("Invalid sentence.\n");
        return EXIT_FAILURE;
    }
}


/* Check to see if the string is a valid 'sentences'
   I'm going to add the null byte to the definition of a sentences, to make
   life easier on myself.
   <sentences> ::= <words><punctuation>'\0'|
                   <words><punctuation><space><sentences> */
char *is_sentences( char *s )
{
    char *r1, *r2, *r3;     /* Report variables. */
    
    /* We recursively evaluate the string, passing back the pointer after each
       call. */
    r1 = is_words( s );
    if ( r1 )
    {
        r2 = is_punctuation( r1 );
        if ( r2 )
        {
            /* First we check the null byte. */
            if ( *r2 == 0 )
                return r2;
            
            /* Either it's a sentences or it isn't. */
            else
            {
                /* I needed to add this for pedantic reasons. */
                if ( *r2 == ' ' )
                    r2++;
                else
                    return NULL;
                
                /* Now we recursively check the rest of the string. */
                r3 = is_sentences( r2 );
                if ( r3 )
                    return r3;
                else
                    return NULL;
            }
        }
    }
    return NULL;
}


/* Check to see if the string is a valid 'words'
   <words> ::= <word> | <word><space><words> */
char *is_words( char *s )
{
    char *r1, *r2, *r3;         /* Report variable. */
    
    /* You'll start to see a pattern with this as you go down the list. */
    r1 = is_word( s );
    if ( r1 )
    {
        r2 = ( *r1 == ' ' ) ? r1+1 : NULL;  /* is_space - note that here,
                                               at a root element, we increment
                                               the pointer if it's true. */
        if ( r2 )
        {
            r3 = is_words( r2 );
            if ( r3 )
                return r3;
            else
                return NULL;
        }
        else
            return r1;
    }
    
    return NULL;
}


/* Check to see if the string is a valid 'word'
   <word> ::= <character a-z>|<character a-z><characters a-z>
   I'm going to cheat here and return the pointer after the last legal
   character. In a real situation, you might need to go through the whole
   song and dance. */
char *is_word( char *s )
{
    if ( !isalpha(*s) )
        return NULL;
    
    /* Remember, for a root element, you return one past. */
    while ( isalpha(*s) )
        s++;
    return s;
}


/* Check to see if the string is a valid 'punctuation'
   <punctuation> ::= '.'|','|'!'  (just for my purposes) */
char *is_punctuation( char *s )
{
    if ( *s == '.' || *s == ',' || *s == '!' )
        return s+1;
    else
        return NULL;
}
Member Avatar for jephthah

Well, this was probably a bad idea,

yeah.... it's unfair to the newbie poster to be handed such a lovingly polished solution, and it's unfair to the rest of us here who strive to teach students how to do their own work without handing it to them.

it'd be one thing if he were a professional trying to solve a difficult problem. but the rule here is "We Don't Do Your Homework". it's kind of hidden up at the top of every forum as a sticky.


but, i will say, your code is very nice.

.

Edited by jephthah because: n/a
Member Avatar for techno_weenie

Thank you IsharaComix this will be very useful for me to understand how to process the BNF grammar and I hope your exam went well.

Jephthah the "bad idea" was probably taking the time to help somebody out before an exam when they could have been looking over notes before the exam. I agree with your comment, thats why I haven't actually just given a link to the whole assignment. Instead i've asked if somebody could help me with a simple problem i've made up based on a section i'm suck on. Then hopefully I can work out how to do what I really need. As too be honest I hate being asked to do something I've never seen before in my life and expected to complete it just like that, I learn things from experience and knowledge of similar questions/methods thats just me.

Edited by techno_weenie because: n/a
Member Avatar for IsharaComix

Just because the OP condones my bad behavior does not make it all right. :(

I figured there was no harm in taking the time to punch out a toy example. It's always been my experience that being able to look at and play with working code really helps drive the concepts home more than anything else. If that's what happened for you, then it was well worth the effort.

@jephthah:
I've read the links before, but they seem to speak a lot more clearly now that I've actually joined the site and seen what they're talking about firsthand. I'll be sure to use more discretion (and be more conservative) with my responses in the future. Thanks for calling me out on it - I'm new at this.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.