2026-07-21T14:17:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10874 2024-03-06T10:30:44Z ddc:004 open_access

Definite Clause Grammars with Parse Trees: Extension for Prolog Nogatz, Falco Seipel, Dietmar Abreu, Salvador Definite Clause Grammar Prolog Term Expansion Parse Tree EBNF 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Falco Nogatz and Dietmar Seipel and Salvador Abreu 2019 Is Part Of OASIcs, Volume 74, 8th Symposium on Languages, Applications and Technologies (SLATE 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.SLATE.2019.7 urn:nbn:de:0030-drops-108743 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SLATE.2019.7 eng https://creativecommons.org/licenses/by/3.0/legalcode