grammar - 如何编写带有函数的 CFG？

Question

在一个作业中，我被要求为以下功能编写一个 CFG：

def f(x, y): 返回 x + y

def g(x, y): 返回 x – y

def h(x, y, z): 返回 x + y % z

def w(x, y, z): 返回 x * y – z

和

def h1(x, y, z): 返回 (x + y) % z

def h2(x, y, z): 返回 x + y % z

我试图将其作为普通 CFG 进行处理，但是对于函数定义和函数体，我无法做到这一点。我不太确定如何从这种 CFG 开始。

Answer 1

这是一个不好的问题 - 您通常不能在 CFG 中对“仅在函数体中使用参数”的规则进行编码。但是，忽略这个小问题，我们可以尝试：

S := def F (L): return E

F := CN
C := f | g | h | w
N := (empty string) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0

L := X | XY
X := x | y | z
Y := , L

E := X | E + E | E - E | E / E | E % E | E * E | (E)

S提供函数的整体结构。F定义如何制作函数名称。L定义如何制作变量列表。E定义如何制作涉及变量和运算符的表达式。请注意，这将允许类似的东西def f(x): return y，但您不能在 CFG 中阻止它。