0
$\begingroup$

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
$\endgroup$
0
$\begingroup$

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
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jan Parzydło May 30 at 14:07
  • $\begingroup$ @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). $\endgroup$ – rici May 30 at 14:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.