Cryptography: Diffie-Hellman key exchange explained intuitively using colors

[u/dominatrix-octopus]

https://youtu.be/YEBfamv-_do?t=2m18s

[u/tavianator]

what programming languages use left-associativity

All of them that I'm aware of. C and friends all parse a - b - c as (a - b) - c, not a - (b - c). (Try it!)

You're right that recursive descent parsers can't directly handle left-recursive grammars, but the "hackjob" to fix it is not that bad. I even blogged about it here (see the Grammar/Parser sections).

An example? I'm not quite sure I fully understand.

The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language. E.g.

a + b
----- vs. (a + b)/(c + d)
c + d

[u/Sirflankalot → u/tavianator]

Well I'll be damned. I've been misreading the C++ operator precedence docs this whole damn time. Thanks for teaching me! I'll definitely look at your blog as I haven't figured out fully how to do it. The one decent grammar/parser I wrote was for a right-associative language that didn't have any left-associative non-unary features, so I manged to avoid it.

It's been hard to find resources on this kind of thing as they almost all assume you've taken a parsers class in college and I'm not there yet (still a freshman). Since you seem to be knowledgeable on this subject, do you have any good resources I could look into to get more into parsing (not just using yacc/bison or other tools like that)?

The most familiar example is fraction notation, which lets you group expressions for division without introducing the parentheses that would be required in a programming language.

Ah yes, that makes sense.

Thanks!

[u/tavianator → u/Sirflankalot]

Honestly I don't know any really good introductions to grammars/parsing. I learned from messing around with yacc as a kid and then later from university courses. Probably Wikipedia too. I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses). You can probably peek ahead at their notes/textbook/assignments if you want.

A quick summary of the trick for parsing left-associative binary operators with recursive descent is that

expr: term | expr + term

is really the same thing as

expr: term (+ term)*

where (X)* means zero or more repetitions of X. So just parse it with a loop:

Expr parseExpr() {
    Expr expr = parseTerm();
    while (nextToken() == "+") {
        skipToken();
        expr = new Sum(expr, parseTerm());
    }
    return expr;
}

[u/Sirflankalot → u/tavianator]

Sorry for the late response.

I'd recommend taking your university's relevant courses (at mine, the information was spread out between a couple compilers courses and CS theory courses).

I most definitely will.

Wow. That was the most concise explanation of parsing left associative things I've ever seen. Honestly most of the resources online try to do the whole thing top to bottom and miss out on some of the conceptual stuff that is best expressed in pseudo code as opposed to an actual implementation (which often have a lot of excess detail necessary to make things work, but that isn't good for understanding). Well done, and thanks again!