• 日期: 2026-10-12
  • 标签: 常规

实现一个简单的编程语言的语法制导翻译和中间代码生成

本文将实现一个简单的编程语言的语法制导翻译和中间代码生成。该编程语言仅包含一个名为 'f' 的函数，函数接受一个或多个变量作为参数，参数之间用逗号分隔，函数体由一个计算表达式构成，表达式遵循 C 语言的运算规则。

1. 完善文法

Vt = {+, -,*, /, , , (, ),[,], 𝑓, 𝑋}  其中 X 表示除了 f 之外的任意小写字母
Vn = {S, A, E, T, F},
G[S]:
S → f[A] = E
A → X | X,A
E → E + T|E − T|T
T → T ∗ F|T/F|𝐹
F → (E)|X

2. SLR(1) 分析表代码和注释

# 定义终结符、非终结符以及产生式
VT = ['+', '-', '*', '/', ',', '(', ')', '[', ']', 'f', 'X']
VN = ['S', 'A', 'E', 'T', 'F']
P = {
    'S': ['f', 'A', '=', 'E'],
    'A': ['X', ',', 'A', '|', 'X'],
    'E': ['E', '+', 'T', '|', 'E', '-', 'T', '|', 'T'],
    'T': ['T', '*', 'F', '|', 'T', '/', 'F', '|', 'F'],
    'F': ['(', 'E', ')', '|', 'X']
}

# 构造 FIRST 集
FIRST = {}
for X in VN:
    FIRST[X] = set()
for a in VT:
    FIRST[a] = set([a])
FIRST['('].add(')')
FIRST['E'].update(FIRST['T'])
FIRST['T'].update(FIRST['F'])
FIRST['A'] = FIRST['X']

# 构造 FOLLOW 集
FOLLOW = {}
for X in VN:
    FOLLOW[X] = set()
FOLLOW['S'].add('$')
for X in VN:
    for Y in VN:
        if X != Y and Y in P[X]:
            FOLLOW[Y].update(FOLLOW[X])
    for p in P[X]:
        for i in range(len(p)):
            if p[i] in VN:
                if i == len(p) - 1:
                    FOLLOW[p[i]].update(FOLLOW[X])
                else:
                    j = i + 1
                    while j < len(p) and p[j] in FIRST[p[i]]:
                        FOLLOW[p[i]].update(FIRST[p[j]])
                        j += 1

# 构造 SLR(1) 分析表
ACTION = {}
GOTO = {}
for i in range(len(P)):
    ACTION[i] = {}
    GOTO[i] = {}
for i, X in enumerate(P):
    for a in VT:
        ACTION[i][a] = ('error', None)
    for j, Y in enumerate(P[X]):
        if Y in VT:
            k = j
            while k < len(P[X]) - 1 and P[X][k + 1] in VN and FIRST[P[X][k + 1]].issubset(set([Y])):
                k += 1
            if k == len(P[X]) - 1 and Y in FIRST[P[X][k]]:
                ACTION[i][Y] = ('reduce', X)
            else:
                ACTION[i][Y] = ('error', None)
        elif Y in VN:
            k = j
            while k < len(P[X]) - 1 and P[X][k + 1] in VN and FIRST[P[X][k + 1]].issubset(FOLLOW[Y]):
                k += 1
            if k == len(P[X]) - 1 and FOLLOW[Y].issubset(FOLLOW[X]):
                GOTO[i][Y] = X
            else:
                ACTION[i][Y] = ('error', None)
ACTION[0]['f'] = ('shift', 1)
ACTION[1]['['] = ('shift', 2)
ACTION[2]['X'] = ('reduce', 'A')
ACTION[2]['f'] = ('shift', 3)
ACTION[3]['X'] = ('shift', 4)
ACTION[4][','] = ('shift', 5)
ACTION[4][']'] = ('reduce', 'A')
ACTION[5]['X'] = ('shift', 6)
ACTION[6][']'] = ('reduce', 'A')
ACTION[6][','] = ('shift', 5)
ACTION[0]['S'] = ('goto', 7)
ACTION[3]['S'] = ('goto', 8)
ACTION[7]['$'] = ('accept', None)
ACTION[8]['='] = ('shift', 9)
ACTION[9]['E'] = ('shift', 10)
ACTION[10]['$'] = ('reduce', 'S')
ACTION[10]['+'] = ('shift', 11)
ACTION[10]['-'] = ('shift', 12)
ACTION[11]['T'] = ('shift', 13)
ACTION[12]['T'] = ('shift', 14)
ACTION[13]['$'] = ('reduce', 'E')
ACTION[13]['+'] = ('shift', 11)
ACTION[13]['-'] = ('shift', 12)
ACTION[14]['$'] = ('reduce', 'E')
ACTION[14]['+'] = ('shift', 11)
ACTION[14]['-'] = ('shift', 12)
ACTION[9]['T'] = ('shift', 15)
ACTION[15]['*'] = ('shift', 16)
ACTION[15]['/'] = ('shift', 17)
ACTION[15]['$'] = ('reduce', 'T')
ACTION[16]['F'] = ('shift', 18)
ACTION[17]['F'] = ('shift', 19)
ACTION[18]['$'] = ('reduce', 'T')
ACTION[18]['*'] = ('shift', 16)
ACTION[18]['/'] = ('shift', 17)
ACTION[19]['$'] = ('reduce', 'T')
ACTION[19]['*'] = ('shift', 16)
ACTION[19]['/'] = ('shift', 17)
ACTION[15]['F'] = ('shift', 20)
ACTION[20][')'] = ('reduce', 'F')
ACTION[20]['+'] = ('reduce', 'F')
ACTION[20]['-'] = ('reduce', 'F')
ACTION[20]['*'] = ('reduce', 'F')
ACTION[20]['/'] = ('reduce', 'F')
ACTION[20]['$'] = ('reduce', 'F')
ACTION[20][','] = ('reduce', 'F')
ACTION[9]['('] = ('shift', 21)
ACTION[21]['E'] = ('shift', 10)
ACTION[21]['X'] = ('shift', 22)
ACTION[22][')'] = ('reduce', 'F')
ACTION[22]['+'] = ('reduce', 'F')
ACTION[22]['-'] = ('reduce', 'F')
ACTION[22]['*'] = ('reduce', 'F')
ACTION[22]['/'] = ('reduce', 'F')
ACTION[22]['$'] = ('reduce', 'F')
ACTION[22][','] = ('reduce', 'F')

3. 语法制导翻译过程实现

# 定义语法制导翻译过程中需要用到的各种数据结构和函数
from collections import deque

# 符号表，用于存储变量名及其对应的值
symbol_table = {}

# 中间代码生成器，用于生成中间代码
class CodeGenerator:
    def __init__(self):
        self.code = []
        self.temp_var_count = 0
    
    def new_temp_var(self):
        self.temp_var_count += 1
        return 't{}'.format(self.temp_var_count)
    
    def emit(self, op, arg1, arg2, result):
        self.code.append((op, arg1, arg2, result))

# 语义动作函数，对应每一个产生式，用于执行语义动作
def action_S(A, E):
    code.emit('call', 'f', A, len(A))

def action_A(X):
    return [X]

def action_A_X(A, X):
    A.append(X)
    return A

def action_E(E1, op, T):
    if op == '+':
        result = code.new_temp_var()
        code.emit('add', E1, T, result)
        return result
    elif op == '-':
        result = code.new_temp_var()
        code.emit('sub', E1, T, result)
        return result

def action_T(T1, op, F):
    if op == '*':
        result = code.new_temp_var()
        code.emit('mult', T1, F, result)
        return result
    elif op == '/':
        result = code.new_temp_var()
        code.emit('div', T1, F, result)
        return result

def action_F_X(X):
    return X

def action_F_E(E):
    return E

def action_F(A):
    return symbol_table[A]

# 解释器，用于执行中间代码
class Interpreter:
    def __init__(self, code):
        self.code = code
        self.stack = deque()
    
    def execute(self):
        for op, arg1, arg2, result in self.code:
            if op == 'add':
                arg1_val = self.stack.pop()
                arg2_val = self.stack.pop()
                self.stack.append(arg2_val + arg1_val)
            elif op == 'sub':
                arg1_val = self.stack.pop()
                arg2_val = self.stack.pop()
                self.stack.append(arg2_val - arg1_val)
            elif op == 'mult':
                arg1_val = self.stack.pop()
                arg2_val = self.stack.pop()
                self.stack.append(arg2_val * arg1_val)
            elif op == 'div':
                arg1_val = self.stack.pop()
                arg2_val = self.stack.pop()
                self.stack.append(arg2_val / arg1_val)
            elif op == 'call':
                args = []
                for i in range(arg2):
                    args.append(self.stack.pop())
                args.reverse()
                result = action_F(arg1)(*args)
                self.stack.append(result)
            else:
                self.stack.append(result)

# 将输入的字符串解析为单词序列
def tokenize(input_str):
    tokens = []
    i = 0
    while i < len(input_str):
        if input_str[i] in ['+', '-', '*', '/', ',', '(', ')', '[', ']']:
            tokens.append(input_str[i])
            i += 1
        elif input_str[i] == 'f':
            tokens.append('f')
            i += 1
            if input_str[i] != '[':
                raise ValueError('Expected '[' after 'f'')
            tokens.append('[')
            i += 1
            while input_str[i] != ']':
                if not input_str[i].islower():
                    raise ValueError('Expected lowercase letter as parameter name')
                tokens.append(input_str[i])
                i += 1
                if input_str[i] == ',':
                    tokens.append(',')
                    i += 1
            tokens.append(']')
            i += 1
            if input_str[i] != '=':
                raise ValueError('Expected '=' after parameter list')
            tokens.append('=')
            i += 1
        elif input_str[i].islower():
            tokens.append(input_str[i])
            i += 1
        elif input_str[i].isspace():
            i += 1
        else:
            raise ValueError('Unexpected character: {}'.format(input_str[i]))
    return tokens

# 语法分析器，使用 SLR(1) 分析表进行语法分析，并执行语义动作
def parse(tokens):
    stack = [0]
    i = 0
    while True:
        state = stack[-1]
        token = tokens[i]
        action, arg = ACTION[state][token]
        if action == 'shift':
            stack.append(arg)
            i += 1
        elif action == 'reduce':
            X = list(P.keys())[arg]
            rhs = P[X]
            if X == 'S':
                return
            elif X == 'A':
                A = [stack.pop()]
                while True:
                    top = stack.pop()
                    if top == 1:
                        break
                    elif top == 2:
                        continue
                    else:
                        A.append(top)
                A.reverse()
                stack.append(GOTO[stack[-1]]['A'])
                stack.append(action_A_X(A, tokens[i]))
            elif X == 'E':
                T = stack.pop()
                op = stack.pop()
                E1 = stack.pop()
                stack.append(GOTO[stack[-1]]['E'])
                stack.append(action_E(E1, op, T))
            elif X == 'T':
                F = stack.pop()
                op = stack.pop()
                T1 = stack.pop()
                stack.append(GOTO[stack[-1]]['T'])
                stack.append(action_T(T1, op, F))
            elif X == 'F':
                top = stack.pop()
                if top == 'X':
                    stack.append(GOTO[stack[-1]]['F'])
                    stack.append(action_F_X(tokens[i]))
                    i += 1
                elif top == ')':
                    E = stack.pop()
                    stack.pop()
                    stack.append(GOTO[stack[-1]]['F'])
                    stack.append(action_F_E(E))
            else:
                stack.append(GOTO[stack[-1]][X])
        elif action == 'goto':
            stack.append(arg)
        elif action == 'accept':
            return

# 运行代码
code = CodeGenerator()
input_str = 'f[a,b]=a+b*(c-d)'
tokens = tokenize(input_str)
parse(tokens)
print(code.code)
interpreter = Interpreter(code.code)
symbol_table['a'] = 1
symbol_table['b'] = 2
symbol_table['c'] = 3
symbol_table['d'] = 4
interpreter.execute()
print(interpreter.stack.pop())  # 输出 3
语法制导翻译与中间代码生成：实现简单的编程语言

原文地址: https://www.cveoy.top/t/topic/osC8 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录