Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Zippy LL(1) Parsing with Derivatives
 
conference paper

Zippy LL(1) Parsing with Derivatives

Edelmann, Romain  
•
Hamza, Jad  
•
Kuncak, Viktor  
January 1, 2020
Proceedings Of The 41St Acm Sigplan Conference On Programming Language Design And Implementation (Pldi '20)
41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

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 general case, suffers from cubic worst-case time complexity and slow performance in practice. We specialise the parsing with derivatives algorithm to LL(1) context-free expressions, where alternatives can be chosen given a single token of lookahead. We formalise the notion of LL(1) expressions and show how to efficiently check the LL(1) property. Next, we present a novel linear-time parsing with derivatives algorithm for LL(1) expressions operating on a zipper-inspired data structure. We prove the algorithm correct in Coq and present an implementation as a part of Scallion, a parser combinators framework in Scala with enumeration and pretty printing capabilities.

  • Details
  • Metrics
Type
conference paper
DOI
10.1145/3385412.3385992
Web of Science ID

WOS:000614622300069

Author(s)
Edelmann, Romain  
Hamza, Jad  
Kuncak, Viktor  
Date Issued

2020-01-01

Publisher

ASSOC COMPUTING MACHINERY

Publisher place

New York

Published in
Proceedings Of The 41St Acm Sigplan Conference On Programming Language Design And Implementation (Pldi '20)
ISBN of the book

978-1-4503-7613-6

Start page

1036

End page

1051

Subjects

Computer Science, Software Engineering

•

Computer Science, Theory & Methods

•

Computer Science

•

parsing

•

ll(1)

•

derivatives

•

zipper

•

formal proof

•

recognition

•

languages

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LARA  
Event nameEvent placeEvent date
41st ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI)

ELECTR NETWORK

Jun 15-20, 2020

Available on Infoscience
March 26, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/176252
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés