BNF (Backus-Naur form) & Syntax Diagrams (3.7.d)
BNF is used to define the syntax of any programming language.
::= means is defined as and
| means or.
<DIGIT> ::= 0|1|2|3|4|5|6|7|8|9 means that a digit is defined as 0 or 1 or 2 or (etc.). Below is the same syntax in a syntax diagram:
The first diagram below means that exactly one foo is required. The second diagram means that at least one foo is required. The third diagram means that a foo is optional.
Reverse Polish Notation (3.7.e, 3.7.f)
Reverse polish notation is where operands (e.g.
2 3) are written before their operators (e.g.
2+3 would become
23+ in reverse polish notation. Where brackets are used, "do" the brackets first. For example,
2*(AB+), which then becomes
2AB+*. Brackets are never needed because there is no question about the order of operations.
To convert from a binary tree to "normal" algebra, simply transverse the tree (see Data Structures / Trees for more information).