ECE/CPSC 3520

ECE/CPSC 3520
Fall 2014
Software Design Exercise #1
Blackboard submission only
Assigned 9-08-2014
Due 9-24-2014 11:59PM
Contents
1 Preface 3
1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 The Bigger Picture: SDEs 2 and 3 . . . . . . . . . . . . . . . . 3
2 Resources and Notation 4
2.1 Resources . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.2 Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.3 Prolog Argument Designations . . . . . . . . . . . . . . . . . . 4
3 The Lexical Constraints and Data Structures 5
3.1 Basic Lexical Constraints . . . . . . . . . . . . . . . . . . . . . 5
3.2 ’needs’ Predicate and Argument Syntax . . . . . . . . . . . . . 5
3.3 ’resources’ Predicate and Argument Syntax . . . . . . . . . . . 6
4 Using flex and bison to Validate The Syntactic Correctness
of an Input String 7
4.1 Entities to be Recognized . . . . . . . . . . . . . . . . . . . . 7
4.2 Naming and Building . . . . . . . . . . . . . . . . . . . . . . . 8
5 Sample Use 8
6 Notes 11
1
7 Format of the Electronic Submission 11
2
1 Preface
1.1 Objectives
The overall objectives of SDE1 are:
1. To introduce flex and bison as general purpose scanner/parser devel-
opment tools.
2. To use flex and bison to build a grammatical recognizer to check the
syntactic correctness of a set of data structures to be used in SDEs 2
and 3.
These data structures will be used with Prolog and ocaml to satisfy a
scheduling (CSP) problem (see the section below).
Alternately, we are designing, implementing and testing an application-
dependent syntactic recognizer, implemented as a scanner/parser.
3. To give you experience in grammatical inference. Given the specifica-
tions herein, you will design G and implement it using flex and bison.
Grammatical ambiguity is not desired.
All work is to be done on a linux platform. Your grade is based upon a
correctly working implementation. Significant in-class discussion will accom-
pany this SDE. Get started now.1
This is an individual (not group) effort.
1.2 The Bigger Picture: SDEs 2 and 3
As a part of my ’un-retirement’ from the ECE Graduate Coordinator posi-
tion, I am now faced with a significant problem every semester:
The ECE Department offers many undergraduate labs. These
labs must be staffed by graduate Teaching Assistants (TAs).
Thus, the framework for a real problem. The long-term purpose of this
project is to design, implement and test systems for the scheduling of ECE
Graduate student teaching assistants (TAs). All representation and manip-
ulation will be done using Prolog (SDE2) and ocaml (SDE3). System inputs
1At least install flex and bison.
3
include department TA needs and available TA capabilities. System output
will be an assignment of TAs to labs. Here, the problem is to check the
syntactic correctness of inputs.
2 Resources and Notation
2.1 Resources
As discussed in class, it would be foolish to attempt this SDE without care-
fully exploring:
1. The text, especially the many examples in Chapter 6;
2. The flex manual (http://flex.sourceforge.net/manual/); and
3. The bison manual (http://www.gnu.org/software/bison/manual/).
2.2 Notation
The data structures will be used as Prolog arguments in SDE2. For now,
we concentrate on the structure (syntax) of the arguments. This does two
things:
1. It gets you familiar with the data structures you’ll use in SDE 2; and
2. It provides an application for flex and bison.
2.3 Prolog Argument Designations
See the book, p. 77, Section 3.1.5. This was discussed in class. I show argu-
ment structure with a combination of the notation used for Prolog predicate
arguments (+,-,?) and the notation for the positive closure set (+). For
example,
+Course+
indicates a variable ’Course’, which is bound when used (the left +), and
may be repeated 1 or more times (the right +).
4
3 The Lexical Constraints and Data Struc-
tures
3.1 Basic Lexical Constraints
1. Days are atoms m,tu,w,th,f.
2. Times are unsigned integers and causal (Stop_Time > Start_Time).
You do not need to check for causality.
3. Sections are unsigned integers.
4. Course names are the letters ’ece’ followed by four digits.
5. Student names are variable-length and comprised of lowercase alpha-
betic characters, e.g., jason, freddy, michael.
6. White space (see the text and examples) is allowed.
You need to develop REs for each of these entities, as a precursor to
building a scanner. I strongly recommend you design, implement
and test a freestanding scanner first.
3.2 ’needs’ Predicate and Argument Syntax
needs([+Course_List+])
where
Course_List itself is a list of form:
[+Course_name,+Section,+Day,+Start,+End]
A sample ’needs’ argument is shown below:
[[ece2090,1,m,13,16],
[ece2090,2,tu,13,16],
[ece2090,3,w,13,16],
[ece2090,4,f,9,12],
[ece2060,1,tu,11,14],
[ece2060,2,tu,14,17],
[ece2060,3,w,9,12],
[ece2060,4,f,13,16],
[ece3520,1,tu,11,14],
5
[ece3520,2,tu,14,17],
[ece4420,1,w,13,16],
[ece4420,2,f,13,16]]
Thus, the predicate could be used in Prolog (SDE 2) as:
needs([
[ece2090,1,m,13,16],
[ece2090,2,tu,13,16],
[ece2090,3,w,13,16],
[ece2090,4,f,9,12],
[ece2060,1,tu,11,14],
[ece2060,2,tu,14,17],
[ece2060,3,w,9,12],
[ece2060,4,f,13,16],
[ece3520,1,tu,11,14],
[ece3520,2,tu,14,17],
[ece4420,1,w,13,16],
[ece4420,2,f,13,16]]).
Notice the (allowed) use of whitespace.
3.3 ’resources’ Predicate and Argument Syntax
The Prolog predicate ’resources’ is an arity-1 predicate whose single argument
is used to ’hold’ the list-structured database of resources.
resources([+Student_Resource+])
The resources argument is a list of the overall resources database and is
of (list-of-lists) form, where individual student resource entries are lists of
resources_entry structure:
[+Student_Name,+Course_Capabilities_List,+Unavailable_List]
The 2nd and 3rd elements of the above resources_entry are variable-
length lists. Course_Capabilities_List is just a list of courses the student
is qualified to TA for. Time periods a student is not available are represented
in Unavailable_List with structure
6
=[[+Day,+Start_Time,+Stop_Time]+]
An empty Unavailable_List = [] means a student is available 24/5.
As a note in the Prolog solution (later), you MUST revise a specific
student’s Unavailable when used in a generated schedule.
Sample resources and resource entries:
[[joe, [ece2090,ece2010,ece3520,ece4420],[[m,8,9]]],
[sam, [ece2010,ece4420],[[tu 9,11],[th,9,11]]],
[pete, [ece3520,ece4420],[]],
[randi, [ece2090],[]],
[gwen, [ece2090,ece2010],[]]]
4 Using flex and bison to Validate The Syn-
tactic Correctness of an Input String
Here you will treat scanning and parsing of an input file, using a prespecified
set of data structures, as if it were ’source code’ constrained by a grammar
whose corresponding language is shown in Section 3. I’ll discuss syntactic
correctness in class and show examples of correct and incorrect files.
This SDE MUST be done using both flex and bison (and c).
4.1 Entities to be Recognized
The examples presented (both valid and errors) should help in understanding
of the desired syntax.
The following syntactically correct valid expressions, later to be used as
Prolog arguments, are to be recognized:
• needs
• unavailable_list
• course_capabilities_list
• resources_entry
• resources (resources_list)
7
The astute reader will note that some of the above entities are parts of others
(e.g., resources_entry and resources_list). In this case, the recognizer
should recognize the larger entity, not the component.
As shown in the examples, after recognition of each, a printf statement is
used to signify recognition of a syntactically correct construct. The display
format shown in the examples is to be used.
4.2 Naming and Building
The evaluation of your work will be partially automated. Therefore, you
must adhere to a number of specifications. The flex input file is to be
named schedule.in; the bison file is to be named schedule.y; the c file
containing main is to be named schedule.c; and the linux executable is to
be named schedule. We will use flex and bison to build your executable
with the following script (buildit):
#! /bin/bash
## to build scanner/parser */
bison -d -v $1.y
flex $1.in
gcc $1.c -lfl -Wall -o $1
For reference, here is the building of my solution:
$./buildit schedule
$
Anybody see any errors or warnings?
5 Sample Use
Here are a few cases. I’ll discuss these in class. Your effort should follow the
output format shown.
$./buildit scheduler
$ cat needs
[[ece2090,4,f,9,12],
[ece2095,4,w,9,12],
[ece3090,1,tu,1,3]
8
]
$./schedule <needs
found valid ’needs’ list’
$cat bad_needs
[[ece2090,4,f,9,12],
[ece2095,w,9,12],
[ece3090,1,tu,1,3]
]
$./schedule <bad_needs
syntax error
$cat bad_needs2
[[ece2090,4,f,9,12],
[cpsc2095,4,w,9,12],
[ece3090,1,tu,1,3]
]
$./schedule <bad_needs2
syntax error
$cat unavail_list0
[]
$./schedule <unavail_list0
found valid ’unavailable_list’
$cat unavail_list1
[[tu,7,9],[w,13,16]]
$./schedule <unavail_list1
found valid ’unavailable_list’
$cat bad_unavail_list1
[[tu,7,9][w,13,16]]
$./schedule <bad_unavail_list1
syntax error
$cat bad_unavail_list2
[[tu,7,9],[w,13-16]]
$./schedule <bad_unavail_list2
syntax error
$cat course_capabilities_list1
[ece2090,ece2010,ece3520,ece4420]
$./schedule <course_capabilities_list1
9
found valid ’course_capabilities’ list
$cat bad_course_capabilities_list1
[[ece2090,ece2010,ece3520,ece4420]]
$./schedule <bad_course_capabilities_list1
syntax error
$cat resources_entry1
[sam, [ece2010,ece4420],[]]
$./schedule < resources_entry1
found valid ’resources_entry’ list
$cat bad_resources_entry1
[ece3400, [ece2010,ece4420],[]]
$./schedule < bad_resources_entry1
syntax error
$cat bad_resources_entry2
[jenny, [ece2010,ece4420],[12,13]]
$./schedule < bad_resources_entry2
syntax error
$cat resources2
[
[joe, [ece2090,ece2010,ece3520,ece4420],[[m,8,9]]],
[sam, [ece2010,ece4420],[[tu,9,11],[th,9,11]]],
[pete, [ece3520,ece4420],[]],
[randi, [ece2090],[]],
[gwen, [ece2090,ece2010],[]]
]
$./schedule <resources2
found valid ’resources list’
$cat resources2b
[[joe, [ece2090,ece2010,ece3520,ece4420],[[m,8,9]]],
[sam, [ece2010,ece4420],[[tu,9,11],[th,9,11]]],
[pete, [ece3520,ece4420],[]],
[randi, [ece2090],[]],
[gwen, [ece2090,ece2010],[]]]
$./schedule <resources2b
found valid ’resources list’
$cat bad_resources2b
[[joe, [ece2090,ece2010,ece3520,ece4420],[[m,8,9]]],
[sam, [ece2010,ece4420],[[tu,9,11],[th,9,11]]],
10
[pete, [ece3520,ece4420],[sat,12,15]],
[randi, [ece2090],[]],
[gwen, [ece2090,ece2010],[]]]
$./schedule <bad_resources2b
syntax error
$cat bad_resources1
[[joe, [ece2090,ece2010,ece3520,ece4420],[]],
[sam, [ece2010,ece4420],[]],
[pete, [ece3520]],
[randi, [ece2090],[]],
[gwen, [ece2090,ece2010],[]]]
$./schedule <bad_resources1
syntax error
6 Notes
• Building of the scanner parser should not generate any shift/reduce
conflicts and/or useless rule or nonterminal warnings.
• The parser should never report that a file is syntactically correct in
addition to reporting an error.
• If we can’t build your scanner/parser with the buildit script, we can’t
grade it.
7 Format of the Electronic Submission
The final zipped archive is to be named <yourname>-sde1.zip, where <yourname>
is your (CU) assigned user name. You will upload this to the Blackboard
assignment prior to the deadline.
The use of gcc, flex and bison should not generate any errors or warn-
ings. The grader will attempt to build and then test your executable. The
grade is based upon a correctly working solution.
The minimal contents of your archive are:
1. A readme.txt file listing the contents of the archive and a brief de-
scription of each file. Include ’the pledge’ here. Here’s the pledge:
11
Pledge:
On my honor I have neither given nor received aid on this
exam.
This means, among other things, that the code you submit is your
code, and it was developed independently. Thus, you should not be
discussing your approach or solution with others in class or anywhere
else.
2. The flex, bison and c sources for your implementation named schedule.*,
where * is in, y and c, respectively. We will use the yyerror.c file
shown in class and in the book, page 180, Figure 6.11 to build the
executable. You should too. Do not redefine this function or include
yyerror.c in your archive.
3. A log of 6 sample uses (3 correct, 3 errors) of the resulting executable for
each element to be recognized in Section 4.1. Name this log schedule.log.
Pick examples other than the ones shown here.
12