CSP 701 : Design Practices in Computer Science
Assignment 1 : Parser for Digital Circuits
Problem :
To display (draw) a digital circuit given it's description. Digital (combinational) circuits described in XML should be parsed and drawn as SVG figures. The description may be hierarchical with components described in terms of sub-components.
Tools to use :
Flex, Bison
Grammar :
Use the XML grammar given in Figure 3. mentioned in this paper for the circuit's description .
Changes :
- No need for bidirectional ports.
- Add another type of Connector : cn := <connector> <port> {id}.id </port> <port> {id}.id </port> </connector> | <connector> <bit_constant> <port> {id}.id </port> </connector> (where bit_constant = 0|1)
- Assume only basic components (AND, OR, XOR, NAND, NOR, NOT) will have their body described as truth table. You may ignore these for this assignment.
Input :
Files describing a combinational digital circuit in the format mentioned below. A file named top.ckt is the top-level circuit to be rendered. Each component has it's own file [comp-id].ckt.
To do :
Parse top.ckt and each component file it needs and render them as SVG drawings. Consider only combinational circuits.
Identify nets - and create them. That is, if the same signal is sent to 3 outputs, instead of drawing 3 wires, draw a net that has one source and 3 wire segments branching towards the 3 destinations.
Find invalid circuits and flag errors - syntax or semantic errors. Define & enforce design rules.
Bear in mind that this would be the base for Assignment 2 - a digital circuit simulator. Write modular and efficient code accordingly.
Output :
Two SVG (displayable in browser) files for top.ckt - one containing a high level view with black-boxes for sub-components, one containing a fully collapsed view. Clicking on a sub-component black-box should open it's SVG rendering.
Bound each subcomponent instance in a dotted rectangle & label it as [instance name]:[component name]
Use standard symbols for the basic gates.
Examples :
Ckt files :
The set of files below describe a 2-to-1 MUX using basic gates as sub-components. Two instances of 2and, one instance each of 2or & not are created. Connections are made to implement out = !sel.inp0 + sel.inp1 . Note that the connectors mention two ports each - the first being the source & the second being the destination of the wire. Each port is specified by {[instance-id-of-subcomponent]}.[port-id-in-that-subcomponent's-definition].
- 2-input AND gate
- 2-input OR gate
- NOT gate
- 2-to-1 Multiplexer
- 2-to-1 Multiplexer Instantiated into a top-level circuit
SVG files :
The basic gates used are described in basic_gates.svg (drawn using Inkscape). The ones used are - not, 2and and 2or. Note that these gates are described by the text between <g id="gate-name"> and </g> tags.
- 2mux.svg - View of a 2mux
- top_high.svg - High level view of top.ckt
- top_low.svg - Low level view of top.ckt
Open these SVG files in a text editor. You would note that the first 63 lines are the same in all. These are mandatory lines that need to be included to be able to render the SVG figures successfully in a browser. The figure drawn in each of these files follow immediately - as groups enclosed within <g id="ID"> & </g > tags or as separate elements. Groups are sets of elements that can be transformed as a single unit. For example, the 2or group is translated by (100,-22.5) in 2mux.svg using the transform attribute. Similarly, two instances of the 2and group are created simply by copying the code of 2and group from basic_gates.svg and adding translate attributes.
Wire connections are created by using the line tags (lines 170 onwards). Port names are added using text tags.
In top_low.svg, the whole of 2mux.svg's drawing area is grouped together by adding <g> & </g> tags, translated and used. The bounding box is draw using the rect tag and the name of the instance is added.
In top_high.svg, only input, output port names from 2mux.svg are retained, and the bounding box is made to act as a hyperlink to 2mux.svg using the <a xlink:href> tag.
Pointers to Help :
Refer SVG Primer for basic SVG help.
A nice Lex & Yacc Tutorial
Book : Levine, John R., Tony Mason and Doug Brown [1992]. Lex & Yacc. O’Reilly & Associates, Inc. Sebastopol, California.
(optional) Yacc with C++ How-To
(optional) STL and Boost Graph Libraries
(optional) Custom graph using Boost : code hints
Submit :
- Specification document - How do you plan to do it? What is the grammar you would use? What are the design rules you would enforce?
- Complete source code (only source code!) in folder (no sub-folders) : src
- Executable - filename : ckt_parse
