1.1做网站的目的,抖音代运营怎么做,早教网站建设方案,青岛的建筑公司本篇讲解编译原理基础知识#xff0c;看完选择不必再死记硬背#xff0c;大题不再蒙圈 ^_^ 一 编译概述
1.翻译程序的三种方式#xff1a;编译#xff0c;解释#xff0c;汇编
2.编译程序的五个阶段#xff1a;词法分析#xff0c;语法分析#xff0c;语义分析和中… 本篇讲解编译原理基础知识看完选择不必再死记硬背大题不再蒙圈 ^_^ 一 编译概述
1.翻译程序的三种方式编译解释汇编
2.编译程序的五个阶段词法分析语法分析语义分析和中间代码生成代码优化目标代码生成其中中间代码生成和代码优化非必须
二 文法与语言
2.1 符号串和语言
字母表字母表是有穷非空的符号集合通常用大写英文字母和希腊字母Σ表示
符号串由字母表中的符号组成的又穷序列通常由小写英文字母表示 字母表就像一个装满各种小零件的盒子这些零件就是我们的符号它们可能是各种形状颜色和大小的字母数字或特殊符号但这个盒子是有限的只能装下有限多的小零件符号串就是用这些零件编手链你可以决定零件的个数顺序是否重复使用等或者什么都不穿做一条“空串” 符号串的前缀和后缀若zabd是字母表Σ{a,b,c,d}上的符号串则εaababd都是z的前缀εdbdabd都是z的后缀前缀从第一个字符开始到某个字符为止的子串后缀从某个字母开始到最后一个字符为止的子串
语言由字母表上的一些符号串组成的集合空集Ø是一个语言仅含一个空符号串的集合{ε}也是一个语言。Ø和{ε}是不同的语言
2.2文法和语言的形式化定义
文法的形式化定义
1.产生式规则 1定义一般形式为 前件—后件 2非终结符号产生式规则左部出现的符号终结符号不是非终结符号的符号。非终结符号既可以出现在产生式规则的左部也可以出现在产生式规则的右部。终结符号不能出现在产生式规则的左部。非终结符号通常用大写字母或尖括号括起来的部分表示。 2.文法 1定义产生式规则的非空有穷集合。由四元组G(VNVTPZ)组成。 2VN是一个非空有穷集合。它的每个元素称为非终结符号。且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和两个终结符ab 3.语言由文法产生的所有句子组成的集合 4.递归规则(直接递归)用于描述可以无限次重复的结构S → S S → S0 | S1 | ε 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的规则)
短语由一个或多个终结符号和非终结符号组成ABaABabBaA等都是短语 直接短语由一个非终结符直接推导出aA因为A→aAABS的直接短语等是直接短语 句柄一个句型的最左直接短语成为句柄当aAB推导出abB时aA是这个步骤的句柄……
2.3语法分析树和文法二义性
语法分析树一个句型推导过程的树形表示成为语法分析树简称语法树
文法二义性若一个文法存在某个句子对应两棵不同的语法树则称这个文法是二义的
2.4语言的分类
0型文法短语文法至少含有一个非终结符
1型文法上下文有关文法形如α→β但要求α中字符数不多于β中字符数
2型文法上下文无关文法要求α只能是一个非终结符
3型文法正规文法产生式右侧只能包含一个终结符后跟一个非终结符或者只包含一个终结符或空串 三 词法分析与有限自动机
3.1词法分析器
作用输入源程序输出单词符号识别源代码中各种标记并将他们转化成内部表示形式
3.2 有限自动机
这里可能会考识图或化简以及正规式和正规文法与有限自动机的转换有限自动机本身的定义很简单。 四 语法分析
1.最左推导与最右推导这两种方法是语法分析的基础技术。最左推导是从开始符号出发选择产生式的左侧进行替换直到得到句子而最右推导则是选择产生式的右侧进行替换。 2.自顶向下分析这种方法从语法结构的顶部开始逐步向下分析。它通常使用递归下降分析根据输入流中的下一个终结符选择最左非终结符的一个候选式进行替换。自顶向下分析的一个关键步骤是构造预测分析表以指导分析过程。比如LL分析法 3.自底向上分析与自顶向下分析相反自底向上分析从输入序列的底部开始逐步向上归约。它使用如算符优先分析法、LR分析法等算法。 4.基于规则的语法分析这种方法利用一系列语法规则来识别输入序列中的结构。规则可以是显式的如上下文无关文法中的产生式也可以是隐式的如基于状态机的分析。 暂时这些想到其他考点再补充……
