# Backus-Naur Form/Reverse Polish Notation Flashcards

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

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

What is the syntax of a language?

The set of rules that define a valid statement.

What is backus-naur form a type of?

It’s a type of meta-language

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)

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

it means “is defined by”

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

LHS : := RHS

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

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

They are called a production

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

: := |

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.

What is a syntax diagram?

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

What does an oval shape mean in a syntax diagram?

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

What does an rectangle shape mean in a syntax diagram?

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

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