Monday, December 29, 2008

Experiences converting a C lex/yacc parser for Verilog to pure Python

href="http://en.wiktionary.org/wiki/back_in_the_day">Back in
the day, simulators only had point delays, so all gate
libraries had buffers on their I/O. Now, we tend to use path, or
pin-to-pin delays in gate level models things have been made more
difficult for me.

My task was to randomly inject
some stuck-at faults in a large gate level Verilog design for
simulation. Individual gates of the design are connected by nets and
although I can force a net  I cannot force a node as all nodes
on a net are affected by a force on the net, and you cannot get at
individual nodes by looking to force a net  inside  a
particular gate model as their are no input buffers.  The
other problem with forcing nets/nodes using interactive commands of the
simulator is that you have to compile the design sub-optimally as all
the nets have to be accessible which stops the compiler/elaborator from
performing certain speed optimizations on what will be an execution
speed critical set of simulations.

Brainstorming
with a colleague we came up with the concept of modifying the netlist
to insert logic to either pass-through or force its out put to either 1
or 0 from an external control.

So off I went to href="http://embedded.eecs.berkeley.edu/Alumni/pinhong/scriptEDA/">ScriptEDA,
(great page - awful backdrop), and installed his href="http://www-cad.eecs.berkeley.edu/%7Epinhong/scriptEDA/pythongnd-0.35.tar.gz">Python
Interface for Gate-level Netlist Engine., which I then tried
on my gate level netlist.. Unfortunately our gate-level netlist failed
to parse because it used concatenations of nets which the parser
couldn't handle. I would need to extend the parser to support
 net concatenations.

Looking at the
source of the parser it was a C program using href="http://en.wikipedia.org/wiki/Flex_lexical_analyser">lex
and yacc
creating C data structures which were then interfaced to Python via a href="http://www.swig.org/">SWIG generated
wrapper. I don't like  to maintain C programs , and I needed
to flex my parsing abilities so decided to spend a short time
researching a pure Python solution.

PLY
The
obvious choice of  Python parsing tool seemed to be PLY as it
stands for Python Lex Yacc, so a download later and poking around in
the install, I came across href="http://code.google.com/p/ply/source/browse/trunk/example/yply/yply.py?r=43">yply.py:
style="margin-left: 40px;">
yply.py

This example implements a program yply.py that converts a UNIX-yacc
specification file into a PLY-compatible program. To use, simply
run it like this:

% python yply.py [-nocode] inputfile.y >myparser.py

The output of this program is Python code. In the output,
any C code in the original file is included, but is commented out.
If you use the -nocode option, then all of the C code in the
original file is just discarded.

To use the resulting grammer with PLY, you'll need to edit the
myparser.py file. Within this file, some stub code is included that
can be used to test the construction of the parsing tables. However,
you'll need to do more editing to make a workable parser.

Disclaimer: This just an example I threw together in an afternoon.
It might have some bugs. However, it worked when I tried it on
a yacc-specified C++ parser containing 442 rules and 855 parsing
states.
yply.py
worked on converting the ScriptEDA yacc source (after an edit to remove
some comments in the .y file that it could not handle). It saved me a
lot of work and saved me from transcription errors.  I then
wrote the Python lexer based on the C, and created Python
datastructures to   represent the parsed netlist. After
getting everything parsing I experimented until I got the net
concatenation for module ports and instance pins working. All the
classes used for the pares datastructure new how to print themselves in
valid Verilog so I could now read in a gate-level Verilog netlist
 then write it out in my 'standard' form.

I
then documented the parsed datastructures and worked out how to
randomly insert my 'tie' gate in an instance port connection for any
input or output instance port by selective modifications of the parsed
netlist. By using the Python standard difflib module  I
generated the standard form of the unmodified netlist and compared it
to the modified netlist as an aid when debugging .

After
a weeks work I now have a completely Python based tool to
programmatically modify our gatelevel netlists. Their is no C level
maintenance envisaged  and the tool should be flexible enough
to meet future needs - in the past, I may have not contemplated netlist
modification solutions to problems because of a lack of a suitable
parser. PLY turned out to be straight-forward to use

Thursday, December 04, 2008

Debugging vs inserting print statements

After reading this blog entry from Corey Goldberg, you got some people saying use debuggers instead of print statements.



So why can't you put that same print statement in the debugger and have it show up as an inserted print statement in the source? Why can't you do that for any code to insert? Rather than a breakpoint appearing as a blob to the side, you should have the option of it appearing as inserted code, maybe made visually distinct via shading and containing the logic inherent in the breakpoint such as coded indication that it counts down and only fires on the 20'th pass and then executes this code without pausing the run (or not).





A debugger breakpoint that doesn't stop the simulation but prints some text and the value of a few variables could then look like the insertion of a print statement in your source.





If you could make the interface work the other-way round too, i.e. stick the IDE into Add Debug Text mode, then code added would automagically be turned into equivalent statements executed by the debugger, then you could really fight those pesky inserters of print statements for debugging purposes by giving them a debugger whose interface works that way anyway ;-)




</only_slightly_tongue_in_cheek>

Yet Another Blog Entry On Doctests.

Doctests are a current hot Python blog topic. I thought I would point out that many of the bloggers, especially those pointing out its problems, seem to be seasoned Pythoneers, aware of alternatives and so able to compare doctesting with other forms of testing..



I've found that there is a significant number of programmers out there who just don't write reusable and maintainable tests at all. They may test to ensure their program 'works' when they wrote it, but that is all - job done, finito!



Doctests perform the very important task of lowering the entry point to the subject of testing. Novice pythoneers ready for exposure to testing are likely to have used the python shell to "try things out"; it is a small cognitive step to point out that by cutting and pasting those explorations from the shell into a docstring and adding some "magic sauce" to invoke it, you get a test. A trainer can then move on to the "why" of tests with the student thinking "I do most of it anyway", rather than thinking that it is yet more to learn



I am not saying that doctest is without flaws. I am saying that it is still a good tool, without being perfection.

Tuesday, December 02, 2008

Knapsack Problem

The Rosetta Code Blog this week mentioned that entries starting with a K were missing so I reviewed my sources and added a knapsack type problem to RC together with the python solution.



It's not the first time that I've remembered that itertools.product can do arbitrary nested for loops. Before, I would have had to employ recursive function calls.



- Paddy.