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