如何从 python PLY 中的方案解释 "do" 循环
How to interpret a "do" loop from scheme in python PLY
我正在使用 PLY (Python Lex-Yacc) 为 Scheme 做一个解释器，我无法使用堆栈中的值来实现 "do" 循环，该堆栈跟踪对应一个变量（比如循环的i）。
这是编译器设计课程的期末项目，主要问题是向堆栈添加值的那一刻，我使用字典将变量名作为键，然后作为值，但是它并没有在它应该被分配的那一刻被分配，相反，它试图在一个值和变量之间进行比较但是它失败了，因为堆栈仍然是空的。
这是代码中最重要的部分：
ids = { }
def p_program(p):
'program : form'
#return p
print(p[1])
def p_form_a(p):
'''
form : definition
| expression
'''
p[0] = p[1]
def p_expression(p):
'''
expression : constant
| do_expression
| ID
| display
'''
p[0] = p[1]
def p_do_expression_a(p):
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
'do_expression : OPEN_PAR DO OPEN_PAR ID constant OPEN_PAR symbol ID expression CLOSE_PAR CLOSE_PAR comparison_expression expression CLOSE_PAR'
ids[p[4]] = p[5]
aux = p[12]
while True:
expr = p[13]
if ((type(p[5]) == int and type(p[9]) == int)
or (type(p[5]) == int and type(p[9]) == float)
or (type(p[5]) == float and type(p[9]) == int)
or (type(p[5]) == float and type(p[9]) == float)):
if p[7] == '+': ids[p[4]] = ids[p[4]] + p[9]
elif p[7] == '-': ids[p[4]] = ids[p[4]] - p[9]
elif p[7] == '*': ids[p[4]] = ids[p[4]] * p[9]
elif p[7] == '/': ids[p[4]] = ids[p[4]] / p[9]
elif p[7] == 'remainder': ids[p[4]] = ids[p[4]] % p[9]
else:
print("Error: Type mismatch.")
sys.exit()
aux = p[12]
if aux == '#t':
break
p[0] = expr
def p_comparison_expression(p):
'comparison_expression : OPEN_PAR comparison expression expression CLOSE_PAR'
if type(p[3]) == str:
p[3] = ids[p[3]]
if type(p[4]) == str:
p[4] = ids[p[4]]
if p[2] == 'eq?':
if p[3] == p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != 'neq?':
if p[3] != p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '=':
if p[3] == p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '>':
if p[3] > p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '<':
if p[3] < p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '>=':
if p[3] >= p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '<=':
if p[3] <= p[4]: p[0] = '#t'
else: p[0] = '#f'
else:
print("Error: Comparison problem.")
sys.exit()
def p_display(p):
'display : OPEN_PAR DISPLAY expression CLOSE_PAR'
if type(p[3]) == str:
p[3] = ids[p[3]]
print(p[3])
def p_symbol(p):
'''
symbol : ADD
| MINUS
| DIVIDE
| MULTIPLY
| REMAINDER
'''
p[0] = p[1]
def p_boolean(p):
'''
boolean : TRUE
| FALSE
'''
p[0] = p[1]
def p_comparison(p):
'''
comparison : EQQUES
| NEQQUES
| EQUALS
| GREATER
| LESS
| GREATER_EQUAL
| LESS_EQUAL
'''
p[0] = p[1]
def p_constant(p):
'''
constant : INT
| FLOAT
| CHARACTER
| STRING
| boolean
'''
p[0] = p[1]
我正在测试以下方案代码：
(do (i 0 (+ 1 i)) (< i 5) (display i))
应该显示：
0
1个
2个
3个
4
但我得到：
Traceback (most recent call last):
File "C:\Compiladores\Lexer\scheme_compiler.py", line 510, in <module>
parser.parse(s)
File "C:\Compiladores\Lexer\ply\yacc.py", line 333, in parse
return self.parseopt_notrack(input, lexer, debug, tracking, tokenfunc)
File "C:\Compiladores\Lexer\ply\yacc.py", line 1120, in parseopt_notrack
p.callable(pslice)
File "C:\Compiladores\Lexer\scheme_compiler.py", line 338, in p_comparison_expression
p[3] = ids[p[3]]
KeyError: 'i'
有人可以帮我实现吗？非常感谢
你的 do 语法有点错误，
不应该
(do (i 0 (+ 1 i)) (< i 5) (display i))
应该是
(do ((i 0 (+ 1 i))) ((not (< i 5))) (display i))
您可以通过将 DO 脱糖为 LETREC 来实现它，或者如果您还没有实现 LETREC，则可以使用 Y-combinator 的 lambda 演算实现循环。所以这个 do 表达式可以变成这样：
(letrec ((loop (lambda (i)
(if (not (< i 5))
(begin (display i)
(loop (+ 1 i)))
#t))))
(loop 0))
您的 do 形式语法是（分成几行并使用 single character literals 以提高可读性）：
do_expression : '(' DO '(' ID constant '(' symbol ID expression ')' ')'
comparison_expression expression ')'
(注意： 由于多种原因，这实际上不是正确的语法，其中一个原因在不同的答案中有所说明。但这与这个问题无关。）
在你的语义动作中，p[12]和p[13]对应于comparison_expression和expression。剥离其本质，您的语义操作执行以下操作：
# create a new bound variable with the indicated initial value (`p[5]`).
aux = p[12]
while True:
expr = p[13] # You have a typo; I assume you meant p[13], not [13]
# Update the index variable's value
aux = p[12] # This value is still the same as it was at entry
if aux == '#t':
break
p[0] = expr
现在，重要的是要反思 p[12] 和 p[13] 是什么。 Ply 在 Python 引擎盖下不做任何魔术；它只是生成 Python 代码。所以 p[12] 和 p[13] 是普通的 Python 值，它们是对 comparison_expression 和 expression non-terminals 执行语义操作的结果。并且这些语义动作在 do_expression 被减少之前被评估，因此它们的值是在没有任何参考 do_expression 的情况下计算的。 comparison_expression 和 expression 都引用绑定变量 i（对于迭代构造来说很自然），但是在评估这些语义操作时该变量未绑定。因此出现错误消息。
但逻辑的根本缺陷远不止于此。在您的模型中，比较表达式和操作表达式在解析时只计算一次。但这不是循环结构的语义；在循环语义中，比较表达式会被重复求值，直到它指示循环已完成，并且如果在第一个绑定值上比较失败，则可能根本不会对操作表达式求值。
您似乎假设访问 p[12] 和 p[13] 将以某种方式重新评估关联的语义操作。但是 Python 没有这样的工具，Ply 也没有神奇地实现它。这是您的责任，具体取决于您尝试编译（或在本例中为解释）的语言的预期语义。
为此，您需要将解析的输入转换为某种数据结构，您可以稍后 评估（或不评估，视情况而定）。因此，您必须将语义操作返回的值安排为对已解析代码的描述，而不是立即评估（如果没有变量绑定，这将毫无意义）。
在 Scheme 的情况下，解析确实是最少的问题。尽管特殊形式确实使任务稍微复杂了一些，但 Scheme 程序基本上是 S-expressions，几乎可以轻松地将其转换为列表，而无需任何复杂的解析技术。这就是 Scheme（或者更确切地说，Lisp）语法的初衷。一旦你有了列表结构，或一些等效的功能（抽象语法树甚至 three-address 代码），你就可以在必要时使用正确的变量绑定来评估程序文本。
曾几何时，no-one 会想到分配这样的任务而不参考 Abelson & Sussman 的优秀（并且仍然相关）教科书 Structure and Interpretation of Computer Programs，亲切地称为 SICP。感谢作者和出版商的慷慨解囊，该书的全文可在线免费获取。我怎么推荐都不为过。
P.S.: 另外，请注意循环控制变量的绑定（i 在这种情况下）仅在循环评估期间存在。循环终止后，应删除该变量。但是你不能用一个简单的字典来模拟它，因为可能有一个同名的外部变量。这在 SICP 中也有解释。
我正在使用 PLY (Python Lex-Yacc) 为 Scheme 做一个解释器，我无法使用堆栈中的值来实现 "do" 循环，该堆栈跟踪对应一个变量（比如循环的i）。
这是编译器设计课程的期末项目，主要问题是向堆栈添加值的那一刻，我使用字典将变量名作为键，然后作为值，但是它并没有在它应该被分配的那一刻被分配，相反，它试图在一个值和变量之间进行比较但是它失败了，因为堆栈仍然是空的。
这是代码中最重要的部分：
ids = { }
def p_program(p):
'program : form'
#return p
print(p[1])
def p_form_a(p):
'''
form : definition
| expression
'''
p[0] = p[1]
def p_expression(p):
'''
expression : constant
| do_expression
| ID
| display
'''
p[0] = p[1]
def p_do_expression_a(p):
# 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
'do_expression : OPEN_PAR DO OPEN_PAR ID constant OPEN_PAR symbol ID expression CLOSE_PAR CLOSE_PAR comparison_expression expression CLOSE_PAR'
ids[p[4]] = p[5]
aux = p[12]
while True:
expr = p[13]
if ((type(p[5]) == int and type(p[9]) == int)
or (type(p[5]) == int and type(p[9]) == float)
or (type(p[5]) == float and type(p[9]) == int)
or (type(p[5]) == float and type(p[9]) == float)):
if p[7] == '+': ids[p[4]] = ids[p[4]] + p[9]
elif p[7] == '-': ids[p[4]] = ids[p[4]] - p[9]
elif p[7] == '*': ids[p[4]] = ids[p[4]] * p[9]
elif p[7] == '/': ids[p[4]] = ids[p[4]] / p[9]
elif p[7] == 'remainder': ids[p[4]] = ids[p[4]] % p[9]
else:
print("Error: Type mismatch.")
sys.exit()
aux = p[12]
if aux == '#t':
break
p[0] = expr
def p_comparison_expression(p):
'comparison_expression : OPEN_PAR comparison expression expression CLOSE_PAR'
if type(p[3]) == str:
p[3] = ids[p[3]]
if type(p[4]) == str:
p[4] = ids[p[4]]
if p[2] == 'eq?':
if p[3] == p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != 'neq?':
if p[3] != p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '=':
if p[3] == p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '>':
if p[3] > p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '<':
if p[3] < p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '>=':
if p[3] >= p[4]: p[0] = '#t'
else: p[0] = '#f'
elif p[2] != '<=':
if p[3] <= p[4]: p[0] = '#t'
else: p[0] = '#f'
else:
print("Error: Comparison problem.")
sys.exit()
def p_display(p):
'display : OPEN_PAR DISPLAY expression CLOSE_PAR'
if type(p[3]) == str:
p[3] = ids[p[3]]
print(p[3])
def p_symbol(p):
'''
symbol : ADD
| MINUS
| DIVIDE
| MULTIPLY
| REMAINDER
'''
p[0] = p[1]
def p_boolean(p):
'''
boolean : TRUE
| FALSE
'''
p[0] = p[1]
def p_comparison(p):
'''
comparison : EQQUES
| NEQQUES
| EQUALS
| GREATER
| LESS
| GREATER_EQUAL
| LESS_EQUAL
'''
p[0] = p[1]
def p_constant(p):
'''
constant : INT
| FLOAT
| CHARACTER
| STRING
| boolean
'''
p[0] = p[1]
我正在测试以下方案代码：
(do (i 0 (+ 1 i)) (< i 5) (display i))
应该显示： 0 1个 2个 3个 4
但我得到：
Traceback (most recent call last):
File "C:\Compiladores\Lexer\scheme_compiler.py", line 510, in <module>
parser.parse(s)
File "C:\Compiladores\Lexer\ply\yacc.py", line 333, in parse
return self.parseopt_notrack(input, lexer, debug, tracking, tokenfunc)
File "C:\Compiladores\Lexer\ply\yacc.py", line 1120, in parseopt_notrack
p.callable(pslice)
File "C:\Compiladores\Lexer\scheme_compiler.py", line 338, in p_comparison_expression
p[3] = ids[p[3]]
KeyError: 'i'
有人可以帮我实现吗？非常感谢
你的 do 语法有点错误，
不应该
(do (i 0 (+ 1 i)) (< i 5) (display i))
应该是
(do ((i 0 (+ 1 i))) ((not (< i 5))) (display i))
您可以通过将 DO 脱糖为 LETREC 来实现它，或者如果您还没有实现 LETREC，则可以使用 Y-combinator 的 lambda 演算实现循环。所以这个 do 表达式可以变成这样：
(letrec ((loop (lambda (i)
(if (not (< i 5))
(begin (display i)
(loop (+ 1 i)))
#t))))
(loop 0))
您的 do 形式语法是（分成几行并使用 single character literals 以提高可读性）：
do_expression : '(' DO '(' ID constant '(' symbol ID expression ')' ')'
comparison_expression expression ')'
(注意： 由于多种原因，这实际上不是正确的语法，其中一个原因在不同的答案中有所说明。但这与这个问题无关。）
在你的语义动作中，p[12]和p[13]对应于comparison_expression和expression。剥离其本质，您的语义操作执行以下操作：
# create a new bound variable with the indicated initial value (`p[5]`).
aux = p[12]
while True:
expr = p[13] # You have a typo; I assume you meant p[13], not [13]
# Update the index variable's value
aux = p[12] # This value is still the same as it was at entry
if aux == '#t':
break
p[0] = expr
现在，重要的是要反思 p[12] 和 p[13] 是什么。 Ply 在 Python 引擎盖下不做任何魔术；它只是生成 Python 代码。所以 p[12] 和 p[13] 是普通的 Python 值，它们是对 comparison_expression 和 expression non-terminals 执行语义操作的结果。并且这些语义动作在 do_expression 被减少之前被评估，因此它们的值是在没有任何参考 do_expression 的情况下计算的。 comparison_expression 和 expression 都引用绑定变量 i（对于迭代构造来说很自然），但是在评估这些语义操作时该变量未绑定。因此出现错误消息。
但逻辑的根本缺陷远不止于此。在您的模型中，比较表达式和操作表达式在解析时只计算一次。但这不是循环结构的语义；在循环语义中，比较表达式会被重复求值，直到它指示循环已完成，并且如果在第一个绑定值上比较失败，则可能根本不会对操作表达式求值。
您似乎假设访问 p[12] 和 p[13] 将以某种方式重新评估关联的语义操作。但是 Python 没有这样的工具，Ply 也没有神奇地实现它。这是您的责任，具体取决于您尝试编译（或在本例中为解释）的语言的预期语义。
为此，您需要将解析的输入转换为某种数据结构，您可以稍后 评估（或不评估，视情况而定）。因此，您必须将语义操作返回的值安排为对已解析代码的描述，而不是立即评估（如果没有变量绑定，这将毫无意义）。
在 Scheme 的情况下，解析确实是最少的问题。尽管特殊形式确实使任务稍微复杂了一些，但 Scheme 程序基本上是 S-expressions，几乎可以轻松地将其转换为列表，而无需任何复杂的解析技术。这就是 Scheme（或者更确切地说，Lisp）语法的初衷。一旦你有了列表结构，或一些等效的功能（抽象语法树甚至 three-address 代码），你就可以在必要时使用正确的变量绑定来评估程序文本。
曾几何时，no-one 会想到分配这样的任务而不参考 Abelson & Sussman 的优秀（并且仍然相关）教科书 Structure and Interpretation of Computer Programs，亲切地称为 SICP。感谢作者和出版商的慷慨解囊，该书的全文可在线免费获取。我怎么推荐都不为过。
P.S.: 另外，请注意循环控制变量的绑定（i 在这种情况下）仅在循环评估期间存在。循环终止后，应删除该变量。但是你不能用一个简单的字典来模拟它，因为可能有一个同名的外部变量。这在 SICP 中也有解释。