%0 Conference Paper %1 nogatz2019dcg4pt %A Nogatz, Falco %A Seipel, Dietmar %A Abreu, Salvador %B Proceedings of 8th Symposium on Languages, Applications, Technologies (SLATE) %D 2019 %K myown %P 7:1-7:14 %R 10.4230/OASIcs.SLATE.2019.7 %T Definite Clause Grammars with Parse Trees: Extension for Prolog %U http://drops.dagstuhl.de/opus/volltexte/2019/10874/ %V 74 %X 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. %@ 978-3-95977-114-6

@inproceedings{nogatz2019dcg4pt, 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.}, added-at = {2019-04-23T10:05:40.000+0200}, author = {Nogatz, Falco and Seipel, Dietmar and Abreu, Salvador}, biburl = {https://www.bibsonomy.org/bibtex/2f7f3d18b49836b87ad17a6c22439ff8a/falco.nogatz}, booktitle = {Proceedings of 8th Symposium on Languages, Applications, Technologies (SLATE)}, doi = {10.4230/OASIcs.SLATE.2019.7}, interhash = {f63e64d4d5e39965175c657507e61cc3}, intrahash = {f7f3d18b49836b87ad17a6c22439ff8a}, isbn = {978-3-95977-114-6}, issn = {2190-6807}, keywords = {myown}, pages = {7:1-7:14}, series = {OpenAccess Series in Informatics (OASIcs)}, timestamp = {2019-07-24T13:57:48.000+0200}, title = {Definite Clause Grammars with Parse Trees: Extension for Prolog}, url = {http://drops.dagstuhl.de/opus/volltexte/2019/10874/}, volume = 74, year = 2019 }