CS 697 Software Engineering Term Project

Fall 2000

Sketcho Match-Maker




Sketcho, a programming language, was designed for the production line drawings for small hand-held devices. Sketcho is a simple stack-implemented language. The grammar for Sketcho is listed in BNF form.

Review of BNF:

In the Backus-Naur Form a terminal symbol is indicated by not enclosing it within angle brackets. The angle brackets and enclosed words are non-terminals. Production rules consists of non-terminal at the left-hand side of the symbol := and one or more constructs, consisting of non-terminals and terminals at the right-hand side. If the right-hand side has several alternative productions, these can be separated by vertical bars (|). Syntactic elements may be grouped together by using curly brackets. A curly bracketed group may contain one or more vertical bars, indicating alternative syntactic elements. Repetition of curly bracketed groups is indicated by an asterisk (*) or a plus sign (+). An asterisk denotes that the group is optional and can be repeated any number of times. A plus sign indicates the group must be present and can be repeated any number of times. If syntactic elements are grouped using square brackets, the group is optional

<program> =: [comments] <main module definition>{ [comments] <module definition> }*

<main module definition > =: <start statement> { <body statement> }* <end statement>

<module definition> =: <begin statement> { <body statement> }* <end statement>

<start statement> =: START <program name> ;

<begin statement> =: BEGIN <module name> ;

<end statement> =: END [ <module name> | <program name> ] ;

<body statement> =: <declaration> |

<comments> |

<assignment> |

<pen attributes> |

<call statement> |

<moveto statement>

<declaration> =: DCL [<identifier> | <module name> ] ;

<identifier> =: <letter> { <alphanumeric> }*

<alphanumeric> =: <letter> | <decimal digit> | <national>

<letter> =: A-Z | a-z

<decimal digit> =: 0-9

<national> =: any symbol on the keyboard

<module name> =: <identifier>

<program name> = : <identifier>

<call statement> =: CALL <module name> ;

<assignment> =: <identifier> = <expression> ;

<expression> =: { primary> |

<expression> <arithmetic operator> <expression> }* ;

<primary> =: <identifier> | <constant> | ( <expression> )

<constant> =: integer | float

<arithmetic operator> =: + | - | / | * | ** | MOD

<pen attributes> =: DOWN ; | UP ; | <color statement> | <moveto statement>

<color statement> =: COLOR <hex color> ;

<hex color> =: { <hex number>}+

<hex number> =: 0-9 | A-F

<moveto statement> =: MOVETO <expression> <expression> ;

<comments> =: [REM any text until a newline]*

General rules:

  1. All lexical tokens are case-insensitive.
  2. To use a CALL statement, either the module definition or a declaration (DCL module name) must preceded the CALL.
  3. The default is pen up at the beginning of execution.
An example of a Sketcho program:

REM example of a box drawing Sketcho program

START DrawBox

DCL Box

DCL x

DCL y

x = 100;

y = 100;

MOVETO x, y;

CALL Box;

END DrawBox;

BEGIN Box;

DOWN;

MOVETO X+10, Y;

MOVETO X, Y - 10;

MOVETO X - 10, Y;

MOVETO X, Y +10;

END Box;
 
 

Since space is the most important constraint of Sketcho programs, designers would like to have a tool to find patterns in Sketcho programs. Using this information, these patterns could be abstracted out and placed in modules, thereby reducing size of the current executing unit. You are going to take up the cause to help out the Sketcho designers. For your semester software engineering project, you will design and implement a Sketcho match-maker.

Project Requirements

  1. Sketcho Match-Maker searches for a pattern and finds all lines that contain that pattern.
  2. Matches are case insensitive and based on the syntactic tokens of Sketcho. Spacing and line controls are ignored.

    3.  

     

    Example pattern:

    Moveto *

    Moveto *

    Result stemming from the Sketcho program above, assuming that the listing began on the first line of the file:

    File abc.sko Line 14

    File: abc.sko Line 15

    File: abc.sko Line 16

    Note the pattern could also have been entered as

    Moveto * Moveto *

  3. The following are the exit values :
  1. The user will input the pattern using the wild cards * and ?.
  1. The search source are file(s) that contain Sketcho modules.
  2. Match-Maker must be very time efficient. It must find matches in a 10,000 line Sketcho file(s) in less than 1 second. You must prove that your design can accomplish this feat and for the final implementation you must have modules that clock the speed at which searches are made.
  3. Since the web interface has become such a popular interface, the Sketcho designers would like the interface to be web based.
  4. On the calendar of future related projects is Sketcho++. Thus your design of Sketcho Match-Maker must be extensible, and maintainable.
To view a Sketcho Match-Maker prototype, see

http://www.bsu.edu.edu/homepages/dolores/CS689/mm_inter.html