编译原理考试简明教程。
2012版 powerup
一．概念。1.编译器的阶段。
2.分析与综合。
定义：将分析源程序以计算其特性的编译器操作归为编译器分析；将生产编译**时所涉及到的操作称作编译器的综合。
分析部分：词法分析，语法分析，语义分析；
综合部分：**生成；
优化步骤中，分析和综合都有。
优点：将分析和综合区分开来，有利于减少发生变化时的相互影响。
3.前端，后端。
定义：将编译器分成了只依赖于源语言（前端）的操作和只依赖于目标语言（后端）的操作两部分。
前端部分：扫描程序，分析程序，语义分析，中间**的综合；
后端部分：**生成，一些优化分析；
dfa定义：dfa m由字母表∑、状态集合s、转换函数t：s×∑→s、初始状态s0∈s以及接受状态的集合as组成。
由m接受的且写作l (m) 被定义为字符c1c2 . cn 串的集合，其中每个ci∈∑，存在状态s1 = t (s0, c1 ),s2 = t (s1, c2sn = t(sn-1 , cn )，其中sn 是a（即一个接受状态）的一个元素。
nfa定义：nfa m由字母表∑、状态的集合s、转换函数t : ss)、s 的初始状态s0，以及s的接受状态a的集合组成。
由m接受的语言写作l (m)，它被定义为字符c1c2 . cn ，其中每一个ci 都属于∑∪，且存在关系：s1 在t (s0 , c1 ) 中、s2 在t (s1 , c2 ) 中、.
sn 在t (sn-1 , cn ) 中，sn是a中的元素。
5.扫描程序与语法分析程序的任务。
扫描程序任务：它执行词法分析将字符序列收集到称作记号的有意义的单元中，还可完成与识别记号一起执行的其他操作（如将标识符输入到符号表中）。
语法分析程序任务：从扫描程序中获得记号形式的源**，并完成定义程序结构的语法分析。语法分析定义了程序的结构元素及其关系。语法分析的结果通常为分析树或语法树。
6.上下文无关文法，最左/最右推导。
上下文无关文法定义：由以下各项组成：
1） 终结符集合t。（2） 非终结符集合n（与t不相交）。
3） 产生式或文法规则a→a的集合p，其中a是n的一个元素，a是（t∪n）*中的一个元素（是终结符和非终结符的一个可为空的序列）。
4） （s为）来自集合n的开始符号。
令g是一个如上所定义的文法，g = t, n, p, s)，则g为上下文无关文法。
最左（右）推导：指每一步中最左（右）的非终结符都要被替代的推导。
最左（右）推导数学表示：在推导的每一步αaγαβ都有α（γt*
7.自底向上分析和自顶向下分析。
算法。（1）ll(1)属于自顶向下算法，其他为自底向上算法。
（2）lr(0)和slr(1)的dfa是一样的。
（3）lr(1)与lr(0)的dfa相比，多了先记号。
二．写正规表达式（nfa ->dfa ->最小化）
构造（thompson结构）的三种基本结构：
1）基本正则表达式（2）并置（3）选择（4）重复。
转dfa：将状态t通过ε转换到达的状态视为状态t的一部分。
最小化：先将状态集合分为非接受状态和接受状态两个集合，通过转换来再分状态：如果某条转换到达不同的状态，则需要拆分状态。
三．写最左/最右推导，画分析树、抽象语法树。
1.最左（右）推导：指每一步中最左（右）的非终结符都要被替代的推导。
2.画分析树：按推导过程的每一步画，非叶结点为非终结符，叶节点为终结符。
3.抽象语法树：去掉分析树中不必要的信息，并调整结构（例如：表达式的抽象语法树中非叶节点为操作符，叶节点为操作数）
四．表明语法是二义性的。
举反例？用定理去证明？
五．给定文法，写递归下降分析。
六．给定文法，1）提取左因子，消除左递归。
提取左因子：p→αγ转为 p→αp’， p’ →
消除左递归：p→pα|β转为 p→βp’， p’ →p’|ε
2）构造first和follow集
first：1.在构造first(a)时，只看左边为a的文法规则；
2.终结符的first集合为本身；
3.将右边第一个记号的first（除了ε）包含进来，如果第一记号可以为空，将第二个记号的first（除了ε）也包含进来，如此反复处理右边所有字符；
4.如果右边的每个记号都可以为ε，则ε∈first(a)
follow：1.在构造follow(a)时，只看右边包含a的文法规则；
2.取a之后的记号的first（除了ε）集合加入到follow中；
3.如果a之后的记号可以为ε，则将左边记号的follow集合包含进来。
3）表明是否为ll(1)文法。
1.对于有多个选择的文法，每一个选择的first集合都不相交。
2.对于first包含了ε的非终结符，它的first与follow集不相交。
4）构造ll(1)分析表。
1.设a∈first(α)将a→α添加到m[a, a]中。
2.设a∈follow(a)，如果ε∈first(α)将a→α添加到m[a, a]中。
5）写出分析动作：根据分析表写。
七．给定文法，1）构造lr(0)或lr(1)的dfa
2）构造lr(0)或slr(1)或lr(1)或lalr(1)分析表。
3）证明是lr(0)或slr(1)，若不是，描述它的冲突。
归约-归约冲突，移进-归约冲突。
4）写出lr(0)或slr(1)的分析步骤。
八．算法：dfa code
（1）多层循环嵌套。
（2）双层case嵌套+状态变量：tiny的scanner
（3）表驱动：转换表t[state][ch]，先行转换advance[state][ch]，接受状态accept[state]
ll(1)分析。
1）计算first和follow集：六。（2）中。
2）构造分析表m[n,t]：六。（4）中。
lr(0)分析。
1）画lr(0)项的dfa图：先画nfa再转dfa；直接画dfa，如果状态包含a→α.bγ，b为非终结符，则状态需包含b的初始项（b→.xy）；
2）构造分析表：根据dfa图构造，与slr(1)不同的是，如果状态x包含了完整项(b→y.)，则该状态只能进行归约（如果还包含非完整项，则出现移进-归约冲突；如果包含其他完整项，则出现归约-归约冲突）。
slr(1)分析。
1）dfa与lr(0)的dfa相同。
2）构造分析表：与lr(0)不同的是，在包含完整项和非完整项的状态，可通过输入符号来判定应该移进还是归约（对于包含完整项(b→y.)的状态，如果还包含非完整项且其下一个符号在follow(b)中，则出现移进-归约冲突；如果还包含其他完整项且与b的follow有交集，则出现归约-归约冲突）
编译原理 A withanswer
北京交通大学。2011 2012 学年第二学期期末考试试题 a 课程名称 编译原理出题教师 徐金安于双元丁丁 专业班级姓名学号。注意 请将所有题答案写在答题纸上，标明题号。一 选择题 每空2分，共20分 1 编译程序的各个阶段都涉及 b a 词法分析b 管理和错误处理。c 语法分析d 语义分析。2 ...
编译原理试题
语法分析 自顶向下的分析。重点与难点。重点 自顶向下分析的基本思想，分析器总体结构，分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。难点 first和follow集的求法，对它们的理解以及在构造ll 1 分析表时的使用。递归子程序法中如何体现分析的结果。基本要求。掌握语法分析 ...
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式，并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合，并判断该文法是否是ll 1 的，请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...