As a reminder, here is the grammar for lambda calculus expressions: E xXx.E|EE|(E) The rules for...

 

Transcribed Image Text:

As a reminder, here is the grammar for lambda calculus expressions: E xXx.E|EE|(E) The rules for parsing with this (ambiguous) grammar are: Application is left associative, so "E E2 E2" is parsed as "(E E2) E3" Abstraction (A) extends as far right as possible, so "Ar.E E2" is parsed as "Ax. (E E)" E (E) is the grouping rule, so "(Ar.E1 E2) E3" is parsed as "(Ar.(E E2)) (E3)" 2. (9 points) Find the free variables in each of the following expressions: (a) xx.xzxy.ry (b) (Ax.xz)Ay.wAXw.wyzx (c) xx.xyxx.yx As a reminder, here is the grammar for lambda calculus expressions: E xXx.E|EE|(E) The rules for parsing with this (ambiguous) grammar are: Application is left associative, so "E E2 E2" is parsed as "(E E2) E3" Abstraction (A) extends as far right as possible, so "Ar.E E2" is parsed as "Ax. (E E)" E (E) is the grouping rule, so "(Ar.E1 E2) E3" is parsed as "(Ar.(E E2)) (E3)" 2. (9 points) Find the free variables in each of the following expressions: (a) xx.xzxy.ry (b) (Ax.xz)Ay.wAXw.wyzx (c) xx.xyxx.yx