Not Backus-Naur Form

Factual Questions
1

When I was in college studying computer science 38 years ago, we learned about a form of mathematical notation called Backus-Naur Form (or Backus Normal Form, or as we students called it, Backwards is Normal Form). In BNF, so we were taught, the operator follows the operands. For example, instead of writing…

(5 + 7) * 3 - 6

…in BNF one would write…

5 7 + 3 * 6 -

I just looked at the Wikipedia entry on Backus-Naur Form, and it has nothing to do with arithmetic notation. It says that BNF is a grammar for describing the syntax of a programming language.

If this is the case, either the definition has changed, or (more likely) my memory is flaky. In either case, there must be a name for the alternate arithmetic notation that I remembered as BNF. What is it?

2

Reverse Polish.

3

BNF is, in fact, a language grammar description notation.

You’re thinking of RPN (Reverse Polish Notation), like high-end HP calculators.

4

I normally hear that referred to as “reverse Polish notation”.

5

You could also call it ‘post-fix’ notation, as opposed to ‘in-fix’ or ‘pre-fix’ notation.

6

All the cool kids had RPN-calculators when I studied engineering 20 years ago.

7

Yes, you’ve confused BNF for RPN.

Maybe because a common computer science exercise is to make a RPN calculator in a stack-based language like Forth, which would be described with BNF.

8

I’ve had my HP 11C for 30 years! Damn, I hadn’t thought about when I bought that thing in a while.

I was SA to the head of the math department, she looked sideways at us geeks with RPN calculators, she was a TI fan. So she’d make up complex (only algebra level stuff) equations and we’d race, her TI vs my HP. And I could beat her about half the time.

Are RPN calculators still popular with geeks in school these days?

9

I’ve had my HP-35 for over forty years. It hasn’t worked in decades though. It might just be the (non standard) batteries but I’ve never bothered to try to replace them.

RPN is the only way to go! I hate using non-RPN calculators.

–Mark

10

I was in college studying computer science 38 years ago and your memory just committed a hardware fault. :wink:

11

Yoda speaks in RPN.

12

Since others have given the correct name, here’s a video on the topic.

“Polish” notation is basically, “we can’t pronounce the name of the guy who popularized this but he was Polish” notation.

13

You mean “In RPN Yoda speaks”.

–Mark

14

Indeed, Jan Łukasiewicz.

Commonly held misconception: RPN is precisely what Łukasiewicz invented. Łukasiewicz invented PN, a prefix-oriented notation in which operation symbols precede operands. So that “(5 − 6) × 7” in conventional infix algebraic notations becomes “× − 5 6 7” in classic Łukasiewicz.

RPN, Reverse Polish, is a postfix notation. In this, you state operations after operands, like “5 6 - 7 ×”. RPN is nice because it’s easy to implement in a simple stack-oriented calculator: push operands on the stack as they occur in the input symbol stream, pop operands to process when encountering an operator. Push results back on the stack. In non-reversed, you push operations and manipulate operands out-of-stack, and requires a bit of “look-ahead” in the input stream (in other words, if an operation is binary, you have to know the two operands in the input stream). In RPN, the state of the calculation is completely held in the stack and the stream position. Simplicity.

But no, not Backus-Naur Form at all. The only things the two have in common are they’re both TLAs and they both occur in computer science subjects, albeit in slightly different spheres.

15

The two would be taught nearly side-by-side in a classic compiler course. The syntax of expressions (and whole programming languages) would be given in BNF. Using a BNF parser, you could then generate the expression in RPN, which in turn can be converted into assembly language.

So both are involved in different stages of the process.

Once stuff like yacc came along, this became much easier. (Then came Bison which in turn inspired the name GNU, if you wanted to know where that came from.)

16

The same process is the computation model for PostScript and JVM bytecode. Just gigantic stack machines.

17

I don’t think so. The GNU project started in 1983. Bison was written in 1988.

–Mark

18

Just to set record straight, algebraic is best for a product (an already given formula), while RPN is best for a process. As an example, consider the equation F = (m_1m_2)/d^2. On an algebraic calculator, you put in (m_1m_2)/rr=. On an HP, you think of a process, take m_1 and m_2 and multiply them. Then take r and square it. Then divide.

FWIW, I find an algebraic calculator a royal PITA.

When we were in elementary, we used something that might be called VPN (vertical Polish notation):
2
2
+

4

Backus-Naur is a formal syntax for describing programming languages. I find it unreadable.

19

Huh, I had an RPN calculator when I was studying physics and computer science in the late 1970s, back when HP first starting making them. They were ***ultra ***cool. I had an HP 29C, which was… wait for it… programmable.

I still love RPN calculators today. I found a great one for my android phone - so good that I even paid for it, even though there are so many free calculator apps around. RealCalc (I’m not affiliated with them.)

20

I know I learned it in 1974 when I took compilers in grad school, and I suspect I learned it a few years before that.

I’ve also seen BNF defined as Backus Normal Form, though I’ve seen Backus Naur Form also.