% $Id: language-definition.tex,v 1.14 2023/03/31 13:08:25 leavens Exp leavens $
\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 in Spring 2023).
\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}
       ./compiler test.flt
\end{lstlisting}
will run the compiler on the program in \texttt{test.flt}
and put the generated FLOAT VM machine code on standard output;
any error messages are printed on 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 context-free grammar for FLOAT is defined in
\figref{fig:cf-grammar}
and its lexical grammar is defined in \figref{fig:lexical-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{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{ident} \arbno{\nonterm{comma-ident}}
\nonterm{comma-ident} \: , \nonterm{ident}

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

\nonterm{expr} \: \nonterm{lterm} \nonterm{rel-op-lterm}
\nonterm{lterm} \: !~\nonterm{lfactor} \| \nonterm{lfactor} 
\nonterm{rel-op-lterm} \: \nonterm{empty} \| \nonterm{rel-op} \nonterm{lterm}
\nonterm{rel-op} \: == \| != \| < \| <=
\nonterm{empty} \:
\nonterm{lfactor} \: \nonterm{term} \arbno{\nonterm{add-sub-term}}
\nonterm{add-sub-term} \: \nonterm{add-sub} \nonterm{term}
\nonterm{add-sub} \: \nonterm{plus} \| \nonterm{minus}
\nonterm{term} \: \nonterm{factor} \arbno{\nonterm{mult-div-factor}}
\nonterm{mult-div-factor} \: \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}

\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{exponent-marker} \: e \| E
\nonterm{plus} \: +
\nonterm{minus} \: -
\nonterm{mult} \: *
\nonterm{div} \: /

\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$.
  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 (except that each
  instance of \nonterm{eol} ends a line).}
\label{fig:lexical-grammar}
\end{figure}

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

The type for the enhanced abstract syntax trees (ASTs), which also
serves as an IR,
is defined in the provided files \texttt{ast.h}, with helping
functions in \texttt{ast.c}.

The file \texttt{ast.h} declares a type named \texttt{AST}
and a type \lstinline!AST_list!.
The type \lstinline!AST_list! is a
(linked) list of ASTs.

\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.

  The file location has the type \lstinline!file_location!,
  which is a type defined in \lstinline!file_location.h!.
  The file location is used in error messages.

\item
  A field named \lstinline!next! that is used for working with linked
  lists of ASTs.

\item
  A field named \lstinline!type_tag! that 
  indicates what kind of AST is held in the \texttt{data} field
  (see the next item below).

  These type tags are members of the enumerated type \lstinline!AST_type!,
  which is declared in the file \texttt{ast.h}.
  Each of these tags corresponds to a nonterminal symbol in the
  abstract syntax of PL/0 (see \figref{fig:ast-grammar}).

\item
  A field named \texttt{data} that holds a struct which has a type
  corresponding to the type tag (see the previous item above).
  This field is a C union, meaning that it can hold any one of the
  declared struct types corresponding to the tags of the union,
  which can be thought of as subfields.
\end{itemize}

\begin{figure}[hbp]
\begin{grammar}
\nonterm{program} \: \arbno{\nonterm{var-decl}} \nonterm{stmt}
\nonterm{var-decl} \: \KW{float} \nonterm{ident} \| \KW{bool} \nonterm{ident}
\nonterm{stmt} \: \nonterm{ident} = \nonterm{expr}
         \> \| \> \KW{begin} \arbno{\nonterm{var-decl}} \arbno{\nonterm{stmt}}
         \> \| \> \KW{if} \nonterm{expr} \nonterm{stmt}
         \> \| \> \KW{read} \nonterm{ident}
         \> \| \> \KW{write} \nonterm{expr}
\nonterm{ident} \: \nonterm{name} \nonterm{id-use}         
\nonterm{id-use} \: \nonterm{attrs} \nonterm{levelsOutward}
\nonterm{attrs} \: \nonterm{file-location} \nonterm{var-type} \nonterm{loc-offset}
\nonterm{var-type} \: \KW{float} \| \KW{bool}
\nonterm{expr} \: \nonterm{expr} \nonterm{op} \nonterm{expr} \| \nonterm{ident} \| \nonterm{number} \| !~\nonterm{expr}
\nonterm{op} \: == \| != \| < \| <= \| + \| - \| * \| /

\nonterm{op-expr} ::= \nonterm{op} \nonterm{expr}
\end{grammar}
\caption{Abstract Syntax for FLOAT
  Again $\arbno{x}$, means a possibly empty list of $x$.
  Note that \nonterm{op-expr} is intended only as an
  intermediate form during parsing, and is not used directly
  by any of the other rules. Indeed, the parser eliminates all such
  ASTs and builds the information in them into other types of ASTs;
  thus when walking the ASTs, it is not necessary to consider the
  \nonterm{op-expr} type of AST.}
\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.
The \texttt{ast.h} file declares a type \lstinline!AST_list!
that describes such lists and several operations that work on such lists.

\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}.

It is an error if the left hand side \nonterm{ident} has not been
declared as a variable.
% (The evaluation of the \nonterm{expr} may produce runtime errors.)

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.

\paragraph{Write Statement}

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

\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.

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$.

  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$,
  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.

\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 input these or test for these.
\end{itemize}

\end{document}
