Undershoot: Parsing theory in 1965

At the end, Kegler links to this comprehensive overview of the history of parsing:<p><a href="https:&#x2F;&#x2F;jeffreykegler.github.io&#x2F;personal&#x2F;timeline_v3" rel="nofollow">https:&#x2F;&#x2F;jeffreykegler.github.io&#x2F;personal&#x2F;timeline_v3</a><p>which contains this easily overlooked but IMHO extremely significant statement:<p>&quot;a recursive descent implementation can parse operator expressions as lists, and add associativity in post-processing&quot;<p>Personally, it has always seemed like a no-brainer to me that this is clearly the Right Answer. It is a mystery to me that the computing world at large has spent so much effort on a problem whose solution is actually very straightforward if you just give in on one tiny little piece of theoretical purity.<p>See <a href="http:&#x2F;&#x2F;www.flownet.com&#x2F;ron&#x2F;lisp&#x2F;parcil.lisp" rel="nofollow">http:&#x2F;&#x2F;www.flownet.com&#x2F;ron&#x2F;lisp&#x2F;parcil.lisp</a> for my own implementation of such a parser. As you will see if you count LOCs, it&#x27;s very, very simple by parser standards, and yet it handles all the &quot;hard&quot; problems: associativity, precedence, infix and prefix operators.

The thing is that writing a parser requires that a person to understand what a formal language is. Overall, only a subset of programmers understand even this, so parsing has a certain inherent hardness to it (you can&#x27;t just use a library or just use an object).<p>Of course, the problem of how to create a parser is solvable any number of ways if you mean how to convert an unambiguously specified formal language into a parser. But that doesn&#x27;t mean basic challenges don&#x27;t remain. Especially because a formal language is hard to understand (and can be ambiguous) and because what one wants the language to actually do something, there is a further trickiness involved (you have to bridge interface between syntax and semantics). So which <i>way</i> to solve the problem of parsing become a complex decision. But it&#x27;s not so much &quot;we don&#x27;t know how to efficiently do this yet&quot; but rather &quot;there is no one-size fits all approach.&quot;

Superb website with loads of content.<p>This <a href="https:&#x2F;&#x2F;jeffreykegler.github.io&#x2F;personal&#x2F;timeline_v3" rel="nofollow">https:&#x2F;&#x2F;jeffreykegler.github.io&#x2F;personal&#x2F;timeline_v3</a> is also worth your time twofolds.

If parsing is &quot;complicated&quot;, then there&#x27;s another solution. Don&#x27;t play the game. Change the rules. Play a different game.<p>My understanding (and, since this is the Interwebs I will quickly be corrected if I&#x27;m wrong) is that Python is easy to parse; a lot of the battles about adding features to the language involve keeping the grammar simple.<p>And yet Python is eminently useful, despite being simple to parse.<p>I&#x27;m reminded of how we didn&#x27;t understand how to specify a simple grammar in the &quot;good old days&quot;. E.g. take ancient FORTRAN.<p>The for-loop in FORTRAN is actually called do. And you specify the end of the loop by numerical statement label (found in columns 1 thru 5). Thus:<p><pre><code> DO 10 I = 1, 7 some stuff here, loop done for I = 1,2,3,4,5,6,7 10 final line of loop </code></pre> But spaces aren&#x27;t significant. So if you write the following statement<p><pre><code> DO 10 I = (1, 7) </code></pre> You get something totally different. You set the value of the complex variable DO10I to (1,7). Bheech. Who wants to parse that? (And yet, there were very capable FORTRAN compilers back in the 1960s!)

I’m a little surprised that ANTLR and L* don’t make the list (ANTLR from the practitioner POV and L* from theory).

I&#x27;m sorry, but this is just rambling. He goes on about theorists and practitioners without actually saying anything about the problem at all. He doesn&#x27;t explain why he thinks the current state of the art isn&#x27;t the solution. What <i>does</i> he want to do that isn&#x27;t handled well?<p>There are many ways in which parsing can be improved in practice and theory. Actual technical aspects would be more interesting.