% $Id: language-definition.tex,v 1.24 2023/11/11 18:15:50 leavens Exp $
\documentclass[11pt]{article}
\input{macros}
\newcommand{\BP}{\textsf{BP}}
\newcommand{\SP}{\textsf{SP}}
\newcommand{\PC}{\textsf{PC}}
\newcommand{\IR}{\textit{IR}}
\newcommand{\STACKNAME}{\textrm{stack}}
\newcommand{\STACK}[1]{\ensuremath{\STACKNAME[#1]}}
\newcommand{\AND}{\ensuremath{\:\wedge\:}}
\newcommand{\GETS}{\ensuremath{\leftarrow}}
\newcommand{\IFO}[2]{\textrm{\textbf{if} \ensuremath{#1} \textbf{then}
    \{\ensuremath{#2}\} }}
\newcommand{\IF}[3]{\textrm{\textbf{if} #1 \textbf{then} #2 \textbf{else} #3}}
\newcommand{\EQUALS}{\ensuremath{=}} % or {\ensuremath{\:\texttt{==}\:}}
%
\bibliographystyle{abbrv}
\title{FLOAT Language Manual}
\author{Gary T. Leavens}
\date{\today}
\begin{document}
\noindent
\maketitle
%
\begin{abstract}
This document defines the Fancy Language Offering Arithmetic Terms
(FLOAT).
This language is intended as a simple demonstration of some compiler
techniques (for COP 3402 at UCF).
\end{abstract}

\section{Overview}

The FLOAT compiler operates as command-line program.
The following subsections specify the interface between the Unix
operating system and the compiler.

\subsection{Inputs and Outputs}

The compiler takes a single command line argument specifying the name
of a program in the FLOAT language.
For example, if the file name argument is \texttt{test.flt}
(and both the compiler executable, \texttt{./float},
and the file \texttt{test.flt} are in the current directory),
then the following command line (given to the Unix shell)
\begin{lstlisting}
       ./float -u test.flt
\end{lstlisting}
will run the compiler on the program in \texttt{test.flt},
print the program's AST on standard output,
with any error messages to standard error output.

There are two optional command line arguments, both of which must
appear before the file name on the command line calling the program.

The \texttt{-l} option requests that the compiler
prints a table of tokens read (on stdout), and then stops.
Thus the compiler only performs lexical analysis on the input.
This is useful in debugging the compiler's lexical analysis phase.

The \texttt{-u} option requests that the compiler parse the program
and unparse the resulting AST, with output (onto stdout), and then the
compiler stops (before generating any code).
This is useful for debugging (the parser or) the syntax of a program.

\section{FLOAT language}

\label{sec:FLOAT}
This section defines the FLOAT language.

\subsection{Syntax}

The lexical grammar of FLOAT is defined in
\figref{fig:lexical-grammar},
and its context-free grammar for FLOAT is defined in \figref{fig:cf-grammar}.

There is an interesting lexical issue regarding the lexical analysis
of numeric literals (\nonterm{number} in \figref{fig:lexical-grammar}).
The lexical grammar allows an optional sign,
either plus (\texttt{+}) or minus (\texttt{-},
before the first digit of a numeric literal.
Since the lexer favors the longest match, an expression like:

\begin{lstlisting}
   3-4-5
\end{lstlisting}

\noindent
has 3 tokens (\texttt{3}, \texttt{-4}, and \texttt{-5}) and no
operators, so it will lead to a parse error.

If subtraction is desired, then a minus sign must be separated from
the any following number numbers by whitespace, as in:

\begin{lstlisting}
   3 - 4 - 5
\end{lstlisting}

\noindent
which has 5 tokens (\texttt{3}, \texttt{-}, \texttt{4}, \texttt{-},
and \texttt{5}) and will be parsed as an expression.

\begin{figure}
\begin{grammar}
\nonterm{ident} \: \nonterm{letter} \arbno{\nonterm{letter-or-digit}}
\nonterm{letter} \: \_ \| a \| b \| $\ldots$ \| y \| z \| A \| B \| $\ldots$ \| Y \| Z
\nonterm{letter-or-digit} \: \nonterm{letter} \| \nonterm{digit}
\nonterm{number} \: \nonterm{sign} \nonterm{digit} \arbno{\nonterm{digit}} \nonterm{dotted-digits} \nonterm{exponent}
\nonterm{sign} \: + \| - \| \nonterm{empty}
\nonterm{digit} \: 0 \| 1 \| 2 \| 3 \| 4 \| 5 \| 6 \| 7 \| 8 \| 9
\nonterm{dotted-digits} \: . \arbno{\nonterm{digit}} | \nonterm{empty}
\nonterm{exponent} \: \nonterm{exponent-marker} \nonterm{sign} \nonterm{digit} \arbno{\nonterm{digit}} \| \nonterm{empty}
\nonterm{exponent-marker} \: e \| E
\nonterm{plus} \: +
\nonterm{minus} \: -
\nonterm{mult} \: *
\nonterm{div} \: /

\nonterm{reserved-word} \: \KW{float} \| \KW{bool} \| \KW{if} \| \KW{read} \| \KW{write}
\nonterm{rel-op} \: == \| != \| < \| <= \| >= \| >
\nonterm{punctuation} \: , \| ;
\nonterm{language-symbols} \: \gramquote{\{} \| \gramquote{\}} \| =

\nonterm{ignored} \: \nonterm{blank} \| \nonterm{tab} \| \nonterm{vt} \| \nonterm{formfeed} \| \nonterm{eol} \| \nonterm{comment}
\nonterm{blank} \: \textrm{``A space character (ASCII 32)''}
\nonterm{tab} \: \textrm{``A horizontal tab character (ASCII 9)''}
\nonterm{vt} \: \textrm{``A vertical tab character (ASCII 11)''}
\nonterm{formfeed} \: \textrm{``A formfeed character (ASCII 12)''}
\nonterm{newline} \: \textrm{``A newline character (ASCII 10)''}
\nonterm{cr} \: \textrm{``A carriage return character (ASCII 13)''}
\nonterm{eol} \: \nonterm{newline} \| \nonterm{cr} \nonterm{newline}
\nonterm{comment} \: \nonterm{pound-sign} \arbno{\nonterm{non-nl}} \nonterm{newline}
\nonterm{pound-sign} \: \#
\nonterm{non-nl} \: \textrm{``Any character except a newline''}
\end{grammar}
\caption{Lexical grammar of FLOAT. The grammar uses a \texttt{terminal font}
  for terminal symbols. Note that an underbar (\texttt{\_}) and all ASCII letters (a-z and A-Z)
  are included in the production for \nonterm{letter}.
  Again, $\arbno{x}$ means an arbitrary number of (i.e., 0 or more) repetitions of $x$.
  However, \gramquote{\texttt{\{}} and \gramquote{\texttt{\}}} are
  terminal characters (the left and right curly brackets).
  Some character classes are described in English, these are described
  in a Roman font between double quotation marks (`` and '').
  Note that all characters matched by the nonterminal
  \nonterm{ignored} are ignored by the lexer.}
\label{fig:lexical-grammar}
\end{figure}

\begin{figure}
\begin{grammar}
\nonterm{program} \: \nonterm{var-decls} \nonterm{stmt}

\nonterm{var-decls} \: \arbno{\nonterm{var-decl}}
\nonterm{var-decl} \: \KW{float} \nonterm{idents} ; \| \KW{bool} \nonterm{idents} ;
\nonterm{idents} \: \nonterm{empty} \| \nonterm{idents} , \nonterm{ident}
\nonterm{empty} \:

\nonterm{stmt} \: \nonterm{assign-stmt} \| \nonterm{begin-stmt} \| \nonterm{if-stmt}
\> \| \> \nonterm{read-stmt} \| \nonterm{write-stmt}

\nonterm{assign-stmt} \: \nonterm{ident} = \nonterm{expr} ;
\nonterm{begin-stmt} \: \gramquote{\texttt{\{}} \nonterm{var-decls} \nonterm{stmts} \gramquote{\texttt{\}}}
\nonterm{stmts} \: \nonterm{stmt} | \nonterm{stmts} \nonterm{stmt}
\nonterm{if-stmt} \: \KW{if} ( \nonterm{expr} ) \nonterm{stmt}
\nonterm{read-stmt} \: \KW{read} \nonterm{ident} ;
\nonterm{write-stmt} \: \KW{write} \nonterm{expr} ;

\nonterm{expr} \: \nonterm{lterm} \| \nonterm{lterm} \nonterm{rel-op} \nonterm{lterm}
\nonterm{lterm} \: \nonterm{lfactor} \| !~\nonterm{lterm}
\nonterm{lfactor} \: \nonterm{term} \| \nonterm{lfactor} \nonterm{add-sub} \nonterm{term}
\nonterm{add-sub} \: \nonterm{plus} \| \nonterm{minus}
\nonterm{term} \: \nonterm{factor} \| \nonterm{term} \nonterm{mult-div} \nonterm{factor}
\nonterm{mult-div} \: \nonterm{mult} \| \nonterm{div}
\nonterm{factor} \: \nonterm{ident} \| \nonterm{number} \| ( \nonterm{expr} )
\end{grammar}
\caption{Context-free grammar for FLOAT.
  The grammar uses a \texttt{terminal font}
  for terminal symbols, and a \KW{bold terminal font} for reserved words.
  As in EBNF, the notation $\arbno{x}$ means an arbitrary number of
  (i.e., 0 or more) repetitions of $x$.
  The terminal symbols \texttt{\{} and \texttt{\}} are quoted
  (like \gramquote{\texttt{\{}}) to make clear that they are to be
  interpreted as terminal symbols, not as meta-notations.}
\label{fig:cf-grammar}
\end{figure}

\subsection{ASTs}
\label{sec:asts}

The type for the abstract syntax trees (ASTs),
which is defined in the \texttt{ast} module
(files \texttt{ast.h}, and \texttt{ast.c}).
The file \texttt{ast.h} declares a type named \texttt{AST} that is
used by the contex-free grammar file \texttt{float.y}.

\subsubsection{The AST Type}
\label{sec:ast-type}

An \texttt{AST} is a C \KW{struct} containing the following fields:
\begin{itemize}
\item
  A field named \lstinline!file_loc! that gives the AST's
  (starting) file location.
  That is, it gives information about the place in a PL/0 source
  file where (the start of) the first token that was parsed into the AST
  was found: its filename, line number, and column number.
  File locations are defined in the \lstinline!file_location! module
  (files \lstinline!file_location.h! and \lstinline!file_location.c!).

\item
  If an AST type can appear in lists, then it will have a field named 
  \lstinline!next! that is a pointer to that type of AST.

\item
  Other fields are specific to the type of AST, but include subtrees
  representing nested grammatical constructs or tokens.
\end{itemize}

\begin{figure}[hbp]
\begin{grammar}
\nonterm{program} \: \nonterm{var-decls}  \nonterm{stmt}
\nonterm{var-decls} \: \arbno{\nonterm{var-decl}}
\nonterm{var-decl} \: \nonterm{var-type} \nonterm{ident}
\nonterm{var-type} \: \KW{float} \| \KW{bool}
\nonterm{stmt} \: \nonterm{ident} = \nonterm{expr}
         \> \| \> \KW{begin} \nonterm{var-decls} \nonterm{stmts}
         \> \| \> \KW{if} \nonterm{expr} \nonterm{stmt}
         \> \| \> \KW{read} \nonterm{ident}
         \> \| \> \KW{write} \nonterm{expr}
\nonterm{stmts} \: \arbno{\nonterm{stmt}}
\nonterm{expr} \: \nonterm{binary-op-expr} \| \nonterm{ident} \| \nonterm{number} \| !~\nonterm{expr}
\nonterm{binary-op-expr} ::= \nonterm{expr} \nonterm{op} \nonterm{expr}
\nonterm{op} \: == \| != \| < \| <= \| + \| - \| * \| /
\end{grammar}
\caption{Abstract Syntax of FLOAT.
  Again $\arbno{x}$, means a possibly empty list of $x$.}
\label{fig:ast-grammar}
\end{figure}

\subsubsection{AST Lists}
\label{sec:ast-lists}

In some ASTs some of the fields hold lists of other AST.
These are just linked lists that use a field \texttt{next} to refer to
the next element. The \texttt{NULL} pointer is used for an empty list.

\clearpage

\subsection{Semantics}

This subsection describes the semantics of FLOAT.

Nonterminals discussed in this subsection refer to the nonterminals in
the context-free grammar defined in \figref{fig:cf-grammar}.

A \nonterm{program} consists of zero-or-more variable declarations
(\nonterm{var-decls}), followed by a statement.

All arithmetic is done on floating point numbers as in C's
\KW{float} type.
The execution of a program declares the named variables,
initializes these variables, and then it runs the statement.

It is an error if an \nonterm{ident} is declared more than once.

\subsubsection{Variable Declarations}

The \nonterm{var-decls} specify zero or more variable declarations.

Each variable declaration, of the form \KW{float} \nonterm{ident},
declares that \nonterm{ident} is a (double-precision) floating point variable
that is initialized to the value 0.0.
A variable declaration of the form \KW{bool} \nonterm{ident}
declares that \nonterm{ident} is a Boolean variable that is
initialized to the value false (i.e., 0).

The scope of a variable declaration is:
the area of the program's text if the variable is declared at the
beginning of the program),
or the area of a \nonterm{begin-stmt} if the variable is declared at
the beginning of that statement.

It is an error for an \nonterm{ident} to be declared as a variable if
it has already been declared as a variable in the same scope.

\subsubsection{Statements}

A program contains a single statement that is run when the program
starts executing.

Note that the base case statements are terminated with a semicolon
(\texttt{;}).

\paragraph{Assignment Statement}

An assignment statement has the form
\nonterm{ident} \texttt{=} \nonterm{expr} \texttt{;}.
It evaluates the expression \nonterm{expr} to obtain a value and then
it assigns it to the variable named by \nonterm{ident}.
Thus, immediately after the execution of this statement, the value of
the variable \nonterm{ident} is the value of \nonterm{expr}.
(The evaluation of the \nonterm{expr} may produce runtime errors.)

It is an error if the left hand side \nonterm{ident} has not been
declared as a variable.

It is a type error if the type declared for \nonterm{ident} is not the
same as the type of the \nonterm{expr}.

\paragraph{Sequential Statement}

A begin-statement has the form
  \texttt{\{} $D_1 D_2 \ldots D_m S_1 S_2 \ldots S_n$ \texttt{\}}
(where $m \geq 0$ and $n \geq 1$)
and is executed by first allocating the variables declared
 by $D_1 \ldots D_m$ (initialized to $0$ for float variables and false
 for bool variables) and then executing statement $S_1$, then if $S_1$
finishes without encountering an error $S_2$ is executed, and
so on, in sequence.

Any runtime errors encountered cause the entire compound statement's
execution to terminate with that error.

\paragraph{If Statement}

An if statement has the form
  \KW{if} \texttt{(} $E$ \texttt{)} $S$
and is executed by first evaluating the expression $E$.
When $E$ evaluates to true, then $S$ is executed;
otherwise, if $E$ evaluates to false then this statement does nothing.

It is a type error if $E$ does not have type \KW{bool}.

\paragraph{Read Statement}

A read statement of the form \KW{read} $x$, where $x$ is a declared
\KW{float} identifier, reads a single floating-point
number
(using the format of the nonterminal \nonterm{number})
from standard input
and puts (an approximation of) its value into the variable $x$.

It is an error if $x$ has not been previously declared as a
floating-point variable.

It is a type error if the variable $x$ does not have type \KW{float}.

\paragraph{Write Statement}

A write statement of the form \KW{write} $E$,
first evaluates the expression $E$,
which must have type \lstinline!float!,
and then writes (an approximation to)
its value on standard output in decimal notation.

It is a type error if the \nonterm{expr} does not have type \KW{float}.

\subsection{Expressions}

An \nonterm{expr} of the form $E_1 \:o\: E_2$
first evaluates $E_1$ and then $E_2$, obtaining values $V_1$
and $V_2$, respectively.
(If either evaluation encounters an error, then the expression as a
whole encounters that error.)
Then it combines $V_1$ and $V_2$ according to the operator
$o$ following the semantics for C's operators.
If $o$ is an arithmetic operator (i.e., not a \nonterm{rel-op}),
then the types of $E_1$ and $E_2$ must both be \KW{float},
and the expression as a whole has type \KW{float}.
However, if $o$ is a \nonterm{rel-op}, then the types of $E_1$ and $E_2$ must
both be the same and the expression as a whole has type \KW{bool}.
(The semantics of FLOAT orders the Booleans so that false $<$ true.)

There are also a few other cases of expressions that do not involve
binary operators. These have the following semantics:

\begin{itemize}
\item
  An identifier expression, of the form $x$,
  has as its value the value stored in variable named $x$
  and it has the type of that variable.

  It is an error if $x$ has not been previously declared.
\item
  An expression of the form \texttt{!}$E$,
  first evaluates $E$, which must have a Boolean value $V$
  (and thus must be of type \KW{bool});
  the result is the logical negation of $V$.

\item
  An expression of the form \texttt{(}$E$\texttt{)} yields the value
  of the expression $E$.
\end{itemize}

\section{Future Work}

There are some things that the VM can do but are not expressible in
FLOAT. These include the following, all of which could be considered
future work to add into FLOAT:
\begin{itemize}
\item
  Integer data. The VM can deal with integers and can round a
  floating-point number to an integer.

\item
  Character data. The VM can read and write individual characters,
  but these are not found in FLOAT.

\item
  Procedures. The VM has instructions to support procedures, but those
  are not present in FLOAT.

\item
  Infinities and NaN. In floating point arithmetic, the results might
  be an infinity (\texttt{-inf} or \texttt{+inf}) or ``not a number'',
  but the language has no way to test for these.
\end{itemize}

\end{document}
