Engineering and Materials and Computing and Informatics Research Centres Seminar

Computing Seminar: Generalised Parsing as Descriptor Processing

Event icon
Seminars

As part of the School of Science and Technology Joint seminar programme for the Engineering and Materials and Computing and Informatics Research Centres, L. Thomas van Binsbergen, Royal Holloway, University of London, presents: Computing Seminar: Generalised Parsing as Descriptor Processing.

  • From: Wednesday 7 June 2017, 1 pm
  • To: Wednesday 7 June 2017, 2 pm
  • Location: CELS015, CELS, Nottingham Trent University, Clifton Campus, Clifton Lane, Nottingham, NG11 8NS

Past event

Event details

As part of the School of Science and Technology Joint seminar programme for the Engineering and Materials and Computing and Informatics Research Centres, L. Thomas van Binsbergen, Royal Holloway, University of London, presents: Computing Seminar: Generalised Parsing as Descriptor Processing.

Abstract

Generalised parsing technologies are applicable to all context-free grammars including left-recursive and ambiguous grammars.  State of the art algorithms find and represent all possible derivations of an input string in cubic time and space.  Although originally studied in the context of natural language processing, generalised parsing has recently attracted the interest of programming language researchers.  The prospect is the principled development of parsers based on (often highly ambiguous) abstract syntax grammars that emphasise semantics rather than syntax.  The renewed interest has led to the proposal of several new approaches to top-down generalised parsing in particular.  Generalised parsers are used in language workbenches like `Spoofax`, semantic frameworks like `K`, and in several recent parser combinator libraries. Earley's algorithm (1970) is a generalised parsing algorithm that can be seen as a generalisation of basic top-down parsing (recursive descent).  GLL Parsing (2010,2013) is a technique for (manually or mechanically) writing generalised top-down parsers. The GLL parsers implement the GLL algorithm which has many similarities to Earley's algorithm.  Both algorithms use "descriptors" that contain information to uniquely identify the state of a parser.  Processing a descriptor results in an arbitrary number of new descriptors that require processing, whereas a deterministic parser always moves from one state to a unique other.  In this talk we present a high-level generalised parsing algorithm called CDS based on descriptor processing.  We explain Earley's algorithm and the RGLL algorithm (2016) as specialisations of CDS, thus highlighting their commonalities and differences.  The framework in which we explain these algorithms can also be used to compare the algorithms underlying parser combinator libraries for generalised parsing.

All welcome.

This seminar will be hosted by Dr Neil Sculthorpe and Dr Richard Cant.

Location details

Room/Building:

CELS015, CELS

Address:

Nottingham Trent University
Clifton Campus
Clifton Lane
Nottingham
NG11 8NS

Past event

Still need help?

+44 (0)115 941 8418