Languages
Natural languages
- We use natural languages to communicate with each other.
- Syntax and grammar rules determine valid word order.
- Semantics determine what a group of words ‘means’.
- Syntax can be fine, but the semantics can be bad.
- The petrol ate the car
- One statement could be ambiguous—have multiple meanings
- Bath the dog wearing an apron.
Formal Languages
-
Formal languages are much more carefully defined than a natural language.
-
As a result, ambiguity is not possible.
-
Some formal languages include:
- Chemical formulae
- Maths
- Programming languages
Reverse Polish Notation (RPN)
Infix Notation
- When we look at mathematical expression the operands are placed on either side of the operator.
- 3+4
- The operand being the data we want to use and the operator being what we want to do with it
- This is infix notation
- The problem is that we often need brackets to alter the order of operations.
- (5+7) x 3
RPN
-
Polish mathematician Jan Łukasiewicz devised a way to represent mathematical expressions so that we don’t need to use brackets
-
This uses postfix notation so the operator is shown after the items we need to operate on
- 3 4 +
-
The result of an operation replaces the items that caused it to happen in the expression.
- 5 7 + 3 x ⇒ 12 3 x ⇒ 36
-
Representing calculations in reverse polish makes it easier for machines to interpret.
-
In particular, calculations express in RPN take less steps to process on a computer.
-
To perform an RPN calculation, we use a stack.
RPN and the Stack
-
Here’s an infix notation:
- 5 x ( 1 + 2)
-
Represented as RPN it looks like
- 1 2 + 5 x
-
In operation
- Push 1 and 2
- Pop 2, 1 and add.
- Push 3 (result of add)
- Pop 3,5 and multiply.
- Push 15 (result of multiply)
-
Stack now contains the result
RPN as a Tree
- You can also represent RPN as a tree.
- The tree can be reversed post order with each calculation replacing the operator.
Regular Expressions
- A regular expression provides a way to define sequences of characters
- The regular expression can then be used to pattern match
- To find examples in a bigger body of characters
- To determine if an input matches an allowed pattern
- The regular expression defines the whole set