Parsing is much simpler than you think!

Показать описание

Sam H Smith

Рекомендации по теме

Комментарии

This is the technique jon blow recently presented right? Its a nice concise description of it.

krystofjakubek

Recursion is a good way to think about this problem. What I believe you are trying to describe is called "recursive descent parsing". Commonly described using context-free grammar rules which are similar to more commonly known regular expressions.
Addition and subtraction with parentheses and unary negation would look like this:

A = M ('+' M)*
M = T ('*' T)*
T = ('-'|) (number | '(' A ')')
(* means the previous term can be repeated none to any times and | imeans that an expression from either side can occur there)

A representing an additive expression, M a multiplicative expression, and T a term expression. Each expression has its own function returning a numerical value.
The parser would evaluate the input as an additive expression. When encountering M, it would recursively call the evaluation of the multiplicative expression, and again with T. The third function now either reads a number or open parenthesis, in the latter case recursing once again to the top before reading the closing parenthesis.
Returning from a function will occur when the regular expression no longer fits the input (ie. in M when there is no '*' after returning from T). The A and M terms then accumulate the returned values.

This blew my mind when I learned about this from a homework assignment, especially how simple it was to implement. Shame it is so rarely talked about.

hhehe

i think there is value in the shunting yard method too, especially if you are writing an encoder rather than an interpreter.

androth

2:33 Pretty sure that 4+5*6 is not 34 factorial (sarcasm)

alexdiezg

Parsing is insanely easy... it just becomes kinda tedious. Definitely not as tedious as a lexer or a code analyzer though. 😅

oglothenerd

Now talk about type checking/inference next :P

omega_sine

Thank you. I humbly ask for one more favor: script your videos. They do have real substance, but are rather difficult to listen/follow.

toomasvendelin

Parsing is much simpler than you think!

Parsing is much simpler than you think!

How to parse a file - Matt Ellis

Faster apps with JSON.parse (Chrome Dev Summit 2019)

Introduction to Parsers

Parsing JSON Really Quickly: Lessons Learned

Parsing with Pest: Fun with Grammar based parsing on timesheets

Parse only exactly what you need with LlamaParse parsing instructions

Daniel Spiewak: Fun With Parsing - λC 2017 Winter Retreat

The Journey To Replace Python's Parser And What It Means For The Future

Bitwise Day 5: Ion Parser/AST Code Review

Patrick Dubroy: Parsing, Compiling, and Static Metaprogramming -- JSConf EU 2013

Create a Programming Language - Episode 7: Parsing All Primary Expressions

Marja Hölttä: Parsing JavaScript - better lazy than eager? | JSConf EU 2017

Starting Simple Scene File Parsing - (Kohi Ep. 101, Live Stream 2023.03.29)

Rust Simple Dummy Tiny Rust Parser

A Verified Packrat Parser Interpreter for Parsing Expression Grammars

Create a Programming Language - Episode 6: Parser and Nodes

Scala Parser Combinators: The Easier Way to Create an External DSL - Lior Schejter

Monadic Parser in Scala - Wix Tech Talks

The Marpa Parser

Parsing Expression Grammar (PEG) [07]: Parsing Method Definitions

Hadoop : XML Parsing with MapReduce | MapReduce Tutorial | Big Data Tutorial For Beginners | Edureka

Challenge 159|Alteryx – Parsing Patterns with Regex

One Hour Coding Challenge: Parse a Functional Language 1/4