This technical report describes the implementation of a VHDL-AMS Parser and Pretty-Printer in Prolog. (We use VHDL-AMS and VHDL 1076.1 interchangeably in this document.) The original VHDL-87 parser written in Quintus Prolog and the original report are due to Peter Reintjes (then at Microelectronics Center of North Carolina, Reasearch Triangle Park). This parser was been revised to conform to the IEEE 1076-1993 standard of VHDL and ported to SWI-Prolog by the first author. Now it has been further revised to meet IEEE 1076.1 standard of VHDL (also called VHDL-AMS) and can be downloaded from http://www.cs.wright.edu/people/faculty/tkprasad .
The SWI-Prolog is an implementation of Prolog designed for experiments with logic programming. It provides a very rich environment for program development and is available in the public domain from ftp://swi.psy.uva.nl/pub/SWI-Prolog/.
The entire VHDL-93 parser is implemented in about 2300 lines (about 700 clauses) of Prolog, thus making it between one tenth and one fifth the size of other VHDL implementations. This demonstrates vividly that complex VLSI systems will not require millions of lines of code if they are described at an appropriate level of abstraction.
This parser can become the basis of a wide variety of tools which require input in the VHDL-AMS language. In particular, the original VHDL-87 parser was developed in conjunction with software components for schematic entry, logic synthesis, and a universal hardware description language translator. Both VHDL-AMS parser and the original VHDL-87 parser make no semantic consistency checks on the VHDL that they read, and only require that the program be syntactically correct. However, these parsers do detect both lexical and syntax errors. Furthermore, the VHDL-AMS parser generates reasonable messages for lexical errors.
This implementation will also be useful to VLSI/CAD developers who are not using Prolog because this implementation of the VHDL grammar contains corrections and clarifications that other textual specifications have omitted.
For example, a direct implementation of the grammar given in VHDL: Hardware Description and Design , (Kluwer Academic Press, 1989) (Authors: Lipsett, Schaefer and Ussery) would contain:
Since some readers of a grammar specification will be charged with the task of implementing a parser, it would be nice if they could trust the specification. In the original VHDL-87 parser, all left-recursive rules have been translated into right-recursions and overlapping rules have been combined to eliminate look-ahead. However, the original parser does not recognize based literals and does not handle ticks (') correctly. Furthermore, it vastly improves the parsing of operators, though it is not entirely ``correct''. The current VHDL-AMS parser attempts to remedy these problems, in order to conform to the IEEE 1076.1 Standard of VHDL. But most importantly, this ``specification'' in Prolog is actually an executable program which has succesfully parsed files in the VHDL Validation Suites, an exercise which flushed out errors in the grammar rules.
Programming Methodology
This document is written in HTML and contains the Prolog code for the parser and the pretty-printer embedded in it. Running the filter program Make.java (included in the distribution) on these HTML files will produce the Prolog source files, and eventually create the parser executable. If modifications are made to this parser, they should be made to the \HTML\ files, thus preserving the integrity of the relationship between the documentation and the code. The current distribution can be run on UNIX and on Windows 95 as long as SWI_Prolog and JDK 1.1 are available.
Data Structures
The parser builds a simple parse-tree reflecting the structure of the VHDL grammar rules. Once in this internal form, this description can be simulated, translated into other high-level circuit description languages, or interrogated by Prolog queries.
Since there are many optional constructs in VHDL, the naive parse will frequently contain the atom null when an optional structure is missing. Alternatively, when the optional item is a list of objects, a simple nil list ( [] ) may appear. The parse tree would be much simpler if missing optional items caused the creation of slightly different terms. For example, if term/5 has three optional sub-units which are frequently missing, it might be worthwhile to substitute a new version, term/2 when all three are missing. Thus, frequent occurrences of:
The current implementation maintains the verbose version of the parse tree for the following reasons:
optimize([],[]).
optimize([H|T],[OH|OT]) :- optimize(H,OH), optimize(T,NT).
optimize(term(null,null,Value,Name,[]),term(Value,Name)).
optimize(term2(null,null,X),term2(X)).
.
.
.
optimize(Tree,New) :-
Tree =.. [F|Args],
optimize(Args,OArgs),
New =.. [F|OArgs].
The VHDL Grammar
The original VHDL-87 parser written by Peter Reintjes is based upon the grammar in the appendix of VHDL: Hardware Description and Design, (Kluwer Academic Press, 1989) (Authors: Lipsett, Schaefer and Ussery). According to the authors, this grammar is simpler than the official definition in the IEEE Standard, but is functionally equivalent. Whereever there has been a departure, we have tried to patch things up. The DCG rules in the original VHDL-87 report are numbered to coincide with the grammar rules in the book. Here too, we maintain the old numbering scheme, except that the new rules added to satisfy VHDL 1076-1993 have been given a rule number followed by a letter tag to indicate the point of insertion, while those added to satisfy VHDL 1076.1-1997 have been given a rule number followed by a number tag (not necessarily consequetive).
A full appreciation of this report requires at least a reading knowledge of Prolog, although most of the grammar rules are only slightly more complex than a standard BNF description. In particular, a casual reader should probably not waste time on the section describing the tokenizer.
The names of predicates and terms are defined by the principle functor followed by a slash and the arity (number of arguments). Thus, the term name(A,B) is described as: name/2 . The names of Definite Clause Grammar (DCG) rules, which are transformed into Prolog predicates with additional arguments, are given names in the form: vhdl_prefix//1 , alluding to the fact that the actual arity of the resulting predicate is different from the DCG arity. Thus, the name vhdl_prefix//1 describes a DCG rule with arity equal to one, which translates into the Prolog predicate vhdl_prefix/3 , which has an arity of three.
The goal vhdl_read('Filename') directs the parser to read a VHDL description from the file named Filename.vhdl or Filename.vhd and store it in the database as a design_unit/2 term. This top-level goal to read a VHDL file is given below.
vhdl_read(Name) :-
file_path(Name,File),
exists_file(File),
see(File),
current_position(Pos),
vhdl_get_token_line(Tokens),
vhdl_design_units(Tokens,File,Pos),
seen.
current_position(Pos) :-
current_input(Stream),
stream_position(Stream,Pos,Pos).
% line_count(Stream, LineNo).
% Pos = '$stream_position'(A,LineNo,B).
vhdl_read(Name,Design_Units) :-
file_path(Name,File),
exists_file(File),
see(File),
vhdl_get_token_line(Tokens),
vhdl_design_units(Tokens,Design_Units),
seen.
vhdl_design_units([],[]) :- !.
vhdl_design_units(Tokens,[Design|Designs]) :-
vhdl_design_unit(Design,Tokens,[]),
!, vhdl_get_token_line(Next),
vhdl_design_units(Next,Designs).
There can be any number of design units in a file.
To maintain the correspondence between the source file and the design units defined in there, a predicate assoc_file_design_unit/4 has been introduced. The assoc_file_design_unit/4 -facts retain the line numbers corresponding to the beginning and the end of the text of a design unit. Because comments relevant to a design unit can occur immediately before or as a part of the VHDL code, additional lines preceding the code are also included. The parser can be modified, in future, to include comments immediately after the design unit, if that is considered natural. (This fix was motivated by the VHDL Browser application we wrote on top of the parser. The tokenizer strips away all the comments from the source program, that is it does not store any comments in the parse tree. So there seemed to be no way for the browser application to display the original source program without this workaround.)
The following predicate will terminate when it successfully reads an empty token line. This will occur when we have reached the end of the file. The predicate vhdl_get_token_line/1 reads in tokens up to a semicolon. The list of tokens it returns does not include the semi-colon itself, so it does not appear in any grammar rules. An asterisk is printed on standard output after reading each design unit.
vhdl_design_units([],_,_) :- !.
vhdl_design_units(Tokens,File,PosStart) :-
vhdl_design_unit(Design,Tokens,[]),
!, write('*'),ttyflush,
current_position(PosEnd),
assert(assoc_file_design_unit(Design,File,PosStart,PosEnd)),
vhdl_get_token_line(Next),
vhdl_design_units(Next,File,PosEnd).
/*********
% When a syntax error occurs, this extra clause
% calls up the editor "vi" on the VHDL file at
% the offending line.
% This code depends on several Quintus features.
vhdl_design_units(_) :-
seeing(File),
current_input(Stream),
stream_position(Stream,'$stream_position'(A,Line,B),
'$stream_position'(A,Line,B)),
put(7),put(7),nl,
format("Syntax error in statement ending on line ~d of file ~a~n~n",
[ Line, File]).
% write('Editing VHDL file ...'),ttyflush,
% concat_atom(['vi +',Line,' ',File],Cmd),
% shell(Cmd),
% write(' Edit Completed'),nl.
**********/
design_unit(CI,D) :- assoc_file_design_unit(design_unit(CI,D),_,_,_).
The rest of this document is a bottom-up tour of the parser, beginning with the tokenizer. Normally, a tokenizer is uninteresting, but it is helpful to be familiar with the primitive tokens before reading the grammar rules.