Parser Testing

I spent about 4 hours testing and debugging the recursive decent parsing algorithm, trying to understand the flow by writing each and every step. Here are my test cases.

Test case-1

exp = 2+3*4
tokens = ['2', '+', '3', '*', '4']
expected result = ('+', 2, ('*', 3, 4))

• This test case was used so that i can better understand parse_add and parse_mul along with the main parse_atom.
• Reached the correct answer.
• Found a bug in approach: I was not handling the case when pos was out of index ideally.
• Researched a bit on RDP and found out there is a basic template used in RDP which is while pos < len(tokens) ... and thus used this refined knowledge in my successive attempts.

Test case-2

exp = 2+3+4+5
tokens = ['2', '+', '3', '+', '4', '+', '5']
expected result = ('+', ('+', ('+', 2, 3), 4), 5)

• This specific test case defines why a while loop is important as it includes accumulation of same operator.
• I wanted to work through this by hand as I was really confused why we need a while loop instead of a simple if-else check whether the pos is out of range or not but the answer became clean when i worked through it.
• Reached the correct answer.

Test case-3

exp = (2+3)*4+1
tokens = ['(', '2', '+', '3', ')', '*', '4', '+', '1']
expected result = ('+', ('*', ('+', 2, 3), 4), 1)

• I used this test case as it introduces parenthesis into the parsing algorithm which is a fundamental feature.
• correctly worked through the parsing and reached the correct answer.

Parser

• I also completed the v1 of the parser in just 20 minutes. It is pretty hilarious that it took me 4 hours just to understand RDP but 20 minutes to code it. But, I believe those were 4 hours well spend because earlier, I found RDP to be mind breaking, but now I understand it so well that I think I can teach it even to a 12 year old.