Article

Free access

GRASP: a grammar-based schematic parser

Authors:

C. Bamji,

J. AllenAuthors Info & Claims

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

Pages 448 - 453

https://doi.org/10.1145/74382.74457

Published: 01 June 1989 Publication History

PDF eReader

Abstract

The process of verifying that a circuit's schematic netlist obeys a particular design methodology is formalized. Circuit correctness is tied to a rigorous set of context free grammar composition rules. These rules define how a small set of module symbols may be combined for circuits adhering to the design methodology. Schematic netlists are represented as graphs, and composition rules are defined as graph transformations akin to grammatical productions. Starting with a circuit netlist, a hierarchical parse tree that can demonstrate the wellformedness of the circuit is constructed. The procedure is hierarchical, incremental, and fast. GRASP operates one to two orders of magnitude faster than previous approaches.

References

[1]

A. Aho and J. Ullman. Principles of Compiler Design. Addison Wesley, 1977.

Digital Library

Google Scholar

[2]

C. Bamji, C. Hauck, and J. Allen. A designby-example regular structure generator. In A CM IEEE 22nd Design Automation Conference, 1985.

Digital Library

Google Scholar

[3]

G. Goos and J. Hartmanis. Graph-Grammars and their Application to Computer Science. Springer- Verlag, New-York, 2~d international workshop edition, 1983.

Google Scholar

[4]

C. Hauck, C. Bamji, and J. Allen. The systematic exploration of pipelined array multiplier performance. In Proceedings Inlernation Conference on Accoustic, Speech and Signal Processing, 1985.

Crossref

Google Scholar

[5]

K. Karplus. Exclusion constraints" a new application of graph algorithms to VLSI design. In Proceedings of the Fourth MIT Conference on Advanced Research in VLSI, 1986.

Digital Library

Google Scholar

[6]

A. Kolodny, R. Friedman, and T. Ben-Tzur. Rulebased static debugger and simulation compiler for VLSI schematics. In IEEE International Conference oa Computer-aided Design, 1985.

Google Scholar

[7]

C. Leiserson, F. l~ose, and J. Saxe. Optimizing synchronous circuitry by retiming. In Proceedings of the Third Caltech conference on VLSI, 1983.

Google Scholar

[8]

H. De Man, I. Bolsens, and E. Vanden Meersch. An expert system for logical and electrical debugging of MOSVLSI networks. In IEEE International Conference on Computer-aided Design, 1984.

Google Scholar

[9]

R. Spickelmier and A. Newton. Critic' a knowledge-based program for critiquing circuit designs. In International Conference on Computer Design, 1988.

Crossref

Google Scholar

[10]

N. Weste and K. Eshraghian. Principles of CMOS VLSI Design. Addison Wesley, 1985.

Digital Library

Google Scholar

Cited By

View all

Jäschke CHerter UWolkober CSchmitt CZoellin C(2017)Static netlist verification for IBM high-frequency processors using a tree-grammarProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130742(1556-1561)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130742
Jaschke CHerter UWolkober CSchmitt CZoellin C(2017)Static netlist verification for IBM high-frequency processors using a tree-grammarDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927237(1552-1557)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927237
Bamji CAllen J(1994)GLOVE: a graph-based layout verifierProceedings of 7th International Conference on VLSI Design10.1109/ICVD.1994.282688(215-220)Online publication date: 1994
https://doi.org/10.1109/ICVD.1994.282688
Show More Cited By

Index Terms

GRASP: a grammar-based schematic parser
1. Hardware
2. Theory of computation
  1. Formal languages and automata theory
    1. Grammars and context-free languages
  2. Semantics and reasoning
    1. Program reasoning
      1. Parsing

Recommendations

A unification-based parser for relational grammar
ACL '93: Proceedings of the 31st annual meeting on Association for Computational Linguistics

We present an implemented unification-based parser for relational grammars developed within the stratified feature grammar (SFG) framework, which generalizes Kasper-Rounds logic to handle relational grammar analyses. We first introduce the key aspects ...
Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking
Special Issue on Concurrency Specification and Programming (CS&P)

Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, ...
Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking
Special Issue on Concurrency Specification and Programming (CS&P)

Two recent developments in the field of formal languages are Parsing Expression Grammar (PEG) and packrat parsing. The PEG formalism is similar to BNF, but defines syntax in terms of recognizing strings, rather than constructing them. It is, in fact, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

DAC '89: Proceedings of the 26th ACM/IEEE Design Automation Conference

June 1989

839 pages

ISBN:0897913108

DOI:10.1145/74382

Chairman:
Donald E. Thomas
Carnegie Mellon Univ., Pittsburgh, PA

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

DAC89

Sponsor:

IEEE-CS\TCDA
SIGDA

DAC89: The 26th ACM/IEEE-CS Design Automation Conference

June 25 - 28, 1989

Nevada, Las Vegas, USA

Acceptance Rates

DAC '89 Paper Acceptance Rate 156 of 465 submissions, 34%;

Overall Acceptance Rate 1,770 of 5,499 submissions, 32%

Upcoming Conference

DAC '25

Sponsor:
sigda

62nd ACM/IEEE Design Automation Conference

June 22 - 26, 2025

San Francisco , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

7
Total Citations
View Citations
281
Total Downloads

Downloads (Last 12 months)52
Downloads (Last 6 weeks)7

Reflects downloads up to 14 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Jäschke CHerter UWolkober CSchmitt CZoellin C(2017)Static netlist verification for IBM high-frequency processors using a tree-grammarProceedings of the Conference on Design, Automation & Test in Europe10.5555/3130379.3130742(1556-1561)Online publication date: 27-Mar-2017
https://dl.acm.org/doi/10.5555/3130379.3130742
Jaschke CHerter UWolkober CSchmitt CZoellin C(2017)Static netlist verification for IBM high-frequency processors using a tree-grammarDesign, Automation & Test in Europe Conference & Exhibition (DATE), 201710.23919/DATE.2017.7927237(1552-1557)Online publication date: Mar-2017
https://doi.org/10.23919/DATE.2017.7927237
Bamji CAllen J(1994)GLOVE: a graph-based layout verifierProceedings of 7th International Conference on VLSI Design10.1109/ICVD.1994.282688(215-220)Online publication date: 1994
https://doi.org/10.1109/ICVD.1994.282688
Peltz GSchweikert D(1992)An interpreter for general netlist design rule checkingProceedings of the 29th ACM/IEEE Design Automation Conference10.5555/113938.149465(305-310)Online publication date: 1-Jul-1992
https://dl.acm.org/doi/10.5555/113938.149465
Pelz G(1992)An interpreter for general netlist design rule checking[1992] Proceedings 29th ACM/IEEE Design Automation Conference10.1109/DAC.1992.227788(305-310)Online publication date: 1992
https://doi.org/10.1109/DAC.1992.227788
Greenbaum JBrewer F(1991)Interface constrained processor specification and scheduling[1992] Proceedings of the Second Great Lakes Symposium on VLSI10.1109/GLSV.1992.218349(168-175)Online publication date: 1991
https://doi.org/10.1109/GLSV.1992.218349
Allen J(1990)Performance-directed synthesis of VLSI systemsProceedings of the IEEE10.1109/5.5221678:2(336-355)Online publication date: Jan-1990
https://doi.org/10.1109/5.52216

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A unification-based parser for relational grammar

Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking

Parsing Expression Grammar as a Primitive Recursive-Descent Parser with Backtracking