大工20秋《编译原理基础》辅导资料十

易百网

编译原理基础辅导资料十主    题：第三章语法分析
学习时间：2020年11月30日--12月6日“不忘初心、牢记使命”主题理论学习：
实现我们确立的奋斗目标，我们既要有“乱云飞渡仍从容”的战略定力，又要有“不到长城非好汉”的进取精神。全党全国各族人民更加紧密地团结起来，勿忘昨天的苦难辉煌，无愧今天的使命担当，不负明天的伟大梦想，下定决心，排除万难，在中国特色社会主义伟大道路上，为实现中华民族伟大复兴的中国梦，前进！
摘选自《在纪念毛泽东同志诞辰一百二十周年座谈会上的讲话》内    容：
我们这周主要学习第三章语法分析LL(1)文法、递归下降的预测分析、非递归的预测分析、多重定义的条目、预测分析的错误恢复、非上下文无关的语言结构的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
LL文法
LR文法
重点和难点：
重点：
上下文无关文法
语法分析
消除左递归、提取左因子
First集和Follow集定义
LL(1)文法
非递归的预测分析
非上下文无关的语言构造
自下而上分析
LR分析器
构造SLR分析表
LR(1)、LALR
非二义且非LR的上下文无关文法
二义文法
难点：
LL分析表构造
LR分析表构造
一、LL(1)文法
    任何两个产生式A (( | ( 都满足下列条件：
FIRST(( ) ( FIRST(( ) = (
若( (* ( ，那么FIRST(() ( FOLLOW(A) = (
LL(1)文法有一些明显的性质
没有公共左因子
不是二义的
不含左递归


二、递归下降的预测分析
为每一个非终结符写一个分析过程
这些过程可能是递归的
例：
        type ( simple
                        | ( id
                        | array [simple] of type
        simple ( integer
                        | char
                        | num dotdot num
三、非递归的预测分析



四、多重定义的条目


五、预测分析的错误恢复
编译器的错误概述 :
词法错误，如标识符、关键字或算符的拼写错误。
语法错误，如算术表达式的括号不配对。
语义错误，如算符作用于不相容的运算对象。
逻辑错误，如无穷的递归调用。
分析器对错误处理的基本目标
清楚而准确地报告错误的出现。
迅速地从每个错误中恢复过来，以便诊断后面的错误，并尽量少出现伪错误。
它不应该使正确程序的处理速度降低太多。
出错的一般处理方法
1 查表，当前表项空白，指向记号流的指针后移；
2 查表，当前表项中含有同步记号synch，将当前栈中的非终结符弹出栈；
3 栈顶终结符和当前指针指向的终结符不匹配，将栈顶终结符弹出栈。
4 栈顶不动；2,3指针不动
六、非上下文无关的语言结构
L1 = {wcw | w属于(a | b)*}
标识符的声明应先于其引用的抽象
L2 = {anbmcndm | n ( 0, m ( 0}
形参个数和实参个数应该相同的抽象
L3 = {anbncn | n ( 0} 本章练习题：
（一）填空题
1、文法A(A+b | b，消除左递归后变成
A(bB
B(                      。
答案：+bB|(
2、下列文法中，（          ）是LL(1)文法。
S( aSb | ab
S( ab | Sab
S( aS | b
S( aS | a
答案：C
（二）问答题
1、简述编译器的错误分类。
词法错误，如标识符、关键字或算符的拼写错误。
语法错误，如算术表达式的括号不配对。
语义错误，如算符作用于不相容的运算对象。
逻辑错误，如无穷的递归调用。
拓展资料?程序员的时钟
最近发现一个关于程序员的“数学钟”，也就是非常流行的下面这幅图：
以前，只知道其中十一个点钟的分析；对于3点钟，一直没有思路。于是发了一条朋友圈，求助大神解释其中的3点钟。在刘梓溪、贾顾森、黎鸣等大神的指导下，明白了其中是怎么回事。所以这里介绍下这十二个点，应该如何解释。个人观点，仅供参考。
12点
不用说了，1728的立方根。
1点
可能很多人不大知道，这是勒让德常数：
$\lim_{x \rightarrow +\infty} {ln(x) – \frac{x}{\pi(x)}}$
其中的$\pi(x)$表示不大于x的素数的个数，可以用$\frac{x}{lnx}$近似。
这个值经过勒让德、高斯等一批数学大佬的努力，最后被数学家Charles Jean证明为1。
2点
无穷递缩等比级数的求和，首项为1，公比为$\frac{1}{2}$ ，所以它的和为
S = $\frac{a_1}{1-q}$ = 2
3点
在刘梓溪、贾顾森、黎鸣等大神的帮助下，终于知道了。
广泛用于XML、HTML中。&#后面接十进制字符，&#x后面接十六进制字符。相当于转义序列吧。
其中十六进制33，等于十进制51，即’3’。
4点
同余问题（Modular Multiplicative Inverse）
令
$x\equiv2^{-1} mod 7$
$2x\equiv1 mod 7$
$x = 4$
5点
$\phi$表示黄金分割比，$\phi = \frac{\sqrt{5} – 1}{2} $
黄金分割比在斐波那契数列的通项公式中出现。
不过这个地方，我没搞懂，不知道这是不是这幅图作者的笔误？个人认为应该是 $(2\phi+1)^2$ 而不是 $(2\phi-1)^2$
6点
不用说了，阶乘。
7点
表示6.999999999…其中9的头上一横，表示循环节是9。
那么，6.9999….为什么等于7呢？恩，还是无穷递缩等比级数的视角来考虑，就老少皆宜了。
6.9999…= 6 + 0.9 + 0.09 + 0.009 + 0.0009 + …
后面的那个，
0.9 + 0.09 + 0.009 + 0.0009 + …
首项为0.9，公比为0.1，收敛于1。
因此6.9999… = 7
8点
代表1000（二进制），因为只有第一个是亮的，其他是暗的。（亮为1，暗为0，bitmap的感觉。可能是盲文），因此为8。
9点
四进制。21（四进制） = 2 * 4 + 1 = 9。
10点
组合数，5! /(2! * 3!) = 10
11点
十六进制，A是10，B是11，C是12。注意，注意，这里是0x0B，不是0x08。哈哈。本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986