如何从python PLY中的方案解释“do”循环

Question

我正在使用 PLY (Python Lex-Yacc) 为 Scheme 做一个解释器，但我无法使用堆栈中的值来实现“do”循环，该值跟踪与变量对应的 ID（例如 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]

我正在测试以下 Scheme 代码：

(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'

有人可以帮我实现它吗？我会很感激

Answer 1

您的do表单语法是（分成几行并使用单个字符文字以提高可读性）：

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非终端执行语义操作的结果。并且这些语义动作do_expression在 减少之前被评估，因此它们的值是在没有任何参考的情况下计算的do_expression。既comparison_expression与expression参考绑定变量i（如自然的迭代构建体），但是，当这些语义动作被评估该变量没有绑定。因此出现错误消息。

但逻辑上的缺陷比这更根本。在您的模型中，比较和操作表达式在解析时只计算一次。但这不是循环结构的语义；在循环语义中，比较表达式被重复计算，直到它指示循环完成，如果比较在第一个边界值上失败，则可能根本不会计算动作表达式。

您似乎假设访问p[12]并p[13]会以某种方式重新评估相关的语义操作。但是 Python 没有这样的功能，Ply 也没有神奇地实现。这是你的责任，基于你试图编译（或者，在这种情况下，解释）语言的预期语义。

为此，您需要将解析后的输入转换为某种数据结构，您可以稍后评估（或不评估，视情况而定）。因此，您必须将语义操作返回的值安排为已解析代码的描述，而不是立即评估（在没有变量绑定的情况下，这无论如何都没有意义）。

在 Scheme 的情况下，解析实际上是最少的问题。尽管特殊形式使任务稍微复杂化，但 Scheme 程序基本上是 S 表达式，几乎可以轻松地将其转换为列表，而无需任何复杂的解析技术。这就是 Scheme（或者更确切地说，Lisp）语法的初衷。一旦您拥有列表结构或某些功能等效物（抽象语法树或什至三地址代码），您就可以在必要时使用正确的变量绑定评估程序文本。

曾几何时，如果不参考 Abelson & Sussman 的优秀（并且仍然相关）教科书Structure and Interpretation of Computer Program（被亲切地称为 SICP ），没有人会想到分配这样的任务。由于作者和出版商的慷慨解囊，该书的全文可在线免费获取。我不能推荐它。

PS：另外，请注意循环控制变量（i在这种情况下）的绑定仅在循环评估期间存在。一旦循环终止，变量应该被删除。但是你不能用一个简单的字典来建模，因为可能有一个同名的外部变量。这在 SICP 中也有解释。