The semantics of parsing with semantic actions

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

Abstract

The recovery of structure from flat sequences of input data is a problem that almost all programs need to solve. Computer Science has developed a wide array of declarative languages for describing the structure of languages, usually based on the context-free grammar formalism, and there exist parser generators that produce efficient parsers for these descriptions. However, when faced with a problem involving parsing, most programmers opt for ad-hoc hand-coded solutions, or use parser combinator libraries to construct parsing functions.
This paper develops a hybrid approach, treating grammars as collections of active right-hand sides, indexed by a set of non-terminals. Active right-hand sides are built using the standard monadic parser combinators and allow the consumed input to affect the language being parsed, thus allowing for the precise description of the realistic languages that arise in programming.

We carefully investigate the semantics of grammars with active right-hand sides, not just from the point of view of language acceptance but also in terms of the generation of parse results. Ambiguous grammars may generate exponentially, or even infinitely, many parse results and these must be efficiently represented using Shared Packed Parse Forests (SPPFs). A particular feature of our approach is the use of Reynolds-style parametricity to ensure that the language that grammars describe cannot be affected by the representation of parse results.
LanguageEnglish
Title of host publicationProceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012)
EditorsNachum Dershowitz
Publication statusAccepted/In press - 2012

Fingerprint

Context free grammars
Computer programming
Computer science
Semantics
Recovery

Keywords

  • semantics
  • parsing
  • parser generators

Cite this

Atkey, R. (Accepted/In press). The semantics of parsing with semantic actions. In N. Dershowitz (Ed.), Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012)
Atkey, Robert. / The semantics of parsing with semantic actions. Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012). editor / Nachum Dershowitz. 2012.
@inproceedings{2382fa242bb9409580d7ba579e096ded,
title = "The semantics of parsing with semantic actions",
abstract = "The recovery of structure from flat sequences of input data is a problem that almost all programs need to solve. Computer Science has developed a wide array of declarative languages for describing the structure of languages, usually based on the context-free grammar formalism, and there exist parser generators that produce efficient parsers for these descriptions. However, when faced with a problem involving parsing, most programmers opt for ad-hoc hand-coded solutions, or use parser combinator libraries to construct parsing functions.This paper develops a hybrid approach, treating grammars as collections of active right-hand sides, indexed by a set of non-terminals. Active right-hand sides are built using the standard monadic parser combinators and allow the consumed input to affect the language being parsed, thus allowing for the precise description of the realistic languages that arise in programming. We carefully investigate the semantics of grammars with active right-hand sides, not just from the point of view of language acceptance but also in terms of the generation of parse results. Ambiguous grammars may generate exponentially, or even infinitely, many parse results and these must be efficiently represented using Shared Packed Parse Forests (SPPFs). A particular feature of our approach is the use of Reynolds-style parametricity to ensure that the language that grammars describe cannot be affected by the representation of parse results.",
keywords = "semantics, parsing, parser generators",
author = "Robert Atkey",
year = "2012",
language = "English",
editor = "Nachum Dershowitz",
booktitle = "Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012)",

}

Atkey, R 2012, The semantics of parsing with semantic actions. in N Dershowitz (ed.), Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012).

The semantics of parsing with semantic actions. / Atkey, Robert.

Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012). ed. / Nachum Dershowitz. 2012.

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - The semantics of parsing with semantic actions

AU - Atkey, Robert

PY - 2012

Y1 - 2012

N2 - The recovery of structure from flat sequences of input data is a problem that almost all programs need to solve. Computer Science has developed a wide array of declarative languages for describing the structure of languages, usually based on the context-free grammar formalism, and there exist parser generators that produce efficient parsers for these descriptions. However, when faced with a problem involving parsing, most programmers opt for ad-hoc hand-coded solutions, or use parser combinator libraries to construct parsing functions.This paper develops a hybrid approach, treating grammars as collections of active right-hand sides, indexed by a set of non-terminals. Active right-hand sides are built using the standard monadic parser combinators and allow the consumed input to affect the language being parsed, thus allowing for the precise description of the realistic languages that arise in programming. We carefully investigate the semantics of grammars with active right-hand sides, not just from the point of view of language acceptance but also in terms of the generation of parse results. Ambiguous grammars may generate exponentially, or even infinitely, many parse results and these must be efficiently represented using Shared Packed Parse Forests (SPPFs). A particular feature of our approach is the use of Reynolds-style parametricity to ensure that the language that grammars describe cannot be affected by the representation of parse results.

AB - The recovery of structure from flat sequences of input data is a problem that almost all programs need to solve. Computer Science has developed a wide array of declarative languages for describing the structure of languages, usually based on the context-free grammar formalism, and there exist parser generators that produce efficient parsers for these descriptions. However, when faced with a problem involving parsing, most programmers opt for ad-hoc hand-coded solutions, or use parser combinator libraries to construct parsing functions.This paper develops a hybrid approach, treating grammars as collections of active right-hand sides, indexed by a set of non-terminals. Active right-hand sides are built using the standard monadic parser combinators and allow the consumed input to affect the language being parsed, thus allowing for the precise description of the realistic languages that arise in programming. We carefully investigate the semantics of grammars with active right-hand sides, not just from the point of view of language acceptance but also in terms of the generation of parse results. Ambiguous grammars may generate exponentially, or even infinitely, many parse results and these must be efficiently represented using Shared Packed Parse Forests (SPPFs). A particular feature of our approach is the use of Reynolds-style parametricity to ensure that the language that grammars describe cannot be affected by the representation of parse results.

KW - semantics

KW - parsing

KW - parser generators

UR - https://personal.cis.strath.ac.uk/~raa/semantic-actions.html

UR - http://www2.informatik.hu-berlin.de/lics/lics12/

M3 - Conference contribution book

BT - Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012)

A2 - Dershowitz, Nachum

ER -

Atkey R. The semantics of parsing with semantic actions. In Dershowitz N, editor, Proceedings of the Twenty-Seventh Annual ACM/IEEE Symposium on Logic In Computer Science (LICS 2012). 2012