Elamur Research⌕
☰
home / papers / 2021 / BINGO: A Dependency Grammar Framework to Understand Hardware Specifications Written in English

BINGO: A Dependency Grammar Framework to Understand Hardware Specifications Written in English

Paper · 2021 · Rahul Krishnamurthy and Michael S. Hsiao

Summary

The paper targets automatic reading of hardware design specifications in English. Learned semantic parsers need many training examples, and existing rule-based translators only accept rigid word order. The authors present BINGO, a framework based on link grammar. Each lexical rule pairs a syntactic connector with a semantic link, which states the domain context a word may appear in and how meaning moves along the edge. Every word gets a chart: its rows are alternative readings, and its columns are the connection requirements each reading must meet. Parsing has two steps. First, cells are marked when both the syntactic and semantic constraints are satisfied. Then the parser looks for a single horizontal "BINGO row" that links all words. Declarative propagation rules are applied edge by edge in a transition-based manner to build semantic frames, which can become SystemVerilog Assertions when RTL signal names are present. On AMBA, memory-controller and UART specifications, the system handled varied word order. It also reports incomplete or ambiguous sentences instead of guessing, which matters when no executable design exists yet to check the output.

Key points

  • Syntactic connectors come from the link grammar of Sleator and Temperley. Semantic links reuse the same matching idea: identical propagation rule, opposite head/child polarity. A propagation rule has five colon-separated parameters.
  • 123 low-level RTL specifications from ARM AMBA documents were translated into SVA code. They took 30.2 s in total, about 245 ms each.
  • 113 high-level specifications from the AMBA 4 ACE protocol checker document were translated into semantic frames only, because they lack signal names.
  • 40 memory-controller and 40 UART specifications were manually extracted and rewritten for further testing.
  • Specs with many conjuncts were slowest; one AMBA sentence with a six-item coordination took about 2 s.
  • When no complete BINGO row exists, the spec is flagged as incomplete. When several complete rows exist, it is flagged as ambiguous.

Interesting ideas

  • I1. Give each word a table where rows are competing interpretations and columns are the attachments each reading still needs; a parse is a single choice of row per word that satisfies everyone at once.
  • I2. Use the parser's failure as a signal: zero full solutions means information is missing, and two or more means genuine ambiguity, so the system reports instead of guessing.
  • I3. Pair every syntactic connector with a semantic connector, and allow an edge only when both match, so domain knowledge prunes wrong prepositional and coordination attachments.
  • I4. Write meaning composition as small declarative rules fired per dependency edge, each saying what content the child contributes and which slot of the head's frame receives it.
  • I5. Let different phrasings map to the same frame by writing alternative link rules, instead of retraining a model, so word-order variants become cheap to support.

For Mova

How these ideas could serve Mova, our small open language model — its files, stages and tests:

  • I1 (tree): Such per-word requirement tables could act as an explainable checker on gparse or perceptron output, showing which word's need was left unmet.
  • I2 (answer): Readers could reply "the text does not say" or "this is ambiguous" with the specific missing or competing attachment, rather than forcing a guess.
  • I3 (frames): VerbNet role expectations could serve as semantic connectors that veto or rerank attachments before frames are built.
  • I4 (frames): A rule table keyed by UD relation and verb class would make each frame slot traceable to the exact edge and rule that filled it.
  • I5 (learn): Self-induced repair rules could be stored in this declarative edge-rule form, keeping learned fixes readable and testable against paraphrase sets.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 2The field of science this work belongs to (OpenAlex fields).Arts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 2Research subjects and languages the work is about.English · 2,263 worksGPU & parallel computing · 19 works

Cite

Cite as Rahul Krishnamurthy and Michael S. Hsiao. 2021. BINGO: A Dependency Grammar Framework to Understand Hardware Specifications Written in English. Proceedings of the Sixth International Conference on Dependency Linguistics (Depling, SyntaxFest 2021).

The paper itself, not this page. BibTeX from the library's record of the work.

@inproceedings{krishnamurthy2021bingo,
  title = {{BINGO: A Dependency Grammar Framework to Understand Hardware Specifications Written in English}},
  author = {Rahul Krishnamurthy and Michael S. Hsiao},
  booktitle = {Proceedings of the Sixth International Conference on Dependency Linguistics (Depling, SyntaxFest 2021)},
  year = {2021},
  url = {https://aclanthology.org/2021.depling-1.7/}
}

References

31 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. ARM, 2006. AMBA 3 AXI Protocol Checker User Guide. https://developer.arm.com/ documentation/dui0305/b/Assertion-Descriptions. ↗
  2. ARM, 2012. AMBA 4 ACE and ACE-Lite Protocol Checkers User Guide. https://developer.arm.com/ docs/dui0576/b/ace-and-ace-lite-protocol-assertion-descriptions. ↗
  3. Imran Sarwar Bajwa, Mark Lee, and Behzad Bordbar. 2012. Resolving syntactic ambiguities in natural language specification of constraints. In International Conference on Intelligent Text Processing and Computational Linguistics, pages 178–187. Springer. find
  4. Aishwarya Chhabra, Amit Sangroya, and C Anantaram. 2018. Formalizing and verifying natural language system requirements using petri nets and context based reasoning. In MRC@ IJCAI, pages 64–71. find
  5. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the 39th Annual ACM Southeast Conference, pages 95–102. find
  6. Marie-Catherine De Marneffe and Joakim Nivre. 2019. Dependency grammar. Annual Review of Linguistics, 5:197–218. find
  7. Aaron Dutle, César Muñoz, Esther Conrad, Alwyn Goodloe, Laura Titolo, Ivan Perez, Swee Balachandran, Dimitra Giannakopoulou, Anastasia Mavridou, and Thomas Pressburger. 2020. From requirements to autonomous flight: An overview of the monitoring icarous project. In Matt Luckcuck and Marie Farrell, editors, Proceedings Second Workshop on Formal Methods for Autonomous Systems, Virtual, 7th of December 2020, volume 329 of Electronic Proceedings in Theoretical Computer Science, pages 23–30. Open Publishing Association. ↗
  8. Shalini Ghosh, Daniel Elenius, Wenchao Li, Patrick Lincoln, Natarajan Shankar, and Wilfried Steiner. 2016. Arsenal: automatic requirements specification extraction from natural language. In NASA Formal Methods Symposium, pages 41–46. Springer. find
  9. Dimitra Giannakopoulou, Thomas Pressburger, Anastasia Mavridou, and Johann Schumann. 2020. Generation of formal requirements from structured natural language. In International Working Conference on Requirements Engineering: Foundation for Software Quality, pages 19–35. Springer. find
  10. Daniel Gildea. 2001. Corpus variation and parser performance. In Proceedings of the 2001 Conference on Empirical Methods in Natural Language Processing.
  11. Jacob Gorban, 2002. UART ip core specification Architectures. http://www.isy.liu.se/edu/kurs/ TSEA44/OpenRISC/UART_spec.pdf. ↗
  12. Xiaodong Gu, Hongyu Zhang, Dongmei Zhang, and Sunghun Kim. 2016. Deep api learning. In Proceedings of the 2016 24th ACM SIGSOFT International Symposium on Foundations of Software Engineering, pages 631– 642. ↗
  13. Christopher B Harris and Ian G Harris. 2016. Glast: Learning formal grammars to translate natural language specifications into hardware assertions. In 2016 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 966–971. IEEE. find
  14. Michael S Hsiao. 2018. Automated program synthesis from object-oriented natural language for computer games. In Proceedings of the Sixth International Workshop on Controlled Natural Language (CNL), pages 71–74. ↗
  15. Michael S Hsiao. 2021. Multi-phase context vectors for generating feedback for natural-language based programming. In Proceedings of the Seventh International Workshop on Controlled Natural Language (CNL). find
  16. Oliver Keszocze and Ian G Harris. 2019. Chatbot-based assertion generation from natural language specifications. In 2019 Forum for Specification and Design Languages (FDL), pages 1–6. IEEE. find
  17. Rahul Krishnamurthy and Michael S Hsiao. 2019. Controlled natural language framework for generating assertions from hardware specifications. In 2019 IEEE 13th International Conference on Semantic Computing (ICSC), pages 367–370. IEEE. find
  18. Rahul Krishnamurthy and Michael S Hsiao. 2020. Transforming natural language specifications to logical forms for hardware verification. In 2020 IEEE 38th International Conference on Computer Design (ICCD), pages 393–396. IEEE. find
  19. Xi Victoria Lin, Chenglong Wang, Luke Zettlemoyer, and Michael D Ernst. 2018. Nl2bash: A corpus and semantic parser for natural language interface to the linux operating system. In Proceedings of the Eleventh International Conference on Language Resources and Evaluation (LREC 2018). find
  20. Anastasia Mavridou, Hamza Bourbouh, Dimitra Giannakopoulou, Thomas Pressburger, Mohammad Hejase, Pierre-Loic Garoche, and Johann Schumann. 2020. The ten lockheed martin cyber-physical challenges: formalized, analyzed, and explained. In 2020 IEEE 28th International Requirements Engineering Conference (RE), pages 300–310. IEEE. find
  21. Zifan Nan, Hui Guan, Xipeng Shen, and Chunhua Liao. 2021. Deep nlp-based co-evolvement for synthesizing code analysis from natural language. In Proceedings of the 30th ACM SIGPLAN International Conference on Compiler Construction, pages 141–152. find
  22. Alexis Nasr and Owen Rambow. 2004. A simple string-rewriting formalism for dependency grammar. In Proceedings of the Workshop on Recent Advances in Dependency Grammar, pages 17–24. find
  23. Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the eighth international conference on parsing technologies, pages 149–160.
  24. Sandip Ray, Ian G Harris, Goerschwin Fey, and Mathias Soeken. 2016. Multilevel design understanding: from specification to logic. In IEEE/ACM International Conference on Computer-Aided Design (ICCAD), pages 1–6. IEEE. find
  25. Daniel Sleator and Davy Temperley. 1991. Parsing english with a link grammar. carnegie mellon university computer science technical report cmu-cs-91-196. http://www.cs.cmu.edu/afs/cs.cmu.edu/ project/link/pub/www/papers/ps/tr91-196.pdf. ↗
  26. Daniel D Sleator and David Temperley. 1993. Parsing english with a link grammar. In Proceedings of the Third International Workshop on Parsing Technologies, pages 277–292.
  27. Mathias Soeken, Christopher B Harris, Nabila Abdessaied, Ian G Harris, and Rolf Drechsler. 2014. Automating the translation of assertions using natural language processing techniques. In Proceedings of the 2014 Forum on Specification and Design Languages (FDL), volume 978, pages 1–8. IEEE. find
  28. Srikanth Vijayaraghavan and Meyyappan Ramanathan. 2006. Sva for memories. In A practical guide for SystemVerilog assertions, chapter 5, pages 191–232. Springer US, Boston, MA. https://doi.org/10. 1007/0-387-26173-7_6. ↗
  29. Rongjie Yan, Chih-Hong Cheng, and Yesheng Chai. 2015. Formal consistency checking over specifications in natural languages. In 2015 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 1677–1682. IEEE. ↗
  30. Shiyu Zhang, Juan Zhai, Lei Bu, Mingsong Chen, Linzhang Wang, and Xuandong Li. 2020. Automated generation of ltl specifications for smart home iot using natural language. In 2020 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 622–625. IEEE. find
  31. Junchen Zhao and Ian G Harris. 2019. Automatic assertion generation from natural language specifications using subtree analysis. In 2019 Design, Automation & Test in Europe Conference & Exhibition (DATE), pages 598– 601. IEEE. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/krishnamurthy-2021-bingo-dependency-grammar-framework-understand/