Recall Cambridge Polish Notation $($CPN$),$ in which operators and their operands are enclosed in parenthesis.

For example, $($add $12)$ is the CPN equivalent of $1+2.$

Expressions in CPN can be nested, so the following expression would be valid, and would result in $6.$

$($add $1($add $23))$

Your must create a functioning CPN calculator which works with the functions listed in the FUNC$\_$TYPE enum in the provided code through the MIN$\_$FUNC function $($all functions appearing after MIN$\_$FUNC in the enum will be implemented in later tasks.

This calculator will serve as the core functionality for CI$-$LISP.

You may want to check out the sample runs below better understand what will be implemented before reading further.

The initial grammar is as follows:

program ::$=$ s$\_$expr EOL $|$ s$\_$expr EOFT $|$ EOL $|$ EOFT

s$\_$expr ::$=$ f$\_$expr $|$ number $|$ QUIT

f$\_$expr ::$=($ FUNC s$\_$expr$\_$section $)$

s$\_$expr$\_$section ::$=$ s$\_$expr$\_$list $|$

s$\_$expr$\_$list ::$=$ s$\_$expr $|$ s$\_$expr s$\_$expr$\_$list

FUNC ::$=$ neg $|$ abs $|$ add $|$ sub $|$

mult $|$ div $|$ remainder $|$ exp $|$

exp$2|$ pow $|$ log $|$ sqrt $|$

cbrt $|$ hypot $|$ max $|$ min

number ::$=$ INT $|$ DOUBLE

INT ::$=$ optional $+/-,$

then some digits

DOUBLE ::$=$ optional $+/-,$

then some digits,

then a decimal point,

then optionally some more digits

QUIT ::$=$ quit

The non$-$terminals s$\_$expr and f$\_$expr are shorthand:

s$\_$expr means symbolic expression

f$\_$expr means function expression

LEXING

First, it is necessary to define all tokens and all non$-$terminals within the grammar. tokens $($and non$-$terminals, called types by yacc$),$ will be defined in cilisp.y in the definitions section. The provided token and type definitions are:

$\%$union $\{$

double dval;

int ival;

struct ast$\_$node $*$astNode;

$\}$;

$\%$token FUNC

$\%$token INT

$\%$token QUIT EOL EOFT

$\%$type s$\_$expr

Clearly, this is incomplete; you should know from the previous labs how to complete this definitions section, and we will not discuss it further here $($but as always, questions are welcome$).$

The union contains all types that tokens and types will have. In this case, token and type values will all be stored as double, int or ast$\_$node $*.$

The tokens defined by the yacc file must be lexed. As we know, the lex file is used to configure a lexer.

The provided cilisp.l is barely started. It has rules to tokenize and return some tokens, but not all of them. You must complete it$.$

Pay attention to the llog calls made for debugging purposes each time a token is created. Just like in the lab, these calls print to a log file src$/$bison$-$flex$-$outputs$/$flex$\_$bison$\_$log$.$ Every rule in cilisp.l should include an llog call.

PARSING

The goal of the parser is to construct an abstract syntax tree after tokenization. Most of the productions in your grammar will have an equivalent production in cilisp.y$,$ which is the configuration file for the parser.

The first set of productions in cilisp.y are for parsing programs, which serve as an entry point. The productions are provided, and should be changed cautiously if at all. Productions for s$\_$expr ::$=$ error and s$\_$expr ::$=$ QUIT are also provided.

program:

s$\_$expr EOL $\{$

ylog$($program$,$ s$\_$expr EOL$)$;

if $($$$1)\{$

printRetVal$($eval$($$$1))$;

freeNode$($$$1)$;

$\}$

YYACCEPT;

$\}$

$|$ s$\_$expr EOFT $\{$

ylog$($program$,$ s$\_$expr EOFT$)$;

if $($$$1)\{$

printRetVal$($eval$($$$1))$;

freeNode$($$$1)$;

$\}$

exit$($EXIT$\_$SUCCESS$)$;

$\}$

$|$ EOL $\{$

ylog$($program$,$ EOL$)$;

YYACCEPT; $//$ paranoic; main skips blank lines

$\}$

$|$ EOFT $\{$

ylog$($program$,$ EOFT$)$;

exit$($EXIT$\_$SUCCESS$)$;

$\}$;

s$\_$expr:

QUIT $\{$

ylog$($s$\_$expr, QUIT$)$;

exit$($EXIT$\_$SUCCESS$)$;

$\}$

$|$ error $\{$

ylog$($s$\_$expr, error$)$;

yyerror$("$unexpected token"$)$;

$$ $=$ NULL;

$\}$;

Note that every production has a ylog call; this function, like llog, prints to the log file stating what lexing and parsing steps are taken. Every production that you add should include a ylog file, as well, as the log will be a crucial tool in debugging the lexer and parser.

The rest of the yacc file is up to you.

The figure below $($which can be found here$)$ may help you visualize what needs to be done. Note that some reductions in the grammar are not illustrated in the figure.

figure$\_$t$1$

You are strongly encouraged to illustrate prouductions like this as you go through the project, and to occasionally draw out entire syntax trees for test inputs.

Many of these productions will need to call the functions declared at the bottom of cilisp.h:

AST$\_$NODE $*$createNumberNode$($double value, NUM$\_$TYPE type$)$;

AST$\_$NODE $*$createFunctionNode$($FUNC$\_$TYPE func, AST$\_$NODE $*$opList$)$;

AST$\_$NODE $*$addExpressionToList$($AST$\_$NODE $*$newExpr$,$ AST$\_$NODE $*$exprList$)$;

These functions are defined in cilisp.c; some of their definitions are partially completed already.

Whenever a function or value needs to be accessible by the lexer or parser, it mus