形式语言与自动机 + 编译原理考试突击

这是汇总突击的知识梳理部分

Note

• 极限预习，突击用时一周，从第一章开始学，时间刚刚好🤡
• 最终得分: 90/100
• PS: 这门课我用NJU课程学习，XJTU课程只是应付下考试而已

自动机理论

DFA-NFA-RE

• [x] DFA-NFA-RE

DFA 是五元组 (𝑄,Σ,𝛿,𝑞0,𝐹)，分别表示状态，符号集，迁移函数，开始状态，接收状态集

DFA 扩展转移函数 𝛿^:𝑄×Σ∗→𝑄

NFA 是五元组 (𝑄,Σ,𝛿,𝑞0,𝐹)，其中 𝛿:𝑄×Σ→2𝑄

NFA 扩展转移函数 𝛿^:𝑄×Σ∗→2𝑄

𝜀-NFA 是五元组 (𝑄,Σ,𝛿,𝑞0,𝐹)，其中 𝛿:𝑄×(Σ∪{𝜀})→2𝑄

• 𝜀-NFA 到 DFA：ECLOSE(𝑟) 与子集构造
• NFA 到 DFA：（惰性）子集构造，𝑂(𝑛32𝑛)
• DFA 到 RE：消除状态得 GNFA，𝑂(𝑛34𝑛)；证明：归纳法
• RE 到 𝜀-NFA：𝑂(𝑛)

泵引理证正则：

存在 𝑛 使得对任意 𝑤∈𝐿，若 |𝑤|≥𝑛，我们能写成 𝑤=𝑥𝑦𝑧，其中 |𝑥𝑦|≤𝑛，|𝑦|≥1，且 ∀𝑘≥0,𝑥𝑦𝑘𝑧∈𝐿

泵引理证非正则使用反证法，由上推论引出矛盾。或者

对于任意 𝑛 存在串 𝑤∈𝐿，且 |𝑤|≥𝑛，使得对任意书写 𝑤=𝑥𝑦𝑧，|𝑥𝑦|≤𝑛，|𝑦|≥1，存在 𝑘≥0 使 𝑥𝑦𝑘𝑧∉𝐿

正则语言的封闭运算：交并补、连接反向、闭包

• 交 𝐿∩𝐿′：状态对
• 并 𝐿∩𝐿：揉起来
• 补 𝐿𝐶：DFA 改变接收状态拒绝状态
• 连接 𝐿𝐿′：正则表达式连接
• 逆 𝐿𝑅：DFA 反向
• 幂 𝐿𝑘：𝑘 个表达式连接
• 闭包 𝐿∗：表达式的闭包

DFA 最小化：区分状态等价类填 𝑛×(𝑛−1) 的下三角表

DFA 等价性：放在一起填表，区分开始状态是不是等价

• [x] DFA-eNFA-RE转换 // DFA最小化

PDA-CFG-CFL

• [x] CFG产生

CFG 是四元组 𝐺=(𝑉,𝑇,𝑃,𝑆)，分别是变元集，终结符集，产生式集，开始符号

产生式惯用法

• 变元：字母表开头大写字母 A，B，C
• 终结符：字母表开头小写字母 a，b，c
• 符号（终结符或变元）：字母表结束大写字母 X，Y，Z
• 终结符串：字母表结束小写字母 w，x，y，z

• 符号串：𝛼，𝛽，𝛾

• [x] 推导

直接推导 𝛼𝐴𝛽⇒𝛼𝛾𝛽⟺𝐴→𝛾

连续推导 𝛼𝐴𝛽⇒∗𝛼𝛾𝛽⟺𝐴⇒⋯⇒𝛾

多于一次的推导 𝛼𝐴𝛽⇒+𝛼𝛾𝛽

最左推导 ⇒𝑙𝑚，最右推导 ⇒𝑟𝑚

• [x] 句型与句子

句型：从开始符号推导的任意串

句子：从开始符号推导的终结符串

规约：序列 𝛼1,⋯,𝛼𝑛，其中 𝛼1=𝑤，𝛼𝑛=𝑆，𝛼𝑖⇐𝛼𝑖+1

歧义文法：该文法存在一个串是多个语法树的产物；该文法存在一个串存在两个不同最左推导

固有歧义的：语言的每个文法均是歧义的

• [x] CFG化简

CFG 化简：

找网课

• 消除 𝜀-产生式：删去可空变元，重写产生式，若出现无用符号则消除
• 消除单位产生式：对于单位产生式推导的序列，以最后的产生式（组）替代单位产生式的产生式变元（检查所有变元序对）
• 无用符号（先消 无产出 后消 不可达 ）
  • “非产生” 的变元：推导不出终结符串（无候选式、死循环）
  • “非可达” 符号：不出现在任意句型中的符号

注意以上简化步骤的次序

乔姆斯基范式：每个产生式右侧仅有 两个变元或一个终结符

PDA 是七元组 (𝑄,Σ,Γ,𝛿,𝑞0,𝑍0,𝐹)，分别为状态集，输入字母集，栈字母集，迁移函数 𝛿:𝑄×(Σ∪{𝜀})→2𝑄×Γ∗，初始状态，开始符号，终结状态集

PDA 的移动 (𝑝,𝛾)∈𝛿(𝑞,𝑎,𝑋)：状态 𝑞 移动到 𝑝，消耗输入符号 𝑎，使用 𝛾 替代 𝑋 作为新栈顶

PDA 图示边标记格式：输入符号，弹出符号/压入符号串

瞬时描述 ID：(𝑞,𝑤,𝛼)，当前状态，剩余串和栈内容

迁移：ID 𝐼 在一次移动变为 ID 𝐽，记为 𝐼⊢𝐽

定理 6.5 与 6.6：串里看不见的符号不影响迁移

终结状态定义语言，空栈定义语言可互相模拟

确定性 PDA：至多存在一个迁移（可以是 𝜀-迁移）

• [x] 模拟CFG与PDA之间的互相转换

找网课

• CFG 到 PDA：仅三个状态，迁移模拟移入，𝜀-迁移模拟规约
• PDA 到 CFG

编译原理概要

源语言、实现语言、目标语言

宿主机器、目标机器

词法分析、语法分析、语义分析、代码优化、代码生成

源程序、中间表示、目标代码

词法分析（<种属，值>）：关键字一符一种、全体一种

语法分析

自上而下语法分析

• [x] LL(1) 文法（自顶向下）

LL(1) 文法：无二义性，无回溯（无左递归，无左公因子，候选式 FIRST 不相交，若候选首符含空则其 FIRST 交 FOLLOW 为空）

LL(1) 分析：从左到右扫描，最左推导，向前查看一个

消除左递归：对非终结符排序，对每个终结符看前面的终结符，将代带入前面终结符的候选，消除直接左递归（𝐸→𝐸𝛼 | 𝛽 到 𝐸→𝛽𝐸′；𝐸′→𝛼𝐸′ | 𝜀）

FIRST(𝛼)：串 𝛼 能推导出来的串的 最左侧终结符（或空符）集合

求解 FIRST 迭代法：首先构造非终结符 FIRST，然后根据串构造

FOLLOW(A)：所有句型中符号 A 右侧的终结符（或结束符）

求解 FOLLOW：先求 FIRST，后遍历产生式

提左公因子：加变元消去公因子

递归下降语法分析：每个变元构造一个过程

构造预测分析表 M[A, a]，对于每一个产生式 𝐴→𝛼：

• 对任意 𝑎∈FIRST(𝛼)，M[A, a]=𝐴→𝛼
• 若 𝜀∈FIRST(𝛼)，M[A, b]=𝐴→𝛼，𝑏∈FOLLOW(𝐴)

错误处理：

• 栈顶终结符与输入不匹配：弹出
• M[A, b] == null：Sync

预测分析表的使用：状态栈和剩余字符串

自下而上的分析

短语：有 𝑆⇒∗𝛼𝐴𝛿，且 𝐴⇒+𝛽，则 𝛽 是句型 𝛼𝛽𝛿 相对于规则 𝐴→𝛽 的短语

直接短语：若 𝐴⇒𝛽，则 𝛽 是句型 𝛼𝛽𝛿 相对于规则 𝐴→𝛽 的直接短语

句柄：句型的 最左直接短语

规范规约（最左规约）：最右推导的逆过程

LR(0) 文法：项目集不包含冲突项目

增广文法：在 𝐺 中增加 𝑆′→𝑆

活前缀 NFA：初态 𝑆′→∙𝑆，从状态 𝑋→⋯𝑋𝑖−1∙𝑋𝑖⋯ 到 𝑋→⋯𝑋𝑖∙𝑋𝑖+1⋯ 有 𝑋𝑖 弧；到状态 𝑋𝑖→∙𝛽 有 𝜀 弧

直接构造活前缀 DFA：初态 𝑝0=CLOSURE({[S′→∙S]})，𝑞 的 𝑋 迁移到 𝑝 当且仅当 𝑝=CLOSURE({[A→𝛼X∙𝜂] | [A→𝛼∙X𝜂]∈q})

构造 LR(1) 分析表：使用活前缀 DFA，ACTION 为终结符迁移动作（点不在最后 shift / 点在最后 reduce），GOTO 为针对变元迁移动作（当 reduce 时使用）

SLR(1) 分析表：使用 FOLLOW 来加强规约的能力，则 SLR(1) 文法为对于所有项目集，移进项目与规约项目 FOLLOW 不相交的；重新定义项目使其带有 1 个终结符

LR 分析表使用：状态栈、符号栈和剩余字符串

归约项目（Reduction Item）

归约项目是指在LR分析中，一个项目已经匹配到某个产生式的右部，并准备应用这个产生式进行归约。形式上，它的特征是项目点在产生式右部的最右侧。

例如，对于产生式 A→αA \rightarrow \alphaA→α，归约项目表示为：

A→α⋅A \rightarrow \alpha \cdotA→α⋅

在这个项目中，点号（·）表示输入已经匹配了产生式 A→αA \rightarrow \alphaA→α 的右部，并且可以进行归约。

移进项目（Shift Item）

移进项目表示分析器当前已匹配到某个产生式的部分右部，且下一步需要将下一个输入符号移进来以继续匹配。形式上，它的特征是项目点位于产生式右部的非终结符或终结符之前。

例如，对于产生式 A→αβA \rightarrow \alpha \betaA→αβ，移进项目表示为：

A→α⋅βA \rightarrow \alpha \cdot \betaA→α⋅β

在这个项目中，点号（·）表示输入已经匹配了 α\alphaα，并且需要匹配 β\betaβ 以完成产生式的匹配。

接受项目（Accept Item）

接受项目是指在LR分析中，整个输入已经完全匹配文法的开始符号的产生式。这是一个特定的归约项目，表示分析成功地解析了整个输入。

对于文法的开始符号 SSS 和增加的产生式 S′→SS' \rightarrow SS′→S，接受项目表示为：

S′→S⋅S' \rightarrow S \cdotS′→S⋅

这里，点号（·）在产生式的最右侧，表示整个输入已经成功匹配并可接受。

待约项目（Handle Item）

待约项目是指在输入串中已经识别出某个子串，这个子串可以用一个产生式的右部进行替换（归约）。待约项目通常用来表示当前分析器正在考虑是否进行归约。例如，对于产生式 A→αA \rightarrow \alphaA→α，待约项目表示为：

A→α⋅A \rightarrow \alpha \cdotA→α⋅

这个术语有时与归约项目相似，因为它们都表示即将进行归约的状态

语义分析

属性文法

综合属性、继承属性；S-属性文法：仅有综合属性（自下而上）

属性方程，过程调用

中间表示

后缀式，图表示，三地址（四元式、三元式）

翻译

声明的翻译

VarD:   TYP L           {  
                            typfill($2.dtype, $1.dtype);  
                        }  
    ;  

L   :   id Dim, L       {  
                            typlink($2.dtype, $$.dtype);  
                        }  
    |   id Dim          {  
                            typlink($1.dtype, $$.dtype);  
                        }  
    ;  

Dim :   [num] Dim       {}  
    |   %empty          {}  
    ;  

Proc:   M Pdef          {}  
    ;  

M   :   %empty          {}  
    ;  

Pdef:   Pdef; Pdef      {}  
    |   procid  
    ;

嵌套过程声明：mktab(father) 建表，addwidth(tab,name,typr,offset) 填表，fillwidth(tab, width) 填表长，enterproc(tab, name, chtab) 建子表登记

函数调用的翻译

S   :   procid '(' args ')' {  
                                for (auto arg : $3.q) {  
                                    emit(par, arg, _, _);  
                                }  
                                emit(call, entry(procid), $3.q.size(), _);  
                            }  
    ;  

args:   args, E             { $1.q.push(E.place); $$.q = $1.q; }  
    |   E                   { $$.q = queue<void*>(); q.push(E.place); }  

数组引用的翻译

E   :   L   {  
                // and much more  
            }  
    ;  

L   :   EList ']'       {  

                        }  
    |   id              {  

                        }  
    ;  

EList   :   EList',' E  {  

                        }  
        |   id '[' E    {  

                        }  
        ;

&A[i,j]=base+((i-l_1)*(u_2-l_2)+j-l_2)*w

𝑏𝑎𝑠𝑒−𝐶+(⋯(((𝑖1)𝑑2+𝑖2)𝑑3+𝑖3)𝑑4⋯)𝑑𝑛+𝑖𝑛𝑙𝑘≤𝑖𝑘≤𝑢𝑘𝑑𝑘=𝑢𝑙−𝑙𝑘

𝐶=((⋯(((𝑙1)𝑑2+𝑙2)𝑑3+𝑙3)𝑑4⋯)𝑑𝑛+𝑙𝑛)𝑤

布尔表达式的翻译

E   :   E_1 or M E_2    {  
                            backpatch($$.falselist, M.quad);  
                            $$.truelist = merge($1.truelist, $4.truelist);  
                            $$.falselist = $4.falselist;  
                        }  
    |   E_1 and M E_2   {  
                            backpatch($$.truelist, M.quad);  
                            $$.falselist = merge($1.falselist, $4.falselist);  
                            $$.truelist = $4.truelist;  
                        }  
    |   not E_1         {  
                            $$.falselist = $2.truelist;  
                            $$.truelist = $2.falselist;  
                        }  
    |   '(' E_1 ')'     {  
                            $$.falselist = $2.falselist;  
                            $$.truelist = $2.truelist;  
                        }  
    |   id_1 rop id_2   {  
                            $$.truelist = makelist(nextquad);  
                            emit($2.jop, $1.place, $3.place, NULL);  
                            $$.falselist = makelist(nextquad);  
                            emit(j, NULL, NULL, NULL);  
                        }  
    |   id              {  
                            $$.truelist = makelist(nextquad);  
                            emit(jnz, $1.place, NULL, NULL);  
                            $$.falselist = makelist(nextquad);  
                            emit(j, NULL, NULL, NULL);  
                        }  
    ;  

M   :   %empty          {  
                            $$.quad = nextquad;  
                        }

控制语句的翻译

Contr   :   if E then       {  
                                bp($2.tc, nxq);  
                                $$.chain = $2.fc;  
                            }  
        ;  

Stmts   :   Contr Stmts     { $$.chain = merg($1.chain, $2.chain); }  
        |   ConEl Stmts     { $$.chain = merg($1.chain, $2.chain); }  
        |   A               { $$.chain = 0; }  
        |   Wd Stmts        {  
                                bp($2.chain, $1.quad);  
                                Gen(j, _, _, $1.quad);  
                                $$.chain = $1.chain;  
                            }  
        |   begin L end     { $$.chain = $2.chain; }  
        ;  

ConEl   :   Contr Stmts else{  
                                q = nxq; Gen(j, , , 0);  
                                bp($1.chain ,nxq);  
                                $$.chain = merge($2.chain, q);  
                            }  
        ;  

W       :   while           { $$.quad = nxq; }  
Wd      :   W E do          {  
                                bp($2.tc, nxq);  
                                $$.chain = $2.fc;  
                                $$.quad = $1.quad;  
                            }  
        ;  

L       :   Stmts           { $$.chain = $1.chain; }  
        |   Ls Stmts        { $$.chain = $2.chain; }  

Ls      :   L ';'           { bp($1.chain, nxq); }  

符号表

名字、类型（整、实、双精、布尔、字符、复、标号、指针等）、种属、变量地址长度、标号标志位置、形式参数标志；

局部变量（包括形式参数）占用的存储空间、返回结果类型、局部过程名及符号表指针、嵌套外层过程

内情向量表: Dim，base，Type/w， C，𝑙𝑖，𝑢𝑖，𝑑𝑖=𝑢𝑖−𝑙𝑖

注意ZYL 的PPT(ch9/10/11)里对于格式规范的要求

运行时空间组织

offset	chain	content
100		形参
99		……形参
98		参数个数
97		访问链
96	fp	控制链
95		返回地址
94		局部变量
93		……局部变量
92		超长数据
91	sp	超长数据

函数 <ip, ep> 作为参数，ip 代码入口，ep 实参求值的过程的活动记录

program c;  
    procedure p(procedure a);  
        begin  
            a;  
        end;  
    procedure q;  
        var x:integer;  
        procedure r;  
        begin  
            writeln(x);  
        end;  
    begin  
        x:=2;  
        p(r);  
    end;  
begin  
    q;  
end.

认为过程 r 的调用者是过程 q，则在 p 使用 r 时走 l_r-l_p+1 层访问链

Display 表：过程的嵌套层次显示表，记录该过程的各外层过程的最新活动记录的起始地址

运行时存储组织

编译程序是将源程序的算法描述部分和数据说明部分，分别翻译成机器目标代码和数据存储单元，最终获得目标程序。

目标程序在目标机环境中运行时，都置身于自己的一个运行时存储空间。在基于操作系统之上运行的情况下，目标程序将在自己的逻辑地址空间内运行并存储数据。编译程序在生成代码时，负责明确各类对象在逻辑地址空间是如何存放的，以及目标代码运行时，如何使用逻辑地址空间。

在编译过程中，源程序的对象地址分配往往是相对于运行存储空间的偏移量，对象访问采用“基地址＋偏移量”寻址方式进行，使得可以选择内存的任意可用区域作为目标程序运行时的存储区。这样生成的目标代码称为浮动地址代码

注：“基地址”是指运行存储空间之首址。

重点：符号表的内容、组织，过程调用实现，

静态存储分配、动态存储分配的基本方法。

难点：参数传递，过程说明语句代码结构，

​ 过程调用语句的代码结构，

​ 过程调用语句的语法制导定义，

​ 栈式存储分配。

运行时存储组织的任务和作用

编译程序生成的代码大小通常是固定的，一般存放在专用的区域，即代码区；
目标程序运行过程中，需要创建和访问的数据对象存放在数据区。

程序运行时存储空间的布局

![[image-20240627165240717.png]]

存储分配策略

数据空间分配是将源程序数据对象名与给定的数据存储空间地址建立映射关系。数据对象名与数据存储地址可能是一对多的关系，因为在源程序中说明的一个数据对象，在运行时可能对应不同的存储地址，如递归程序中的局部变量。

静态存储分配

静态存储管理是一种最简单的存储管理。当在编译阶段能够确定源程序中各个数据实体的存储空间大小时，就可以采用静态存储管理。一般而言，适于静态管理的语言必须满足下面的条件：

( 1 )、数组的上下界必须是常数；

( 2 )、过程调用不允许递归；

( 3 )、不允许用户动态地建立数据实体。

对于静态存储分配，数据空间仅需要有静态数据区即可。在源程序翻译时，对于所有数据对象，其分配的存储地址都是相对于静态数据区的偏移量。这个偏移量就是登记在符号表中数据对象的地址( .place)属性值。在目标程序运行时，访问数据对象的绝对地址是：

绝对地址＝静态数据区首址+偏移量。

动态存储分配

如果源语言允许递归调用、可变数组和允许运行期间自由申请与释放空间，那么其需占用的存储空间在编译阶段无法确定，这样数据对象就需要采用动态存储分配的策略。

所谓动态存储分配是指在运行期间，动态进行存储地址分配。

•基于控制栈的原理，存储空间被组织成栈，活动记录的推入和弹出分别对应于活动的开始和结束。

•与静态分配不同，在每次活动中把局部名字和新的存储单元绑定，在活动结束时，活动记录从栈中弹出，因此局部名字的存储空间也随之消失。

栈式动态存储分配

由于过程允许递归，在某一时刻一个过程A 很可能已被自己调用了若干次，但只有最近一次正处于执行状态，而其余各次则处于等待返回被中断的那次调用的状态。这样，属于每次调用相应的数据区中的内容就必须保存起来，以便于调用返回时继续使用。对于这种语言来说，其存储分配策略必须采用栈式存储管理，即引入一个运行栈，让过程的每一次执行和过程的调用记录相对应，每调用一次过程，就把该过程的相应调用记录推入栈中，过程执行结束时再把栈顶的调用记录从找中弹出。

在运行期间以子程序数据区为基本单位，在数据空间栈中进行动态地址分配。

当调用子程序时，在数据空间栈顶，给子程序分配所需的子程序数据区；

当子程序返回时，从数据空间栈顶，收回分配给子程序所占用存储区。

当子程序被递归调用时，同一个子程序可能在数据空间中同时拥有多个子程序数据区，每个数据区对应于同一个子程序的一次执行过程。

堆式动态存储分配

某些程序设计语言(如C 和PASCAL等）允许程序在运行时，为其中的一些变量动态地申请和释放所需的存储空间，并且申请和释放这两类操作可以在任何时间、以任意的顺序来进行，这就需要一种更为灵活和更加有效的动态分配策略，即堆式存储分配来完成上述工作。

堆式分配的基本思想是：为正运行的程序划出一适当大的存储区域，称之为堆（Heap) ; 每当该程序提出申请时, 就按某种分配原则在堆的自由区（可占用区） 中，找出一块能满足其需求的存储空间分配给它，对于释放操作，则是将程序不再占用的存储空间归还给堆的自由区。
可能遇到的各种情况与操作系统给进程分配存储空间时遇到的极其相似，如同样会出现“碎片”现象等，其根本差异就在于分配的层次和分配对象的粒度。

活动记录

1.活动记录本质是什么？

活动记录本质上是每次为函数调用时分配的一大块内存。一个函数的活动记录只由在函数被调用时才会创建，并且当函数返回时就会被销毁。

2.活动记录是如何存在的？

活动记录被组织在栈中，栈可以是物理上的实体也可以是逻辑上的概念。在数据结构中的栈是一个逻辑上的概念，而芯片中也可以根据这个概念来设计一部分电路，这部分能够模拟栈操作的电路就是物理意义上的栈了。
主函数的活动记录位于栈底，当一个函数调用另外一个函数时，被调用函数的活动记录就会被压入栈。或当记录所在的栈满足数据结构中的栈的特性：FILO(first in last out)。这个限制使得当主调函数和被调函数中出现了同名函数时，在执行被调函数时主调函数的变量对被调函数来说是不可见的。
特别提醒：大部分计算机为活动记录栈分配内存地址都是从高到低！

3.活动记录是如何进行入栈出栈的？

由于活动记录是位于一个栈中的，所以要近栈就需要知道栈结束处的位置，当出栈时就需要知道当前活动记录之前的一个活动记录的结束点。
所以编译器和硬件都会维护两个很重要的值：栈指针，帧指针。
栈指针：始终指向战结束处（注意不是栈底！）的地址，如果有新的活动记录入栈，那里就是新活动记录的起始地址所在。
帧指针：保存着先前那个活动记录的结束处的地址，在当前函数返回后，栈指针就会指向那里。
In short, 栈指针和帧指针就是用来界定活动记录的，并操作活动记录

复习重点

• [x] DFA-eNFA-RE转换: RE -> \(\epsilon NFA\) // \(\epsilon NFA\) -> DFA // DFA最小化
• [x] 模拟CFG与PDA之间的互相转换: 根据指定语言设计PDA / PDA-CFG / DPDA video
• [x] CFG化简 video // RE < DCFL < CFL < \(\Sigma\)
• [x] LL(1) 文法（自顶向下）
• [x] LR分析（自底向上）
• [x] 语法置导 && 符号表
• [x] 运行时空间组织

Following Video

最后一个先看PPT，其余找网课！

RE -> \(\epsilon NFA\)

https://www.bilibili.com/video/BV1fi4y1Q7Yz/?spm_id_from=333.788&vd_source=8a3dd36862125e80dc439254ef65d959

\(\epsilon NFA\) -> DFA

https://www.bilibili.com/video/BV1fi4y1Q7Yz/?spm_id_from=333.788&vd_source=8a3dd36862125e80dc439254ef65d959

DFA的化简

https://www.bilibili.com/video/BV1rY411J7cR/?spm_id_from=trigger_reload&vd_source=8a3dd36862125e80dc439254ef65d959

• 二义文法：对一部文法，如果至少存在一个句子，有两棵不同语法树，称该句子是二义性的，包含二义性的句子的文法称为二义文法。
• 上下文无关文法是否具有二义性是不可判定的。但有些特殊的2型文法[例如LL（1）、LR（0）、LR（1）等文法] 是 先天无二义性 的
• NFA和DFA的主要区别在于：1）DFA没有输入空串之上的转换动作。2）对于DFA，一个特定的符号输入，有且只能得到一个状态，而NFA就有可能得到一个状态集。DFA：只有唯一初态。NFA：有初态集。DFA是NFA的特例。
• 分析方法分两大类：自上而下分析法(推导) 和 自下而上分析法(归约)，最右推导是规范推导，逆过程为规范规约
  • 自上而下语法分析是：从G的 开始符号S 出发，通过反复使用产生式句型中的 非终结符 进行替换，逐步推导出源程序串，是一种产生的方法，面向目标的方法
  • 自下而上语法分析：从输入串开始不断寻找子串与文法G中 某个产生式P的候选式 进行匹配，并 用P的左部 代替之，逐步归约到S，是一种辨认的方法，基于目标的方法
• 短语，直接短语，句柄，素短语，最左素短语：（这里给出在语法树上的直观区别方法）
  • 短语：在语法树中表示所有分支结点对应子树，短语即子树叶子对应的符号。注： 子树包括语法树本身，及句型本身也可以称为短语
  • 直接短语：在语法树中表示为该短语只有上下相邻父子两代
  • 句柄：最左直接短语
  • 素短语：指一个短语至少包含一个终结符，并且除它自身之外不再包含其他素短语
  • 最左素短语：最左素短语就是句型最左边的素短语，是算符优先分析法的规约对象
• 翻译程序、编译程序、解释程序
  • 翻译程序：将用某种语言编写的程序转换成另一种语言形式的程序的程序
  • 编译程序：用高级语言编写的源程序转换（加工）成与之等价的另一种用低级语言编写的目标程序的翻译程序。
  • 解释程序：解释程序是高级语言翻译程序的一种，他将输入的源程序作为输入，解释一句后就提交给计算机执行一句，源程序命令被逐个直接解释执行
• 算符文法与算符优先文法:
  • 算符文法：任一产生式的右部都 不含两个连续非终结符 的文法
  • 算符优先文法：是不含空字符且对任一对终结符都有确定的><=关系的算符文法
• 字母表：元素的非空有穷集合
  符号：字母表中的元素
  符号串：字母表中符号组成的有穷序列
• 句子、句型、语言
  • 句型是由识别符Z推导而得的符号串
  • 句子是没有非终结符号的句型（句子是全为terminal的句型）
  • 语言是句子的集合
• 中间代码形式：常见的有逆波兰记号、三元式、四元式和树
  1. 逆波兰（也称后缀表示）：没有括号，易于计算机处理
  2. 三元式（运算符，对象1，对象2）：不便于优化但间接三元式，可以克服这个缺点
  3. 树形表示 三元式表示也可用相应的树形表示
  4. 四元式：（运算符; 对象1，对象2, 结果）：有利于代码优化