
The parser is written in accordance with {\em Lex} and {\em Yacc} 
format.  Like most other things, the parser module ({\em parser.y}) can be 
divided into 
three submodules, the {\em Lex} specification file (lex.l), the {\em Yacc}
specification file and the resulting parser source code files
({\em lex.yy.c, y.tab.c}). The source code
files are generated automatically and our interest is only in the two 
specification files.

The semantic attribute ({\em yylval}) of the tokens and variables is an integer. The 
other variables shared by the {\em Lex} and {\em Yacc} routines are

\begin{verbatim}
int line_num
\end{verbatim}
\begin{quotation}
An integer that keeps count of the line numbers in the circuit description
file. It is initialized to 1 and incremented when a newline character 
($\backslash n$) is read.
\end{quotation}

\begin{verbatim}
char names[2*max_fan][8]
\end{verbatim}
\begin{quotation}
Every line in the circuit description file defines a different gate. Most of
the information about the gate can be stored only when the entire line has 
been read. Some of this information is the names of the input and output lines.
These are placed, by {\em Lex}, in the string {\em yytext}, and every time
a new string is read, it writes over the previous string. Hence, we must store
these names somewhere else. {\em names[][]} is used to store all the line names
associated with a gate description in the circuit description file.
\end{quotation}

\begin{verbatim}
int name
\end{verbatim}
\begin{quotation}
A counter of the number of names stored in {\em names[][]}. It is also a 
pointer to the next available row in {\em names[][]}.
\end{quotation}

\subsection{The lexical analyzer}
The lexical analyzer has three major responsibilities.
The first responsibility is, of course, the identification of tokens and
passing them on to the parser. Its second responsibility is to catch certain
syntax errors. The third task is a cleanup and maintenance job.

In identifying tokens, the lexical analyzer allows each keywords to be entered
in either upper or lower case. A keyword can not, however, be written in both
lower and upper case. 

All line and gate user names are allowed up to seven characters. If a longer
name is used, it is truncated, leaving only the first seven. All messages
concerning that gate or line will include only the truncated name. As long as
all seven character prefixes are distinct, the system will not care. If
gate names share a seven character prefix, system messages concerning those
gates will be ambiguous (although the user name for these gate will appear
to be the same, the internal names will be different). If line names share
a seven character prefix, the system will generate some kind of error message
during the parsing procedure and the values placed in the data structures
might not be valid.

When specifying delay parameters for a gate, the order of these parameters
is fixed. The order is {\em rise, fall, setup} and {\em hold}. Some parameters 
may be
omitted, but their relative order can not be changed. For every parameter read,
a flag is set to true and the flags of all parameters that follow it are checked
to be false.

When describing the input lines of a flip-flop the {\em preset} and {\em reset}
lines are 
optional. If both appear, the preset line must come before the reset line.
Boolean flags are used to check these requirements.

When describing the output lines of a flip-flop, one of either the {\em q} or 
the
{\em qnot} lines must be specified. Both can also be used. When both are used,
the {\em q} line must come before the {\em qnot} line. These requirements are 
also checked by flags.

The cleanup jobs include the identification of {\em C}-like comments in the 
circuit
description file, ignoring white spaces and tab characters. The maintenance
jobs include keeping track of the line numbers and catching unexpected 
characters in the stream, i.e. characters not in a comment that are not part
of any token.
When a newline ($\backslash n$) character is read, besides incrementing the 
{\em line\_num} counter, all boolean flags are set to {\em false}.

The lexical analyzer will generate a message whenever a name is truncated,
an ordering syntax error is found or an unexpected character is encountered.

\subsection{The parser}

The parser, like most other functional elements in the system, has three
major responsibilities.
The first and foremost responsibility of the parser is to read the circuit
description file and convert the text description of the circuit to a 
description based on our data structures. These actions include
\begin{enumerate}
\item Sets the fields of all the elements of {\em gate\_list[]}. 
\item Sets the fields of all the elements of of {\em line\_list[]}, except line 
values. 
\item Sets the elements of {\em line\_x\_reference[]}. 
\item Sets the entries in {\em fan\_table[][].} 
\item Sets the counters {\em number\_of\_gates} and {\em number\_of\_lines}. 
\item Sets the pointers {\em first\_pi} and {\em first\_po}. 
\item Creates an initial list of representatives of fault equivalence classes.
\end{enumerate}

The second task the parser has is that of a semantic checker. The semantic 
checks that are carried out are
\begin{enumerate}
\item No two lines have the same user name.
\item Every line has a source and destination, i.e. there are no dangling lines.
\item The number of input lines and output lines of a gate are in accordance 
with the gate definition.
\item The number of gates and lines in the circuit does not exceed the allowed
maximum.
\item The clocks driving the different flip-flops have all been declared.
\end{enumerate}

The third and obvious task is a syntax checker for the circuit description file.

\subsubsection{Parser variables}

Besides the variables that are shared with the lexical analyzer, the parser
uses the following variables.

\begin{verbatim}
int parse_err
\end{verbatim}
\begin{quotation}
A boolean flag that indicates whether a syntax or semantic error occurred 
during parsing process.
\end{quotation}

\begin{verbatim}
int lines[2*max_fan]
\end{verbatim}
\begin{quotation}
An array corresponding to the array of user names, {\em names[][]}. While 
{\em names[][]}
holds user names associated with a line in the circuit description file,
{\em lines[]} holds the internal names for those lines. The running pointer for
{\em lines[]} is the variable $i$, which is reset to zero after a gate has been 
derived.
\end{quotation}

\begin{verbatim}
int rise_val, fall_val, setup_val, hold_val
\end{verbatim}
\begin{quotation}
These variables are assigned either the user specified delay parameters or,
when no parameters are specified, -1. When the whole gate is derived, if
a delay parameter is -1, the gate is given the default delay value of the gate
type. If the delay parameter is not -1, the gate is given that value as its
delay value.
\end{quotation}

\begin{verbatim}
fault_rec *fp 
\end{verbatim}
\begin{quotation}
The parser constructs an initial list of representatives of equivalent fault
classes. The pointer {\em *fp} points to the last element of the list, which is 
empty and ready to accept a class representative.
\end{quotation}

\begin{verbatim}
int number_of_clocks
\end{verbatim}
\begin{quotation}
A counter for the number of clocks in the circuit.
\end{quotation}

\subsubsection{Procedures and functions}

\begin{verbatim}
int add_line(user_name)
char *user_name ;
\end{verbatim}
\begin{quotation}
This function receives a pointer to a line user name and adds that name to the
{\em Hash} table. It returns the internal name for the line. If the name was 
already 
in the table, the function returns the internal name. When we say that a name
is in the table, we mean the internal name corresponding to the user name. 
To check whether an internal name matches a user name, we check the 
{\em user\_name}
field in the line structure pointed to by the internal name.
\end{quotation}

\begin{verbatim}
add_to_gate_list(gate,type)
int gate, type ;
\end{verbatim}
\begin{quotation}
This procedure receives two parameters, the internal name of a gate and an
integer equal to the constant corresponding to the gate type. The procedure
first sets the fields of the gate structure in {\em gate\_list[]}. It then sets
the gate entries in fan\_table and sets the source or destination fields
for its output and input lines. Finally it resets to zero the running indices
$i$ and $name$ of the arrays {\em lines[]} and {\em names[][]}.

The algorithm is
\begin{enumerate}
\item Set the fields of the gate entry in {\em gate\_list[]}.
\begin{enumerate}
\item Set {\em type, q} (and {\em qnot}).
\item For those delay parameters not equal to -1, set the corresponding delay
field to the parameter value. For those delay parameters equal to -1, set the 
corresponding 
delay fields to the default values of the gate type.
\end{enumerate}
\item Using $i$ and {\em lines[]}, set the gate row in {\em fan\_table[][]} and 
for each line set its destination (source) field to {\em gate}. 
\item Reset $name$ and $i$ to zero.
\end{enumerate}
\end{quotation}

\begin{verbatim}
dangling_lines()
\end{verbatim}
\begin{quotation}
After parsing is completed, this procedure goes over all the source and
destination fields in {\em line\_list[]} and verifies that none of the entries 
are equal to or greater than {\em max\_gate\_number}.
\end{quotation}

\begin{verbatim}
int find_gate_name(s)
char *s ;
\end{verbatim}
\begin{quotation}
This function receives a pointer to a user name and returns the internal name 
of the gate. The only time a conversion is needed from a user gate name to an
internal gate name is when the name is read from the circuit description file.
The internal name given to the gate is the current value of 
{\em number\_of\_gates},
the gate counter for the circuit. If this value is greater than
{\em max\_gate\_number}, an error message is generated. Otherwise, the user 
name is
copied into the {\em user\_name[]} field of the gate structure pointed to by
{\em number\_of\_gates}, which is then incremented. 
\end{quotation}

\begin{verbatim}
gen_err(err_num,site_name,line_num)
int err_num ;
char *site_name ;
int line_num ;
\end{verbatim}
\begin{quotation}
The procedure parameters are an error message number, a pointer to a string
with the name of the site (gate or line) in error and a line number in the
circuit description file. If the line is not known, the number is -1.
The appropriate error message, with the corresponding site name and line number 
is generated.
\end{quotation}

\begin{verbatim}
gen_warn(warn_num,site_name,line_num)
int warn_num ;
char *site_name ;
int line_num ;
\end{verbatim}
\begin{quotation}
The procedure parameters are a warning message number, a pointer to a string
with the name of the site (gate or line) involved and a line number in the
circuit description file. If the line is not known, the number is -1.
The appropriate warning, with the corresponding site name and line number 
is generated.
\end{quotation}

\begin{verbatim}
int get_line(user_name)
char *user_name ;
\end{verbatim}
\begin{quotation}
The function receives a pointer to a line user name and returns the internal 
name for the line. If the specified name is not in the table, an error message
is generated, stating that the name can not be found.
\end{quotation}

\begin{verbatim}
int hash_name(user_name)
char *user_name ;
\end{verbatim}
\begin{quotation}
This function returns the initial {\em Hash} index for the user name. The 
{\em Hash}
function used is the integer whose base 256 representation is the user name,
taken modulo the length of the {\em Hash} table ($2*max\_line\_number-1$).
\end{quotation}

\begin{verbatim}
init()
\end{verbatim}
\begin{quotation}
This procedure initializes certain fields in the global data structures
before starting the parsing process. The initialization steps are
\begin{enumerate}
\item In {\em line\_list[]}, the source and destination fields are set to
{\em max\_gate\_number}. After parsing is completed, these fields are 
checked.
If any of them has a value equal to {\em max\_gate\_number} then the line does
not have either a source or destination, depending on the field.
\item In {\em line\_list[]} the user name is set to the empty string. 
\item The entries in the {\em Hash} table, {\em line\_x\_reference}, are all 
set to -1.
\item The equivalent fault classes lists and pointers are initialized.
\item All clock counters are set to zero and all clock names to the empty
string.
\end{enumerate}
\end{quotation}

\begin{verbatim}
int parse(circuit)
FILE *circuit ;
\end{verbatim}
\begin{quotation}
This is the function one should use when he wants to read a circuit description
file. The parameter to the function is a {\em FILE} pointer to the circuit 
description
file. The function returns the constant {\em success} or the constant 
{\em fail}, 
depending on whether an error was detected during the parsing process.
\end{quotation}

\begin{verbatim}
print_tables()
\end{verbatim}
\begin{quotation}
This procedure prints the global structures {\em gate\_list[], line\_list[],
fan\_table[][], clock\_table[][], line\_x\_reference[]} and the initial list
of fault equivalence classes representatives.
\end{quotation}

\begin{verbatim}
yyerror(s)
char *s ;
\end{verbatim}
\begin{quotation}
A {\em Yacc} routine that generates the message pointed to by $s$. Can be 
overridden by a ({\em Yacc}) user specified routine. Our version sets the
{\em parse\_err} flag to true and in addition to the message in $s$, generates 
the
line number of the circuit description file that is currently read. This gives
a fair idea as to the location of the error.
\end{quotation}

\subsubsection{Changing the parser}

Any change to the parser will involve a combination of changes to the
lexical analyzer, the input grammar and the semantic routines (it's that
magic number three again). As an example, suppose we want to add a new
gate type, {\em newtyp}. First we must recognize this new keyword, and this
involves an addition to the lexical analyzer. Next, we must add a derivation
rule for this new type, and this requires a change in the grammar. Opon
deriving a gate of this type, we need to tell the parser what to do, and
so we must add the appropriate semantic routines.

\subsubsection{Using the parser}

To use the parser, the user object files must be linked with the object
files {\em y.tab.o, lex.yy.o} and {\em fc\_lists.o} . These files can be found 
in the parser directory ({\em parser}). 
The user must also include the files {\em global.h} and {\em global.g}
found in the main directory and the files {\em fc.h} and {\em fc.g} found in the
fault collapsing directory ({\em fc}). An example file, {\em parse.c}, can be 
found in the parser directory ({\em parser}).

\subsubsection{An exapmle program}

The following example program is in the file {\em parse.c} in the {\em parser}
directory.

\begin{verbatim}
/*****************************************************************************
  A program that wants to use the parser must :
 
  1. include "global.g"
  2. open the circuit file in read mode
  3. call parse with 1 parameter :
      i. the file pointer to the circuit file
  4. if parse returns success, there is no parsing error, 
     if parse returns fail there is a syntax or semantic error in the circuit 
     file.
  5. link with /home/poisson3/ee658/parser/y.tab.o, 
               /home/poisson3/ee658/parser/lex.yy.o, 
               /home/poisson3/ee658/parser/fc_lists.o

 *****************************************************************************/
#include <stdio.h>

#include "/home/poisson3/ee658/global.h"
#include "/home/poisson3/ee658/global.g"

main(argc,argv)
int argc ;
char *argv[] ;
{ FILE *circuit ;
  int ok ;

  circuit = fopen(argv[1],"r") ;
  ok = parse(circuit) ;
  if (ok == success) print_tables() ;
}
\end{verbatim}

The program is called with the circuit description file as a parameter. It first
open the description file for reading and then calls the parsing procedure
{\em parse()}. If {\em parse()} returns {\em success}, it calls 
{\em print\_tables()}, which prints the global structures {\em gate\_list[],
line\_list[], fan\_table[][]} and {\em line\_x\_reference[]}.

