I am trying to write a recursive-descent parser for untyped lambda calculus. While researching the way of formulating the grammar, I managed to put together something like this:
without left-recursion: TERM -> APPLICATION | ABSTRACTION ABSTRACTION -> LAMBDA LCID DOT TERM APPLICATION -> ATOM APPLICATION' APPLICATION' -> ATOM APPLICATION' | ε ATOM -> LPAREN TERM RPAREN | LCID LCID -> 'a' | 'b' | ... | 'z' DOT -> '.' LAMBDA -> 'λ'
I assume that for writing the parser I do not necessarily need the productions that only expand into terminals.
Can this grammar be used to write a recursive descent parser that only does 1-token lookups? What would be the resulting AST for