Could I suggest also looking at a sed-inspired parsing language
(a DSL) which is called nom and is documented at http://www.nomlang.org
An example script for parsing symbolic expressions is at
http://www.nomlang.org/eg/maths.parse.pss and another which turns the
expressions into LaTeX is /eg/maths.tolatex.pss
Nom may seem quite verbose. I have written another language (which compiles
to nom) which I call Syntagma. The syntax of syntagma is much closer to
EBNF but also has powerful additions, such as a "lookahead" syntax, a
negated lookahead syntax (eg: "parse this as an expression if it is not
followed by a multiply operator"). Also, Syntagma has a "condition" syntax,
meaning that a parse rule will only reduce if the attributes of the
parse tokens match certain conditions.
An example of an expression parser written in Syntagma is at
http://www.nomlang.org/syntagma/eg/expr.sta This is much more succinct
than the equivalent nom script. The script /syntagma/eg/expr.toforth.sta
converts symbolic expressions (and assignments) into Forth.
Parsing is an interesting topic, but I feel that it is quite difficult
or non-intuitive with some of the traditional tools and methods (at
least for me).
For me, the win is that a Pratt parser is more data-driven.
It’s easy to look at a table or map of operators and their precedence and convince myself that it’s correct. A recursive descent parser needs to be very clearly structured to have similar clarity, IMO.
You can easily combine Pratt parsing with recursive descent, using the Pratt part only for expressions. FWIW, this is my favorite approach for parsing C.
The table-driven aspect is nice when you have user defined operators. I've used it inside a combinator based parser for a language with mixfix operators (e.g. _≡⟨_⟩_ ).
Lean4 takes this to an extreme and has "syntax categories" (e.g. expression), each of which has something like a pratt parser. Ambiguity is broken by taking the option that makes the most progress, and it is made efficient by memoization. You can add syntax at compile time, down to the lexing level. There is an example that adds HTML-like syntax and uses it later in the same file.
Pratt parsing, in its simplest form, is essentially an optimized recursive descent that uses lookahead to skip levels. Which as you say ends up being clearer too.
Yeah, for “normal” syntax I’d generally go for recursive descent, but for expression parsing with operator precedence I’d implement Pratt parsing if I had any say in the matter.
Could I suggest also looking at a sed-inspired parsing language (a DSL) which is called nom and is documented at http://www.nomlang.org An example script for parsing symbolic expressions is at http://www.nomlang.org/eg/maths.parse.pss and another which turns the expressions into LaTeX is /eg/maths.tolatex.pss
Nom may seem quite verbose. I have written another language (which compiles to nom) which I call Syntagma. The syntax of syntagma is much closer to EBNF but also has powerful additions, such as a "lookahead" syntax, a negated lookahead syntax (eg: "parse this as an expression if it is not followed by a multiply operator"). Also, Syntagma has a "condition" syntax, meaning that a parse rule will only reduce if the attributes of the parse tokens match certain conditions.
An example of an expression parser written in Syntagma is at http://www.nomlang.org/syntagma/eg/expr.sta This is much more succinct than the equivalent nom script. The script /syntagma/eg/expr.toforth.sta converts symbolic expressions (and assignments) into Forth.
Parsing is an interesting topic, but I feel that it is quite difficult or non-intuitive with some of the traditional tools and methods (at least for me).
Personally I never found the shunting yard algorithm very intuitive at all.
A recursive descent parser makes much more sense to me.
For me, the win is that a Pratt parser is more data-driven.
It’s easy to look at a table or map of operators and their precedence and convince myself that it’s correct. A recursive descent parser needs to be very clearly structured to have similar clarity, IMO.
You can easily combine Pratt parsing with recursive descent, using the Pratt part only for expressions. FWIW, this is my favorite approach for parsing C.
The table-driven aspect is nice when you have user defined operators. I've used it inside a combinator based parser for a language with mixfix operators (e.g. _≡⟨_⟩_ ).
Lean4 takes this to an extreme and has "syntax categories" (e.g. expression), each of which has something like a pratt parser. Ambiguity is broken by taking the option that makes the most progress, and it is made efficient by memoization. You can add syntax at compile time, down to the lexing level. There is an example that adds HTML-like syntax and uses it later in the same file.
https://github.com/leanprover/lean4/blob/0f2eaa6e776255083f9...
(I'm not saying changing the language on the fly is a good idea, but it's interesting that they pulled it off.)
Pratt parsing, in its simplest form, is essentially an optimized recursive descent that uses lookahead to skip levels. Which as you say ends up being clearer too.
Yeah, for “normal” syntax I’d generally go for recursive descent, but for expression parsing with operator precedence I’d implement Pratt parsing if I had any say in the matter.
I think of it as expressions vs statements, but I think we agree.
Lexing for tokenization -> recursive descent for statements -> Pratt parsing for expressions.
S-Expressions and prefix-notation are so easy to work with (compared to in-fix IMO), because the precedence is explicit.