Как написать CFG с функциями?

Question

В Assignment, меня попросили написать CFG для функций, таких как:

четкости Р (х, у): возвращение х + у

Защиту г (х, у): возвращение х - у

защиту ч (х, у, г): возвращение х + у% г

защиту ш (х, у, г): возвращение х * у - г

и

защиту h1 (x, y, z): return (х + у)% г

Защиту h2 (х, у, г): возвращение х + у% г

Я пытался работать его как обычный 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.