「集训队互测 2015」未来程序 · 改 - 编译原理

在 2111 年,第 128 届全国青少年信息学奥林匹克冬令营前夕,Z 君找到了 2015 年,第 32 届冬令营的题目来练习。

他打开了第三题「未来程序」这道题目:

「本题是一道提交答案题,一共 10 个测试点。

对于每个测试点,你会得到一段程序的源代码和这段程序的输入。你要运行这个程序,并保存这个程序的输出。

遗憾的是这些程序都效率极其低下,无法在比赛的 5 个小时内得到输出。」

Z 君想了一下,决定用 2111 年的计算机来试着运行这个题目,但是问题来了,Z 君已经找不到 96 年前的那次比赛的测试数据了 ……

没有给出输入数据的提交答案题就不成其「提交答案题」之名,为了解决这个问题,Z 君决定将这个题目改造成传统题。

Z 君知道 96 年前的计算机的性能比现在差多了,所以这道题的测试数据中,输入数据的规模被设计成很小,从而,做这道题的选手只需要暴力模拟源代码的工作流程就可以通过它。

现在这道题摆到了你的面前。

本题是一道传统题,一共有 10 个测试点。

对于每个测试点,你的程序会得到一段程序的源代码和这段程序的输入。你的程序需要运行这段程序,并输出这段程序的输出。

链接

UOJ #98

题解

题目要求编写一个 C++(的子集)解释器,一个可行的思路是,将 C++ 代码编译为等价的 Python 代码,然后调用 exec() 执行 Python 代码;同时,Python 的字符串处理非常方便,对于这道题来说是一个不错的选择。

先说 Parser。

从顶层做起,顶层只可能是函数或者全局变量定义,并且一定以一个 int 开始。向后读,读到 (,; 停止,如果读到了 (,表示这是一个函数定义,接下来读到 ) 停止,得到参数列表,以 , 分割并解析参数列表,然后读取并解析函数体即可;如果读到 ,,表示这是一条全局变量定义,并且定义了多个全局变量,接下来继续读到 ; 停止,可以读取出定义的所有的变量,以 , 分割并解析变量列表即可;如果读到 ;,则表示是单条变量定义,直接解析即可。

我们可以将函数体看作一个「复合语句」,接下来只需要考虑语句的解析即可。

对于一个语句的分析,首先从头开始读到空白字符停止。

  • 如果读到了 {,则这是一个复合语句,向后读匹配的括号,读到 } 停止,即可得到整个复合语句,去除外层的花括号,继续递归处理里面的语句即可。
  • 如果读到了 if,读匹配括号取出判断条件,对于之后的部分递归处理一个语句,如果接下来是 else,则再递归处理一个语句。
  • 如果读到了 while 或者 for,读括号内部的内容,对于 for,可以直接用 ; 分割三个语句,之后递归处理一个语句。
  • 如果读到了 int,则这是一个变量定义,读到 ;,以 , 分割即可。
  • 否则,这是一个普通语句,读到 ; 停止即可。

注意到,给出的代码中没有字符串常量,所以读到某符号停止不会受到干扰。

这样,我们就得到了一棵语句级别的 AST,接下来考虑表达式语法的处理。

对于普通变量,这里的方法是,定义一个变量容器的类型,重载它的一些运算符。=&&||! 四个运算符找不到对应优先级的可重载的 Python 运算符,前三个的解决方法是将其转化为函数调用,对于 !,可以替换为 X **,其中 X 是一个对象,我们定义 X ** a 的返回值为将 a 取反 —— 因为 ** 运算符没有被用到,并且它的优先级类似于 !。对于 cincout>><<,可以替换它们,在两边加上括号,如 cin >> <expr> >> <expr2> 替换为 (cin) >> (<expr>) >> (<expr2>)

数组,对于多维数组,我们可以计算其大小,并为其写一个寻址器,每一维的 [] 会返回下一维的寻址器,最后一维的 [] 返回变量的容器。这里还有一个小小的 Trick —— 对于没有访问到的数组,不实际为其分配空间,可以节省很多时间。

再接下来,我们需要生成与 AST 等价的 Python 代码。

具体的思路仍然是递归,对于一个复合语句,在需要增加一级缩进。变量的定义需要被生成为变量容器的构造。

一个问题是变量的作用域,复合语句内部的变量会遮蔽外部的变量 —— 解决方法是给每次变量定义分配一个唯一的 ID,将所有语句变量名替换为 ID + 原变量名即可。

for 语句的处理,对于一个这样的 for 语句:

for (int i; i < n; i = i + 1) {
    s = s + i;
    cout << i << endl;
}

转化为:

if (1) {
    int i;
    while (i < n) {
        s = s + i;
        cout << i << endl;
    }
    i = i + 1;
}

注意全局变量必须在每个函数开头声明 global VAR,如果某一个全局变量与参数重名,则不再声明这个全局变量。

题目中的递归深度很大,可以通过 sys.setrecursionlimit(1000000) 增大 Python 的递归深度限制。

代码

#!/usr/bin/python3

# 用于辅助代码执行的类与函数
class IntegerVariable:
    def __init__(self, x):
        if (isinstance(x, IntegerVariable)):
            self.val = x.val
        else:
            self.val = int(x)

    def __repr__(self):
        return repr(self.val)

    def __add__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val + x.val)

    def __radd__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val + self.val)

    def __sub__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val - x.val)

    def __rsub__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val - self.val)

    def __mul__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val * x.val)

    def __rmul__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val * self.val)

    def __floordiv__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val // x.val)

    def __rfloordiv__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val // self.val)

    def __mod__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val % x.val)

    def __rmod__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val % self.val)

    def __lt__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val < x.val)

    def __le__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val <= x.val)

    def __eq__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val == x.val)

    def __ne__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val != x.val)

    def __gt__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val > x.val)

    def __ge__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val >= x.val)

    def __xor__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(self.val ^ x.val)

    def __rxor__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        return IntegerVariable(x.val ^ self.val)

    def assign_with(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        self.val = x.val
        return self

def logical_and(x, y):
    if (not isinstance(x, IntegerVariable)):
        x = IntegerVariable(x)
    if (not isinstance(y, IntegerVariable)):
        y = IntegerVariable(y)
    return IntegerVariable((x.val != 0) and (y.val != 0))

def logical_or(x, y):
    if (not isinstance(x, IntegerVariable)):
        x = IntegerVariable(x)
    if (not isinstance(y, IntegerVariable)):
        y = IntegerVariable(y)
    return IntegerVariable((x.val != 0) or (y.val != 0))

# 将逻辑非('!')运算符转化为乘方('**')运算符
class LogicalNotHelper:
    def __pow__(self, x):
        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(int(x))
        return IntegerVariable(int(not x.val))

logical_not = LogicalNotHelper()

class ArrayAccessProxy:
    def __init__(self, l, length, lengths, curr_dim, curr_pos):
        self.l = l
        self.length = length
        self.lengths = lengths
        self.curr_dim = curr_dim
        self.curr_pos = curr_pos

    def __getitem__(self, x):
        new_length = self.length // self.lengths[self.curr_dim]
        new_pos = self.curr_pos + x * new_length
        if self.curr_dim + 1 == len(self.lengths):
            return self.l[new_pos]
        else:
            return ArrayAccessProxy(self.l, new_length, self.lengths, self.curr_dim + 1, new_pos)

    def __setitem__(self, x, val):
        new_length = self.length // self.lengths[self.curr_dim]
        new_pos = self.curr_pos + x * new_length
        if self.curr_dim + 1 == len(self.lengths):
            self.l[new_pos] = IntegerVariable(val)
        else:
            raise TypeError('Assign to a Array')

class Array:
    def __init__(self, lengths):
        self.lengths = lengths
        self.length = 1
        for i in lengths:
            self.length *= i
        self.l = None

    def __repr__(self):
        return repr(self.l)

    def construct(self):
        if not self.l:
            self.l = [IntegerVariable(0) for i in range(0, self.length)]

    def __getitem__(self, x):
        if not self.l:
            self.construct()

        if isinstance(x, IntegerVariable):
            x = x.val
        if len(self.lengths) == 1:
            return self.l[x]
        else:
            new_length = self.length // self.lengths[0]
            new_pos = x * new_length
            return ArrayAccessProxy(self.l, new_length, self.lengths, 1, new_pos)

    def __setitem__(self, x, val):
        if not self.l:
            self.construct()

        if (not isinstance(x, IntegerVariable)):
            x = IntegerVariable(x)
        if len(self.lengths) == 1:
            self.l[x.val] = val
        else:
            raise TypeError('Assign to a Array')

class OutputStream:
    def __lshift__(self, x):
        if isinstance(x, EndLine):
            print('\n', end = '')
        elif isinstance(x, IntegerVariable):
            print(x.val, end = '')
        else:
            print(x, end = '')
        return self

class InputStream:
    def __init__(self):
        self.index = 0

    def __rshift__(self, x):
        x.val = self.data[self.index]
        self.index += 1
        return self

class EndLine:
    def __init__(self):
        pass

cout = OutputStream()
cin = InputStream()
endl = EndLine()

def variable(array_lengths):
    if array_lengths == None or len(array_lengths) == 0:
        return IntegerVariable(0)
    else:
        return Array(array_lengths)

def get_value(x):
    if not isinstance(x, IntegerVariable):
        return x
    else:
        return x.val

def init_arg(x):
    if isinstance(x, IntegerVariable):
        return IntegerVariable(x.val)
    else:
        return IntegerVariable(int(x))

def putchar(ch):
    print(chr(get_value(ch)), end = '')

# 读取输入数据,初始化 cin 输入流
def init_input_stream():
    def read_integers():
        return list(map(int, str(input()).split(' ')))
    a = read_integers()
    data = []
    n = a.pop(0)
    for i in range(0, n):
        if len(a) == 0:
            a = read_integers()
        data.append(a.pop(0))
    cin.data = data

# 从字符串最右边向左取出尽量多的字符,直到下一个字符会导致括号不能匹配或【下一个字符为逗号(',')且当前的括号是匹配的】
def left_until_nearest_unmatched_bracket_or_comma(s):
    right_bracket_count = 0
    res = ''
    while len(s) > 0:
        ch = s[-1:]
        if ch == ',':
            if right_bracket_count == 0:
                break
        elif ch in ')]}':
            right_bracket_count += 1
        elif ch in '([{':
            right_bracket_count -= 1
            if right_bracket_count < 0:
                break
        res = ch + res
        s = s[:-1]
    return s, res

# 从字符串最左边向右取出尽量多的字符,直到下一个字符会导致括号不能匹配或【下一个字符为逗号(',')且当前的括号是匹配的】
def right_until_nearest_unmatched_bracket_or_comma(s):
    left_bracket_count = 0
    res = ''
    while len(s) > 0:
        ch = s[:1]
        if ch == ',':
            if left_bracket_count == 0:
                break
        elif ch in '([{':
            left_bracket_count += 1
        elif ch in ')]}':
            left_bracket_count -= 1
            if left_bracket_count < 0:
                break
        res += ch
        s = s[1:]
    return s, res

# 转化赋值运算符为函数调用
def transform_expression_assignment(s):
    s = s.strip()
    pos = s.find('=')

    # 找到的等号是不等于(!=)、等于(==)、大于等于(>=)、小于等于(<=)运算符的一部分
    while pos != -1 and (s[pos + 1] == '=' or s[pos - 1] in '!><'):
        pos = s.find('=', pos + 2)

    # 找不到赋值运算符
    if pos == -1:
        return s

    left = s[:pos].strip()
    left, left_exp = left_until_nearest_unmatched_bracket_or_comma(left)
    right = s[pos + 1:].strip()
    right, right_exp = right_until_nearest_unmatched_bracket_or_comma(right)
    return '%s((%s).assign_with(%s))%s' % (left, left_exp, transform_expression_assignment(right_exp), transform_expression_assignment(right))

# 转化逻辑运算符为函数调用
def transform_expression_logical_operators(s, op, function_name):
    s = s.strip()
    pos = s.find(op)

    # 找不到对应的运算符
    if pos == -1:
        return s

    left = s[:pos].strip()
    left, left_exp = left_until_nearest_unmatched_bracket_or_comma(left)
    right = s[pos + 2:].strip()
    right, right_exp = right_until_nearest_unmatched_bracket_or_comma(right)
    # print('transform_expression_logical_operators(%s): left = "%s", right = "%s"' % (op, left, right))
    return '%s(%s(%s, %s))%s' % (left, function_name, left_exp, transform_expression_logical_operators(right_exp, op, function_name), transform_expression_logical_operators(right, op, function_name))

# 转化运算符
def transform_expression_operators(s):
    # 将 '!exp' 替换为 'logical_not ** exp'
    s = s.replace('!=', '
fb47173d-0dcc-4477-a202-3258177137b1
#39;
) s = s.replace('!', 'logical_not ** ') s = s.replace('
fb47173d-0dcc-4477-a202-3258177137b1
#39;
, '!=') # 将 '/' 替换为 '//' # 保证之前替换过的不会再次替换 s = s.replace('//', '/') s = s.replace('/', '//') return s # 对表达式进行转化 def transform_expression(s): def transform(s): s = transform_expression_operators(s) s = transform_expression_logical_operators(s, '||', 'logical_or') s = transform_expression_logical_operators(s, '&&', 'logical_and') s = transform_expression_assignment(s) return s last_l = len(s) last_r = 0 while True: # 从右向左找更靠右的圆括号('(')或方括号('[') l_round = s.rfind('(', 0, last_l) l_box = s.rfind('[', 0, last_l) if l_round == -1 and l_box == -1: break # 优先处理更靠右的 right_bracket = ')' if l_round > l_box else ']' l = l_round if l_round > l_box else l_box left = s[:l + 1] right, mid = right_until_nearest_unmatched_bracket_or_comma(s[l + 1:]) # r = s.find(right_bracket, l + 1) # print('transform_expression(): Find expression %s' % s[l + 1:r]) # s = s[:l + 1] + transform(s[l + 1:r]) + s[r:] s = left + transform(mid) + right last_l = l return transform(s) # 跳过开头的 3 行 def skip_header(): for i in range(0, 3): input() # 读代码,即从当前标准输入读到文件结束 def read_code(): code = '' while True: try: code += input() + '\n' except EOFError: break return code # 判断一个字符(串)是否为空字符 def is_empty(str): return not str.strip() # 增加一级缩进(4 个空格) def indent(code): return '\n'.join(list(map(lambda s: ' ' + s, code.split('\n')))) # 文本处理器 class Tokenizer: def __init__(self, s): self.s = s self.pos = 0 # 读取下一个字符,但不改变当前位置 def peek(self): if self.pos == len(self.s): raise IndexError('peek() reached end of string') return self.s[self.pos] # 读取下一个字符,并将当前位置向后移动一个字符 def next(self): if self.pos == len(self.s): raise IndexError('next() reached end of string') ch = self.s[self.pos] self.pos += 1 return ch # 将当前位置向前移动一个字符 def back(self): if self.pos == 0: raise IndexError('back() reached begin of string') self.pos -= 1 # 向后读取,直到读到空白字符 def next_until_empty(self): s = '' while is_empty(self.peek()): self.next() while self.pos < len(self.s) and (not is_empty(self.peek())): s += self.next() return s # 向后读取,直到读到空白字符,不改变当前位置 def peek_until_empty(self): pos_bak = self.pos res = self.next_until_empty() self.pos = pos_bak return res # 向后读取,直到读到 `strings` 中的任何一个字符串停止,不改变当前位置 # 返回一个二元组,读到的字符串(不包含结束字符串)和结束字符串 def peek_until(self, strings): pos_bak = self.pos res = self.next_until(strings) self.pos = pos_bak return res # 向后读取,直到读到 `strings` 中的任何一个字符串停止 # 返回一个二元组,读到的字符串(不包含结束字符串)和结束字符串 def next_until(self, strings): s = '' while is_empty(self.peek()): self.next() while True: for i in strings: if s.endswith(i): return s[:len(s) - len(i)], i s += self.next() # 向后读取一个括号匹配的块 # 这里并没有保证对应匹配(即比如 ] 可以匹配 (),因为题目保证源代码合法 def next_brackets_block(self): left_count = 0 s = '' while True: ch = self.next() s += ch if ch in '([{': left_count += 1 elif ch in '}])': left_count -= 1 if left_count == 0: return s.strip() # 替换整个 Token def replace_token(s, to_replace, replace_with): def is_part_of_token(ch): if ord(ch) >= ord('A') and ord(ch) <= ord('Z'): return True if ord(ch) >= ord('a') and ord(ch) <= ord('z'): return True if ord(ch) >= ord('0') and ord(ch) <= ord('9'): return True if ch == '_': return True return False last_l = len(s) while True: l = s.rfind(to_replace, 0, last_l) if l == -1: break last_l = l r = l + len(to_replace) - 1 if (l - 1 >= 0 and is_part_of_token(s[l - 1])) or (r + 1 < len(s) and is_part_of_token(s[r + 1])): continue s_l = s[:l] s_r = s[r + 1:] s = s_l + replace_with + s_r return s # 应用变量名映射 def apply_var_map(expression, var_map): for x in var_map: expression = replace_token(expression, x, var_map[x]) return expression # 生成表达式 def generate_expression(expression, var_map): return transform_expression(apply_var_map(expression, var_map)) # 一些语句相关的结构体 global_variables = [] # 变量或数组变量 class VariableDeclaration: def __init__(self, name, array_lengths): self.name = name self.array_lengths = array_lengths def __repr__(self): return '<VariableDeclaration name=%s array_lengths=%s>' % (repr(self.name), repr(self.array_lengths)) def generate(self, var_map): # 如果 var_map 为 None,则表示这是一条全局变量定义 name = self.name if var_map == None else var_map[self.name] if self.array_lengths == None: # 非数组变量 return '%s = variable(None)' % name else: # 数组变量 array_lengths = ', '.join(list(map(lambda x: str(x), self.array_lengths))) return '%s = variable([%s])' % (name, array_lengths) # 表达式语句 class ExpressionStatement: def __init__(self, expression): self.expression = expression def __repr__(self): return '<ExpressionStatement expression=%s>' % repr(self.expression) def generate(self, var_map): expression = generate_expression(self.expression, var_map) if expression.find('<<') != -1: expression = '(%s)' % expression.replace('<<', ') << (') elif expression.find('>>') != -1: expression = '(%s)' % expression.replace('>>', ') >> (') return expression def get_var_map(self): return {} # 返回语句 # 将可能返回的常数值转换为 IntegerVariable class ReturnStatement: def __init__(self, return_value): self.return_value = return_value def __repr__(self): return '<ReturnStatement return_value=%s>' % repr(self.return_value) def generate(self, var_map): if self.return_value == '': return 'return' else: return 'return IntegerVariable(%s)' % generate_expression(self.return_value, var_map) def get_var_map(self): return {} # if 语句 # condition 为 'if ()' 括号里面的表达式 # statement_true 为 'if ()' 后跟的语句 # statement_false 为 'else' 后跟的语句(如果没有 'else',则为 None) class IfStatement: def __init__(self, condition, statement_true, statement_false): self.condition = condition self.statement_true = statement_true self.statement_false = statement_false def __repr__(self): return '<IfStatement condition=%s statement_true=%s statement_false=%s>' % (repr(self.condition), repr(self.statement_true), repr(self.statement_false)) def generate(self, var_map): condition = generate_expression(self.condition, var_map) statement_true = indent(self.statement_true.generate(var_map)) if self.statement_false: statement_false = indent(self.statement_false.generate(var_map)) return 'if get_value(%s):\n%s\nelse:\n%s' % (condition, statement_true, statement_false) else: return 'if get_value(%s):\n%s' % (condition, statement_true) def get_var_map(self): return {} # while 语句 # condition 为 'while ()' 括号里面的表达式 # statement 为 'while ()' 后跟的语句 class WhileStatement: def __init__(self, condition, statement): self.condition = condition self.statement = statement def __repr__(self): return '<WhileStatement condition=%s statement=%s>' % (repr(self.condition), repr(self.statement)) def generate(self, var_map): condition = generate_expression(self.condition, var_map) statement = indent(self.statement.generate(var_map)) return 'while get_value(%s):\n%s' % (condition, statement) def get_var_map(self): return {} # for 语句 # control_statements 为 'for ()' 括号里面的三个语句,表示为一个列表 # statement 为 'for ()' 后跟的语句 class ForStatement: def __init__(self, control_statements, statement): assert len(control_statements) == 3 self.control_statements = control_statements self.statement = statement def __repr__(self): return '<ForStatement control_statements=%s statement=%s>' % (repr(self.control_statements), repr(self.statement)) def generate(self, var_map): while_condition = self.control_statements[1].expression if self.control_statements[1] else '1' while_inner_statements = [self.statement] + ([self.control_statements[2]] if self.control_statements[2] else []) while_statement = WhileStatement(while_condition, CompoundStatement(while_inner_statements)) if_wrapper = IfStatement('1', CompoundStatement([self.control_statements[0], while_statement]), None) return if_wrapper.generate(var_map) def get_var_map(self): return {} # 复合语句 class CompoundStatement: def __init__(self, statements): self.statements = statements def __repr__(self): return '<CompoundStatement statements=%s>' % repr(self.statements) def generate(self, var_map): res = '' curr_var_map = dict(var_map) for statement in self.statements: curr_var_map = dict(curr_var_map, **statement.get_var_map()) res += statement.generate(curr_var_map) + '\n' return res def get_var_map(self): return {} # 变量定义 variables_declaration_id = 0 class VariablesDeclaration: def __init__(self, var_list): global variables_declaration_id variables_declaration_id += 1 self.var_list = var_list self.id = variables_declaration_id def __repr__(self): return '<VariablesDeclaration var_list=%s>' % repr(self.var_list) def generate(self, var_map = None): # 如果 var_map 为 None,则表示这是一条全局变量定义 return '\n'.join(list(map(lambda var: var.generate(var_map), self.var_list))) def get_var_map(self): return {variable.name: '__local_var_%d_%s' % (self.id, variable.name) for variable in self.var_list} # 函数 class Function: def __init__(self, name, arg_list, body): self.name = name self.arg_list = arg_list self.body = body def __repr__(self): return '<Function name=%s arg_list=%s body=%s>' % (repr(self.name), repr(self.arg_list), repr(self.body)) def generate(self): args = ', '.join(self.arg_list) init_args = '\n'.join(['%s = init_arg(%s)' % (arg, arg) for arg in self.arg_list]) + '\n' declare_global_variables = '\n'.join(['global %s' % variable for variable in global_variables if variable not in self.arg_list]) + '\n' body = indent(init_args + declare_global_variables + self.body.generate({}) + '\nreturn 0\n') return 'def %s(%s):\n%s' % (self.name, args, body) # 解释器 class Parser: def __init__(self, code): self.tokenizer = Tokenizer(code) self.pos = 0 # 解析参数列表 def parse_arg_list(self, s): if (not s.strip()): return [] # 解析参数,去掉参数类型 int def parse_arg(s): s = s.strip() return s[s.find(' '):].strip() return list(map(parse_arg, s.split(','))) # 解析变量列表 def parse_var_list(self, s): if (not s.strip()): return [] # 解析数组变量 def parse_var(s): s = s.strip() try: tokenizer = Tokenizer(s) name, ends_with = tokenizer.next_until(['[']) lengths = [] try: tokenizer.back() while True: # print(tokenizer.s[tokenizer.pos:]) length = tokenizer.next_brackets_block().strip() length = int(length[1:-1].strip()) lengths.append(length) except IndexError: pass return VariableDeclaration(name, lengths) except IndexError: return VariableDeclaration(s, None) return list(map(parse_var, s.split(','))) # 解析一个普通语句(或声明) def parse_normal_statement(self, statement): if statement.startswith('int '): # 变量定义 var_list = self.parse_var_list(statement[4:]) # print('Variable Declaration: %s' % var_list) return VariablesDeclaration(var_list) elif statement.startswith('return '): # 单独处理 return 语句,原因见 ReturnStatement 的定义 return ReturnStatement(statement[7:].strip()) else: # 表达式语句 # print('Normal Statement: "%s"' % statement) return ExpressionStatement(statement) # 解析下一个语句 def next_statement(self, tokenizer): t = tokenizer.peek_until_empty() # 判断流程控制语句 if t == 'if': # 读取圆括号中的内容(condition) tokenizer.next_until(['(']) tokenizer.back() condition = tokenizer.next_brackets_block()[1:-1] # 读取 'if ()' 后跟的语句 statement_true = self.next_statement(tokenizer) # 读取 'else' 及其后跟的语句 statement_false = None try: if tokenizer.peek_until_empty() == 'else': tokenizer.next_until_empty() statement_false = self.next_statement(tokenizer) except IndexError: pass # print('If Statement: condition = "%s", statement_true = "%s", statement_false = "%s"' % (condition, statement_true, statement_false)) return IfStatement(condition, statement_true, statement_false) elif t == 'while': # 读取圆括号中的内容(condition) tokenizer.next_until(['(']) tokenizer.back() condition = tokenizer.next_brackets_block()[1:-1] # 读取 'while ()' 后跟的语句 statement = self.next_statement(tokenizer) # print('While Statement: condition = "%s", statement = "%s"' % (condition, statement)) return WhileStatement(condition, statement) elif t == 'for': # 读取圆括号中的内容(control_statements) tokenizer.next_until(['(']) tokenizer.back() in_bracket = tokenizer.next_brackets_block()[1:-1] control_statements = list(map(lambda s: self.parse_normal_statement(s.strip()), in_bracket.split(';'))) # 读取 'for ()' 后跟的语句 statement = self.next_statement(tokenizer) # print('For Statement: control_statements = "%s", statement = "%s"' % (control_statements, statement)) return ForStatement(control_statements, statement) # 判断复合语句 elif t.startswith('{'): tokenizer.next_until_empty() for i in range(0, len(t)): tokenizer.back() s = tokenizer.next_brackets_block() statement = self.parse_compound(s) # print('Compound Statement: "%s", [parsed] = "%s"' % (s, statement)) return statement else: # 表达式语句(或声明) # 直接读到分号 ';' 即为一条语句 statement, ends_with = tokenizer.next_until([';']) return self.parse_normal_statement(statement) # 解析一个复合语句 def parse_compound(self, content): # 去除最外侧花括号 content = content.strip() content = content[1:-1].strip() # 编译每一条语句(或声明) tokenizer = Tokenizer(content) statements = [] try: while True: statements.append(self.next_statement(tokenizer)) except IndexError: pass return CompoundStatement(statements) # 解析顶层(全局变量与全局函数) def parse_top_level(self): global global_variables l = [] try: while True: # 顶层可包含变量定义与函数定义 # 变量定义与函数定义的开头均为类型名 t = self.tokenizer.next_until_empty() # 读取函数或变量名 name, ends_with = self.tokenizer.peek_until(['(', ',', ';']) if ends_with == '(': # 以 '(' 结束了一个函数名 self.tokenizer.next_until(['(', ',', ';']) # 读到 ')',获取参数列表 arg_list, ends_with = self.tokenizer.next_until([')']) arg_list = self.parse_arg_list(arg_list) body = self.tokenizer.next_brackets_block() body = self.parse_compound(body) l.append(Function(name, arg_list, body)) else: # 变量定义 statement, ends_with = self.tokenizer.next_until([';']) var_list = self.parse_var_list(statement) global_variables += [variable.name for variable in var_list] l.append(VariablesDeclaration(var_list)) except IndexError: pass return l def parse(self): ast = self.parse_top_level() return ast # 生成 Python 代码 def generate_pycode(ast): pycode = '' for node in ast: pycode += node.generate() + '\n' return pycode import sys # sys.stdin = open('program10.in', 'r') sys.setrecursionlimit(1000000) # 读入 init_input_stream() skip_header() code = read_code() # 编译 parser = Parser(code) ast = parser.parse() # print(ast) # 生成代码 pycode = generate_pycode(ast) # print('\n\n\n\n\n') # print(pycode) try: exec(pycode) main() except Exception as e: # print(e) raise e # print(transform_expression('putchar(c = a * b[7], 233, k * 5 + 0)'))