# Handling epsilon productions in recursive descent parsing

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
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'
return AppNode.new([left_child, parse_application], @l)
end
# application' -> atom application' | ε
return left_child
end

def parse_atom
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}, "\
end
@l += 1
return @tokens[@l]
end

return @tokens[@l + 1]
end
end


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()
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

• It has been a while, but I implemented Application parsing the way you suggested (the left-associative version) and while it does work, it parses applications in right-associative manner. For example: ABC gets parsed as EXPR(APP(A, APP(B, C))). I'll edit the question and paste in the code for you to look at. May 30, 2019 at 14:07
• @jan: WHILE condition RETURN expr makes little sense; it might as well be an IF since it cannot execute more than once. That is not the while statement in my answer (which calls Atom, not Application).
– rici
May 30, 2019 at 14:17