66 lines
1.9 KiB
Typst
66 lines
1.9 KiB
Typst
#import "@preview/simplebnf:0.1.1": *
|
|
|
|
= Task 1
|
|
First i split on whitespace, producing lexemes, then I converte these lexemes into tokens, represented as records. Then I evaluate the expression by adding numbers to a stack until get an operator, which is when i pop 2 tokens from the stack, and use those as arguments, and the result is pushed to the stack again. This continues until the list of tokens is empty, and the stack should contain the result.
|
|
|
|
= Task 2
|
|
|
|
You start with an empty expression stack and a list of tokens to be converted into a expression stack. The tokens are popped one at a time until the list of tokens is empty. When a token is popped and is a number, it is added to the expression stack. If the popped token is a operator, two tokens are popped from the expression stack and put as the arguments for the function based on the operator. Any expression may be a number or a operator function with two expressions as arguments.
|
|
|
|
= Task 3 Theory
|
|
== a)
|
|
$ V = {c, o, n, d} $
|
|
|
|
$ S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, +, -, \/, \*} $
|
|
|
|
$ R = {(c, o), (c, n), (n, d n), (o, +), (o, -), (o, \/), (o, \*), (d, 0), (d, 1), (d, 2), (d, 3), (d, 4), (d, 5), (d, 6), (d, 7), (d, 8), (d, 9)} $
|
|
|
|
== b)
|
|
|
|
#bnf(
|
|
Prod(
|
|
$e$,
|
|
annot: $sans("")$,
|
|
{
|
|
Or[$angle.l o angle.r(angle.l e angle.r, angle.l e angle.r)$][]
|
|
Or[$angle.l n angle.r$][]
|
|
},
|
|
),
|
|
Prod(
|
|
$o$,
|
|
annot: $sans("")$,
|
|
{
|
|
Or[plus][]
|
|
Or[minus][]
|
|
Or[multiply][]
|
|
Or[divide][]
|
|
},
|
|
),
|
|
Prod(
|
|
$n$,
|
|
annot: $sans("")$,
|
|
{
|
|
Or[$angle.l d angle.r angle.l n angle.r$][]
|
|
},
|
|
),
|
|
Prod(
|
|
$d$,
|
|
annot: $sans("")$,
|
|
{
|
|
Or[$0$][]
|
|
Or[$1$][]
|
|
Or[$2$][]
|
|
Or[$3$][]
|
|
Or[$4$][]
|
|
Or[$5$][]
|
|
Or[$6$][]
|
|
Or[$7$][]
|
|
Or[$8$][]
|
|
Or[$9$][]
|
|
},
|
|
),
|
|
)
|
|
|
|
== c)
|
|
Both of the grammars are context-free, but only the first one is regular.
|