views:

49

answers:

1

A good exercise while learning programming, is to write a calculator. To do this, I created some kind of DSL in BNF and want to ask for your help to improve it. With this minilanguage you should be able to add, multiply and assign values and expressions to names (a.k.a. create variables and functions).

Hava a look at the BNF first:

<Program>     ::= <Line>(<NewLine><Line>)*
<Line>        ::= {"("}<Expression>{")"}|<Assignment>
<Assignment>  ::= <Identifier>"="<Expression>
<Identifier>  ::= <Name>{"("<Name>(","<Name>)*")"}
<Expression>  ::= <Summand>(("+"|"-")<Summand>)*
<Summand>     ::= <Factor>(("*"|"/")<Factor>)*
<Factor>      ::= <Number>|<Call>
<Call>        ::= <Name> {"("<Expression>(","<Expression>)*")"}
<Name>        ::= <Letter>(<Letter>|<Digit>)*
<Number>      ::= {"+"|"-"}(<Digit>|<DigitNoZero><Digit>+)
<Digit>       ::= "0"|<DigitNoZero>
<DigitNoZero> ::= "1"|"2"|"3"|"4"|"5"|"6"|"7"|"8"|"9"
<Letter>      ::= [a-zA-Z]
<NewLine>     ::= "\n"|"\r"|"\r\n"

As you can see, this BNF treats no Whitespace beside NewLine. Before the parsing begins I plan to remove all whitespace (beside NewLine of course) from the string to parse. It is not nessesary for the parser anyway.

There are 4 things, that might lead to problems when using this language as defined right now and I hope you can help me figure out appropriate solutions:

  1. I tried to follow the top-down approach, while generating this gramar, but there is a circle between <Expression>, <Summand>, <Factor> and <Call>.
  2. The gramar treats variables and functions exactly the same way. Most programming languages make a difference. Is it nessesary to differentiate here?
  3. There are maybe some things that I don't know about programming, BNF, whatever, that will kill me later, while trying to implement the BNF. But you might be able to spot that before I start.
  4. There might be simple and stupid mistakes that I could not find myself. Sorry in that case. I hope there are none of these mistakes anymore.

Using hand and brain I could successfully parse the following test cases:

"3"
"-3"
"3-3"
"a=3"
"a=3+b"
"a=3+b\nc=a+3"
"a(b,c)=b*c\ra(1+2,2*3)"

Please help to improve the BNF, that it can be used to successfully write a calculator.

edit: This BNF is really not finished. It does not treat the cases "2+-3" (should fail, but doesn't) and "2+(-3)" (should not fail, but does) correctly.

+1  A: 

The gramar treats variables and functions exactly the same way. Most programming languages make a difference. Is it nessesary to differentiate here?

Being able to treat the result of a function invocation exactly the same as a local variable or a constant expression is precisely the point of defining (mathematical) functions in the first place. I can't imagine the use of a grammar that allowed functions but didn't treat

1 + 1

exactly the same as

1 + a

or

1 + sin(x)
AakashM