Arithmetic evaluation: Difference between revisions

=={{header|F_Sharp|F#}}==

Using FsLex and FsYacc from the F# PowerPack, we implement this with multiple source files:

<code>AbstractSyntaxTree.fs</code>:

<lang fsharp>module AbstractSyntaxTree

type Expression =

| Int of int

| Plus of Expression * Expression

| Minus of Expression * Expression

| Times of Expression * Expression

| Divide of Expression * Expression</lang>

<code>Lexer.fsl</code>:

<lang fsharp>{

module Lexer

open Parser // we need the terminal tokens from the Parser

let lexeme = Lexing.LexBuffer<_>.LexemeString

}

let intNum = '-'? ['0'-'9']+

let whitespace = ' ' | '\t'

let newline = '\n' | '\r' '\n'

rule token = parse

| intNum { INT (lexeme lexbuf |> int) }

| '+' { PLUS }

| '-' { MINUS }

| '*' { TIMES }

| '/' { DIVIDE }

| '(' { LPAREN }

| ')' { RPAREN }

| whitespace { token lexbuf }

| newline { lexbuf.EndPos <- lexbuf.EndPos.NextLine; token lexbuf }

| eof { EOF }

| _ { failwithf "unrecognized input: '%s'" <| lexeme lexbuf }</lang>

<code>Parser.fsy</code>:

<lang fsharp>%{

open AbstractSyntaxTree

%}

%start Expr

// terminal tokens

%token <int> INT

%token PLUS MINUS TIMES DIVIDE LPAREN RPAREN

%token EOF

// associativity and precedences

%left PLUS MINUS

%left TIMES DIVIDE

// return type of Expr

%type <Expression> Expr

%%

Expr: INT { Int $1 }

| Expr PLUS Expr { Plus ($1, $3) }

| Expr MINUS Expr { Minus ($1, $3) }

| Expr TIMES Expr { Times ($1, $3) }

| Expr DIVIDE Expr { Divide ($1, $3) }

| LPAREN Expr RPAREN { $2 } </lang>

<code>Program.fs</code>:

<lang fsharp>open AbstractSyntaxTree

open Lexer

open Parser

let parse txt =

txt

|> Lexing.LexBuffer<_>.FromString

|> Parser.Expr Lexer.token

let rec eval = function

| Int i -> i

| Plus (a,b) -> eval a + eval b

| Minus (a,b) -> eval a - eval b

| Times (a,b) -> eval a * eval b

| Divide (a,b) -> eval a / eval b

do

"((11+15)*15)*2-(3)*4*1"

|> parse

|> eval

|> printfn "%d"</lang>