Task: Verilog Parser

Owner: Jennifer Gillenwater

Goal

To build a parser for Verilog. This will allow us to import standard commerical and open source circuit descriptions into PreVIEW, as well as allow us to build simulators and analysis tools for Verilog. It will also allow us to explore extensions to Verilog.

References

• quick reference card

Administrivia

1. Getting an account on the CS network (talking to BJ, Lena, or Darnell. There'll be a form for me to sign) [done]
2. Getting an account on (or "register for") the wiki. [done]
3. Make a CVS directory for your work (after getting account on CS). [done]

Proposed Work Plan

1. Construct a restricted Verilog BNF containing only the more frequently used syntax constructs.
   • Find small Verilog example programs in Wikipedia at http://en.wikipedia.org/wiki/Verilog
   • Figure out what subset of the entire Verilog grammar is used for these examples
   • Find more examples in Verilog tutorials such as http://tutor.al-williams.com/wpv-1.htm to see if the basic subset still needs to grow
   • Write out the subset in a file (copy from BNF page and modify)
   • Describe in English what the subset does and what the rest of the language does (what main elements or functionality is excluded from the subset)
2. Design and implement an OCaml algebraic datatype to represent the abstract syntax tree (AST) Verilog programs
   • This involves writing a set to type descriptions in OCaml which describe the Verilog language.
   • Language documentation for OCaml can be found online at http://caml.inria.fr/pub/docs/manual-ocaml/index.html. This is a reference, so, only use it if you need to look up stuff.
   • Details on declaring types can be found in section 6.4 http://caml.inria.fr/pub/docs/manual-ocaml/manual012.html
   • For restricted Verilog subset comparison, Gordon Pace's paper The Semantics of Verilog Using Transition System Combinators, which decribes a subset of Verilog called VeriSmall, can be found at http://www.inrialpes.fr/vasy/people/Gordon.Pace/Research/Papers/fmcad2000.pdf
3. Design and implement a lexer for Verilog. This lexer will read from a file or string and generate a sequence of tokens
   • Use OCamlLex to generate the lexer for the Verilog BNF http://www.verilog.com/VerilogBNF.html.
   • OCamlLex documentation can be found at http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamllex-tutorial/.
   • Specific techniques for designing lexers can be found in section 14.5 of the Little Rapster.
   • Example lexers can be found in the Dr. Lint project as well as in the PreVIEW project.
4. Implement a parser which will take the sequence of tokens and generate the correct Verilog AST for the circuit.
   • Use OCamlYacc to generate the parser which uses the lexer generated in the previous step.
   • OCamlYacc documentation can be found at http://pllab.kaist.ac.kr/~shoh/ocaml/ocamllex-ocamlyacc/ocamlyacc-tutorial/index.html as well as in the Dr. Lint project.
   • Techniques for developing parsers can be found in section 14.5 of the Little Rapster, and example parsers can be found in the PreVIEW and the Dr. Lint projects.
5. Implement a pretty-printer for the Verilog AST.
   • This involves developing a function in OCaml which accepts an AST and returns a nicely formatted string of the program.
   • Refer to the Little Rapster for Pretty Printing with the OCaml Format Library (chapter 11) and the example MetaOCaml Pretty Printer (chapter 12).
   • Also, consult the Format library documentation
   • More help can be found in the Dr. Lint documentation section of The Little Rapster (chapter 14).
   • Examples can be found in the Dr. Lint project as well as in PreVIEW.
6. Implement a translator which will convert PreVIEW programs into equivalent Verilog programs.
   • Implement a function which accepts a PreVIEW AST and returns a Verilog representation of the program using the AST developed for step 2.
   • Consult the text-to-graph and graph-to-text translation functions and function implementations in the PreVIEW project.
   • PreVIEW documentation can be found in Ellner's Master's thesis and in the CVS tree.
7. Implement a translator which will convert Verilog programs into equivalent PreVIEW programs.
   • Implement a function which accepts a Verilog AST and returns a PreVIEW text or graph representation.
   • The text-to-graph and graph-to-text translation functions in PreVIEW will serve as good reference material.
   • PreVIEW documentation can be found in Ellner's Master's thesis.

Parts 1 to 5 constitute the basic components for representing, reading and writing Verilog programs. Parts 6 and 7 constitute the integration of the parser into PreVIEW and in the CVS tree.

Done

• restricted_verilog_BNF.txt: Restricted Verilog Grammar
• complex_BNF_constructs.txt: More Complex Grammar Constructs
• UtilityoftheRestrictedVerilogGrammar.doc: Grammar Semantics
• verilog_sample_programs.txt: Wikipedia Verilog Examples