Object-Oriented Parser Combinators

This lecture introduces the concept of object-oriented parser combinators, which are used to build parsers in Scala. The instructor explains the basic idea in code, the structure of parser classes, and the implementation of parsers for different types of tokens. The lecture covers the development of an embedded DSL for parsing in Scala, the creation of specific single-token parsers, and the use of combinator parsers for sequential and alternative composition. Additionally, the lecture delves into the implementation of parsers for JSON data and provides examples of testing and improving the JSON parser. The instructor concludes by discussing the advantages of combinator parsers over classical parser generators and the challenges of top-down parsing.

About this result

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related lectures (9)

Related concepts (59)

CS-452: Foundations of software

The course introduces the foundations on which programs and programming languages are built. It introduces syntax, types and semantics as building blocks that together define the properties of a progr

Parser combinator

In computer programming, a parser combinator is a higher-order function that accepts several parsers as input and returns a new parser as its output. In this context, a parser is a function accepting strings as input and returning some structure as output, typically a parse tree or a set of indices representing locations in the string where parsing stopped successfully. Parser combinators enable a recursive descent parsing strategy that facilitates modular piecewise construction and testing.

Parsing expression grammar

In computer science, a parsing expression grammar (PEG) is a type of analytic formal grammar, i.e. it describes a formal language in terms of a set of rules for recognizing strings in the language. The formalism was introduced by Bryan Ford in 2004 and is closely related to the family of top-down parsing languages introduced in the early 1970s. Syntactically, PEGs also look similar to context-free grammars (CFGs), but they have a different interpretation: the choice operator selects the first match in PEG, while it is ambiguous in CFG.

Top-down parsing

Top-down parsing in computer science is a parsing strategy where one first looks at the highest level of the parse tree and works down the parse tree by using the rewriting rules of a formal grammar. LL parsers are a type of parser that uses a top-down parsing strategy. Top-down parsing is a strategy of analyzing unknown data relationships by hypothesizing general parse tree structures and then considering whether the known fundamental structures are compatible with the hypothesis.

Parsing

Parsing, syntax analysis, or syntactic analysis is the process of analyzing a string of symbols, either in natural language, computer languages or data structures, conforming to the rules of a formal grammar. The term parsing comes from Latin pars (orationis), meaning part (of speech). The term has slightly different meanings in different branches of linguistics and computer science. Traditional sentence parsing is often performed as a method of understanding the exact meaning of a sentence or word, sometimes with the aid of devices such as sentence diagrams.

Recursive descent parser

In computer science, a recursive descent parser is a kind of top-down parser built from a set of mutually recursive procedures (or a non-recursive equivalent) where each such procedure implements one of the nonterminals of the grammar. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes. A predictive parser is a recursive descent parser that does not require backtracking.

Parsing with Combinators CS-210: Functional programming

Explores parsing text into trees using parser combinators in Scala, covering filtering, transforming, sequencing, alternatives, recursion, spaces handling, lexing, monadic nature, and for-notation.

CYK Parsing Algorithm for General Grammars CS-320: Computer language processing

Introduces the CYK parsing algorithm for context-free grammars, explaining its handling of ambiguity and importance in parsing general grammars.

Standard Model Overview

Provides an in-depth analysis of the Standard Model, covering topics such as the Higgs mechanism, gauge boson interactions, and the role of chirality in particle physics.

Syntactic Parsing and Graph2Graph Transformers EE-608: Deep Learning For Natural Language Processing

Covers syntactic parsing, dependency grammar, and graph-based neural network parsing.

Syntactic Parsing: Dependency Structure

Covers syntactic structure, dependency parsing, and neural network transition-based parsing, highlighting the importance of dependency structure in linguistic analysis.