Backus-Naur Form/Reverse Polish Notation

Question 1

Explain why Reverse Polish notation is sometimes used instead of infix notation.

Answer 1

• Removes use of brackets
• Easier for a machine/computer to evaluate
• simpler to code algorithm
• Operators appear in the order required for computation

Question 2

Explain how a stack could be used in the process of evaluating an expression in Reverse Polish notation.

Answer 2

• (Starting at LHS of expression) push values/operands onto stack
• Each time an operator is reached pop top two values off stack and apply operator to them, (Except when the operator is an exponential or unary minus)
• Add result (of applying operator) to stack

Question 3

What is the syntax of a language?

Answer 3

The set of rules that define a valid statement.

Question 4

What is backus-naur form a type of?

Answer 4

It’s a type of meta-language

Question 5

Why do we use meta-languages instead of just regular expressions?

Answer 5

• Regular expressions are lengthy and time consuming to define
• Meta-languages can do this more succinctly (briefly and clearly expressed)

Question 6

What does : := mean in backus-naur form?

Answer 6

it means “is defined by”

Question 7

What is the notation for a statement in backus-naur form?

Answer 7

LHS : := RHS

Question 8

Give the names of each of the components in the following backus-naur form statement:
: := 0|1|2|3|4|5|6|7|8|9

Answer 8

: := 0|1|2|3|4|5|6|7|8|9
is a meta component / syntactic variable
: := and | are meta symbols

Question 9

What is each individual rule called in backus-naur form?

Answer 9

They are called a production

Question 10

Give an example of using recursion in backus-naur form?

Answer 10

: := |

Question 11

What is parsing and how is it achieved?

Answer 11

• Ascertaining whether a given statement is valid

- Done by replacing meta variables with more comprehensible meta variables at each stage.

Question 12

What is a syntax diagram?

Answer 12

• A graphical method of representing the syntax of a language
• Maps directly to BNF

Question 13

What does an oval shape mean in a syntax diagram?

Answer 13

This is a terminal element (so it cannot be broken further broken down)

Question 14

What does an rectangle shape mean in a syntax diagram?

Answer 14

This is a non-terminal element which will be defined in another syntax diagram

Question 15

What does an arrow around the rectangle shape mean in a syntax diagram?

Answer 15

This is a non-terminal element that may be used more than once

Question 16

What is the other name for reverse polish notation?

Answer 16

Postfix notation

Question 17

What is Reverse polish notation?

Answer 17

It is a method of writing arithmetic expressions

Question 18

What are the advantages of using Reverse polish notation?

Answer 18

• It eliminates the need for brackets

- It produces expression in a form suitable for evaluation using a stack

Question 19

What is the normal/human way arithmetic expressions are written?

Answer 19

Arithmetic expressions are usually written in infix notation

Question 20

What is the order of precedence in Reverse Polish Notation?

Answer 20

=
(
\+ - )
*/
^
- (unary minus, as in -3 + 2)

Question 21

How do we know that an expression is in infix notation?

Answer 21

Because the operator is written in between operands (numbers)

Question 22

How do we know that an expression is in postfix notation?

Answer 22

Because the operator is written after the operands (numbers)

Question 23

What are the steps to translate from postfix to infix?

Answer 23

• Scan the expression until you find two operands followed by an operator
• Bracket the next two operands with the operator between them
• Continue writing down operands until you find the next operator, which will operate on the preceding operands

Question 24

What type of expression will traversing an in-order binary tree give?

Answer 24

It will give an algebraic expression in infix format

Question 25

What type of expression will traversing an post-order binary tree give?

Answer 25

It will give an algebraic expression in post format

Question 26

What can bnf be used for?

Answer 26

Can be used to define context free languages

Question 27

What is the definition of a meta language?

Answer 27

A meta language is a language which describes a language