[原创]入门编译原理之前端体验-软件逆向-看雪-安全社区|安全招聘|kanxue.com

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

2023-9-3 14:03 7912

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

_THINCT

2023-9-3 14:03

7912

一、为什么要学习编译原理，使用LLVM？

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

二、学习编译原理的目标

使用retdec反编译器将目标程序转换成LLVM IR中间指令集的表示形式，以便进一步分析。
引入klee符号执行引擎，通过动态模拟LLVM IR中间指令集的运行，以尝试理解程序中的符号执行路径，而不是具体的数据值。
工具会分析程序中所有thiscall类型函数，这些函数通常用于对象导向编程，其中this指针用于访问对象的成员。工具会对这些函数进行插桩，以收集有关对this指针结构体的引用和偏移量信息。
工具将分析的信息进行汇总，以自动识别this结构体的具体内容，这有助于理解程序中对象的布局和内部结构。
最后，工具会将这些信息集成到IDA Pro工具中，以辅助进行更深入的分析和逆向工程。
向大佬致敬：

三、简单的开始

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

从小项目来演练

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

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

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

# 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]

重点理解

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

# 运算符优先级
def precedence(self, operator):
    precedence = {"+": 1, "-": 1, "*": 2, "/": 2}
    return precedence.get(operator, 0)

PrattParser核心：递归下降

# 解析表达式
    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)

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

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

四、最后补上难懂的名词

词法（Lexicon） 是一个语言或领域中的一组单词、术语或符号的词汇表。它类似于一种语言的"字典"，其中包含了所有合法的单词或符号的清单，以及它们的含义和用法。这些单词和符号构成了语言或领域的基本构建块，用于建立句子、表达思想或进行沟通。
语法是一种规则系统，用于定义如何构建合法的句子、表达式或代码块。它是一种组织语言或编程语言中单词、符号和结构的方式，以确保它们具有正确的结构和含义。
想象一本语法就像是一本"语言食谱书"，它告诉你如何将词汇和符号组合在一起，以创建有意义的内容。在编程语言中，语法规则定义了如何编写有效的程序代码。这包括如何使用关键字、操作符、变量名和函数名，以及如何编写控制结构（例如，if语句和循环）。如果编程语言的语法规则不被遵守，编译器或解释器可能无法理解或执行代码。
语义是有关于词语、短语、句子或代码的含义和意义的方面。它涉及到更深层次的理解，而不仅仅是语法规则所定义的结构。可以将语义视为一种关于"是什么意思"以及"它是如何工作的"问题的研究。
在编程语言中，语义描述了代码的操作和行为。这包括变量如何存储和操作数据，函数如何执行特定的任务，以及程序的整体行为。编程语言的语义规定了代码的意图和效果，而不仅仅是代码的结构。例如，一段代码的语义可能是"将两个数字相加并返回结果"，这涉及到更多的意义和行为，而不仅仅是代码的语法。
AST，全名为抽象语法树（Abstract Syntax Tree），是一种用于表示编程语言代码结构的树状数据结构。它将源代码转化为树形结构，以便更容易地进行语法分析和程序处理。以下是一个简单形象的解释：
想象一下，你正在写一篇文章，这篇文章有章节、段落和句子。在一本书中，章节包含多个段落，段落包含多个句子。你可以将整篇文章的结构用一棵树来表示，树的根节点是文章，它分支出多个章节，每个章节又分支出多个段落，段落分支出多个句子，以此类推。这个树状结构帮助你更好地理解文章的结构和组织。
类似地，编程语言的代码也可以被表示成一棵树状结构，这棵树被称为AST。在AST中，根节点代表整个程序，它分支出多个语句，每个语句分支出多个表达式，表达式分支出多个操作符和操作数，以此类推。AST帮助编程语言解释器或编译器理解代码的结构和语法，并执行相应的操作，比如执行代码或生成机器代码。

[培训]内核驱动高级班，冲击BAT一流互联网大厂工作，每周日13:00-18:00直播授课

最后于 2023-9-3 14:16 被_THINCT编辑，原因：

#其他内容

收藏・15

点赞・7

打赏

最新回复 (2)
秋狝雪币： 19439 活跃值： (29125) 能力值： ( LV2，RANK：10 ) 在线值：发帖 0 回帖 1584 粉丝 31 关注私信	秋狝 2023-9-4 09:12 2 楼 1 感谢分享
xjh88232259 雪币： 803 能力值： ( LV1，RANK：0 ) 在线值：发帖 0 回帖 15 粉丝 1 关注私信	xjh88232259 2023-9-5 09:04 3 楼 0 谢谢楼主分享。
	游客登录 \| 注册方可回帖　回帖　表情雪币赚取及消费高级回复