OCR Computing A-Level Revision

Defining Syntax

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.

For example, <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. +). So, 2+3 would become 23+ in reverse polish notation. Where brackets are used, "do" the brackets first. For example, 2*(A+B) becomes 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).