Chapter 6: Parsing Expressions is little hard to follow

[naveen17797]

I have been stuck in this chapter for a week, i didnt build the interpreter in java, i was using a different language for the task, and i couldn't understand how the left recursive parser worked in that chapter, if you could demonstrate it with a sample series of tokens which where extracted from scanner, it would be more easier to understand.

[naveen17797]

Why it has to be equality rule? cant an expression be an assignment? like

int a = 3 * 5 / 6;

[fengxueem]

Hi naveen17797,

When I was reading this chapter, I took down every GRAMMER RULE, eg

expression     → equality ;

, mentioned in the book and placed them in the comment section of the source code. This helped me a lot when implementing these RULEs into real pragramming codes. You may try so, hope it will also be helpful for you to understand how a Recursive descent does its job. It's a great example of recursion algorithm and it takes time to fully master it. For the 2nd question:

Why it has to be equality rule? cant an expression be an assignment?

From my understanding, it's totally up to you, if we take a look at how C was designed (https://cs.wmich.edu/~gupta/teaching/cs4850/sumII06/The%20syntax%20of%20C%20in%20Backus-Naur%20form.htm), we will find an expression is, just like what's in your mind, an assignment. Bob, the auther, designed Lox in his way. And you can turn it into your way just as simple as

expression    → assignment ;
assignment    → equality ;

Of course, if the language is designed like so, there has to be functions to handle both assignment and equality, like these Java functions working inside Parser.java for Recursive descent

private Expr expression() {
    return assignment();
}

private Expr assignment() {
    Expr expr = equality();
    if (match(EQUAL)) {
        Expr value = assignment();
        ...
    }
    return expr;
}

private Expr equality() {
    Expr left = comparison();
    while(match(EQUAL_EQUAL, BANG_EQUAL)) {
        ...
    }
    return left;
}

And if you are interested, my modification to the Lox's grammer (just the expression part) is like

--- Expression ---
expression     → assignment ;
assignment     → ( call "." )? IDENTIFIER "=" assignment | comma ;
comma          → conditional ( "," conditional )* ;

--- Ternary operator ---
conditional    → logic_or ( "?" expression ":" conditional )? ;

--- Binary operators ---
logic_or       → logic_and ( "or" logic_and )* ;
logic_and      → equality ( "and" equality )* ;
equality       → comparison ( ( "!=" | "==" ) comparison )* ;
comparison     → addition ( ( ">" | ">=" | "<" | "<=" ) addition )* ;
addition       → multiplication ( ( "-" | "+" ) multiplication )* ;
multiplication → unary ( ( "/" | "*" ) unary )* ;

--- Unary operators ---
unary          → ( "!" | "-" ) unary | call ;
call           → primary ( "(" ( expression ( "," expression )* )? ")" | "." IDENTIFIER )* ;

--- Terminals ---
primary        → NUMBER | STRING | "false" | "true" | "nil" | "(" expression ")" | IDENTIFIER | "this" | "super" ;

[naveen17797]

Hi @fengxueem thanks for the explanation, lets say if i have a expression like this a = b + 1; and tokens we get from scanner would be ['a', '=', 'b', '1'] when i call the function expression(), it eventually calls assignment(). in this token array we have first element as 'a', and second element as '=', the match method in the book is written to match with the current token, so when you write if (match(EQUAL)) since the array pointer is pointing to character 'a', this would fail, we wouldn't find a EQUAL token if we try to match against the first element, this is what confuses me, how this is actually working, explaining it with a note stating how these methods are called would help to clarify the problem, sorry i couldn't wrap my head around this problem.

[naveen17797]

Nevermind, thanks for your help, this visualization helped me to understand the function calls

https://salimsah.github.io/Automata/cfg/Bilal_RecursiveDescentParser.html#form

[LevitatingBusinessMan]

for others, commenting down the syntax grammar before all of your parsing functions really help: So

    #comparison → addition ( ( ">" | ">=" | "<" | "<=" ) addition )*
    def self.comparison

Also once you are writing the code and trying it in the interpeter the syntax grammar starts making sense.

@naveen17797 You could close this issue now