1
$\begingroup$

I'm pretty new to CFG, and I've tried out some samples as well. As of now I'm trying this for-loop to write it in CFG using BNF:

Start{
    int z = 20;
    for(int b = 0; b < 5; b++)  
    {
        //some statement
    }
}

Attempted BNF:

<program> ::= Start <blockstatements>
<blockstatements> ::= <statement> | <statement>; | <statement_list> | <empty>
<statement> ::= <typespecification> <varDeclaration> <assignment-operator> <expression> 
<typespecification> ::= char | short | int | long | float | double | string
<varDeclaration> ::= a | b | c | d | e | f | g | h | i | j | k | l | m | n | o | p | q | r | s | t | u | v | x | y | z
<assignment-operator> ::= =
<expression> ::= <value> 
<value> ::= <digit> | <letter> | <number> | <word> 
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
<letter> ::= "A" | "B" | "C" | "D" | "E" | "F" | "G" | "H" | "I" | "J" | "K" | "L" | "M" | "N" | "O" | "P" | "Q" | "R" | "S" | 
            "T" | "U" | "V" | "W" | "X" | "Y" | "Z" | "a" | "b" | "c" | "d" | "e" | "f" | "g" | "h" | "i" | "j" | "k" | "l" | 
            "m" | "n" | "o" | "p" | "q" | "r" | "s" | "t" | "u" | "v" | "w" | "x" | "y" | "z"
<number> ::= <digit> + <digit> | <digit> - <digit> | <digit> * <digit> | <digit> / <digit>

The above CFG isn't complete and I wanted to make sure that I'm doing it correctly. Am I heading towards the right path? Should it be written as above or have I missed anything?

Any help could be appreciated.

$\endgroup$
4
  • 2
    $\begingroup$ Your context-free grammar generates many more strings than your example. Conversely, your particular example, as a language, is regular (since it contains only one string). I suspect that you want a context-free grammar for a certain language, and the string you gave is just an example. $\endgroup$ – Yuval Filmus Aug 1 '17 at 9:11
  • $\begingroup$ @YuvalFilmus Thank you for the quick response. So when I'm writing a context-free-grammar I don't have to check for error handling? I thought it should be done within CFG, and hence I included those extra strings above. $\endgroup$ – Kulasangar Aug 1 '17 at 11:06
  • 2
    $\begingroup$ I'm not sure what error handling has to do with anything. My point was that you describe your problem as writing a context-free grammar for a particular string (i.e., for the language containing only that string), which is probably not what you meant. $\endgroup$ – Yuval Filmus Aug 1 '17 at 12:00
  • $\begingroup$ @YuvalFilmus Noted. :) $\endgroup$ – Kulasangar Aug 1 '17 at 18:21
3
$\begingroup$

I've usually seen it expressed as something like:

forExpression ::= for ( <declExpression> <expression>; <expression> ) <blockStatement>

blockStatement ::= <statement> |  { <statementlist> }

statement ::= <declExpression> | <forExpression> | <ifExpression> | ...

<declExpression> includes the semi colon

You want to be very careful of the details like where you define where things like the semi colon are required,

In your <number> you don't have any priorities set up, there is also no option for parenthesis, ...

Creating a good CFG is hard which is why so many languages start out as a dialect of C and just take that grammar and adapt it.

$\endgroup$
1
  • $\begingroup$ Thank you for the heads-up! I'll try it out and come back. :) $\endgroup$ – Kulasangar Aug 1 '17 at 11:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.