HNU-编译原理-讨论课1

讨论课安排：2次4学时，分别完成四大主题讨论

分组：每个班分为8组，每组4~5人，自选组长1人

要求和说明：

1. 以小组为单位上台报告；每次每组汇报2个小主题，每组按要求在2个小主题中各选1题（共2题）作为报告内容；小组为每个小主题各选1~2名代表作为报告人展示PPT，PPT中需说清楚小组成员分工；主讲人不可重复。
2. 一个组10分钟：每个小主题5分钟，先统一汇报完主题一后再进行主题二的汇报。
3. 制作PPT时要说清相关算法或者解决问题的思路，并结合具体实例进行讲解，如：习题中有相关例题，应选择相关例题；实验中有相关示例，可结合相关示例。
4. 每次上课，学生自带电脑和讨论课PPT及相关素材，组长负责清点到课人数，汇报给班长，汇总后报助教和任课老师。
5. 每个小组每堂讨论课后，要写出总结报告（电子稿），提交老师，于小班课当周内发给助教和教师；小组长将本组报告PPT（每组两份，一个主题1份）于小班课当周内发给助教和教师。
6. 提交的总结报告需包含本组报告主题内容的详细介绍，以及其他小组分享内容的简要总结。
7. 千万不要从网上下载，然后照本宣科，抄录照搬记0分。

第一次讨论课

小主题一（每组任选其一）：

1. 编译发展历史，包括编译原理/理论的发展史、编译工程/技术的发展史以及编译史上的名人；
2. 编译原理中用到的数学知识及相关数学概念的简要介绍；
3. 编译原理学科的研究现状及主流研究方向简介，需调研编译领域的最新顶会论文；
4. 编译原理在其他学科中的应用，包括在其他学科工程实践中的应用以及最新科研中的应用；
5. 主流编译器介绍，包括各自历史、特点、区别与联系。

小主题二（每组任选其一）：

1. 词法分析器；
2. 正则表达式；
3. NFA转DFA；
4. DFA最小化；
5. DFA代码化；
6. TINY；
7. LEX。

小班讨论PPT如下：

 

 

编译原理第一次小班总结

小主题一：编译原理在其他学科中的应用包括在其他学科工程实践中的应用以及最新科研中的应用

编译原理在应用领域的示例

编程语言设计和实现：

    编译原理直接应用于编程语言的设计和实现。编译器用于将高级编程语言翻译成机器代码，同时语言设计者使用编译原理的概念来创建新的编程语言。

自然语言处理（NLP）：

    编译原理中的词法分析和语法分析技术在自然语言处理中用于解析和理解文本，从而帮助机器理解和生成自然语言。

数据库管理系统(DBMS)：

    查询编译器用于解析SQL查询并将其转化为可执行的查询计划，以便数据库管理系统可以高效地检索和操作数据。

硬件描述语言：

硬件描述语言（如VHDL和Verilog）使用编译原理的技术来将硬件电路描述翻译成可在FPGA或ASIC上实现的逻辑。

虚拟机和解释器：

    编译原理的原则也用于创建虚拟机和解释器（Java与JVM），它们用于执行脚本语言和字节码。

优化编译器：

    编译原理中的优化技术用于改进代码的性能，例如，提高程序的执行速度和减少内存使用。

上学期CS课程讨论课7的challenge减少程序存储占用与OS课程Lab系列中有遇到

并行计算：

    在并行计算领域，编译原理的原理用于生成并行代码，

以充分利用多核处理器和分布式系统的性能。

机器学习：

    在深度学习和机器学习领域，编译原理的技术用于优化计算图的执行，以加速训练和推断过程。

安全性和隐私：

    编译原理有助于开发安全编码实践，以减少漏洞和攻击面。它还可以用于静态分析和漏洞检测。

编译原理与自然语言处理

详细讲解：自然语言中的词法分析与语法分析技术

词法分析（Lexical Analysis）：

应用：词法分析是将文本分解成离散单元（标记）的过程，如单词或标点符号。它有助于理解文本的结构，识别单词，并为后续的语法分析和语义分析提供输入。

示例：在自然语言处理中，词法分析通常涉及将文本分解成单词和标点符号。

例如，将句子 "I love coding." 分解成 ["I", "love", "coding", "."] 这些词法单元，以便后续的处理。

三个中间步骤：

扫描（Scanning）：文本被扫描并分解成连续的字符，然后分析器识别出每个标记的起始和结束位置。

识别标记（Tokenization）：标记（Tokens）是文本的基本构建块，通常是单词或标点符号。标记包括单词（如名词、动词、形容词）、标点符号（如句号、逗号）等。

构建符号表（Symbol Table）：标记与其在文本中的位置一起存储在符号表中，以便后续的处理阶段可以访问它们。

语法分析（Syntax Analysis）：

应用：语法分析确定文本的结构，即句子中单词之间的语法关系。这有助于理解句子的语法，构建语法树，以及识别语法错误。

示例：在自然语言处理中，语法分析可用于确定句子的结构，例如主语、谓语和宾语。例如，对于句子 "The cat chases the mouse."，语法分析可以生成如下的语法树：

这个语法树显示了句子的结构，其中NP表示名词短语，

DT表示冠词，NN表示名词，VP表示动词短语，VB表示动词。

两个中间步骤：

分析语法规则（Parsing Grammar Rules）：语法分析器使用一组语法规则，这些规则定义了语言的结构和允许的句法。这些规则通常以上下文无关文法（CFG）的形式表示。

句法树生成（Syntax Tree Generation）：语法分析器根据语法规则将文本的标记组合成语法树，其中树的节点表示文本的不同部分，如名词短语（NP）和动词短语（VP）。

应用实例：

自动纠错：

应用：编译原理技术可以用于自然语言处理中的拼写检查和语法纠错。语法分析帮助识别句子中的语法错误，并建议修复。

示例：当用户输入 "She are a student."，语法分析可以检测到 "are" 在这个上下文中不正确，应该是 "is"，然后提供纠正建议，使句子变为 "She is a student."。

信息抽取：

应用：语法分析有助于识别句子中的实体、关系和事件，从而进行信息抽取，例如从新闻文章中提取关键信息。

示例：在一篇新闻文章中，语法分析可以帮助识别主题、主语、动词和宾语，从而构建信息抽取规则，以提取有关事件、地点和时间的信息。

机器翻译：

应用：语法分析用于将源语言句子分解成语法结构，并生成目标语言句子的语法结构，从而进行机器翻译。

示例：在机器翻译中，语法分析帮助理解源语言和目标语言之间的句法对应关系，从而更准确地进行翻译。例如，将英语句子 "I have a red car." 翻译成法语时需要考虑语法结构和词序，如 "J'ai une voiture rouge."

编译原理的其他运用

量子计算：编译原理用于优化和管理量子程序，以实现更高效的量子计算。

自动驾驶和机器人：编译原理的技术被用于编写和优化自动驾驶车辆和机器人的控制软件。

区块链和智能合约：编译原理技术被用于编写智能合约并对其进行验证，以确保其安全性和正确性。

智能合约（其在代码编写阶段需要使用到编译原理基础知识）

以信息化方式传播、验证或执行合同的计算机协议（允许在不存在第三方的情况下进行可信交易）

量子编程：随着量子计算的发展，新的编程语言和编译器涌现，以支持量子计算机的编程。

总结来说，编译原理是一个跨学科的领域，其原理和技术对于许多领域的科研和工程实践都具有重要意义，尤其是在处理复杂的计算和数据处理任务时。

小主题二：NFA转DFA

状态机引入

NFA——不确定的有穷自动机

DFA——确定的有穷自动机

DFA与NFA的区别

1、对于字母表中的每个符号，DFA中的每个状态都有且只有 至多有一条关于这个符号的出边（exiting transition）。NFA则未必，在同一个状态上可能有零条、一条甚至多条关于某一个符号的出边。

2、DFA的转换箭头上的标签必须是字母表中的，但NFA可以有标识为ϵ 的边，NFA的状态可能有零条、一条甚至多条ϵ 边。

DFA与NFA的等价性证明

假设： 我们有一个NFA，它包括状态集合Q、输入字母表Σ、状态转移函数δ、初始状态q0、和接受状态集合F。

目标： 我们的目标是构造一个等价的DFA，该DFA包括状态集合Q'、输入字母表Σ、状态转移函数δ'、初始状态q0'、和接受状态集合F'。

证明过程：

构建DFA状态集合Q'： 创建一个DFA状态集合Q'，其中每个DFA状态对应于NFA状态集合的某个子集。开始时，DFA只包含NFA的初始状态的ε闭包。

处理状态转移： 对于DFA中的每个状态q'，以及每个输入符号a ∈ Σ，计算从q'经过输入符号a可以到达的NFA状态集合，并计算这些状态的ε闭包。这将成为DFA中的下一个状态q'。确保在DFA状态q'中，对于每个输入符号a，只有一个确定的下一个状态。

标记接受状态： 如果DFA状态q'包含NFA的任何接受状态，则DFA状态q'也是接受状态。

继续构建DFA： 重复步骤2和步骤3，直到不再出现新的DFA状态。这可以通过使用队列或其他数据结构来实现，以确保所有状态都已处理。

构建DFA状态转移函数δ'： 根据得到的DFA状态集合和转移信息，构建DFA状态转移函数δ'，将输入符号映射到下一个状态。

构建DFA的接受状态集合F'： 通过步骤3的标记接受状态，确定DFA的接受状态集合F'。

证明等价性： 通过构建等效的DFA，已经成功证明了NFA和DFA是等价的，即它们都接受相同的语言。这是因为你以一种确定性的方式模拟了NFA，消除了非确定性。

NFA转DFA

ε_closure(s)表示由状态 s 经由条件 ε  可以到达的所有状态的集合

将集合记为状态A，B，C，D

其中我们定义ε_closure(0)为状态A，状态A{0，1，2，4，7}经过符号a可以到达{3，8}，ε_closure(3)={1，2，3，4，6，7}

ε_closure(8)={8}

D状态中包含终态9，需要注意

得到状态转换表

	a	b
A	B	C
B	B	D
C	B	C
D	B	C

由状态转换表得到状态转换图

其他组的简要总结

其他小组很多都选择了NFA转DFA，大都使用了子集构造法，但方法并不完全一样

部分小组在子集构造时，每出现一个子集都赋为一个新状态，而不考虑集合元素相同的情况，这样会导致最后写状态转换图时，还要进行化简。

另一方面

部分小组采用了上图的方式，与我组不同，以初态集合开始，直接寻找输入a,b的下一状态，相当于把我们组的一、两步合并来做