首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 峰会 看雪商城 证书查询
  1. 社区
  2. 软件逆向
    3. 发新帖
[原创]入门编译原理之前端体验
发表于: 2023-9-3 14:03 9113

[原创]入门编译原理之前端体验

_THINCT 活跃值
2023-9-3 14:03
9113

高级语言表示
IDA Pro等工具可以将汇编代码反编译为高级语言表示，但这些表示通常仍然是汇编级别的，难以进行高级分析和修改。LLVM提供了更高级别的中间表示（IR），可用于表示程序的结构和行为，这使得在此IR上进行分析和修改更加容易和灵活。
了解LLVM可以让逆向工程师理解编译器如何优化和变换代码，这对于逆向工程中的代码分析非常有用。例如，通过查看优化后的LLVM IR，您可以了解程序的性能特征和潜在的漏洞。

反汇编和反编译结合：
在逆向工程中，通常需要将反汇编的结果与反编译的结果相结合，以获得更全面的分析。了解LLVM可以帮助您更好地理解反编译器输出的高级语言表示，从而更有效地与反汇编结果结合使用。

向大佬致敬：

上面讲到的路线已经是大佬的大成之作了，作为老菜鸟，在这逆向之前还得先了解基于编译原理的编译器的正向开发开发才行。
接下来的文章，会以 前端(PrattParser) + IR(LLVM) + 后端(LLVM) 三部分来入坑编译原理。每部分点到为止，旨在理解编译原理各个环节的意义。

本文为了第一部分前端内容。前端主要由词法+语法+语义组成。单从概念上学习会很晦涩，所以会用带有变量的计算器小程序来辅助理解。

这个小计算器的代码是使用PrattParse模式来实现的。

上面的代码已经涵盖了词法、语法、语义三部分了。主要理解：

PrattParser核心：递归下降

Pratt Parser的特点是，它按照操作符的优先级来解析表达式，构建一个具有层次结构的AST。每个操作符都与一个处理函数相关联，该函数负责构建AST的一部分。通过递归调用这些处理函数，Pratt Parser可以正确地处理操作符优先级，并构建出正确的AST。

在上面的Python代码示例中，Pratt Parser的核心部分是parse_expression方法。这个方法递归地解析表达式，并根据操作符的优先级构建AST。每次处理一个操作符时，它会递归调用parse_expression以处理更高优先级的操作符，直到整个表达式被解析为一个AST。

# Token 类用于表示词法分析器生成的令牌
class Token:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value
 
# Lexer 类负责将输入文本解析成令牌流
class Lexer:
    def __init__(self, text):
        self.text = text  # 要解析的文本
        self.pos = 0      # 当前解析位置
 
    # 获取下一个令牌
    def get_next_token(self):
        if self.pos >= len(self.text):
            return Token("EOF")  # 如果已经到达文本末尾，返回一个表示结束的令牌
         
        current_char = self.text[self.pos]
 
        # 如果当前字符是字母，则解析标识符
        if current_char.isalpha():
            identifier = ""
            while self.pos < len(self.text) and self.text[self.pos].isalnum():
                identifier += self.text[self.pos]
                self.pos += 1
            return Token("IDENTIFIER", identifier)
 
        # 如果当前字符是数字，则解析数字
        if current_char.isdigit():
            self.pos += 1
            return Token("NUMBER", int(current_char))
     
        # 如果当前字符是运算符，则解析运算符
        if current_char in "+-*/":
            self.pos += 1
            return Token("OPERATOR", current_char)
 
        # 如果当前字符是等号，则解析为赋值符号
        if current_char == "=":
            self.pos += 1
            return Token("ASSIGN", "=")
 
        # 如果当前字符是分号，则解析为分号
        if current_char == ";":
            self.pos += 1
            return Token("SEMICOLON", ";")
 
        # 如果当前字符是左括号，则解析为左括号
        if current_char == "(":
            self.pos += 1
            return Token("LPAREN", "(")
 
        # 如果当前字符是右括号，则解析为右括号
        if current_char == ")":
            self.pos += 1
            return Token("RPAREN", ")")
 
        # 如果当前字符是空格或制表符，则忽略并获取下一个令牌
        if current_char in " \t":
            self.pos += 1
            return self.get_next_token()
 
        raise ValueError("Invalid character")  # 如果遇到无法识别的字符，引发异常
 
# Parser 类负责解析令牌流并计算结果
class Parser:
    def __init__(self, lexer):
        self.lexer = lexer  # 词法分析器
        self.current_token = self.lexer.get_next_token()  # 当前令牌
        self.variables = {}  # 存储变量名和值的字典
 
    # 解析整个表达式
    def parse(self):
        results = []
        while self.current_token.type != "EOF":
            result = self.parse_statement()
            results.append(result)
            if self.current_token.type == "SEMICOLON":
                self.eat("SEMICOLON")
        return results
 
    # 解析语句（赋值语句或表达式语句）
    def parse_statement(self):
        if self.current_token.type == "IDENTIFIER":
            variable_name = self.current_token.value
            self.eat("IDENTIFIER")
            self.eat("ASSIGN")
            expression_value = self.parse_expression()
            self.variables[variable_name] = expression_value
            return expression_value
        elif self.current_token.type == "SEMICOLON":
            self.eat("SEMICOLON")
            return None  # 处理分号
        else:
            return self.parse_expression()
 
    # 解析表达式
    def parse_expression(self, min_precedence=0):
        left = self.parse_atom()
 
        while self.current_token.type == "OPERATOR" and self.precedence(self.current_token.value) >= min_precedence:
            operator = self.current_token.value
            self.eat("OPERATOR")
            right = self.parse_expression(self.precedence(operator) + 1)
            left = self.apply_operator(left, operator, right)
 
        return left
 
    # 解析原子表达式（数字、变量、括号）
    def parse_atom(self):
        if self.current_token.type == "NUMBER":
            value = self.current_token.value
            self.eat("NUMBER")
            return value
        elif self.current_token.type == "IDENTIFIER":
            variable_name = self.current_token.value
            self.eat("IDENTIFIER")
            if variable_name in self.variables:
                return self.variables[variable_name]
            else:
                raise ValueError(f"Undefined variable: {variable_name}")
        elif self.current_token.type == "LPAREN":
            self.eat("LPAREN")
            expression = self.parse_expression()
            self.eat("RPAREN")
            return expression
        else:
            raise ValueError("Invalid syntax")
 
    # 吃掉一个令牌并获取下一个令牌
    def eat(self, token_type):
        if self.current_token.type == token_type:
            self.current_token = self.lexer.get_next_token()
        else:
            raise ValueError("Unexpected token")
 
    # 运算符优先级
    def precedence(self, operator):
        precedence = {"+": 1, "-": 1, "*": 2, "/": 2}
        return precedence.get(operator, 0)
 
    # 应用运算符
    def apply_operator(self, left, operator, right):
        if operator == "+":
            return left + right
        elif operator == "-":
            return left - right
        elif operator == "*":
            return left * right
        elif operator == "/":
            return left / right
 
# 计算函数，接受一个表达式并返回计算结果
def calculate(expression):
    lexer = Lexer(expression)
    parser = Parser(lexer)
    results = parser.parse()
    return results
 
# 测试代码
expression = "x = 3 * (4-1); y = 2*x + 2;"
# expression = "7"
results = calculate(expression)
print(results)  # 输出结果为 [9, 20]
# Token 类用于表示词法分析器生成的令牌
class Token:
    def __init__(self, type, value=None):
        self.type = type
        self.value = value
 
# Lexer 类负责将输入文本解析成令牌流
class Lexer:
    def __init__(self, text):
        self.text = text  # 要解析的文本
        self.pos = 0      # 当前解析位置
 
    # 获取下一个令牌
    def get_next_token(self):
        if self.pos >= len(self.text):
            return Token("EOF")  # 如果已经到达文本末尾，返回一个表示结束的令牌
         
        current_char = self.text[self.pos]
 
        # 如果当前字符是字母，则解析标识符
        if current_char.isalpha():
            identifier = ""
            while self.pos < len(self.text) and self.text[self.pos].isalnum():
                identifier += self.text[self.pos]
                self.pos += 1
            return Token("IDENTIFIER", identifier)
 
        # 如果当前字符是数字，则解析数字
        if current_char.isdigit():
            self.pos += 1
            return Token("NUMBER", int(current_char))
     
        # 如果当前字符是运算符，则解析运算符
        if current_char in "+-*/":
            self.pos += 1
            return Token("OPERATOR", current_char)
 
        # 如果当前字符是等号，则解析为赋值符号
        if current_char == "=":
            self.pos += 1
            return Token("ASSIGN", "=")
 
        # 如果当前字符是分号，则解析为分号
        if current_char == ";":
            self.pos += 1
            return Token("SEMICOLON", ";")
 
        # 如果当前字符是左括号，则解析为左括号
        if current_char == "(":
            self.pos += 1
            return Token("LPAREN", "(")
 
        # 如果当前字符是右括号，则解析为右括号
        if current_char == ")":
            self.pos += 1
            return Token("RPAREN", ")")
 
        # 如果当前字符是空格或制表符，则忽略并获取下一个令牌
        if current_char in " \t":
            self.pos += 1
            return self.get_next_token()
 
        raise ValueError("Invalid character")  # 如果遇到无法识别的字符，引发异常
 
# Parser 类负责解析令牌流并计算结果
class Parser:
    def __init__(self, lexer):
        self.lexer = lexer  # 词法分析器
        self.current_token = self.lexer.get_next_token()  # 当前令牌
        self.variables = {}  # 存储变量名和值的字典
 
    # 解析整个表达式
    def parse(self):
        results = []
        while self.current_token.type != "EOF":
            result = self.parse_statement()
            results.append(result)
            if self.current_token.type == "SEMICOLON":
                self.eat("SEMICOLON")
        return results
 
    # 解析语句（赋值语句或表达式语句）
    def parse_statement(self):
        if self.current_token.type == "IDENTIFIER":
            variable_name = self.current_token.value
            self.eat("IDENTIFIER")
            self.eat("ASSIGN")
            expression_value = self.parse_expression()
            self.variables[variable_name] = expression_value
            return expression_value
        elif self.current_token.type == "SEMICOLON":
            self.eat("SEMICOLON")
            return None  # 处理分号
        else:
            return self.parse_expression()

[招生]科锐逆向工程师培训(2024年11月15日实地，远程教学同时开班, 第51期)

最后于 2023-9-3 14:16 被_THINCT编辑 ，原因：
收藏
免费 ・7
支持
分享
最新回复 (2)
秋狝
雪    币： 2948
活跃值： (30846)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
感谢分享
2023-9-4 09:12
1
xjh88232259
雪    币： 108
能力值： ( LV1，RANK：0 )
在线值：
发帖
回帖
粉丝
私信
3 楼
谢谢楼主分享。
2023-9-5 09:04
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//