Register
handmade.network Library

Parsing

Extracting meaning from text.

Article

  • (How to Write a (Lisp) Interpreter (in Python)) by Peter Norvig
    ★ 0 0
    Programming a basic Lisp interpreter in Python.
  • Avoiding branchy loops in lexers with FSMs
    ★ 0 0
    aka Some Strategies For Fast Lexical Analysis when Parsing Programming Languages, by Sean Barrett
  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
  • Eli Bendersky: Top-Down Operator Precedence Parsing
    ★ 0 0
    "The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
  • Expression Parsing
    ★ 0 0
    Details the Recursive Descent, Shunting Yard and Precedence Climbing parsing algorithms.
  • Faster Integer Parsing
    ★ 0 0
    Exploring fast ways of parsing integers from strings.
  • How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
    ★ 0 0
    "Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works." There is also a video version of this article: https://youtu.be/hqnTvuvXPCc

Blog

  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
  • Eli Bendersky: Top-Down Operator Precedence Parsing
    ★ 0 0
    "The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
  • How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
    ★ 0 0
    "Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works." There is also a video version of this article: https://youtu.be/hqnTvuvXPCc

Book

  • Build Your Own Lisp
    ★ 1 0
    Learn C and build a LISP interpretter using a parser combinator library written by the author

Paper

  • Parsing Gigabytes of JSON per Second
    ★ 0 0
    Abstract: JavaScript Object Notation or JSON is aubiquitous data exchange format on the Web. Ingesting JSON documents can become a performance bottleneck due to the sheer volume of data. We are thus motivated to make JSON parsing as fast as possible. Despite the maturity of the problem of JSON parsing, we show that substantial speedups are possible. We present the first standard-compliant JSON parser to process gigabytes of data per second on a single core, using commodity processors.

Repository

  • Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
    ★ 0 0
    In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP

YouTube Video

  • Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
    ★ 0 0
    In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP
  • How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
    ★ 0 0
    "Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works." There is also a video version of this article: https://youtu.be/hqnTvuvXPCc