Backus-Naur Form/Reverse Polish Notation Flashcards Preview

Paper 1 - Computer Science > Backus-Naur Form/Reverse Polish Notation > Flashcards

Flashcards in Backus-Naur Form/Reverse Polish Notation Deck (27)
Loading flashcards...
1

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

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

2

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

- (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

What is the syntax of a language?

The set of rules that define a valid statement.

4

What is backus-naur form a type of?

It's a type of meta-language

5

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

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

6

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

it means "is defined by"

7

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

LHS : := RHS

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

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

9

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

They are called a production

10

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

: := |

11

What is parsing and how is it achieved?

- Ascertaining whether a given statement is valid
- Done by replacing meta variables with more comprehensible meta variables at each stage.

12

What is a syntax diagram?

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

13

What does an oval shape mean in a syntax diagram?

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

14

What does an rectangle shape mean in a syntax diagram?

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

15

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

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

16

What is the other name for reverse polish notation?

Postfix notation

17

What is Reverse polish notation?

It is a method of writing arithmetic expressions

18

What are the advantages of using Reverse polish notation?

- It eliminates the need for brackets
- It produces expression in a form suitable for evaluation using a stack

19

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

Arithmetic expressions are usually written in infix notation

20

What is the order of precedence in Reverse Polish Notation?

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

21

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

Because the operator is written in between operands (numbers)

22

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

Because the operator is written after the operands (numbers)

23

What are the steps to translate from postfix to infix?

- 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

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

It will give an algebraic expression in infix format

25

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

It will give an algebraic expression in post format

26

What can bnf be used for?

Can be used to define context free languages

27

What is the definition of a meta language?

A meta language is a language which describes a language