Introduced Combined Parsing

[ShadowXBoss696]

Kode was initially following a recursive descent parsing technique to design its parser mechanism, because of its simplicity and readability aspects. But this same technique backfired for expression parsing. This caused us to look for a new way to solve the problems.

According to Bob Nystrom,

When you’re writing a parser, recursive descent is as easy as spreading peanut butter. It excels when you can figure out what to parse based on the next bit of code you’re looking at. That’s usually true at the declaration and statement levels of a language’s grammar since most syntax there starts with keywords—class, if, for, while, etc.
Parsing gets trickier when you get to expressions. When it comes to infix operators like +, postfix ones like ++, and even mixfix expressions like ?:, it can be hard to tell what kind of expression you’re parsing until you’re halfway through it. You can do this with recursive descent, but it’s a chore. You have to write separate functions for each level of precedence (JavaScript has 17 of them, for example), manually handle associativity, and smear your grammar across a bunch of parsing code until it’s hard to see.

This article first sparked the idea in our mind, to combine two or more parsing techniques to solve each part independently and thus provide optimum efficiency.

So, I divided the parsing rules of Kode into 3 parts, namely

• Statements: All kinds of statements that can be effectively handled by recursive descent parsing, like class, if, for, while, etc.
• Expressions: All kinds of expressions involving addition, subtraction, multiplication, division, etc. which has specific precedence and associativity and are used to perform operations on operands. We used Pratt parsing to do expression parsing.
• Atoms: Here atoms do not signify the smallest unit of programing language viz., Tokens, rather it signifies the smallest unit of an expression i.e., Operands. Again for atoms, we fall back into our regular recursive descent parsing technique as we were using previously.

Reference: https://journal.stuffwithstuff.com/2011/03/19/pratt-parsers-expression-parsing-made-easy/