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:


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.


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 

CFG – Left factoring in recursive nested productions

I’m attempting to convert a CFG into an LL(1) grammar for predictive parsing in a compiler. I’ve been able to left factor and eliminate left recursion and ambiguity for every case in the grammar, with the follow exception. I’ve provided the simplest case to illustrate the problem below.

S -> a b S | T T  -> a c T | d T | ϵ 

This grammar rightly generate a FIRST(S)FIRST(T) clash, as both S and T can generate a as a first terminal.

One (clearly wrong) attempt to left-factor the a terminal was to substitute T into the S production.

S -> a b S | a c S | d S | ϵ 

This would allow for left factoring like so:

S -> a U | d S | ϵ U -> b S | c S 

However, this grammar is no longer equivalent, as it would accept the string acab when the original grammar would not.

I’m hoping that there is some way to manipulate this grammar that I’m not aware of to eliminate the FIRST(S) and FIRST(T) clash. Is there a method to left-factor a terminal in recursive nested productions as is described above?