Handling epsilon productions in recursive descent parsing

Question

I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions:

# APPLICATION  -> ATOM APPLICATION'
# APPLICATION' -> ATOM APPLICATION' | ε       

Both APPLICATION and APPLICATION' correspond to the same type of node in the AST. How should I handle parsing the second production? I know that choosing between two alternatives for a production is performed by looking up the next token in buffer, but the epsilon production confuses me.

EDIT:

Here is current implementation (Ruby) that fails to left-associate applications.

require_relative 'token.rb'
require_relative 'ast.rb'

class Parser
    def self.call(tokens)
        new(tokens).send(:parse_expr)
    end

    def self.to_proc
        method(:call).to_proc
    end

    private
        def initialize(tokens)
            @tokens = tokens
            @l = -1
        end

        def parse_expr
            if lookahead.type == :tklambda
                return ExprNode.new([parse_abstraction], @l)
            else
                return ExprNode.new([parse_application], @l)
            end
        end

        def parse_abstraction
            match_token(:tklambda)
            id = parse_identifier
            match_token(:tkdot)
            expr = parse_expr
            return AbstrNode.new([id, expr], @l)
        end

        def parse_identifier
            id_token = match_token(:tkid)
            val = id_token.value
            return IdNode.new(nil, @l, val)
        end

        def parse_application
            left_child = parse_atom
            first_atom = [:tklparen, :tkid] # FIRST(ATOM)
            # application -> atom application'
            while !lookahead.nil? and first_atom.include?(lookahead.type)
                return AppNode.new([left_child, parse_application], @l)
            end
            # application' -> atom application' | ε
            return left_child
        end

        def parse_atom
            if lookahead.type == :tklparen
                match_token(:tklparen)
                expr = parse_expr
                match_token(:tkrparen)
                return AtomNode.new([expr], @l)
            else
                return AtomNode.new([parse_identifier], @l)
            end
        end

        def match_token(type = nil)
            if !type.nil? and lookahead.type != type
                raise "Unexpected token at #{@l + 1}. Expected: #{type}, "\
                      "got: #{lookahead.type}."
            end
            @l += 1
            return @tokens[@l]
        end

        def lookahead
            return @tokens[@l + 1]
        end
end

Answer 1

You need to know FOLLOW(APPLICATION'), and it has to be disjoint to FIRST (ATOM).

Actually, you only have to know that the sets are disjoint, in which case the epsilon action becomes the default.

Personally, I wouldn't bother with two functions:

Application:
    v := Atom()
    if lookahead token in FIRST(ATOM):
        return ApplyNode(v, Application())
    else:  (* default case *)
        return v

That corresponds with your grammar, but it might not correspond with your intended language. Normally, lambda application is left-associative, not right-associative, but of course it is impossible to express left-associative expressions with an LL(k) grammar. Fortunately, it is easy to write a recursive descent parser which left-associates. That's usually done with a local variable and a while loop: (Technically, the parser is doing a tree-rewrite in order to fix the associativity, but the mechanism is so simple that hardly anyone sees that it is even there.)

  Application:
     v := Atom()
     while lookahead token is in FIRST(Atom):
         v := ApplyNode(v, Atom())
     return v