Backus-Naur Form/Reverse Polish Notation Flashcards

1
Q

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

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

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

A
• (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
3
Q

What is the syntax of a language?

A

The set of rules that define a valid statement.

4
Q

What is backus-naur form a type of?

A

It’s a type of meta-language

5
Q

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

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

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

A

it means “is defined by”

7
Q

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

A

LHS : := RHS

8
Q

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

A

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

9
Q

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

A

They are called a production

10
Q

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

A

: := |

11
Q

What is parsing and how is it achieved?

A
• Ascertaining whether a given statement is valid

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

12
Q

What is a syntax diagram?

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

What does an oval shape mean in a syntax diagram?

A

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

14
Q

What does an rectangle shape mean in a syntax diagram?

A

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

15
Q

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

A

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

16
Q

What is the other name for reverse polish notation?

A

Postfix notation

17
Q

What is Reverse polish notation?

A

It is a method of writing arithmetic expressions

18
Q

What are the advantages of using Reverse polish notation?

A
• It eliminates the need for brackets

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

19
Q

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

A

Arithmetic expressions are usually written in infix notation

20
Q

What is the order of precedence in Reverse Polish Notation?

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

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

A

Because the operator is written in between operands (numbers)

22
Q

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

A

Because the operator is written after the operands (numbers)

23
Q

What are the steps to translate from postfix to infix?

A
• 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
24
Q

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

A

It will give an algebraic expression in infix format

25
Q

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

A

It will give an algebraic expression in post format

26
Q

What can bnf be used for?

A

Can be used to define context free languages

27
Q

What is the definition of a meta language?

A

A meta language is a language which describes a language