营销型网站免费模板国际时事新闻2022最新

本篇讲解编译原理基础知识，看完选择不必再死记硬背，大题不再蒙圈  ^_^

一  编译概述

1.翻译程序的三种方式：编译，解释，汇编

2.编译程序的五个阶段：词法分析，语法分析，语义分析和中间代码生成，代码优化，目标代码生成（其中中间代码生成和代码优化非必须）

二 文法与语言

2.1 符号串和语言

字母表：字母表是有穷非空的符号集合，通常用大写英文字母和希腊字母Σ表示

符号串：由字母表中的符号组成的又穷序列，通常由小写英文字母表示

字母表就像一个装满各种小零件的盒子，这些零件就是我们的符号，它们可能是各种形状，颜色和大小的字母，数字或特殊符号，但这个盒子是有限的，只能装下有限多的小零件；符号串就是用这些零件编手链，你可以决定零件的个数，顺序，是否重复使用等，或者什么都不穿做一条“空串”

符号串的前缀和后缀：若z=abd是字母表Σ={a,b,c,d}上的符号串，则ε，a，ab，abd都是z的前缀；ε，d，bd，abd都是z的后缀（前缀：从第一个字符开始到某个字符为止的子串；后缀：从某个字母开始到最后一个字符为止的子串）

语言：由字母表上的一些符号串组成的集合，空集Ø是一个语言，仅含一个空符号串的集合{ε}也是一个语言。Ø和{ε}是不同的语言

2.2文法和语言的形式化定义

文法的形式化定义：

1.产生式规则
    1）定义：一般形式为 前件—>后件
    2）非终结符号：产生式规则左部出现的符号；终结符号：不是非终结符号的符号。非终结符号既可以出现在产生式规则的左部，也可以出现在产生式规则的右部。终结符号不能出现在产生式规则的左部。非终结符号通常用大写字母或尖括号括起来的部分表示。
2.文法
    1）定义：产生式规则的非空有穷集合。由四元组G=(VN，VT，P，Z)组成。
    2）VN：是一个非空有穷集合。它的每个元素称为非终结符号。且VN∩VT=Ø；VT：是一个非空有穷集合。它的每个元素称为终结符号；P：是文法规则(产生式规则)的非空有穷集合，每个产生式规则的形式是A→α或A::=α，其中A∈VN，α∈(VN∪VT)*；Z：是一个非终结符号。称为开始符号或识别符号。它至少要在一条产生式规则的左部出现。有它开始识别定义的语言。

语言的形式化定义：

1.直接推导与推导
    1）直接推导：推导的一种特殊情况，如果我们有一个符号串S，那么根据产生式S -> aSb，我们可以直接推导出aSb，这就是一个直接推导
    2）推导：通过一系列直接推导步骤得到最终目标串，如果我们从S开始，并应用产生式S -> aSb，我们可以得到aSb。然后，我们可以继续推导，将aSb中的S替换为aSb，得到aaSbb。这个过程就是一个推导，它包含了多个直接推导步骤
2.句型和句子                                                                                                                                   设有文法：S → aAb | ε      A → b
    1）句子：从S开始，应用规则得到句子aAb，和aab，需要经过一次或多次推导
    2）句型：aAb是一个句型，由起始符号S经过一次或多次推导直接得到，包含一个非终结符A和两个终结符a，b
3.语言：由文法产生的所有句子组成的集合
4.递归规则(直接递归)：用于描述可以无限次重复的结构S → S'       S' → S'0 | S'1 | ε
5.文法递归：发生在规则右部间接引用其自身的情况E → E + T | T   T → T * F | F   F → (E) | id

设有以下文法规则：S → AB
A → aA | ε
B → Bb | ε

考虑句型ab的一个推导过程：S
→ AB (使用S的规则)
→ aAB (使用A的规则)
→ abB (再次使用A的规则)
→ ab (使用B的规则)

短语：由一个或多个终结符号和非终结符号组成，AB，aAB，abB，aA等都是短语
直接短语：由一个非终结符直接推导出，aA（因为A→aA）AB（S的直接短语）等是直接短语
句柄：一个句型的最左直接短语成为句柄，当aAB推导出abB时，aA是这个步骤的句柄……

2.3语法分析树和文法二义性

语法分析树：一个句型推导过程的树形表示成为语法分析树，简称语法树

文法二义性：若一个文法存在某个句子对应两棵不同的语法树，则称这个文法是二义的

2.4语言的分类：

0型文法：短语文法，至少含有一个非终结符；

1型文法：上下文有关文法，形如α→β，但要求α中字符数不多于β中字符数；

2型文法：上下文无关文法，要求α只能是一个非终结符；

3型文法：正规文法，产生式右侧只能包含一个终结符后跟一个非终结符，或者只包含一个终结符或空串

 

三 词法分析与有限自动机

3.1词法分析器

作用：输入源程序，输出单词符号，识别源代码中各种标记，并将他们转化成内部表示形式

3.2 有限自动机

这里可能会考识图或化简，以及正规式和正规文法与有限自动机的转换，有限自动机本身的定义很简单。

 

四  语法分析

1.最左推导与最右推导：这两种方法是语法分析的基础技术。最左推导是从开始符号出发，选择产生式的左侧进行替换，直到得到句子；而最右推导则是选择产生式的右侧进行替换。
2.自顶向下分析：这种方法从语法结构的顶部开始，逐步向下分析。它通常使用递归下降分析，根据输入流中的下一个终结符，选择最左非终结符的一个候选式进行替换。自顶向下分析的一个关键步骤是构造预测分析表，以指导分析过程。比如LL分析法
3.自底向上分析：与自顶向下分析相反，自底向上分析从输入序列的底部开始，逐步向上归约。它使用如算符优先分析法、LR分析法等算法。
4.基于规则的语法分析：这种方法利用一系列语法规则来识别输入序列中的结构。规则可以是显式的（如上下文无关文法中的产生式），也可以是隐式的（如基于状态机的分析）。

 

暂时这些，想到其他考点再补充……