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
- 浏览: 964704 次
文章分类
最新评论
-
18335864773:
很多公司项目 都在使用pageoffice 来操作word,e ...
用java生成word文档 -
Gozs_cs_dn:
请问下博主, 怎样将sitemesh3.xsd绑定 sitem ...
SiteMesh3配置 -
Rose_06:
springside4.0quick-start.bat报错原因 -
ilemma:
我也是刚参见工作啊,经理让自学这个,有些东西不太懂,能不能发个 ...
Apache Shiro在Web中的应用 -
shanbangyou:
你废了
程序员上班打酱油的方法
ECE/CPSC 3520
- 博客分类:
- 程序代写
发表评论
-
递归归并排序
2016-02-11 20:26 312/* MergeSort.java CSC 225 - ... -
java冒泡排序对布尔类型进行排序
2015-12-11 23:06 602QQ 928900200 程序代写 java不能对 ... -
判断宏是否是“安全”的
2014-11-22 22:54 522给了一系列C++的宏定义,问你一个表达式是否是“安全”的。 ... -
C语言求平均值
2014-11-19 19:14 501木其工作室:QQ928900200 Computing I ... -
C语言连连看
2014-11-18 16:34 565(1)定义一个矩阵,随机产生字符布置地图,例如下面这个4x ... -
The Monty Hall Problem
2014-10-19 12:58 610GNG1106 Lab 3The Monty Hall Pro ... -
java类
2014-10-16 08:27 269木其工作室 qq 928900200 You are ... -
计算机安全
2014-10-07 14:52 390CS461 MP 1: Due Wednesday 09/17 ... -
java星球机器人建模UML
2014-10-06 22:29 360Your task is to design and imp ... -
数据库sql
2014-10-06 22:25 579service QQ 928900200 ... -
C语言 cgi(3)
2014-08-04 09:17 3261cs3157 – Advanced ProgrammingS ... -
C语言 cgi(2)
2014-08-04 09:10 2811Columbia Universitycs3157 – Ad ... -
C语言cgi(1)
2014-08-04 09:08 3041Columbia Universitycs3157 – Ad ... -
c++ input,output
2014-08-04 08:37 429You should be comfortable w ... -
Array of Objects
2014-08-04 08:30 625You should be comfortable w ... -
bat脚本打开网页
2014-07-13 09:54 844start iexplore "http://ww ... -
java 汉诺塔实现自动演示
2014-07-10 11:53 4421、增加计时功能,显 ... -
代写java程序qq:928900200
2014-06-18 12:46 3学校为全面提升学校教学质量,提高管理水平,决定开发一套小型成 ... -
基于MVC的系统代写
2014-06-16 12:13 408人力资源管理系统 完成系统静态页面设计,页面数 ... -
程序设计实践C++ 程序代写(QQ 928900200)
2014-06-10 08:15 284程序设计实践 采用C++ ...
相关推荐
WP29的全称为联合国世界车辆法规协调论坛(简称为UN/WP29),WP29的工作是我国汽车行业参加的主要国际汽车技术法规工作,对我国汽车产业和国际贸易的发展有着至关重要的作用。
欧盟针对道路行人等弱势群体制定了BSIS标准
Concerning the Adoption of Uniform Technical Prescriptions for Wheeled Vehicles, Equipment and Parts which can be Fitted and/or be Used on Wheeled Vehicles and the Conditions for Reciprocal ...
UIUC statics notes. application statics in ECE area
私信博主,可免费获得该...本法规也适用于L6和L7类车辆,如果配备了L3以上的automated driving自动驾驶功能,如参考文件中定义的WP.29下的自动驾驶定义和制定联合国自动驾驶车辆法规的一般原则(ECE/TRANS/WP.29/1140)。
ECE R79
ECE R155.pdf
ECE R10 5欧盟标准05版,含新能源充放电试验要求,additional specifications in the configuration REESS Charging mode coupled to the power grid.
ECE R94标准,汽车行业碰撞标准。 ECE R94标准,汽车行业碰撞标准。 ECE R94标准,汽车行业碰撞标准。
ECE_R10.05
ECE工况数据,包括其电压数据,电流数据,转矩数据,转速数据。
欧盟EMC标准 ECE R10.05标准
上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目上海交通大学ECE项目
ECE R10-05中文版
ECE R64的翻译版本。欧盟第64号法规,规定轮胎压力监测系统的法规和试验要求
ECE R90 中文版!.pdf
ECE法规目录列表(中英对照)[参照].pdf
ECE R13H
ECE R79