expr.tex

由matlab开发的hybrid系统的描述语言

\chapter{\cppclass{Expr}}
\section{Introduction}
\hysdel{} is a description language for hybrid systems. The
associated compiler has been realized using the standard compiler
construction set: Bison (Yacc clone) + C language + Lex. The aim
of this document is not to recall the basic of compiler
construction which are indeed a prerequisite before reading this
paper. The aim is to drive the coder through the source code of
\hysdel{}.

\section{Mathematical expressions}
\hysdel{} deals with two different kinds of mathematical
expressions: (i) \emph{Affine} expressions and (ii) \emph{scalar}
expressions. The first are expression where the symbols declared
as variables appear only with power zero or one and are multiplied
by a scalar coefficient. The latter are any mathematical operation
involving symbols declared as parameters.

A crude implementation would declare two different syntax entities
for affine expressions and scalar expressions, as \hysdel{} 0.76
(see CVS tag: {\tt hydsel0-76}). This however turned out to be a
buggy implementation as the code reported in the file {\tt
buggy01.hys} showed. What was wron with the implementation was the
high number of shift/reduce and reduce/reduce conflicts in the
grammar (e.g.: Operator ``+'' was defined both in {\tt affexp} and
in {\tt scalarexp})

The solution to this problem was to completely redesign the
grammar for those two expressions. The new grammar unifies the
scalar expression and the linear expression in one new
\emph{generic} expression. Implicit casts transform the generic
expression in affine expression or scalar expression when needed.

To contain the number of modifications needed the generic
expression builds up the tree of the mathematical expression. This
tree is converted to an {\tt struct aff} or to a {\tt double}
number, when the cast is required.

The syntactic tree is a collections of {\tt gen} nodes:
\begin{verbatim}
struct gen {
    int             op;         /* name of the operator */
    int             nargin;     /* number of arguments */
                                /* (0=leaf, 1=unary, 2=binary)*/
    int             constant;   /* 1 if all the subtree is a constant */
    double         *value;      /* value, if can be computed */
    struct gen     *leftside;   /* left side of the operator */
    struct gen     *rightside;  /* right side of the operator */
    struct symrec  *symbol;     /* link to the entry in the symtable */
                                /* used only for the leafs */
};
\end{verbatim}
each node is linked to:
\begin{itemize}
  \item One node (using the {\tt rightside} pointer), if the operator is unary ({\tt nargin = 1})
  \item Two nodes (using the {\tt rightside} and {\tt leftside} pointers), if the operator is binary ({\tt nargin = 2}).
\end{itemize}

Leafs are marked with {\tt nargin = 0} and are of tree kinds: (i)
Numerical values, (ii) Parameters, and (iii) Variables. In the
case of parameters and variables, the pointer {\tt symbol} points
to the right entry in the symbol table.

The integer {\tt op} stores the operator that this node
represents. For binary operators, this is the {\tt char}
representing the operator, for unary operators and leafs, this is
the token value reported by the parser.

The pointer {\tt value} stores the numerical value of the result
of the operation, if applicable. It is null if the value of the
operations up to the current node cannot be computed, otherwise it
refer to a memory area where the value is stored.

The value {\tt constant} is 1 if the node represent operations
involving only constants\footnote{As now the fact that {\tt
constant = 1} implies that {\tt value != 0}, in the future, when
the parametric \hysdel{} will be implemented, this will not be
valid any longer. Parametric \hysdel{} allows parameters in the
parameters section to be uninitialized at compile time. Therefore
it will be possible that a node is constant, but the actual value
depends on uninitialized parameters and therefore the pointer will
be null.}.

The grammar for the {\tt genexp} is the following:
\begin{verbatim}
genexp:   NUM                 | '(' REAL BOOLVARIABLE ')'
        | PARAMETER           | REALVARIABLE
        | genexp '+' genexp   | genexp '-' genexp
        | genexp '*' genexp   | genexp '/' genexp
        | genexp '^' genexp   | '('genexp')'
        | '-' genexp          | COS '(' genexp ')'
        | EXP '(' genexp ')'  | SIN '(' genexp ')'
        | SQRT '(' genexp ')' | LOG '(' genexp ')'
\end{verbatim}
\figuraeps{gen_tree}{t!}{.8\hsize}{Example of tree generated
translating an expression}{fig:gen_tree} Figure~\ref{fig:gen_tree}
reports an example of generated tree. Once that this is casted
into affine expression or scalar expression, the syntax is checked
again. In the proposed example the conversion to scalar expression
will succeed if and only if all the referenced symbols are
declared as parameters. Conversion to affine expression will
succeed if at least $s$ or $c$ are declared as parameters.

\subsection{Future Developments}
The aim of this section is to give some hints to who will
implement the parametric \hysdel{}.

The first thing to do is to replace the field {\tt double coeff}
in the structure {\tt aff} with the field {\tt gen *coeff}. This
allows the coefficient to be something different from a number.

The functions that perform the casts ({\tt gen2affine} and {\tt
gen2scalar}) should be redesigned to keep into account that
scalars and coefficients of affine expression can be lacking a
numerical value.

All the functions that manipulate the affine structure should be
double checked and fixed to deal with generic expressions instead
of numerical coefficients. In particular the output function that
writes the matrices should be able to output the right entries in
the right place.

Finally the generated \matlab{} script ({\tt hout.m}, the output
of \hysdel{}) should check that all the uninitialized parameters
are provided by \matlab{}.