Concept

Earley parser

Related publications (21)

Hearing structure in music: An empirical inquiry into listening as representation and processing

As a universal expression of human creativity, music is capable of conveying great subtlety and complexity. Crucially, this complexity is not encoded in the score or in the sounds, but is rather construed in the mind of the listener in the form of nuanced ...

EPFL2024

Musical Garden Paths: Evidence for Syntactic Revision Beyond the Linguistic Domain

Martin Alois Rohrmeier, Steffen Alexander Herff, Gabriele Cecchetti

While theoretical and empirical insights suggest that the capacity to represent and process complex syntax is crucial in language as well as other domains, it is still unclear whether specific parsing mechanisms are also shared across domains. Focusing on ...

Wiley2022

Efficient Parsing with Derivatives and Zippers

Romain Edelmann

Parsing is the process that enables a computer system to make sense of raw data. Parsing is common to almost all computer systems: It is involved every time sequential data is read and elaborated into structured data. The theory of parsing usually focuses ...

EPFL2021

Uniform parsing for hyperedge replacement grammars

Petter Harald Ericson

It is well known that hyperedge-replacement grammars can generate NP-complete graph languages even under seemingly harsh restrictions. This means that the parsing problem is difficult even in the non-uniform setting, in which the grammar is considered to b ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2021

Gramatron: Effective Grammar-Aware Fuzzing

Mathias Josef Payer

Fuzzers aware of the input grammar can explore deeper program states using grammar-aware mutations. Existing grammar-aware fuzzers are ineffective at synthesizing complex bug triggers due to: (i) grammars introducing a sampling bias during input generation ...

ASSOC COMPUTING MACHINERY2021

Modeling and Inferring Proto-Voice Structure in Free Polyphony

Martin Alois Rohrmeier, Christoph Finkensiep

Voice leading is considered to play an important role in the structure of Western tonal music. However, the explicit voice assignment of a piece (if present at all) generally does not reflect all phenomena related to voice leading. Instead, voice-leading p ...

ISMIR2021

Zippy LL(1) Parsing with Derivatives

Viktor Kuncak, Jad Hamza, Romain Edelmann

In this paper, we present an efficient, functional, and formally verified parsing algorithm for LL(1) context-free expressions based on the concept of derivatives of formal languages. Parsing with derivatives is an elegant parsing technique, which, in the ...

ASSOC COMPUTING MACHINERY2020

The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy

Lionel Emile Vincent Parreaux

MLsub extends traditional Hindley-Milner type inference with subtyping while preserving compact principal types, an exciting new development. However, its specification in terms of biunification is difficult to understand, relying on the new concepts of bi ...

2020

Annotated References in the Historiography on Venice: 19th–21st centuries

Matteo Romanello, Giovanni Colavizza

We publish a dataset containing more than 40’000 manually annotated references from a broad corpus of books and journal articles on the history of Venice. References were considered from both reference lists and footnotes, include primary and secondary sou ...

2017

LMS-Verify: Abstraction without Regret for Verified Systems Programming’

Tiark Rompf, Nada Amin

Performance critical software is almost always developed in C, as programmers do not trust high-level languages to deliver the same reliable performance. This is bad because low-level code in unsafe languages attracts security vulnerabilities and because d ...

Assoc Computing Machinery2017

Specialising Parsers for Queries

Manohar Jonnalagedda

Many software systems consist of data processing components that analyse large datasets to gather information and learn from these. Often, only part of the data is relevant for analysis. Data processing systems contain an initial preprocessing step that fi ...

EPFL2016

On Mining Citations to Primary and Secondary Sources in Historiography

Frédéric Kaplan, Giovanni Colavizza

We present preliminary results from the Linked Books project, which aims at analysing citations from the histo- riography on Venice. A preliminary goal is to extract and parse citations from any location in the text, especially footnotes, both to primary a ...

2015

Automating Grammar Comparison

Viktor Kuncak, Mikaël Mayer, Ravichandhran Kandhadai Madhavan

We consider from a practical perspective the problem of checking equivalence of context-free grammars. We present techniques for proving equivalence, as well as techniques for finding counter-examples that establish non-equivalence. Among the key building ...

2015

Interactive Synthesis using Free-Form Queries

Viktor Kuncak, Tihomir Gvero

We present a new code assistance tool for integrated development environments. Our system accepts free-form queries allowing a mixture of English and Java as an input, and produces Java code fragments that take the query into account and respect syntax, ty ...

2015

Query management system and engine allowing for efficient query execution on raw details

Anastasia Ailamaki, Ioannis Alagiannis, Renata Borovica-Gajic, Miguel Sérgio De Oliveira Branco

A database system maintains a feature set of a modern database system while operating directly on raw data files. Systems may use an adaptive indexing mechanism that maintains positional information to provide efficient access to raw data files, a flexible ...

2014

Staged parser combinators for efficient data processing

Martin Odersky, Tiark Rompf, Sandro Stucki, Manohar Jonnalagedda, Thierry Coppey

Parsers are ubiquitous in computing, and many applications depend on their performance for decoding data efficiently. Parser combinators are an intuitive tool for writing parsers: tight integration with the host language enables grammar specifications to b ...

ACM Press2014

Staged Parser Combinators for Efficient Data Processing

Martin Odersky, Tiark Rompf, Sandro Stucki, Manohar Jonnalagedda, Thierry Coppey

Assoc Computing Machinery2014

VLSI Implementation of a Low-Complexity LLL Lattice Reduction Algorithm for MIMO Detection

Andreas Peter Burg, Christoph Studer

Lattice-reduction (LR)-aided successive interference cancellation (SIC) is able to achieve close-to optimum error-rate performance for data detection in multiple-input multiple-output (MIMO) wireless communication systems. In this work, we propose a hardwa ...

Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa2010

Evaluation and Design Exploration of Solar Harvested-Energy Prediction Algorithm

David Atienza Alonso

To respond to variations in solar energy, harvestedenergy prediction is essential to harvested-energy management approaches. The effectiveness of such approaches is dependent on both the achievable accuracy and computation overhead of prediction algorithm ...

ACM/IEEE Press2010

Stationary Features and Cat Detection

François Fleuret

Most discriminative techniques for detecting instances from object categories in still images consist of looping over a partition of a pose space with dedicated binary classifiers. The efficiency of this strategy for a complex pose, i.e., for fine-grained ...

2008