1
$\begingroup$

I'm studying programming language design, and I've been taught the grammar below which lets you write basic math expressions.

Exp ::= Num | Exp Op Exp
Op ::= + | - | * | Div
Num ::= Digit | Digit Num
Digit ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 

According to the lecturer things like 1 - (2 -3) are not valid as it can't generate expressions with brackets and it can't do -1 because it can't start with -1.

While I understand the first one, the second is a little harder to understand.

Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

$\endgroup$
0
$\begingroup$

With Num you can only generate digits, so the only choice left is (starting with Exp) to produce Exp Op Exp. However, Exp and Op must both produce at least one symbol each (i.e., producing the empty word is not allowed). Hence, even if you replace Op with -, you get Exp - 1 and Exp must produce another valid expression (or number), so you cannot get -1 on its own.

Also could you show me how I could modify the above grammar to add the ability to group operations, and start with a -1?

There are several ways of doing so. Check out, for instance, how Java does it (the "Expression3" there is roughly equivalent to your Exp).

Finally, I'm told that a grammar is a set of symbols, rules, and an initial symbol? But I'm struggling to find more info on what an initial symbol is/should be.

The initial symbol is an arbitrary non-terminal symbol. Read more here on what terminal and non-terminal symbols are.

$\endgroup$
  • $\begingroup$ Great! Thank you. I think I've got the hang of it. $\endgroup$ – Shiny_and_Chrome Apr 18 at 15:39

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.