Special circumstances demand special solutions
Russ, an engineer with Micrion Corp., can be contacted at [email protected].
Sidebar: Flex and Bison
In any software-development project, proper design dictates that customizable parameters be easily accessible to allow changes to the system. That works fine for, say, entering limits or defining a set point. But what if the sequence of events changes? What happens when the fundamental structure of the process that you are trying to engineer changes?
That was the problem I faced at Micrion when designing software for a machine that repairs large area flat-panel displays. (Micrion designs and manufactures focused ion beam systems for use in mask repair, failure analysis, micromachining, magnetic head trimming, circuit modification, and the like.) The machine uses two lasers -- one to remove short circuits and another to react with a gas that deposits material on the surface, closing an open circuit.
The main problem was in a deposition system that required the control of several pumps and valves, which, from one process to the next, could be different. The output of transducers would have to direct the flow of control. The status of devices would have to be polled. There would also be a need to wait a predetermined amount of time before continuing to allow pressures to change. A timeout was also required to prevent the vacuum system from becoming deadlocked. In other words, the vacuum system had to be programmable.
Clearly, I needed a way to change the sequence of events in a predefined process while the system was running. It occurred to me that a special-purpose programming language might satisfy my design goals. However, if I was going to write a custom programming language, I wanted to get the most bang for the buck and reuse as much code as possible on other systems that Micrion had in place. But because the hardware was different on those systems, there would have to be different device-control methods. There was also the issue of device availability: There may be a common set of devices that the language could support, but the devices might not be available on some systems or the device might not automatically be detected.
Consequently, I wrote Micrion's Vacuum Command Language (Mvcl) to address these design issues. Figure 1 is a block diagram of the various layers that make up Mvcl. The source code for Mvcl is available electronically; see "Resource Center," page 3.
Choosing Language Statements
What types of statements did Mvcl require? Obviously, statements were needed to open and close valves, start and stop pumps, and so on. Table 1 lists the Mvcl language components by category. Program flow could be influenced from the system, which meant that Mvcl would have an if-then-else construct. If Mvcl was going to have if-then-else blocks, comparisons would have to be added. There is no point in adding an if statement if you can't compare two values. Where would those values be stored? Well, Mvcl would need variables as well. What started out as a simple programming language was quickly changing into a complex one. I was learning that there is a minimum set of features a special-purpose programming language must have to be useful.
One of the benefits of designing your own programming language is that you can tailor the statements to meet your requirements. The Mvcl waitfor statement is a good example. One of the most common activities in working with vacuum systems is to open or close a valve and wait for a pressure change. Without the waitfor statement, a Mvcl script might look like Example 1. The transducer must be repeatedly read and tested to see if the pressure set point has been met. Contrast that with the script in Example 2, where the waitfor statement does all of the work.
I chose statements that can handle either a class of devices or an action that is common across many types of devices. The read statement in Mvcl uses the latter method. The read statement is not device specific; the same read command can read from all of the devices that provide read-back capability. The Mvcl open statement uses the former method: open operates only on valve devices.
One goal of writing your own programming language is to create a language ideally suited to the problems you are solving. You only choose statements that have a direct benefit to your system. Remember, you are not writing a general-purpose programming language. Rather, you are writing a language that will help you express the solution to a specific problem.
Lexer and Parser Implementation
I used Flex and Bison to build the lexical analyzer and grammar parser. The lexer (Flex) and parser (Bison) work together to read and convert the input stream. Listing One resents the parser specification. (For more information, see the accompanying text box entitled "Flex and Bison.")
The lexer splits the input stream into tokens. A token is an integer representing an element read from the input stream. The lexer accomplishes this by matching the input to a regular expression. A regular expression is a way to describe a pattern using a set of rules. To illustrate, I'll use the Mvcl wait statement as an example. The syntax for the Mvcl wait statement is wait time-in-seconds;, where time-in-seconds is a real number.
As the lexer receives each character from the input stream, it tries to match the growing number of characters to one of the regular expressions. In this case, the regular expression for the wait keyword is wait. When the lexer receives the sequence of characters w-a-i-t, it matches the regular expression in the flex specification. Each time a regular expression is matched, Flex executes the actions for the matched rule. An action can be any valid set of C statements. For the wait keyword, the specified action is simply to return the token WAIT to the parser.
{wait} {
return( WAIT );
}
The parser receives the token, pushes it onto its stack, and calls the lexer for the next token. The next expected token is a real number. The specified action for a real number is to convert the ASCII text into a double, store the converted value in a data structure that is common to the lexer and parser, and return the REAL token to the parser.
{real} {
yylval.real = atof( yytext );
return( REAL );
}
Again, the parser receives the token, pushes it onto its stack, and calls the lexer for the next token. The next expected token is a semicolon (;). Like C, Mvcl uses a semicolon to delimit a line. The action for a semicolon is:
{semi} {
return( SEMICOLON );
}
All the while, the parser has been trying to match input as well. The job of the parser, like that of the lexer, is to match its input to a set of rules. The rules of a language are called a "grammar" and the parser is responsible for checking grammar. The parser is unable to match the rule for the wait statement until it receives the SEMICOLON token.
wait_statement: WAIT REAL
SEMICOLON
{ if( BuildMvclWaitNode
( prog, $2 ) )
YYABORT;
}
;
The action for the wait statement is not executed until all of the components of the statement have been received and are syntactically correct. In this case, a node has been built for the Mvcl wait statement.
Mvcl Data Structures
Mvcl encapsulates the concept of a program into the data structure MvclProgramList (see Figure 2). The program list contains pointers to the head and tail of a linked list of MvclProgramNode nodes. A program node is a union of all possible Mvcl statements. Every Mvcl statement has an associated data structure responsible for holding all of the data that can be used by the statement. The data might be a single integer as in the open statement or more complex data used in the waitfor statement. Each node represents an Mvcl statement that was parsed from the input source.
Each statement in Mvcl has its own build routine, which creates the program node. Most build routines follow the same format. Device requests are first validated against a database of available devices. If the device is available, space is allocated for the program node. The node is initialized with the statement data and the node is added to the list. If the device is not present then compilation stops and an error message is issued.
The instruction pointer is also maintained by the program list. It always points to the instruction to be executed by the next iteration of the interpreter. For most of the Mvcl statements the instruction pointer points to the next node in the list. For the flow control statements, the instruction pointer is used to branch around blocks of code in the if-then-else construct, or to repeat blocks of code in the for loop.
The program list also contains a pointer to the data type MvclSymbolTable. The symbol table is a linked list of MvclSymbol symbols. A MvclSymbol is simply a name/value pair, where the value is a union of the data types that Mvcl supports and the variable name. A symbol table entry is allocated to hold each variable name as it is encountered. To prevent duplicate entries, a linear search through the table for the variable is done each time a variable is added. Mvcl scripts typically do not have many variables, so the linear search is more than adequate.
The final component in the program list is a pointer to an instance of the MvclRunTimeStack data type. The stack is a linked list of MvclRunTimeStackEntry entries that each contain a reference to a MvclSymbol. The stack is used to hold the addresses of nested Mvcl if and for statements while compiling the program list. The stack could also be used when I get around to adding subroutines to Mvcl.
Interpreter, Compiler, or Both?
I felt that there was one significant setback in using an interpreted language to operate hardware components. What happens if a syntax error or a failed device verification stops the interpretation? Several valves may have been opened, pumps could have been started. The system could be left in an unsafe state. Granted, once the script has been debugged that may not be an everyday occurrence. But it is certainly a possibility.
With that in mind, Mvcl compiles the script into a program list, verifying as much of the program as possible. The list can later be passed through the interpreter to actually run the program.
Compiling a script into an intermediate form gives the added benefit that the program runs much faster. There can be situations where the response time of a programming language is too slow. The largest contributor to the lack of response time is usually the lexer and parser. The compilation removes that lag.
The interpreter itself is a small while loop that advances through the program list based on the value of the instruction pointer. At each node, the statement type for the node is an index into a dispatch table that calls the interpreter function for that statement. Interpretation continues until either an end or a return statement is encountered. Listing Two shows the implementation.
Replaceable Device Methods
A device method is an interface between Mvcl and the specific device control functions for the hardware. The method is responsible for converting requests for an Mvcl-specified device class and the device ID into the appropriate hardware-level function.
Mvcl is stored as a library. The library contains the default device methods for all of the devices supported by Mvcl. The default device behavior is simply to print a warning to stdout that a default-device method has been called.
You can override the functions in the library by creating functions with the same name in your applications code. The linker will resolve your function names first using your code in place of the default library method.
As an example, suppose that you wanted Mvcl to run on two separate hardware platforms (by sheer coincidence, that's what I wanted to do). For argument's sake, let's say that one of the systems contains only valves. The other system has both pumps and valves. On the former system, two functions would have to be overridden, MvclOpenValve() and MvclCloseValve(). The remaining device actions resolve to the default method, which will never be called, but the linker will need to resolve the reference. On the latter system (which has valves and pumps), two additional functions are written; MvclStartPump() and MvclStopPump().
Conclusion
Preparing for the unexpected changes that a major software development effort has in store is always a concern. If the software is controlling hardware, the job is even tougher. There are hardware changes to contend with as well as the development of a process that the software is supposed to control but may not fully exist.
Hardware changes occur less frequently than software changes (or so I'm told). But they do occur. And, most certainly, a process can't be completely developed until the system is fully integrated. Special-purpose programming languages provide a high level of flexibility to respond to those kinds of changes.
Special-purpose programming languages are an excellent model for how to design reusable software. A large part of Mvcl is not platform specific. Mvcl operates on a generic vacuum system made up of a finite set of devices. The specifics of a given vacuum system are buried in its device methods. Everything else remains the same. There are certain situations in which code reuse should be a foremost design consideration. Mvcl is one of those situations.
References
Kaplan Randy. Constructing Language Processors For Little Languages, John Wiley & Sons, 1994.
Flex and Bison manual pages, Free Software Foundation, 1988.
Levine, Mason, and Brown. Lex & Yacc, O'Reilly and Associates, 1990.
Aho, Sethi, and Ullman. Compilers Principals, Techniques, and Tools, Addison-Wesley, 1986.
DDJ
Listing One
%{/* MICRION SOFTWARE DEPT.
* Copyright (c) 1994 by Micrion Corp. All rights reserved.
* FILE NAME : mvcl.y
* AUTHOR : R. Mello
* DATE WRITTEN : 12/12/94
* VERSION : 1.00
* USAGE : grammar processor for the mvcl programming language
* This file contains a yacc grammar for the micrion ( M ) vacuum
* ( V ) command ( C ) language ( L ).
*/
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <mvcl_int.h>
</p>
/* local globals */
static MvclProgramList *prog = (MvclProgramList *)NULL;
static MvclProgramNode *Node;
static char *tmp;
static int ret;
static MvclPrintItem *plist = (MvclPrintItem *)NULL;
%}
</p>
%union
{
double real;
int integer;
char *string;
}
%token PROC END
%token IF THEN ELSE ENDIF
%token FOR TO DOWNTO ENDFOR
%token OPEN CLOSE READ SET STATUS WAIT TIMEOUT EXTEND RETRACT
%token WAITFOR PUMPON PUMPOFF EXIT PERROR PRINT PRETURN
%token V P HCIG CCIG BT TC NZ PT MFC
%token NAME SEMICOLON COMPARISON ASSIGNMENT QSTRING IDENTIFIER
%token SHELL_START STREAM_START STRING_START INTARG REALARG
%token INTEGER REAL
%token UNKNOWN
%token HELP
</p>
%type <string> QSTRING
%type <integer> V P HCIG CCIG BT TC NZ PT MFC
%type <string> IDENTIFIER
%type <integer> dev_class dev_id
%type <integer> COMPARISON
%type <integer> INTEGER
%type <real> REAL
%type <string> expr
%left '+' '-'
%left '*' '/'
%nonassoc UMINUS
</p>
%%
/* Three grammars can be parsed here. One that will accept
* interactive commands. Interpreting each command as it is entered.
* One that will accept a stream input. Parse the stream into a
* list of program nodes. Then pass the resultant list through the
* interpreter. Finally a grammar that will accept input from a string.
*/
combined: SHELL_START mvcl_shell
| STREAM_START mvcl_stream
| STRING_START mvcl_string
;
/* ============== The stream grammar starts here ============== */
mvcl_stream: proc_statement mvcl_statements end_program
;
proc_statement: PROC QSTRING SEMICOLON
;
mvcl_statements: mvcl_stream_statements SEMICOLON
| mvcl_stream_statements SEMICOLON
mvcl_statements
;
mvcl_stream_statements: status_statement
| read_statement
| mvcl_statement
| cond_statements
| loop_statements
| return_statement
;
status_statement: IDENTIFIER ASSIGNMENT STATUS dev_class
dev_id
{
if(BuildMvclStatusNode( prog, $1, $4, $5))
YYABORT;
}
;
read_statement: IDENTIFIER ASSIGNMENT READ dev_class dev_id
{
if(BuildMvclReadNode( prog, $1, $4, $5))
YYABORT;
}
;
cond_statements: if_statement
| if_else_statement
;
if_statement: IF if_test mvcl_statements endif_statement
;
if_else_statement: IF if_test mvcl_statements else_statement
mvcl_statements endif_statement
;
else_statement: ELSE
{
if( BuildMvclElseNode( prog ) )
YYABORT;
}
;
endif_statement: ENDIF
{
if( BuildMvclEndifNode( prog ) )
YYABORT;
}
;
if_test: expr COMPARISON expr
{
if( BuildMvclIfNode( prog, $1, $2, $3 ) )
YYABORT;
}
;
loop_statements: for_statement
;
for_statement: FOR for_args mvcl_statements endfor_statement
;
for_args: IDENTIFIER ASSIGNMENT expr TO expr
{
if( BuildMvclForNode( prog, $1, $3,
MVCL_FOR_TO, $5 ) )
YYABORT;
}
| IDENTIFIER ASSIGNMENT expr DOWNTO expr
{
if( BuildMvclForNode(prog, $1, $3,
MVCL_FOR_DOWNTO,$5))
YYABORT;
}
;
endfor_statement: ENDFOR
{
if( BuildMvclEndForNode( prog ) )
YYABORT;
}
;
expr: IDENTIFIER
{ $$ = $1;
}
| REAL
{ $$ = MvclCreateRealSymbol( prog, $1 );
}
| INTEGER
{ $$ = MvclCreateIntSymbol( prog, $1 );
}
| QSTRING
{ MvclParserError( "Incompatible Types\n" );
YYABORT;
}
;
return_statement: PRETURN INTEGER
{
BuildMvclReturnNode( prog, $2 );
}
end_program: END SEMICOLON
;
/* ============= The string grammar starts here ============== */
mvcl_string: mvcl_string_statements
;
mvcl_string_statements: /* empty */
| mvcl_shell_commands
;
/* ============= The shell grammar starts here ============== */
</p>
mvcl_shell: mvcl_shell_statements end_shell
;
mvcl_shell_statements: mvcl_shell_commands
| mvcl_shell_commands mvcl_shell_statements
;
mvcl_shell_commands: status_command
| read_command
| help_command
| mvcl_statement
;
status_command: STATUS dev_class dev_id
{ tmp = MvclGenerateVariable();
BuildMvclStatusNode( prog, tmp, $2, $3 );
}
;
read_command: READ dev_class dev_id
{ tmp = MvclGenerateVariable();
BuildMvclReadNode( prog, tmp, $2, $3 );
}
;
help_command: HELP
{ MvclShellHelp(); }
end_shell: END
{ exit( 0 ); }
;
/* ================ Common grammar elements ================= */
</p>
mvcl_statement: open_statement
| close_statement
| timeout_statement
| set_statement
| pumpon_statement
| pumpoff_statement
| extend_statement
| retract_statement
| wait_statement
| waitfor_statement
| print_statement
| error
{ if( MvclGetParserMode() == MVCL_STREAM )
YYABORT;
}
;
open_statement: OPEN V dev_id
{ if( BuildMvclOpenNode( prog, $3 ) )
YYABORT;
}
;
close_statement: CLOSE V dev_id
{ if( BuildMvclCloseNode( prog, $3 ) )
YYABORT;
}
;
timeout_statement: TIMEOUT REAL
{ if( BuildMvclTimeoutNode( prog, $2 ) )
YYABORT;
}
;
set_statement: SET dev_class dev_id REAL
{ if( BuildMvclSetNode( prog, $2, $3, $4 ))
YYABORT;
}
;
pumpon_statement: PUMPON P dev_id
{ if( BuildMvclPumpOnNode( prog, $3 ) )
YYABORT;
}
;
pumpoff_statement: PUMPOFF P dev_id
{ if( BuildMvclPumpOffNode( prog, $3 ) )
YYABORT;
}
;
extend_statement: EXTEND NZ dev_id
{ if( BuildMvclExtendNode( prog, $3 ) )
YYABORT;
}
;
retract_statement: RETRACT NZ dev_id
{ if( BuildMvclRetractNode( prog, $3 ) )
YYABORT;
}
;
wait_statement: WAIT REAL
{ if( BuildMvclWaitNode( prog, $2 ) )
YYABORT;
}
;
waitfor_statement: WAITFOR dev_class dev_id COMPARISON REAL
{
if( BuildMvclWaitForNode(prog,$2,$3,$4,$5))
YYABORT;
}
;
print_statement: PRINT print_list
{ ret = BuildMvclPrintNode( prog, plist );
/* init for another list. */
plist = (MvclPrintItem *)NULL;
if( ret )
YYABORT;
}
;
print_list: print_item
| print_item ',' print_list
;
</p>
print_item: QSTRING
{ MvclAddToPrintList( &plist, $1,
MVCL_PRINT_STR );
}
| IDENTIFIER
{ MvclAddToPrintList( &plist, $1,
MVCL_PRINT_IDENT );
}
| REAL
{ tmp = MvclCreateRealSymbol( prog, $1 );
MvclAddToPrintList( &plist, tmp,
MVCL_PRINT_REAL );
}
| INTEGER
{ tmp = MvclCreateIntSymbol( prog, $1 );
MvclAddToPrintList( &plist, tmp,
MVCL_PRINT_INT );
}
;
dev_class: V { $$ = MVCL_VALVE_CLASS; }
| P { $$ = MVCL_PUMP_CLASS; }
| HCIG { $$ = MVCL_HCIG_CLASS; }
| CCIG { $$ = MVCL_CCIG_CLASS; }
| BT { $$ = MVCL_BT_CLASS; }
| TC { $$ = MVCL_TC_CLASS; }
| NZ { $$ = MVCL_NZ_CLASS; }
| PT { $$ = MVCL_PT_CLASS; }
| MFC { $$ = MVCL_MFC_CLASS; }
;
dev_id: /* empty */ { $$ = 0; }
| INTEGER { $$ = $1; }
;
%%
/***************************************************************/
/* finis */
Listing Two
/* MICRION SOFTWARE DEPT. * Copyright (c) 1995 by Micrion Corp. All rights reserved.
* FILE NAME : mvcl_int.c
* AUTHOR : R. Mello
* DATE WRITTEN : 3/18/95
* VERSION : 1.00
* USAGE : module of the mcvl parser
* This source file contains the mvcl interpreter.
*/
#include <stdio.h> /* for NULL, fprintf(), ect... */
#include <signal.h> /* for SIGALRM */
#include "mvcl.h" /* for statement ID's */
#include <mvcl_int.h> /* for the Mvcl data structures */
/* uncomment the following line for debugging. */
/* #define MVCL_DEBUG */
/* function prototypes. */
int MvclInterpreter( MvclProgramList *, int * );
/* Interpreter function dispatch table. */
static PFI InterpreterTable[]=
{
InterpretOpenStatement,
InterpretCloseStatement,
InterpretStatusStatement,
InterpretSetStatement,
InterpretReadStatement,
InterpretTimeoutStatement,
InterpretPumpOnStatement,
InterpretPumpOffStatement,
InterpretExtendStatement,
InterpretRetractStatement,
InterpretWaitForStatement,
InterpretWaitStatement,
InterpretIfStatement,
InterpretElseStatement,
InterpretEndifStatement,
InterpretForStatement,
InterpretEndForStatement,
InterpretNullStatement,
InterpretPrintStatement,
InterpretReturnStatement
};
/******************************************************************/
int MvclInterpreter(
MvclProgramList *program, /* ptr to the program node list */
int *script_return )
{
/* MvclInterpreter() -- This function will interpret a translated
* source file. The interpreter will simply traverse the list
* of program nodes executing the mvcl program.
* RETURNS: 0 for success
* 1 for failure
*/
int result;
MvclProgramNode *current;
/* Make sure we have a valid program before we continue... */
if( program != (MvclProgramList *)NULL )
{
#ifdef MVCL_DEBUG
printf( "Beginning Interpretation...\n" );
#endif
/* Let's get started... */
current = program->ip;
/* Enter the interpreter loop. */
while( current != (MvclProgramNode *)NULL )
{
#ifdef MVCL_DEBUG
printf( "Executing A '%s' Node At Address %p \n",
MvclStatementTypeToName( current->StatementType ),
current );
#endif
/* based on statement type, dispatch the appropriate function. */
if( current->StatementType != END )
{
result = (*InterpreterTable[current->StatementType])
( program, current );
/* We're done if we see a return statement. */
if( current->StatementType == MVCL_RETURN )
break;
}
else
{
result = 0;
break;
}
/* test the return value, exit if an error occured. */
if( result != 0 )
break;
/* The next node is based on the instruction pointer. */
current = program->ip;
}
}
/* reset the program's instruction pointer to the start of the program. */
program->ip = program->head;
/* Set the return value. */
*script_return = program->return_value;
return( result );
}
/******************************************************************/
/* finis */
Back to Article
Copyright © 1998, Dr. Dobb's Journal