Intro Module
A simple algebraic expressions example to demonstrate the basic concepts of abstract syntax tree, symbolic computation, parsing and prettyprinting.
Table of contents
Types
| Type | Description |
Abstract syntax tree of algebraic expressions. |
Symbolic computation
Functions and values
| Function or value | Description |
Full Usage:
simplify expr
Parameters:
expression
-
The input expression.
Returns: expression
The simplified expression if simplifiable; otherwise the input itself.
|
Simplifies an algebraic expression completely. Completes the work of Intro.simplify1. Recursively simplifies any immediate sub-expressions as much as possible, then applies Intro.simplify1 to the result.
Example
Const 0.
Example
Const 15.
|
Full Usage:
simplify1 expr
Parameters:
expression
-
The input expression.
Returns: expression
The simplified expression if simplifiable; otherwise the input itself.
|
Simplifies an algebraic expression at the first level. This is an example of symbolic computation. It applies the following transformation rules
Example
Const 1.
Example
Mul (Add(Const 0, Const 1), Add(Const 0, Const 0)).
The input is returned unchanged, because even if the rules are applicable to its sub-expressions, they cannot be applied directly to the expression itself. |
Parsing
Functions and values
| Function or value | Description | ||||
Full Usage:
parse_atom i
Parameters:
string list
-
The tokenized string list to be parsed.
Returns: expression * string list
The pair consisting of the parsed expression tree together with any
unparsed input.
|
Parses an atomic expression. Implements the atoms part of the expression's recursive descent parsing: \begin{eqnarray*} atoms & \longrightarrow & (expression) \\ & | & constant \\ & | & variable \end{eqnarray*} An atomic expression is either a constant, a variable or an arbitrary expression enclosed in brackets. See also: Intro.parse_expression; Intro.parse_product.
ExampleParsing of a variable: (Var "x", ["+"; "3"]).
ExampleParsing of a constant: (Const 12, ["+"; "3"]).
ExampleParsing of an expression enclosed in brackets: (Add (Const 12, Const 3), []).
Example
System.Exception: Expected an expression at end of input.
Example
System.Exception: Expected closing bracket.
|
||||
Full Usage:
parse_exp s
Parameters:
string
-
The input string to be parsed.
Returns: expression
The expression corresponding to the input string.
|
Parses a string into an expression. See also: Intro.parse_atom; Intro.parse_product; Intro.parse_expression
Example
Example
System.Exception: Expected an expression at end of input.
Example
System.Exception: Expected closing bracket.
|
||||
Full Usage:
parse_expression i
Parameters:
string list
-
The tokenized string list to be parsed.
Returns: expression * string list
The pair consisting of the parsed expression tree together with any
unparsed input.
|
Parses an expression.
Implements the addition part of the expression's recursive
descent parsing:
\begin{eqnarray*}
expression & \longrightarrow & product \\
& | & product + expression \\
\end{eqnarray*}
An expression is a sequence of 'product expressions' (see Intro.parse_product) separated by
NoteThe grammar is right-associative (\(product + expression \)). So repeated operations that lacks disambiguation are interpreted as right-associative: \(x + y + z = x + (y + z)\) . Example
(Add (Var "x", Const 3), []).
Example
System.Exception: Expected an expression at end of input.
Example
System.Exception: Expected closing bracket.
|
||||
Full Usage:
parse_product i
Parameters:
string list
-
The tokenized string list to be parsed.
Returns: expression * string list
The pair consisting of the parsed expression tree together with any
unparsed input.
|
Parses a product expression.
Implements the products part of the expression's recursive
descent parsing:
\begin{eqnarray*}
product & \longrightarrow & atom \\
& | & atom * product \\
\end{eqnarray*}
A product expression is a sequence of 'atomic expressions' (see Intro.parse_atom) separated by
NoteThe grammar is right-associative (\(atom * product \)). So repeated operations that lacks disambiguation are interpreted as right-associative: \(x * y * z = x * (y * z)\) . ExampleIt parses just the first atom if applied to an addition: (Var "x", ["+"; "3"]).
ExampleIt parses a product completely: (Mul (Var "x", Const 3), []).
ExampleIt parses expressions enclosed in brackets: (Add (Const 12, Const 3), []).
Example
System.Exception: Expected an expression at end of input.
Example
System.Exception: Expected closing bracket.
|
Prettyprinting
Functions and values
| Function or value | Description |
|
Prints to the
Calculates the concrete syntax of an expression
Example
"<<(0 + 1) * (0 + 0)>>" is
written to the stdout.
|
Full Usage:
sprint_exp e
Parameters:
expression
-
The expression to be translated.
Returns: string
The expression's concrete syntax representation.
|
Returns the concrete syntax representation of an expression.
Returns a string of the concrete syntax of an expression
Example
"<<(0 + 1) * (0 + 0)>>"
|
Full Usage:
string_of_exp pr e
Parameters:
int
-
The precedence level of the operator of which the expression is an immediate sub-expression .
e : expression
-
The expression to be translated.
Returns: string
The expression's concrete syntax representation with
additional brackets based on pr.
|
Returns a concrete syntax representation of an expression considering the precedence level of the operator of which the expression is an immediate sub-expression. It is an auxiliary function used to define Intro.sprint_exp and Intro.print_exp. and to calculate whether or not additional brackets can be omitted. The allocated precedences are as follows:
Example
"x + 1"
Example
"(x + 1)"
|
Full Usage:
string_of_exp_naive e
Parameters:
expression
-
The expression to be translated.
Returns: string
The expression's concrete syntax representation.
|
Returns a naive concrete syntax representation of an expression. Reverses transformation, from abstract to concrete syntax keeping brackets. This is a naive version that puts brackets uniformly round each instance of a binary operator, which is perfectly correct but sometimes looks cumbersome to a human. Seealso: Intro.sprint_exp; Intro.print_exp; for clever versions.
Example
"((0 + 1) * (0 + 0))"
|