#ifndef __PARSER_H__
#define __PARSER_H__

#include "lexer.h"
#include "astnode.h"

/*
 * The lexer must be initialized before calling any parser routines
 *
 * Implements the following (left-recursive) CFG, which is broken down below:
 *
 * program              -> block
 * block                -> { declarations statements }
 * declarations         -> declarations declaration | epsilon                                       // left recursion
 * declaration          -> type identifier ;
 * type                 -> int | char | uint                                     
 * statements           -> statements statement | epsilon                                           // left recursion
 * statement            -> identifier = or_expr; |
 *                         if ( or_expr ) statement |                                               // (*1) If/else ambiguity
 *                         if ( or_expr ) statement else statement |
 *                         while ( or_expr ) statement |
 *                         break;
 *                         block
 *
 *
 *
 * or_expr              -> or_expr || and_expr | and_expr                                           // (*2) Precedence; left recursion (see FACTORING too) 
 * and_expr             -> and_expr && eq_expr | eq_expr                                            // left recursion
 * eq_expr              -> eq_expr == rel_expr | eq_expr != rel_expr | rel_expr                     // left recursion
 * rel_expr             -> expr < expr | expr <= expr | expr >= expr | expr > expr | expr           
 * expr                 -> expr + term | expr - term | term                                         // left recursion
 * term                 -> term * unary | term / unary | unary                                      // left recursion
 * unary                -> ! unary | - unary | factor
 * factor               -> ( or_expr ) | identifier | intliteral | true | false
 
 Issue #1: If/else ambiguity.  We don't have to do anything about this, the recursive descent parser will try to match if/else as we would expect first
 (i.e. if we have ... if x else if y else z, it would step through this as : [if x] else --> fail, backtrack --> [if x else statement] -->
 [if x else [if y else z]] which is correct

 Issue #2: Precedence.  I.e., look at the expression a * b + c.  If we had expr -> expr + expr | exr * expr | identifier, we would parse this as expr * (expr + expr) --> 
 a * (b + c), this is wrong, so we "wrap" derivations in multiple levels, as you can see above, we'd have expr -> expr + term | term and term -> term * var
 so for instance, we'd parse this as [a * b + c] --> [a * b] + [c], i.e. the lowest recursion depth has the lowest precedence

 Issue #3: LEFT RECURSION.  We have to rewrite the grammar to fix these issues, which isn't that hard.  There's multiple ways to do this.

 Each left recursive grammar is either of the form
 (1) E -> E T
 (2) E -> E + T

 Which have the following equivalent right recursive grammars:
 (1) E -> T E
 (2) E -> T + E

*/

// returns NULL on failure
struct astnode* parse();
void freeast(struct astnode* node);
void printast(struct astnode* node);

#endif