编译原理基础（1）

1.什么是ASCII码？

ASCII码即美国信息交换标准代码，是基于拉丁字母的电脑编码系统，用于显示现代英语和部分西欧语言。其7位编码范围0-127，8位扩展到0-255。
字符集含控制字符（0-31、127，用于控制设备或表示通信信息，如换行、回车符）和可打印字符（32-126，包括英文字母、数字、标点和常用符号，如“A”是65，“0”是48）。
它在早期计算机系统、编程、网络通信中应用广泛，处理纯英文文本方便，但无法满足多语言字符表示需求。

2.什么是Unicode码？

Unicode是一种字符编码标准，旨在为世界上几乎所有的字符提供统一编码。
它涵盖多种语言文字、象形符号、特殊符号等超百万字符。
编码方式有UTF-8、UTF-16、UTF-32等，其中UTF-8可变长，ASCII字符占1字节，其他字符2-4字节；UTF-16基本多文种平面字符常占2字节，辅助平面字符占4字节；UTF-32固定每个字符占4字节。
它考虑了与ASCII码的兼容，能在同一系统处理多语言文本，提升了多语言环境下的兼容性与互操作性。

3.ASCII码和Unicode的区别？

ASCII码和Unicode都是字符编码标准，区别如下：

1. 编码范围：ASCII码用7位或8位二进制数，范围0-127（7位）或0-255（8位扩展）；

Unicode编码范围广，使用多种编码方式，能表示超百万字符。

2. 字符集涵盖：ASCII码主要是英语字符和常用控制字符；

Unicode涵盖世界多种语言字符、象形文字、特殊符号等。

3. 存储方式：ASCII码一般1个字节存一个字符；Unicode存储依编码方案，UTF-8可变长，ASCII字符1字节，其他2-4字节，UTF-16基本多文种平面字符常2字节，辅助平面4字节，UTF-32固定4字节。

4. 兼容性：ASCII码处理纯英文文本兼容性好，多语言处理受限；Unicode考虑与ASCII码兼容，如UTF-8，且能处理多语言文本，多语言环境兼容性和互操作性强。

4.语言分为什么？

语言分为 自然语言 和计算机语言。

5.什么是计算机语言？

计算机语言是人与计算机之间进行信息交流、沟通和指令传达的工具，是一种能够被计算机识别、理解并执行的指令集合，用于编写各种程序以实现特定的功能和任务。

计算机语言有：

机器语言：由二进制代码（0 和 1）组成，是计算机唯一能直接理解和执行的语言。不同类型的计算机硬件（如 CPU）有不同的机器语言指令集。机器语言执行效率高，但编写和阅读困难，开发成本高。
汇编语言：使用助记符（如 ADD 表示加法，MOV 表示数据传送等）来代替机器语言中的二进制指令，比机器语言更易理解和编写。但它仍然依赖于计算机硬件，属于低级语言，需要通过汇编器将其翻译成机器语言才能被计算机执行。
高级语言：更接近人类自然语言和数学表达式的编程语言，如 Python、Java、C++、C# 等。高级语言具有较好的可读性、可维护性和可移植性，程序员可以更专注于程序的逻辑和功能实现，而无需过多关注底层硬件细节。高级语言编写的程序需要通过编译器或解释器转换为机器语言才能在计算机上运行。

简单来说，汇编语言就是计算机符号形式的指令系统。

6.什么是翻译？

在编译原理里，翻译指的是把一种语言编写的源程序转化为另一种具有相同语义的目标程序的过程，通常是将高级编程语言编写的源程序转换为机器语言或汇编语言的目标程序。下面从翻译的基本概念、主要阶段、翻译的实现方式几个方面为你详细介绍：

基本概念

源语言与源程序：源语言是程序员用来编写程序的高级语言，像 Python、Java、C++ 等；用源语言编写的程序就是源程序。
目标语言与目标程序：目标语言是源程序经过翻译后所生成的程序的语言，常见的有机器语言、汇编语言；生成的程序就是目标程序。
翻译的本质：翻译过程其实是对源程序进行语义和语法分析，然后根据目标语言的规则和要求，把源程序的语义用目标语言重新表达出来。

词法分析

定义：词法分析器按从左到右的顺序对源程序的字符流进行扫描，依据词法规则将其识别为一个个单词（token）。
示例：对于源程序语句int num = 10;，词法分析器会将其识别为int（关键字）、num（标识符）、=（运算符）、10（常量）、;（界符）等单词。

语法分析

定义：语法分析器以词法分析得到的单词序列作为输入，依据语法规则来分析，构建出对应的语法树。
示例：对于上述语句，语法分析器会判断它是否符合该语言的语法规则，若符合就构建出一棵表示该语句语法结构的语法树。

语义分析

定义：语义分析器对语法树进行静态语义检查，比如类型检查、作用域分析等，确保源程序在语义上是正确的。
示例：在int num = "hello";语句中，语义分析器会发现将字符串赋值给整型变量存在类型不匹配的问题。

中间代码生成

定义：对语义分析后的语法树进行处理，将源程序转换为一种中间表示形式，中间代码与具体的机器无关，便于进行优化和生成目标代码。
示例：三地址码就是一种常见的中间代码形式，如x = y + z可表示为t1 = y + z; x = t1;。

代码优化

定义：对中间代码进行优化，在不改变程序语义的前提下，提升目标代码的运行效率、减少代码占用空间。
示例：对代码中的常量折叠、死代码删除、公共子表达式消除等操作。

目标代码生成

定义：把优化后的中间代码转换为目标机器的机器语言或汇编语言代码。
示例：根据目标机器的指令集，将中间代码x = y + z转换为具体的机器指令。

翻译的实现方式

编译方式：在编译方式下，编译器会对整个源程序进行一次性处理，生成目标程序。之后目标程序可以独立于编译器运行。像 C、C++ 等语言通常采用编译方式。
解释方式：解释器逐行读取源程序，边解释边执行，不会生成独立的目标程序。Python、Ruby 等语言常采用解释方式。
编译 - 解释混合方式：结合了编译和解释的特点，先将源程序编译成一种中间表示形式，然后再由解释器对中间表示进行解释执行，Java 就采用这种方式，先将 Java 源程序编译成字节码，再由 Java 虚拟机（JVM）对字节码进行解释执行。

7.什么是文法？

你可以把文法想象成是一种 “语言制造说明书”，它能告诉我们怎么造出符合语法规则的句子。无论是我们日常说的自然语言，还是计算机使用的编程语言，都可以用文法来描述它的语法结构。

文法主要由四个部分组成：

非终结符：就像是一些 “半成品零件”，它们本身不是最终的句子组成部分，但可以用来进一步 “组装” 句子。比如在描述一个算术表达式的文法里，“表达式” 这个概念就是一个非终结符，因为它还可以继续分解成其他部分，像 “数字 + 数字”。你可以把非终结符理解成是一个 “标签”，用来表示可以继续变化、组合的语法概念。
终结符：这就是最终构成句子的 “小零件”，不能再被拆分了。比如在算术表达式里，具体的数字（像 5、10 这些）、运算符（比如 “+”“-”“*”“/”），它们是构成表达式的基本元素，不能再按照文法规则进一步分解了。
产生式：它就像是 “组装说明书” 里的具体步骤，告诉我们怎么把非终结符变成其他的符号组合。比如 “表达式 → 数字 + 表达式” 这个产生式，意思就是一个 “表达式” 可以由一个 “数字” 加上另一个 “表达式” 组成。通过不断使用这些产生式，我们就能从一个非终结符开始，逐步构造出一个完整的句子。
开始符号：这是我们 “组装” 句子的起点，就像搭积木时，我们先拿出的第一块特定的积木。从这个开始符号出发，按照产生式的规则一步步推导，最终就能得到符合文法的句子。

8.什么是语法短语？

语法短语是在语法分析过程中，与某个非终结符相关联的子串。它基于语法规则，是源程序中符合一定语法结构的连续字符序列。简单来说，就是在句子里能根据语法规则被看成一个整体的部分。

9.什么是语法树？

语法树是一种直观表示句子语法结构的树形图。树的根节点是文法的开始符号，内部节点是非终结符，叶子节点是终结符。它清晰展示了句子是如何按照文法规则逐步推导出来的，体现了句子的层次结构和语法关系。

10.什么是巴科斯范式？

巴科斯范式是一种用于表示上下文无关文法的元语言，它提供了简洁、准确描述文法规则的方法。用巴科斯范式可以清晰定义编程语言的语法结构，便于程序员和编译器开发者理解和实现。

规则示例：

<expression> ::= <expression> + <term>
             | <expression> - <term>
             | <term>
<term> ::= <term> * <factor>
         | <term> / <factor>
         | <factor>
<factor> ::= ( <expression> )
           | number

11.符号表中为什么要设计字符串表这样一种数据结构？

标识符记录：编程语言里标识符（变量、函数名等）是字符串形式，符号表需以字符串存其名，便于后续找类型、作用域等信息。
字面常量存储：字符串字面常量常见，符号表记录它们，利于编译优化时如合并重复常量。
作用域管理：符号表处理不同作用域、命名空间的标识符，用字符串可记清所属信息，区分同名标识符。
错误诊断：编译出错时，符号表中字符串形式的标识符信息，便于生成准确易懂的错误提示。
与源程序映射：源程序代码元素多为文本（字符串），符号表用字符串可更好映射，利各编译阶段处理信息。