伟大的编译原理试卷

更伟大的是从2007年就开始流传出来的试卷，SCNUCS伟大的开源精神🙏🙏

心血来潮总结了编译原理近十多年的题目，想要摸索出亲爱的浴帘老师的出题规律，结果被现实狠狠打击，我以后再也不当赌狗了 TAT

提醒总结

一、基础知识题

【2023】修改正则表达式的文法【算术表达式】

【2023】在自顶向下分析中，文法需要满足什么条件，如果不满足如何修改

【2022】正则表达式和正则文法的转换

【2020】修改正则表达式的文法【算术表达式】

【2019】画出“数”DFA和词法分析程序代码段

【2018】纸币问题

【2015】ab 之间有任意个b或c 的正则和DFA

【2014】b 后必有一个a 的正则和DFA

【2010】 /* */的DFA和词法分析程序

【2009】 整数 的正则和DFA

【2007】 /* */ 的词法分析程序\

二、正则表达式 -> DFA

【2023】由NFA构建DFA需要求闭包 （两个状态之间的转移边权值为 a），要求设计算法求闭包。

【2023】十进制数的正则表达式和画出dfa

【2022】DFA 最小化的分拆方法程序【2021】最小化DFA算法程序

【2020】请画出 C++ 语言中单词的DFA图，并写出对应的词法分析程序。

【2020】以0开头的单词的正则表达式，画 DFA，写词法分析程序【0[a-zA-Z0-9]】【2019】DFA 图转换为词法分析的转换程序【需写出DFA的存储结构】

【2019】C语言中，无符号浮点数可以用十进制(非0打头)、八进制(0打头)、十六进制(0x打头)表示，请你用正则表达式表示C语言中的无符号浮点数，并写出该正则表达式的DFA图。

十进制：[0-9]+\.[0-9]*([eE][+-]?[0-9]+)?

八进制：0[0-7]*\.[0-7]*([eE][+-]?[0-9]+)?

十六进制：0[xX][0-9a-fA-F]+\.[0-9a-fA-F]*([pP][+-]?[0-9]+)?

综合：([0-9]+\.[0-9]*([eE][+-]?[0-9]+)?) | (0[0-7]*\.[0-7]*([eE][+-]?[0-9]+)?) | (0[xX][0-9a-fA-F]+\.[0-9a-fA-F]*([pP][+-]?[0-9]+)?)

【2018】售票机只接受1、2元纸币，每次扫描区的纸币大于等于3元时出一张票(但不找钱)，请设计正则表达式并画出DFA图。

【2018】c语言中数、以/开头的token的词法分析程序

【2015】有一只由 a和b和c构成的任意长度的字符串，特点:ab 之间有任意个b或c。要求:写出符合该要求的正则表达式和 DFA(可直接写出)。

【2014】有一只由a和b构成的任意长度的字符串，特点:b后必有一a。要求:写出符合该要求的正则表达式和 DFA。【2010】 写出/**/的DFA图和词法分析程序

【2009】 请写出实验一有关 C 语言词法分析中整数的正则表达式及相应的 DFA

【2009】请将正则表达式转换为 NFA,然后再将该 NFA 转换为 DFA. (a|b)*(aa|bb)\

三、自顶向下分析题

【2023】写出正则表达式的&,|,*,()的文法，然后用递归下降方法写出子程序，最后输出后缀表示

【2023】求Follow集合的分析程序（已有First集合可以用）

【2022】左递归的检测程序 、消除直接左递归和间接左递归的程序

【2021】写出消除直接和间接左公因子的算法程序

【2020】请写出 C 语言中 if-else 语句的文法，并用语法树为其生成四元组，写出该语法树的程序。

【2020】求follow集合

【2019】定义逻辑表达式的文法规则、语法树存储结构、对应的语法树生成算法

【2019】修改tiny语言if文法，模仿c语言，自顶向下方法生成语法树【2018】用自顶向下的方法判断一棵二叉树是否为二叉搜索树

【2015】写出逆波兰表达式的文法和对应 LL1表

【2014】S->a+(闭包)b+(闭包)c*,(其中a的个数等于b的个数)，画LL(1)分析表

【2010】 构造算数表达式的语法树代码【2009】 请构造IF那一堆文法的 LL（1）分析表

【2007】请写出TINY while 语句对应语法树的存储结构

四、LR分析题

【2023】判断是否是SLR(1)的文法的程序(要存储结构，First和Follow已经给出)

【2023】要求设计文法表示括号匹配(括号有三种，分别是{、(、[)，并问设计出来的文法是不是SLR(1)文法

【2022】请写出支持选择()、连接、闭包(*)、可选(?)和括号等运算的正则表达式的文法，并画出该文法的 LR(0)DFA 图和判断其是否为 SLR(1)文法。

【2021】实现后缀表达式，能做加减乘除求余运算，写好文法后，手动实现LALR（1）的DFA以及分析表

【2020】判断是否是SLR(1)的文法的程序(要存储结构

【2019】不以0开头的正奇数文法，判断是否slr(1)文法，能否sIr(1)分析

【2019】括号匹配(............(...)..)，{、(、[的Ir文法规则，判断是否为slr语法

【2019】新增for的文法规则，并判断是否为LR0，是否为SLR1

【2018】写文法，判断是否是SLR1文法

【2015】写出声明变量的文法和SLR分析表

【2014】判断是否是SLR1，不是的话画出LR1的DFA

【2010】画有左公因子文法的LR1分析表

【2009】画有移进冲突文法的LR1分析表

【2007】求first

五、语义分析题

【2023】写出二进制转十进制的文法规则和语义程序

【2023】改写Tiny中if-stmt语句，写出生成四元组的属性文法（讲稿原题几乎是）

【2022】根据广义表建立二叉树/语法树，写出文法规则和语义函数

【2022】声明语句 写出文法和语义函数

【2021】正则表达式（连接选择括号闭包），并且写出语义动作，生成四元组

【2020】八进制转十进制的文法规则和语义程序

【2019】四元组，但是看不太懂题目

【2019】dowhile语句的文法规则和语义函数

【2018】switch语句的文法规则和语义函数

【2015】写出二叉树广义表的文法，并添加语义函数

【2014】解决括号匹配的文法规则，写出语义动作或函数

【2010】将ifelse的代码片段翻译成四元组

【2009】将ifelse的代码片段翻译成四元组

【2007】将ifelse的代码片段翻译成四元组

六、综合分析设计

【2023】TINY 的dowhile语句

【2023】设计正则表达式文法，并根据递归下降的子程序分析法写语法树的生成程序

【2022】TINY处理十进制浮点数，包括带小数部分和科学计数法

【2022】TINY 的 FOR 语句

【2020】用编译原理的方法计算矩阵相乘时间规模

【2019】设计正则表达式文法，并根据递归下降的子程序分析法写语法树的生成程序

【2019】增加TINY 的数据类型 int, bool, char, real

【2018】TINY 的switch语句

【2018】 TINY 增加常量Const定义

【2015】增加TINY 的运算符 +=、-=、*=、/=

【2014】增加TINY 的数据类型 int, bool, char, real

【2010】计算矩阵相乘时间规模的思路和程序

【2009】将一个代数的算术表达式的括号去掉

【2007】课程感悟（羡慕

写出改写后的文法规则

描述词法、语法分析程序

写出语义分析程序

每章考什么

chap01

chap02

正则表达式及DFA正则表达式的几种符号给出特定的things正则表达式及DFA：十进制数、注释、c++单词题目：正则转NFA（画出NFA、把NFA进行连接）、NFA转DFA（消除epslion、消除多重转换、闭包？）、DFA最小化（分拆和合并）DFA转词法分析

chap03 语言和文法

相关知识点：文法、上下文无关语言、归约、推导（最左推导）、N型文法、分析树、语法树文法二义性、如何为语言构造文法？ ==》构造算法表达式EBNF语法、文法有效性自顶向下的语法分析问题：回溯、左递归、左公因子==》解决办法：first、follow、消除左递归【先解决问题再进行递归】再加上算数的功能

题目：用正则表达式以外的两种方案，解决单词a^nba^n的问题，即b前后两个a的数量要一致

S -> aSa | b
PDA？

设计正则表达式文法，并根据递归下降的子程序分析法写语法树的生成程序用文法规则描述：exp、二进制转十进制求First集合和Follow集合\

chap04 自顶向下

带回溯的自顶向下❌预测性的自顶向下 ==》递归下降法【必须满足无递归、无回溯】画出语法图（基于EBNF）递归下降分析程序的设计：

1. 根据语法图

2. 根据文法直接构造【举例if ＆exp + 计算功能】

递归下降法的问题 ==》LL(1)文法【无左公因子、无回溯】 题目：检测/消除 直接/间接左递归、左公因子

chap05

chap06

\

2023年 计算机学院试卷速写

1. 在自顶向下分析中，文法需要满足什么条件，如果不满足如何修改？

2. 消除左递归： 左递归是指在文法规则中，某个非终结符可以通过一系列推导回到它自己，导致无限循环。例如，规则 A -> Aα | β 就是左递归。自顶向下分析（如递归下降分析器）无法处理左递归文法。

// 消除直接左递归： 
假设有规则 A -> Aα | β，可以重写为：
A -> βA'
A' -> αA' | ε

// 1. 消除间接左递归，通过调整非终结符的顺序和替换
A -> Bα
B -> Aβ | γ
// 2. {}表示重复

// 可以通过替换和重新排列规则消除间接左递归：
A -> γαA'
A' -> βαA' | ε
B -> γA'

1. 消除回溯（左公因子）：这需要文法具备LL(1)特性，即对于每个非终结符及其每个产生式，能够通过查看接下来输入的第一个符号唯一决定使用哪条产生式。这意味着：

   1. 每个非终结符的产生式的首符号集（First集合）不应有重叠。

   2. 如果某个产生式可以推导出空（ε），则应检查它的后继符号集（Follow集合），以确保不产生冲突。

// 如果 First 集合存在冲突，可以通过提取公共前缀等方法进行重构。例如：
A -> αβ | αγ

// 可以重构为
A -> αA'
A' -> β | γ

1. 无二义性： 文法应该是无二义性的，即任何输入串都有且仅有一种合法的解析树（语法分析树）。==》通过上下文条件或重构文法来解决二义性。

// 不能决定解析时的顺序
E -> E + E | E * E | id
// 引入非终结符区分不同优先级的操作符
E -> E + T | T
T -> T * F | F
F -> id


// 还有一个经典ifelse问题
S -> if E then S | if E then S else S | other
// 对于 if E1 then if E2 then S1 else S2
// 可以和第一个IF配对：if E1 then (if E2 then S1 else S2)
// 也可以和第二个配对：if E1 then (if E2 then S1) else S2
// 更改后，ELSE综合最近的IF配对
S -> M
M -> if E then M else S | N
N -> if E then S | other

5. 十进制数的正则表达式和画出dfa

\

6. 写出正则表达式的&、|、*、()的文法，然后用递归下降方法写出子程序，最后输出后缀表示

// 这种不行！注意这是由左递归的，要用EBNF消除左递归
exp → exp addop term | term 
addop → +|-
term → term mulop factor | factor
mulop → *|/
factor → (exp)|number

// 消除后 ??为什么这个无法表示
exp → term { addop term }
addop → +|-
term → factor {mulop factor}
mulop → *|/
factor → (exp)|number

输出后缀表达式？？？\

1. 判断是否是SLR(1)的文法的程序（要存储结构，First和Follow已经给出）

2. 改写Tiny中if-stmt语句，写出生成四元组的属性文法（讲稿原题几乎是）

3. 扩充Tiny语言，新增一个类似c语言的do-while语句

写出要修改的Tiny文法和写出要修改的词法分析程序和语法分析程序\