Writing about pratt parsing so I remember it

2 comments

• mjbq1 hour ago
  Could I suggest also looking at a sed-inspired parsing language (a DSL) which is called nom and is documented at <a href="http:&#x2F;&#x2F;www.nomlang.org" rel="nofollow">http:&#x2F;&#x2F;www.nomlang.org</a> An example script for parsing symbolic expressions is at <a href="http:&#x2F;&#x2F;www.nomlang.org&#x2F;eg&#x2F;maths.parse.pss" rel="nofollow">http:&#x2F;&#x2F;www.nomlang.org&#x2F;eg&#x2F;maths.parse.pss</a> and another which turns the expressions into LaTeX is &#x2F;eg&#x2F;maths.tolatex.pss<p>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 &quot;lookahead&quot; syntax, a negated lookahead syntax (eg: &quot;parse this as an expression if it is not followed by a multiply operator&quot;). Also, Syntagma has a &quot;condition&quot; syntax, meaning that a parse rule will only reduce if the attributes of the parse tokens match certain conditions.<p>An example of an expression parser written in Syntagma is at <a href="http:&#x2F;&#x2F;www.nomlang.org&#x2F;syntagma&#x2F;eg&#x2F;expr.sta" rel="nofollow">http:&#x2F;&#x2F;www.nomlang.org&#x2F;syntagma&#x2F;eg&#x2F;expr.sta</a> This is much more succinct than the equivalent nom script. The script &#x2F;syntagma&#x2F;eg&#x2F;expr.toforth.sta converts symbolic expressions (and assignments) into Forth.<p>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).
• jstanley4 hours ago
  Personally I never found the shunting yard algorithm very intuitive at all.<p>A recursive descent parser makes much more sense to me.
  • throw-qqqqq2 hours ago
    For me, the win is that a Pratt parser is more data-driven.<p>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.<p>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.
    • bonzini1 hour ago
      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.
    • arnsholt1 hour ago
      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.
      • throw-qqqqq1 hour ago
        I think of it as expressions vs statements, but I think we agree.<p>Lexing for tokenization -&gt; recursive descent for statements -&gt; Pratt parsing for expressions.<p>S-Expressions and prefix-notation are so easy to work with (compared to in-fix IMO), because the precedence is explicit.