[Table of Contents]

[5. Design information management]

[7. Case Study: Design system for high-level synthesis]

6. Processing design description files

6.1 Overview

This diversity of languages in design use implies that vendors of EDA frameworks make an arbitrary selection of the languages they want to support, mainly based on customer demands. As design methodologies are different from company to company and also evolve constantly, a framework vendor continuously has to support new design description languages. He may quickly be in a position in which supporting new languages(1) based on customer demands forms a major part of the overall effort put into framework development. There are three viable approaches to solve this problem:

1. Not to support design description languages at all. The JESSI Common Framework, for example, never looks into a design file but relies on the designer to chop his designs in pieces small enough to be managed individually by the DIM service of the framework.
   
2. To make an arbitrary selection of the languages to be supported. All design tools integrated with such a framework (e.g. Nelsis) have at least to provide converters from their native languages to the languages supported by the framework. If the supported language selection is not appropriate, and unsupported languages have to be used by design tools because a certain domain or level of detail cannot be represented, design files have to be manipulated manually by the designer to be digested by the framework.
   
3. To provide a framework service that allows a framework administrator or even design team members to add support for a desired design description language on the fly. Of course support for standard languages can already be provided by the framework vendor. Incorporating support for specific design description languages into an existing framework can even form the basis for a flourishing business niche.
   

Traditionally, writing language processors is accomplished by any of the following alternatives:

1. combination of the UNIX tools sed/awk, or dedicated report generation languages like perl(2)
   
2. lex generated lexical scanner
   
3. yacc generated parser
   
4. yacc generated parser enhanced with semantic actions to resolve references
   

The choice of standard compiler construction tools like yacc and lex suggests that the processing of design files is very similar to the initial parsing phase of a compiler for a particular design description language. There are, however, significant differences:

• Lexical and syntactical analysis in a compiler try to digest every single detail of a design description to be able to derive an internal representation that matches the information content of the design description as thoroughly as possible. For the purpose of design tool encapsulation, only a small part of design files has to be analysed down to single lexems. Large parts can simply be skipped and regarded as design representation, uninterpreted as far as design information management is concerned.
  
• A large part of the lexical and syntactical analysis phases of a compiler is concerned with error detection and recovery. As this tedious work is performed by design tools already, we can rely on a design description to be syntactically correct for the purpose of tool encapsulation.
  
• Another great effort in the initial phase of a compiler is the construction and maintenance of a symbol table for semantic analysis. We are not interested in the exact data or control flow and can therefore greatly reduce the effort of symbol handling. The close cooperation of the new encapsulation service with a DIM framework service with versatile querying facilities renders manually constructing a symbol table obsolete.
  

• All text that is considered design representation does not have to be interpreted in any way but must be saved complete for later perusal by design tools. Once an ordinary compiler has built an internal representation of the input read, it can safely forget about the exact textual representation, with the possible exception of line numbers for error messages.
  
• Global text that neither belongs to structural information nor is associated with single chunks of design representation must be preserved to be able to reconstruct complete design files later. In a compiler, this text is sometimes already resolved by a preprocessor and not even seen by the actual compiler or it serves as context information and is also translated to objects in an internal representation.
  

6.2 Requirements

6.2.1 Design file import

• interface, implementation, and configuration objects
  
• attribute values for names, designer, modification dates
  
• relationships for compositional hierarchy, version derivation, and equivalence
  

6.2.2 Design file export

The existence of component configurations in a design hierarchy complicates matters. In cases where a design description language is used that supports configurations (like VHDL), the configurations managed by the DIM service can be translated into appropriate configuration declarations in the language and emitted along with the selected interfaces and implementations. If, however, the design language does not have a notion of "configuration" or the notion supported by the language grossly deviates from the notion used by the DIM service, configurations have to be resolved and emitted as static bindings between compound implementations and their components.

6.2.3 Associating binary objects with structural information

6.3 Approach

6.3.1 Syntax specification

As stated earlier, we can assume that only little information out of the whole information content of a design file is needed for successful design information management. We can furthermore assume design files to be syntactically correct. These two assumptions greatly simplify the amount of syntax that actually has to be specified exactly. On the other hand, partial analysis poses additional problems not normally encountered in syntax analysis. While large parts of a design file can be analysed according to a lexical and syntactical specification that generously ignores most of the tedious detail of a complete design description, other parts have to be analysed down to single lexems in order to retrieve all the information necessary for design information management. For example, the analysis of a VHDL file only has to reveal the names and extent of contained entity declarations and architecture bodies, but all the information specified in a configuration declaration has to be retrieved.

We solve this problem by allowing modular language specifications. The specification of a design description language may consist of several modules, each of which defines the lexical properties and syntax for a part of the whole language. There is always a main module that provides an entry point for syntax analysis and generation. With the recognition of certain constructs, another module may be invoked that takes over syntax analysis from where it was invoked. Once a complete program defined by the language of the subordinate module has been recognized, control is returned to the caller. As different modules can define completely different lexical properties, modular language specifications allow to analyse design files at varying granularities. The net result is a major reduction in the amount of language detail that has to be specified for design file analysis while we are still able to digest fine-grained detail where appropriate.

We use the same language specification to define both input and output. As such, the specification language needs to define both lexical properties and syntax in one place. In addition, grammar symbols may be tagged for ease of reference during import and export. The specification may be decorated with output formatting information.

6.3.2 Parse tree construction

We provide no operations to prune the automatically created parse trees, because there is little need for this extra complexity. With modular language specifications, parse trees proved to be small compared to those created from complete fine-grained syntax analysis. Parse trees directly reflect the extended BNF by which the syntax is specified. Tree nodes that stem from certain syntax rules carry the name of this rule as their type. Lists, possibly with separators like "," or ";", create dedicated list nodes. Text ranges that are parsed by nested specification modules result in sub-trees.

6.3.3 The creating of objects during parse tree traversal

We prefer the programmed approach to the more descriptive approach of statically linking language constructs to DIM object types because thus

• the relatively fixed language definition can be separated more cleanly from the mapping to DIM object types that is likely to evolve as information management requirements change;
  
• more flexibility can be offered to the integrator to gather values from anywhere in the parse tree. Otherwise, a complicated formalism would be necessary that would yet be likely to fail in unexpected situations.
  

6.3.4 Linking types to parse trees

With this association in place, export of a DIM object into a valid design file is a matter of selecting the object and invoking its unparse method. The unparse method creates a parse tree with constant text in the right places and variables filled from the DIM database. Only a simple preorder traversal is needed to transform such a tree into a stream of text in the desired syntax.

Now that we have outlined our approach, we will present the technical realization of this new framework service in Sections 6.4 through 6.6, use VHDL as a case study in Section 6.7 and compare our approach with existing work in Section 6.8.

6.4 A specification language for HDL syntax

As a rule, the generated parser modules assume that they process syntactically correct design files. They therefore read over lexems that are not explicitly defined in the language specification. This behaviour can be exploited to simplify the language specification: Only those languages elements have to be defined that either carry valuable information for design information management or those that are necessary to recognize the syntactical structure of a design description. All other text will be ignored by syntax analysis but will nevertheless appear as text attributes in the parse tree to ensure that no information is lost for later export.

6.4.1 Nested parser modules

When the subordinate parser has recognized a valid text in the language that it defines, it returns the control back to the invoking parser.

rule rule {


    "rule" ID opt { "-syntax" } alternatives
}

---

Figure 25.

How to generate a parser module from a syntax specification. The preprocessor copag reads one or more specification modules and translates them into a parser specification in yacc format, a scanner specification in lex format, unparse tables, an unparse function that uses these tables, and a wrapper function for the extension language binding of language specific parse tree constructors. The parse tree abstract data type itself is language independent and is simply linked into the created module together with a set of wrapper functions for extension language bindings.

6.4.2 Generating a parser from specifications

There are two variants of the parse function:

Tree* parse (char* fileName);
Tree* parse (Tree* parent);

Tree* unparse (char* rule, ...);

6.5 The generated parser and tree constructor

6.5.1 A conceptual schema for parse trees

---

Figure 26.

Schema for parse trees. An analysed design file is mapped into virtual memory and is associated with the tree. Tree nodes only carry the start and end offsets into this mapped text.

6.5.2 Creating a parse tree

6.5.3 Nested parser modules

---

Figure 27.

Schema for the unparse tables. Rules carry their name and a numeric code. An item may either be a literal or optional (both stored as object of type Item), or it may be a reference to a subordinate rule. List items carry a separator if one was specified in the language specification.

6.5.4 Unparsing

• If the item is a literal, the created child takes the literal text as value of its text attribute.
  
• For all other item types, the unparse function first checks if a named parameter has been given to the function that matches this item. A named parameter matches an item if it is yet unused and
  
  • if the item is tagged and the parameter name equals the tag, or
    
  • if the item is a RuleItem and the parameter name equals the name of the referenced rule.
    

For maximum flexibility, a child node can be created from matching parameters in one of the following ways:

• the parameter text is taken as the node text.
  
• the parameter denotes a tree created elsewhere which is taken as the child.
  
• the parameter denotes a list of DIM objects. A new tree node is created as child. This child receives the result of evaluating the unparse method on each object in the list as children.
  

• If no matching parameter could be found, two cases are distinguished:
  
  • the item denotes a list of one or more elements. In this case no child node can be created automatically. The unparse functions fails.
    
  • the item is of type RuleItem. The unparse function calls itself recursively, passing the rule and the named parameters along. The result of this recursive call is taken as the new child node.
    

6.6 Extension language interface

6.6.1 Parsing design descriptions

vhdl t -file dp32.vhdl

set root [t root]

6.6.2 Tree traversal

rule traversal {
    node:IDENTIFIER "all" list { qualifier } 
    "-var" var:IDENTIFIER code_block
  | node:IDENTIFIER "one" list { qualifier }
}
rule qualifier {
    "-type" type:IDENTIFIER
  | "-tag" tag:IDENTIFIER
}

The method on tree nodes that implements these commands realizes the following algorithm:

---

Algorithm 1. Node::traverse

in	set<tags>	tags to be matched against node tag
in	set<types>	types to be matched against node type
in	variable name	Tcl variable to which to assign the node identifier currently processed
in	action code	Tcl code to evaluate for a node with matching tag and type
in	one	one or all command
out	success/failure	return code resulting from evaluating the action code

if (node type and node tag match inputs) {
  set Tcl variables for current node type, 
    current node tag, and current node text
  set Tcl variable named by parameter to current node identifier
  evaluate action code passed as input
  if (return code from action evaluation == OK) {
    if (one) {
      return BREAK;
    } else {
      return (return code from action evaluation);
    }
  }
  if (node type is list or node has children) {
    for each list element or child {
      traverse recursively, 
      passing input tags and types, variable name,
      action code and one flag
      switch (return code from recursive invocation) {
      case OK or CONTINUE:
        break:
      case BREAK:
        return BREAK;
      case RETURN:
        if (node type is list) {
          insert returned node identifier at current list position
        } else {
          replace current child with returned node identifier
        }
        break;
      default:
        return (return code from recursive invocation);
      }
    }
  }

6.6.3 Unparsing

The following extension language command is defined:

rule unparse {
    module:IDENTIFIER "::unparse" "-rule" rule:IDENTIFIER
    list { "-" IDENTIFIER "{" parameter_value "}" }
}
rule parameter_value {
    "-text" LITERAL
  | "-code" tcl_code
  | "-node" node:IDENTIFIER
  | "-list" tcl_code
}

• plain text,
  
• Tcl code to be evaluated to get some text as result,
  
• a tree node identifier, or
  
• a piece of Tcl code that - evaluated - results in a list of DIM object references. A list of tree nodes is yielded from this list by evaluating the unparse method for each of these objects.
  

rule block_configuration {
  "for" implName:IDENTIFIER
    list { use_clause }
    items:repeat { configuration_item }
  "end" "for" ";"
}

set tree [config::unparse -rule block_configuration
  -implName { -code $parent_DesignObject Name }
  -items { -list set ComponentConfigurations } ]
$tree export stdout

6.7 Case study: VHDL

6.7.1 The language

VHDL provides a good case study of our specification language for the following reasons:

• VHDL is important. Almost all ECAD vendors support VHDL input to their design tools, be it high-level synthesis systems, mixed-level simulators from algorithmic down to gate-level, or even systems for hardware-software co-design [Heusinger 93].
  
• VHDL is syntactically complex. VHDL has a rather irregular, handcrafted syntax, tailored to the conception by designers, not by machines. This is why it is a good benchmark for our specification language.
  
• VHDL is semantically complex. VHDL inherits from ADA constructs of a modern, structured programming language like modularization, abstract data types, a rich type system, and polymorphism. It adds its own concepts to describe hardware specific data types, concurrency, module generation, and composition hierarchies.
  
• VHDL has built-in design management features. The language offers a concept of dynamic configurations, which is unusual for a programming language, but very useful during the design and test of electronic circuits on various levels of detail. The designer can first create alternative implementations of a design entity and decide later which one to use at a certain place in her design.
  

The primary design abstraction in VHDL is the design entity. An entity declaration defines the interface between a given design entity and the system in which it is used. An architecture body specifies the implementation of a design entity in terms of the relationships between its inputs and outputs. There may be multiple architecture bodies defined for a given entity declaration. The selection of a specific implementation for a design entity is handled by configuration declarations.

Concurrent statements are used in architecture bodies to define interconnected blocks and processes that jointly describe the overall behaviour or structure of a design. Concurrent statements come in various forms, notably block statements to group other concurrent statements and process statements which represent single independent sequential processes. Other concurrent statements exist for commonly occurring forms of processes as well as for representing structural decomposition and regular descriptions.

VHDL provides a rich type system encompassing scalar, composite, access, and file types much like ADA. Subprograms may be used to define algorithms. Object types provided are constants, signals, and variables. Objects may be associated with predefined or user-defined attributes. Object and subprogram definitions may be grouped into packages, realizing an abstract data type. Entity, configuration and package declarations as well as architecture and package bodies may be independently analysed and inserted into a design library.

6.7.2 Syntax specification

syntax vhdl {
  token comment -ignore -pattern <"--" .* $>
  token ID              -pattern <[_a-zA-Z0-9]+>
  token USE             -pattern <"use" [^;]* ";">
  token LIBRARY         -pattern <"library" [^;]* ";">
  token END             -pattern <"end" [^;]* ";">
  rule design_file { repeat { toplevel } }
  rule toplevel { LIBRARY | USE | entity | architecture | package | config }
} // syntax vhdl

rule entity { "entity" Name:ID <\n> guts <\n> END }
rule architecture { "architecture" Name:ID ID EntityName:ID guts END }
rule package { "package" guts END }
rule guts { list { item | ID } }

While we completely ignore special characters (remember that the generated scanner is instructed to read over all text for which it has no explicit pattern), certain keywords and identifiers have to be distinguished to find component declarations.

rule item {
    "procedure" guts END
  | "function" guts END
  | "units" guts END
  | "record" guts END
  | "block" guts END
  | "generate" guts END
  | "process" guts END
  | "case" guts END
  | "if" guts END
  | "loop" guts END
  | USE
  | component
}
rule component { "component" Name:ID guts END }

rule config -syntax { "configuration" }

The declarative part of a configuration declaration allows the configuration to use items from libraries and packages. The outermost block configuration in the configuration declaration defines the configuration for an architecture of the named entity.

syntax config {
  token comment -ignore       -pattern <"--" .* $>
  token IDENTIFIER            -pattern <[_a-zA-Z] [_a-zA-Z0-9]*>
  rule configuration_declaration {
    "configuration" configName:IDENTIFIER 
    "of" interfaceName:IDENTIFIER "is"
    list { use_clause } block_configuration
    "end" opt { IDENTIFIER } ";"
  }
} // syntax config

Within the block configuration for an architecture, the submodules of the architecture may be configured. These submodules include blocks and component instances. A block is configured with a nested block configuration. Where a sub-module is an instance of a component, a component configuration is used to bind an entity to the component instance. Note the extensive use of tags on rule items. We will see shortly how these are used in both import and export specifications.

rule block_configuration {
    "for" implName:IDENTIFIER 
    list { use_clause }
    items:list { configuration_item }
    "end" "for" ";"
}
rule configuration_item {
    block_configuration
  | component_configuration
}
rule component_configuration {
    "for" component_specification
    binding:opt { "use" binding_indication ";" }
    block:opt { block_configuration }
    "end" "for" ";"
}
rule component_specification {
    instantiation_list ":" componentName:IDENTIFIER
}
rule instantiation_list {
    repeat -separator "," { instanceName:IDENTIFIER }
  | "others"
  | "all"
}
rule binding_indication {
    entity_aspect
    opt { "generic" "map" association_list }
    opt { "port" "map" association_list }
}
rule entity_aspect {
    "entity" "work." childInterfaceName:IDENTIFIER 
    opt { "(" childImplName:IDENTIFIER ")" }
  | "configuration" "work." childConfigName:IDENTIFIER
  | "open"
}
rule use_clause { "use" ";" }
rule association_list { "(" ")" }

6.7.3 Import: Creating objects during parse tree traversal

We assume that the node identifier of the tree root has been assigned to variable tree by the following statement

set tree [[vhdl T -file dp32.vhdl] root]
$tree all -type configuration_declaration -var n1 {
    $n1 one -tag configName -type IDENTIFIER {
      set configName $text }
    $n1 one -tag interfaceName -type IDENTIFIER {
      set interfaceName $text }
    $n1 one -type block_configuration n2 {
      doBlockConfig \
        $n2 $interfaceName $interfaceName $configName
    }
}

The procedure doBlockConfig has the following code:

---

Algorithm 2. doBlockConfig

in	n1	identifier of a block configuration
in	path	list of objects that represent the current nesting level
in	interfaceName	name of the interface of this block
in	configurationName	name of the outermost configuration declaration
out	configuration identifier	the identifier of the block configuration created

proc doBlockConfig {n1 path interfaceName configName} {
  $n1 one -tag implName -type IDENTIFIER { set implName $text }

  $n1 all -type component_configuration -var n2 {
    $n2 one -tag componentName -type IDENTIFIER {
      set componentName $text }
    $n2 one -type entity_aspect -var n3 {
      $n3 one -tag childInterfaceName -type IDENTIFIER {
        set childInterfaceName $text
      }
      set childImplName ""
      catch { $n3 one -tag childImplName -type IDENTIFIER {
          set childImplName .$text 
      }}
    }
    catch(6) { unset CC }
    $n2 all -type block_configuration -var n3 {
      set nestedC [doBlockConfig
        $n3 $path.$implName
        $childInterfaceName $configName]
      if {$childImplName != ""} {
        # check whether the block configuration just created 
        # is for childImpl
        $n3 one -tag implName -type IDENTIFIER {
          set nestedImplName $text }
        if {"$childImplName" == ".$nestedImplName"} {
          # create a component configuration 
          # that points to the block configuration
          set CC [ComponentConfiguration #auto
            -Name 


            "cc:$path.$implName.$componentName"
            -Configuration $C
            -Component
            $interfaceName.$implName.$componentName
            -Child $nestedC]
        }
      }
    }
    if [catch { set CC }] {
      # no nested block configuration has configured the childImpl
      # create a component configuration 
      # that points to the childimpl directly
      set CC [ComponentConfiguration #auto
        -Name "cc:$path.$implName.$componentName"
        -Configuration $C
        -Component 
        $interfaceName.$implName.$componentName
        -Child $childInterfaceName$childImplName]
    }
    # don't search for component_configuration's 
    # in nested block_configuration's
    continue
  }
  return $C
}

6.7.4 Export: Linking types to parse trees

return [config::unparse -rule block_configuration
  -implName { -code [$this Implementation] Name }
  -items { -list set ComponentConfigurations } ]

switch [$Child info class] {
Implementation {
  return [config::unparse -rule component_configuration
	-component_specification { -code 
		concat "all:" [$Component Name] }
	-binding { -code 
		concat "use entity" [$Child Name] } ]
  } 
Configuration {
  return [config::unparse -rule component_configuration
	-component_specification { -code 
		concat "all:" [$Component Name] }
	-binding { -code 
		concat "use entity" 
			[[[$this Implementation] Interface] Name] }
			"(" [[$this Implementation] Name] ")"
	-block { -node $Child unparse } ]
}}

For a configuration, an enclosing VHDL configuration_declaration has to be created first (we assume the variable C to contain the DIM object identifier of the configuration to be exported):

[config::unparse -rule configuration_declaration
  -name { -code $C Name } -entityRef { -code [$C Interface] Name }
  -block_configuration { -node $C unparse } ] export $VHDLfile

6.8 Related work

The Nelsis CAD Framework [Dimes 93b] supports tool integration on a number of different levels, with a set of interface functions that allow to access design data at varying granularities:

While Nelsis, too, does not provide a toolkit to write language processors for arbitrary design description languages, it offers an extensible set of format handlers for common formats. A format handler is a library function that knows how to read and write design data in a specific format. The functions dmGetDesignData and dmPutDesignData take the format handler needed to process a particular design description language as a parameter. Format handlers provide a uniform interface to design data from a tool's point of view. Unfortunately, support to write new format handlers is restricted to scanf/printf-like functions. This is clearly insufficient for free-format languages like VHDL.

Regarding the problem of framework support for design description languages to find an answer to the question "how to map between syntax and objects," some solutions are offered in the literature. Many "C++" class libraries have methods to dump an object graph to a file and to read such files back into memory. However, the format of such a dump is fixed, whereas the object-oriented database system OBST follows a more flexible approach. Its Structurer and Flattener (STF, [Pergande 93]) is a general tool to map between textual files and objects stored in an OBST database. STF translates a single syntax specification into a pair of programs, a structurer to read an object graph from a file, and a flattener to write an object graph to a file (the generation process is similar to the one depicted in Figure 25). The structurer contains a yacc-generated parser, the flattener is constructed from a set of recursive procedures. While the STF approach resembles ours, it can not be applied for the following reasons:

• STF assumes the OBST database system as back-end of the generated language processors. The mapping between (implicit) parse tree and an OBST object graph is compiled into the language processors.
  
• STF syntax specifications are restricted in that the syntax for a class must be described with a single syntax rule. While the provided EBNF constructs make up for this to a certain extent, in general it is complicated to map a given language specification to STF.
  
• STF generated parsers are expected to process every single detail from a file. This does not conform with our approach of only considering the bits in a design description that are important to DIM, ignoring most of the details. To provide more flexibility in choosing the parsing granularity, we provide modular syntax specifications.
  

Graver describes the system T-gen to automatically generate string-to-object translators in the context of the Smalltalk programming environment [Graver 93]. T-gen supports a large class of grammars (LL(1), SLR(1), LALR(1), LR(1)). The generated translators are Smalltalk objects and either create two variants of parse trees, derivation trees or abstract syntax trees from their input. While derivation trees contain all intermediate non-terminals created during parsing, abstract syntax trees are pruned by parse-tree builder directives (PTBs) inserted in the syntax specification by the programmer. PTBs can be used to explicitly construct a parse tree node or to control the flow of information between tree nodes. For example, there is a PTB liftRightChild to help flattening the derivation tree. Consider a set of rules of the form(7)

ArgList : Arg ArgList  { liftRightChild }
        | Arg          { ArgumentListNode };
Arg     : <argument>   { ArgumentNode };

Certainly, there are more sophisticated systems to process parse trees, yet all of them insist on processing files down to single lexems, as, after all, this is required for compiler construction. They also have limitations which make them unusable as general toolkits for building language processors to encapsulate design tools. Txl [Carmichael 92] relies on its own internal representation of parse trees and provides no documented hooks to extract information from such trees. Puma [Grosch 91] uses Modula2 as implementation language and relies on the use of its associated compiler frontend. A viable alternative to our parse tree operators might have been the use of Sorcerer [Parr 94], but we prefer a solution using an interpreted language in which framework administrators or even designers can easily create new or modify existing mappings without the need for recompilation.

Footnotes

(1)

"to support a design description language" here means to be able to manage structural information contained in design files by the DIM service and by framework tools like query interfaces and browsers.

(2)

Perl gains more and more acceptance as one of the primary scripting languages in EDA environments (cf. [CFI-EII95])

(3)

We regard situations in which design information has to be converted from one language to another as the task of dedicated design tools.

(4)

Another popular approach for parse tree construction is the definition of special node types for individual grammar rules. While this seems attractive from a purist's point of view, it would require to define a subtype of the basic node type for each grammar rule. On the other hand, modules with well-defined interfaces rather than deep inheritance trees have proven more usable in practice [Udell94].

(5)

"Abstract class" means that the user cannot create objects of this class but only of subclasses.

(6)

Catch is a Tcl command that evaluates its parameter as usual but "catches" error conditions to avoid that the execution of the whole script is terminated.

(7)

We use yacc's notation here. Curly braces contain action code

[Table of Contents]

[5. Design information management]

[Top of Chapter]

[7. Case Study: Design system for high-level synthesis]