Functional Parsing - Computerphile

TL;DR

Functional parsing involves creating parsers that take a string of characters and output a tree that represents the structure of the input.

Transcript

okay so today we're going to do some more live coding and we're going to talk about something which is quite close to my heart because i wrote some of the early papers on it many years ago and that's something called functional parsing or combinator parsing before we get started with the actual live coding i want to begin with a question and the qu... Read More

Key Insights

• 🌲 Parsers are programs that take a string of characters and produce a tree representing the structure in the input.
• 📚 Combinator parsing or functional parsing libraries provide the tools to implement parsers in programming languages.
• 🏛️ Parsers can be built using basic primitives such as parsing single digits or characters.
• 👻 Combining forms like repetition and choice allow for more complex parsing patterns.
• 🪈 Sequencing is a common operation in parsing, where parsers are combined to parse elements in a specific order.
• 👻 Parsers can be implemented and evaluated simultaneously, allowing for both parsing and processing of the input.
• 💁 The structure of a grammar for a language can be translated directly into a parser using the same basic elements and combining forms.

Questions & Answers

Q: What is a parser?

A parser is a program that takes a string of characters and outputs a tree that represents the structure in the input.

Q: How can parsers be implemented in programming languages?

Parsers can be implemented using libraries like combinator parsing or functional parsing, which provide basic building blocks and combining forms for creating parsers.

Q: What are some basic primitives used in parsing?

Some basic primitives used in parsing are parsing single digits, parsing single characters, and parsing specific symbols or keywords.

Q: What are some common combining forms used in parsing?

Some common combining forms used in parsing are repetition (parsing one or more occurrences of a specific element), choice (parsing one of multiple possible elements), and sequencing (parsing multiple elements in a specific order).

Summary & Key Takeaways

• A parser is a program that takes a string of characters and produces a tree that represents the structure in the input.

• Parsers can be implemented in programming languages using libraries like combinator parsing or functional parsing.

• Parsers can be built using basic primitives such as parsing single digits or characters, as well as combining forms like repetition, choice, and sequencing.