Как написать 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.