时间戳

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

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

问题描述

我正在使用 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]

我正在测试以下方案代码：

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

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

标签： pythonloopsschemeinterpreterply

解决方案

您的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 Programs（被亲切地称为 SICP），没有人会想到分配这样的任务。感谢作者和出版商的慷慨解囊，该书的全文可在线免费获取。我不能推荐它。

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

推荐阅读