编译原理

🚧🚧🚧 暂待施工🚧🚧🚧

绪论

编译系统由哪些部分组成?

阶段程序指的是 特定阶段进行处理的程序

守护程序指的是 守护程序是指在整个编译程序的生命周期中一直在运行的程序

上面的定义是我自己瞎取的, 方便理解记忆

阶段程序

• 词法分析程序
• 语法分析程序
• 语义分析程序
• 中间代码生成程序
• 代码优化程序
• 目标代码生成程序

守护程序

• 信息表管理程序
• 错误检查和处理程序

四元式

规则:

• (运算符, 运算对象, 运算对象, 临时变量)
• 先处理优先级高的一部分, 然后向左遍历
• 每一次运算结果用一个临时变量存起来, 以便后续使用

逆波兰式

规则:

• 遇到字母直接写到答案里
• 遇到符号, 压入栈中
• 遇到成对的括号才出栈
• 新加入的符号, 优先级必须大于(没有等于)原栈顶优先级, 否则栈中原符号出栈

答案没有括号

例题:

A+B*(C-D)+F/(C-D)^N

答案

ABCD-*+FCD-N^/+

前置知识

文法

产生式(规则)

非终结符 定义为 终结符

左部 右部

句型 规则的右部

句子 完全由终结符组成的句型称为句子

语言 句子的集合

闭包合正闭包

最左推导和最右推导

所有短语

(简单短语)直接短语

句柄

正规式转正规文法

NFA, DFA, 最小化

初态集 不含集合终态

终态集 含有集合终态0

覆盖

题目类型

句子推导

• 最左推导

• 最右推导

语法树的短语

简单优先和算符优先

• 非叶子结点的短语

• 层数为2的非叶子结点的直接短语

• 包含终结符, 出自己意外不含其他素短语 素短语

• 最左非叶子结点的句柄

文法二义性

需要一定的灵感

证明是否有二义性

找一个句子, 看从左和从右开始推导看语法树是否不一样

文法生成语言和已知语言生成文法

文法及文法的类型（0型、1型、2型、3型文法）?

NFA和DFA

• ???

• 子集法 (NFA->DFA)

• 划分法

LL(1)自顶向下分析

• 消除文法左递归和回溯

• 构造LL(1)的分析表

• 对字符串#adbc进行语法分析

• First集 首非终结符集合

• Follow集合 紧跟, 开始符 Follow集有#