Document Open Access Logo

Definite Clause Grammars with Parse Trees: Extension for Prolog

Authors Falco Nogatz, Dietmar Seipel, Salvador Abreu

PDF

File

Thumbnail PDF
PDF
OASIcs.SLATE.2019.7.pdf
  • Filesize: 0.53 MB
  • 14 pages

Document Identifiers

Subject Classification

ACM Subject Classification
  • Theory of computation → Grammars and context-free languages
Keywords
  • Definite Clause Grammar
  • Prolog
  • Term Expansion
  • Parse Tree
  • EBNF

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Abstract

Definite Clause Grammars (DCGs) are a convenient way to specify possibly non-context-free grammars for natural and formal languages. They can be used to progressively build a parse tree as grammar rules are applied by providing an extra argument in the DCG rule’s head. In the simplest way, this is a structure that contains the name of the used nonterminal. This extension of a DCG has been proposed for natural language processing in the past and can be done automatically in Prolog using term expansion.
We extend this approach by a meta-nonterminal to specify optional and sequences of nonterminals, as these structures are common in grammars for formal, domain-specific languages. We specify a term expansion that represents these sequences as lists while preserving the grammar’s ability to be used both for parsing and serialising, i.e. to create a parse tree by a given source code and vice-versa. We show that this mechanism can be used to lift grammars specified in extended Backus-Naur form (EBNF) to generate parse trees. As a case study, we present a parser for the Prolog programming language itself based only on the grammars given in the ISO Prolog standard which produces corresponding parse trees.

Cite As Get BibTex

Falco Nogatz, Dietmar Seipel, and Salvador Abreu. Definite Clause Grammars with Parse Trees: Extension for Prolog. In 8th Symposium on Languages, Applications and Technologies (SLATE 2019). Open Access Series in Informatics (OASIcs), Volume 74, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019) https://doi.org/10.4230/OASIcs.SLATE.2019.7

Author Details

Falco Nogatz
  • University of Würzburg, Department of Computer Science, Am Hubland, D - 97074 Würzburg, Germany
Dietmar Seipel
  • University of Würzburg, Department of Computer Science, Am Hubland, D - 97074 Würzburg, Germany
Salvador Abreu
  • LISP, Department of Computer Science, University of Évora, Portugal

Supplementary Materials

References

  1. ISO/IEC 13211-1:1995: Information technology - Programming languages - Prolog - Part 1: General core, 1995. Google Scholar
  2. ISO/IEC 13211-3:2006: Definite clause grammar rules, 2015. Google Scholar
  3. Harvey Abramson and Veronica Dahl. Logic Grammars. Symbolic Computation. Springer, 1989. Google Scholar
  4. Alain Colmerauer. Les grammaires de métamorphose. Technical report, Groupe d'Intelligence Artificielle, Université de Marseille-Luminy, 1975. Google Scholar
  5. Alain Colmerauer. Metamorphosis grammars. In Natural language communication with computers, pages 133-188. Springer, 1978. Google Scholar
  6. Alain Colmerauer. An Introduction to Prolog III. Communications of the ACM, 33(7):69-90, 1990. URL: https://doi.org/10.1145/79204.79210.
  7. Veronica Dahl and Michael C. McCord. Treating coordination in logic grammars. American Journal of Computational Linguistics, 9(2):69-80, 1983. Google Scholar
  8. Lynette Hirschman and Karl Puder. Restriction grammar: A Prolog implementation. Logic Programming and its Applications, pages 244-261, 1985. Google Scholar
  9. Falco Nogatz and Dietmar Seipel. Implementing GraphQL as a Query Language for Deductive Databases in SWI-Prolog Using DCGs, Quasi Quotations, and Dicts. In Proc. 30th Workshop on Logic Programming (WLP), 2016. Google Scholar
  10. Terence J. Parr and Russell W. Quong. ANTLR: A predicated-LL (k) parser generator. Software: Practice and Experience, 25(7):789-810, 1995. Google Scholar
  11. Fernando Pereira and David Warren. Definite clause grammars for language analysis - a survey of the formalism and a comparison with augmented transition networks. Artificial intelligence, 13(3):231-278, 1980. Google Scholar
  12. Christian Schneiker, Dietmar Seipel, Werner Wegstein, and Klaus Prätor. Declarative Parsing and Annotation of Electronic Dictionaries. In 6th International Workshop on Natural Language Processing and Cognitive Science (NLPCS), pages 122-132, 2009. Google Scholar
  13. Peter Van Roy. Extended DCG notation: A tool for Applicative Programming in Prolog. Technical Report UCB/CSD 90/583, Computer Science Division, UC Berkeley, 1990. Google Scholar
  14. Jan Wielemaker. An Overview of the SWI-Prolog Programming Environment. In Proc. 13th International Workshop on Logic Programming Environments (WLPE), pages 1-16, 2003. Google Scholar
  15. Jan Wielemaker. SWI-Prolog Reference Manual 7.6, 2017. Google Scholar
  16. Jan Wielemaker and Michael Hendricks. Why It’s Nice to be Quoted: Quasiquoting for Prolog. In Proc. 23rd Workshop on Logic-based Methods in Programming Environments (WLPE), 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact