Mainly Tech projects on Python and Electronic Design Automation.

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

6 comments:

  1. Care to post the code? =)

    ReplyDelete
  2. Creator of PLY here. I would be very interested to know if there is anything about the yply tool that could be improved. It was always something that was kind of experimental (hence the note in the comment) and I don't actually know how many people have used it to date. I'm really glad to hear that it worked for you however.

    Cheers,
    Dave

    P.S. I agree with your comment on maintaining C programs! :-).

    ReplyDelete
  3. HI Andrew,

    I'm going to be putting my case at work this week for making the code freely available. Wish me luck!

    Dave,
    The original verilog.y file: http://docs.google.com/Doc?id=dxbvd2v_8hhphf7c8 had to be edited into verilog_edit.y: http://docs.google.com/Doc?id=dxbvd2v_99fw7rxd9

    (I hope I've published the google docs OK).

    Thanks for your interest - Paddy.

    ReplyDelete
  4. I wasn't able to get scriptEDA to compile, did you have any hints. Which OS are you on?

    ReplyDelete
  5. hi paddy3118

    it is mostafa, a software developer, i could read your file verilog_edit.y it is very great but now i am stuck in another point ... how to continue parsing the array of instances in this form
    " nor_gate n[1:0] (a,b,c)" to create a parsing tree using C language

    ReplyDelete

About Me

Followers

Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!

whos.amung.us

Blog Archive