1
$\begingroup$

I'm learning BNF, and the text I'm using gives a simple grammar for integer expressions like this:

<expression> ::= <number> | <expression> <operation> <expression>
<operation> ::= + | - | x
<number> ::= <digit> | <digit> <number>
<digit> ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

This makes sense to me, but then it goes on to show that you can have two non-terminal symbols on the left hand side of expression like this:

e,f ::= n | (e o f)
o ::= + | - | x
n ::= d | d n
d ::= 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9

I don't understand what it means to have both e and f on the left hand side: what does it mean and what is the point of it?

Improve this question
$\endgroup$
3
  • $\begingroup$ That seems odd to me, too, but perhaps whoever wrote the textbook has included an explanation. In any event, if you don't mention which textbook it is, you are less likely to find someone who is familiar with it. $\endgroup$
    – rici
    Commented May 13, 2018 at 0:19
  • $\begingroup$ @rici They're from my lecture notes. The explanation given is: "Often non-terminals are used that consist of a single character. Also, to stress that the occurrences of non-terminals represent different terms, we can use indices or will allow us to use more than one non-terminal on the left." $\endgroup$
    – Logan545
    Commented May 13, 2018 at 0:43
  • $\begingroup$ There seem to be some words missing in "or ... will allow" but I think I get the drift. $\endgroup$
    – rici
    Commented May 13, 2018 at 0:51

1 Answer 1

Reset to default
1
$\begingroup$

That seems unorthodox to me, but I'm certainly not current with all the formal language theory textbooks being used these days.

The point is that in

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression\rangle\langle operation\rangle\langle expression \rangle$$

the two instances of $\langle expression\rangle$ on the right-hand side are unrelated to each other. In a derivation, they are derived independently and nothing constrains their derivations. Sometimes we need to refer to them (for example, when we get to semantic analysis) and then it might be convenient to give them different spellings.

I would normally use subscripts:

$$\langle expression\rangle :=\langle number\rangle \;| \;\langle expression_1\rangle\langle operation\rangle\langle expression_2 \rangle$$

but your professor seems to want to be able to say that $e$ and $f$ are aliases for the same non-terminal (but not the same derivation). This seems confusing to me. Is it really so hard to write:

$$e \Rightarrow n \; | \; e_1\; o \; e_2$$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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