% from 10.1.1991 hk, version > 0.4

%aldes syntax

\chapter{The ALDES Language}

This chapter contains the ALDES language description.
The ALDES language has been defined by R. Loos in 
\cite{Loos 76}. We describe the revised version 
as distributed in 1988.
The parser has been implemented by K. Rieger.
Only the the syntax of the language and notes on 
differencies to the FORTRAN implementation of ALDES are given.
\index{ALDES}\index{FORTRAN}
\index{parser ALDES}

The ALDES parser is invoked via the 
\verb/PRAGMA(ALDES)./  switch.
Then a collection of ALDES algorithms is read until 
the ALDES end of file mark `\verb/||/' is encountered.
ALDES algorithms can be executed as normal MAS algorithms 
from the MAS interpreter.
\index{PRAGMA}

In the following sections we discuss 
first the lexical conventions and then 
the language syntax.


\section{Lexical Conventions}

The 'atomic' constituents of the language are characters and
tokens (character sequences with special meaning).


\subsection{Character Set}

The character set of ALDES is the same as the MAS character set.
\index{character set}
It consists of the 
\begin{deflist}{letter}
\item[digits] \verb/0123456789/
\item[letters] \verb/aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ/
\item[others] \verb*0.,=+-*/$() !"#%&':;<>?@[\]^_`{}|~0
\end{deflist}
\index{digit}\index{letter}\index{ASCII}
The number of characters is denoted by $\chi$ ($=95$ here).

\subsection{Tokens}

Lexical tokens of the language are:
\index{token}
\begin{quote}
       \verb/#  <  >  =  <=  >=/  \\
       \verb.+  -  *  /  ^. \\ 
       \verb.~  \/  /\. \\ 
       \verb/(  )  [  ]  {  }  ,  .  ;  :/ \\
       \verb/$  :=  ,...,  ||/ \\ 
       \verb/keyword  number  identifier/ \\
       \verb/string  char  comment/  
\end{quote}
\index{\verb/#/}\index{\verb/</}\index{\verb/>/}
\index{\verb/<=/}\index{\verb/>=/}\index{\verb/=/}
\index{\verb/+/}\index{\verb/-/}
\index{\verb/*/}\index{\verb./.}\index{\verb/^/}
\index{\verb.\/.}\index{\verb./\.}\index{\verb/~/}
\index{\verb/(/}\index{\verb/)/}\index{\verb/,/}
\index{\verb/[/}\index{\verb/]/}\index{\verb/{}/}
\index{\verb/./}\index{\verb/;/}\index{\verb/:/}
\index{\verb/$/}\index{\verb/:=/}\index{\verb/,...,/}
\index{\verb/||/}
\index{number}\index{keyword}\index{identifier}
\index{string}\index{comment}

Characters not contained in this list of tokens 
may only appear in strings and comments.

The keywords are:
\index{keyword}
\begin{quote}
      if, then, else, while, do, for, repeat, until, 
      case, of, \\ 
      return, print, goto, go to, \\
      safe, global, array, const, pragma, intrinsic.
\end{quote}
\index{if keyword}\index{then keyword}\index{else keyword}
\index{while keyword}\index{do keyword}\index{repeat keyword}
\index{until keyword}
\index{case keyword}\index{of keyword}\index{for keyword}
\index{goto keyword}\index{return keyword}\index{print keyword}
\index{goto keyword}
\index{safe keyword}\index{global keyword}\index{array keyword}
\index{const keyword}
\index{pragma keyword}\index{intrinsic keyword}

The meanings of most of the tokens and keywords 
should be 'as expected' and are discussed later. 
At this place we will only say some words on
numbers, identifiers, strings and comments.


\subsection{Numbers}

Numbers may be only so called $\beta$--integers  
\index{number}
as in the MAS language.

\subsection{Identifiers}

Identifiers are used as names of variables and names of 
procedures. 
\index{identifier}
The character sequence of an identifier
must start with a letter and may be 
followed by digits and letters.
Identifiers are case sensitive, i.e. upper case
and lower case letters are distinct.
The length of identifiers is restricted by the 
requirement that they must fit on one input line.

Example: NIL, p123, AL9, XSH, AlongName.

Ornamented identifiers are not supported by the ALDES parser. 
Naming conventions are as discussed in the MAS language section. 

\subsection{Strings}

Character sequences enclosed in double or single quotes
are called strings.
\index{string}\index{quote character}
Within the quotes any character from the character set
may appear. 
\index{\verb/"/}\index{\verb/'/}

Example:
\begin{quote}
       \verb/"this is a string"/ denotes the string
       \verb/this is a string/, \\
       \verb/"'"/ denotes the string \verb/'/, \\
       \verb/'"'/ denotes the string \verb/"/, \\
       \verb/"x'7""'"/ denotes the string \verb/x'7"'/
\end{quote} 

Strings are internally represented as lists of numbers 
($\beta$--integers). So all list operations are applicable to
strings, e.g. concatenating, reversing etc.
 

\subsection{Comments}

Comments are sequences of characters enclosed in
\verb/[/ and \verb/]/.
Comments may be nested, i.e. the comment character sequence may
contain {\em pairs} of \verb/[/, \verb/]/.
\index{comment}\index{\verb/[/}\index{\verb/]/}

Comments can appear everywhere except in other tokens.


\subsection{Blanks}

Blanks can appear everywhere except in 
numbers, identifiers, keywords or multiple letter tokens. 
\index{blank}

Characters in input lines which do not belong to 
the MAS character set are converted to blanks.
ASCII characters like CR (return), LF (line--feed),
EOL (end--of--line) are {\em ignored} during input form
data sets. 


\section{Syntax}

In this section we discuss the ALDES language syntax. 
First we give the complete syntax diagram and the 
list of syntax errors. 


\subsection{Syntax Diagram}

The syntax\index{syntax} definition is given in extended BNF\index{EBNF}
notation. That means
\verb/name/ denotes syntactic entities,
\verb/{}/ denotes (possibly empty) sequences,
\verb/()/ denotes required entities,
\verb/|/ denotes case selection and
\verb/[]/ denotes optional cases. 
Terminal symbols are enclosed in double quotes
and productions are denoted by \verb/=/. 
The syntax diagram is listed in table \ref{tabSDA}.

\begin{table}
\begin{center}{\small
\begin{verbatim}
program      = { declaration | algorithm } "||"
algorithm    = header { declaration } "(" number ")" statementseq 
               { "." "(" number ")" statementseq } "||" 
header       = ident ( "(" identlist [ ";" identlist ] ")" |
                       ":=" ident "(" identlist ")" )
statementseq = statement { ";" statement }
statement    = ( "print" string | 
               ident [ [ "[" termlist "]" ] ":=" expression |
                       "(" termlist [ ";" termlist ] ")" ] |
               "if" expression "then" statement 
                             [ "else" statement ] |
               "while" expression "do" statement |
               "repeat" ( statementseq "until" expression | 
                "{" statementseq "}" [ "until" expression ] ) |
               "for" ident ":=" expression [ "," expression ] 
                     ",...," expression "do" statement | 
               "case" expression "of" "{" 
                   { termlist "do" statement ";" } "}" |
               "return" [ "(" [ expression ] ")" ] | 
               ( "goto" | "go to" ) ( number | "(" number ")" ) |
               "{" statementseq "}" )
expression    = [ prefixop ] part { oper part }
prefixop      = ( "~" | "+" | "-" )
oper          = ( "+" | "-" | "*" | "/" | "^" |  "=" | "#" | 
                  "<" | ">" | "<=" | ">=" | "\/" | "/\" )
part          = ( number | string | char | "$" ident |
                  ident [ ( "(" [ termlist ] ")" | 
                            "[" termlist "]" ) ] |
                "(" expression  { "," expression } ")" )
termlist      = expression { "," expression }
identlist     = ident { "," ident }
variable      = ident [ "[" termlist "]" ]
declaration   = ( "global"    variable { "," variable } |
                  "safe"      variable { "," variable } | 
                  "array"     ident "[" termlist "]" 
                              { "," ident "[" termlist "]" } |
                  "const"     variable "=" expression }  
                              { "," variable "=" expression } | 
                  "pragma"    variable "=" expression 
                              { "," variable "=" expression } | 
                  "intrinsic" identlist ) "."
string        = ('"' {character} '"' | "'" {character} "'")
char          = "'" character "'"
ident         = letter { letter | digit }
number        = digit { digit }
\end{verbatim}
}\end{center}
\label{tabSDA}\index{syntax}\index{syntax diagram}
\caption{ALDES Syntax Diagram}
\end{table}

For ALDES program constructs, which have no or a different
meaning in the MAS environment, a syntax warning message is generated.
These are \verb/intrinsic/, \verb/pragma/, \verb/const/, 
\verb/global/ and \verb/safe/.
\index{intrinsic}\index{pragma}\index{const}
\index{global}\index{safe}
\verb/global/ declarations in algorithms are completely ignored 
since the parser checks for lexicalscope of the variables.
\verb/safe/ declarations are treated as \verb/VAR/ declarations 
in MAS. There is no distingtion between `safe' and `unsafe' 
variables.  For undeclared variables \verb/VAR/ declarations 
are generated.

The syntax errors and syntax warnings detected by the parser 
are summarized in tables \ref{tabASE} and \ref{tabASW}.
\index{syntax error ALDES}
\index{syntax warning ALDES}
\index{ALDES syntax error}
\index{ALDES syntax warning}

\begin{table}
\begin{center}
\begin{tabular}{rl}
           1  & identifier expected \\ 
           2  & \verb/)/ expected \\ 
           4  & factor expected \\ 
           8  & declaration expected \\ 
           9  & \verb/=/ expected \\ 
          10  & \verb/,/ or \verb/./ expected \\ 
          11  & \verb/[/ expected \\ 
          12  & \verb/]/ expected \\ 
          13  & string expected \\ 
          14  & number expected \\ 
          15  & \verb/to/ expected \\ 
          16  & \verb/then/ expected \\ 
          17  & \verb/of/ expected \\ 
          18  & \verb/{/ expected \\ 
          19  & \verb/;/ or \verb/}/ expected \\ 
          20  & \verb/do/ expected \\ 
          22  & \verb/,...,/ expected \\ 
          23  & \verb/,/ or \verb/,...,/ expected \\ 
          24  & \verb/(/ expected \\ 
          25  & \verb/||/ expected \\ 
          26  & statement expected \\ 
          27  & \verb/}/ expected \\ 
          29  & \verb/;/ or \verb/until/ expected \\ 
          30  & \verb/and/ or \verb/or/ un--expected \\ 
          31  & \verb./. un--expected \\ 
          32  & \verb/|/ un--expected \\ 
          33  & \verb/=/ or \verb/:=/ expected \\ 
          34  & expression expected \\ 
          35  & \verb/,/ or identifier expected \\ 
          36  & declaration or algorithm expected \\ 
          37  & \verb/./ expected 
\end{tabular}
\end{center}
\label{tabASE}\index{syntax error}\index{error}
\caption{ALDES Syntax Error Messages}
\end{table}

\begin{table}
\begin{center}
\begin{tabular}{rl}
           2  & \verb/intrinsic/ declaration unsupported \\
           3  & \verb/pragma/ declaration unsupported \\
           6  & \verb/./ in header unsupported \\
           7  & array as function unsupported \\
           8  & \verb/global/ declaration in algorithm unsupported \\
           9  & \verb/const/ declaration unsupported 
\end{tabular}
\caption{ALDES Syntax Warning Messages}
\label{tabASW}\index{syntax warning}\index{warning}
\end{center}
\end{table}

If a syntax error is detected one of the error messages is
displayed followed by the actual input line where the last
character read is underscored. However this last character
is one character and one lexical token to far. That means 
the syntax error is caused by one token behind.

Error repair is limited to skipping tokens until 
something meaningful is found.

In case syntax errors are detected, the execution of the program 
is totally suppressed, that means no executable code is generated.
If a syntax warning is given execution proceeds.

The program constructs \verb/goto/ and arrays are only simulated, so 
they will be interpreted slowly.
There exists no ALDES main program; any ALDES procedure
can be executed as a MAS procedure, 
can call MAS procedures and can be called from MAS procedures.
\index{goto}\index{array}

\section{Example}

We list a sample ALDES input:

{\small
\begin{verbatim}
  PRAGMA(ALDES).
                      b:=AFINV(M,a)
  [Algebraic number field inverse.  a is a nonzero
  element of q(alpha) for some algebraic number alpha.  M is the
  rational minimal polynomial for alpha.  b=1/a.]
  (1)  a1:=M;  a2:=a;  v1:=0;  r:=RNINT(1);
       v2:=LIST2(0,r);  repeat {  c:=RNINV(PLDCF(a2));
       v2:=RPRNP(1,c,v2);  if PDEG(a2) = 0 then { b:=v2;
       return };  a2:=RPRNP(1,c,a2);  RPQR(1,a1,a2;q,a3);
       v3:=RPDIF(1,v1,RPPROD(1,q,v2));  a1:=a2;  a2:=a3;
       v1:=v2;  v2:=v3  }||

                      c:=AFPROD(M,a,b)
  [Algebraic number field element product.  a and b are elements of
  q(alpha) for some algebraic number alpha.  M is the minimal 
  polynomial of alpha.  c=a+b.]
  (1)  cP:=RPPROD(1,a,b);  RPQR(1,cP,M;q,c)||

                      s:=AFSIGN(M,I,a)
  [Algebraic number field SIGN.  M is the integral minimal polynomial
  of a real algebraic number alpha.  I is an acceptable isolating 
  interval for alpha.  a is an element of q(alpha).  s=SIGN(a).]
       safe sS,sP,n,sH,s.
  (1)  [a rational.]  if a = 0 then { s:=0;  return};
       if PDEG(a) = 0 then { s:=RNSIGN(SECOND(a));
       return }.
  (2)  [Obtain the greatest squarefree divisor of an integral 
       polynomial similiar to a.]  IPSRP(1,a;r,aP);  sS:=RNSIGN(r);
       aS:=IPPGSD(1,aP);  IS:=I;  FIRST2(IS;u,v);  sP:=0.
  (3)  [Obtain an isolating interval for alpha containing no roots 
       of als.  RETURN SIGN(a(alpha)). ]
       repeat {  n:=IUPVSI(aS,IS);  w:=RIB(u,v);
       if n = 0 then {s:=IUPBES(aP,w);
       s:=sS  *  s;  return };  if sP = 0 then sP:=IUPBES(M,v);
       sH:=IUPBES(M,w);  if sH # sP then u:=w
       else { v:=w;  sP:=sH };  IS:=LIST2(u,v)  }||

                      c:=AFSUM(a,b)
  [Algebraic number field element sum.  a and b are elements of
  q(alpha) for some algebraic number alpha.  c=a+b.]
  (1)  c:=RPSUM(1,a,b);  return||

  || (* *)
\end{verbatim}
}

The \verb/PRAGMA(ALDES)/ statement switches to the 
ALDES parser. Then commes a sequence of ALDES algorithms.
The ALDES parser is terminated by the end of file mark \verb/||/. 
The dummy (MAS) comment might be neccessary in some situations 
to stop the scanner from reading the next token. 

The ornamented identifiers are denoted according to the 
implementation ALDES transliteration scheme.
For example \verb/a*/ = \verb/aS/,
\verb/s^/ = \verb/sH/ and \verb/s'/ = \verb/sP/.
\index{transliteration}

The used library functions (like \verb/RNINT/ or \verb/RPRNP/)
must be accessible from the MAS interpreter to be executable.

