《编译技术-2021秋》结课考试小结

适用人群：中国矿业大学计算机科学与技术专业学生

2021秋期末真题

题干为个人回忆版本，并对覃航和王唯一提供的版本进行补充，已尽力与原题目描述保持一致。答案来自本人理解，不确保与老师理解完全一致。

1、给出关于货币的自然语言描述：写正则表达式，画有限状态自动机，写代码。（难，考场上老师直接提醒了跳过去，先做后面的题）
2、最右推导，说明一个句型是该文法的句型；画出语法树；写出短语，直接短语，句柄。
3、LL（1），消除左递归，提取公共左因子，构造分析表。
4、LR（1），画出识别活前缀的DFA，构造分析表，说明为什么是LR（1）文法，写出句子的分析过程（考的分析失败！）。
5、while do - if then else - 布尔表达式和赋值语句，翻译成三地址代码。
6、给出文法和示例，构造翻译模式，写出递归下降子程序。（求嵌套深度，但不是括号的嵌套，L-属性文法。注意这里递归下降子程序是带语义动作的，以及不是所有的大写字母都是非终结符，要看具体问题描述。）

第一题

给出关于货币的自然语言描述

1. ：写正则表达式，画有限状态自动机，写代码。（难，考场上老师直接提醒了跳过去，先做后面的题）

考动态规划-最大子段和。

1. 结合题目内容描述最大子段和算法即可。
2. $O(n)$