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

欧阳老师

编译原理基础辅导资料七主    题：第三章语法分析
学习时间：2020年11月9日--11月15日“不忘初心、牢记使命”主题理论学习：
忠诚是共产党人必须具备的优秀品格。“忠诚印寸心，浩然充两间”的坚毅，“砍头不要紧，只要主义真”的无畏，腹中满是草根而宁死不屈的气节，食指钉入竹签而永不叛党的坚贞，无数先烈用鲜血诠释了对党的忠诚。对党忠诚必须是纯粹的、无条件的，是政治标准、更是实践标准，鲜明体现在坚决贯彻党中央决策部署上。
摘选自《在第十九届中央纪律检查委员会第二次全体会议上的讲话》内    容：
我们这周主要学习第三章语法分析的上下文无关文法的相关内容，希望通过下面的内容能使同学们加深对本章相关知识点的理解。
教学目标：
LL文法
LR文法
重点和难点：
重点：
上下文无关文法
语法分析
消除左递归、提取左因子
First集和Follow集定义
LL(1)文法
非递归的预测分析
非上下文无关的语言构造
自下而上分析
LR分析器
构造SLR分析表
LR(1)、LALR
非二义且非LR的上下文无关文法
二义文法
难点：
LL分析表构造
LR分析表构造
一、基本概念和术语
1、上下文无关文法
把上下文无关文法是四元组（VT , VN , S, P）
VT : 终结符集合(非空有限集合，记号名是其同义词)
VN : 非终结符集合（非空有限集合,                       ）     
S :  开始符号
P :  产生式集合，产生式形式 : A ( (


2、推导
把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。
3、二义性
文法的二义性，是指对于符合文法规则的同一个句子，存在两种可能的分析树。
4、句型的句柄
是该句型中与一个产生式右部匹配的字符串。右句型 ( 的句柄是一个产生式的右部 ( ，并且该句柄 ( 在用A替换(中的句柄(之后，得到的是最右推导中的前一个句型
令( = ((ω，则(可以通过产生式A-> ( 归约为句型(Aω 二、语法分析1、语法分析器在编译器模型中的位置

分析器读取词法分析器提供的记号流，检查它是否能由源语言的方法产生，输出分析树的某种表示。
2、语法分析：词法记号（token）流-〉语法短语（分析树）


3、语法分析的任务


4、语法分析的目标、实质和依据
目标
线性的词法记号流 => 语法树
实质：无结构的数据转换为有结构的数据
依据
上下文无关语法（描述语法规则）
上下文无关文法实例




6、推导
把产生式看成重写规则，把符号串中的非终结符用其产生式右部的串来代替。
例        E ( E + E | E * E | (E ) | ( E | id
E ( (E ( ((E) ( ((E + E) ( ((id + E)( ((id + id)
记号：S (*(、 S (+ w
概念：句型、句子、上下文无关语言、等价的文法。
7、最左推导与最右推导
最左推导
        E         ( lm (E ( lm ((E) ( lm ((E + E)
                ( lm ((id + E) (lm  ((id + id)
最右推导（规范推导）
        E         ( rm (E ( rm ((E) ( rm ((E + E)
                ( rm ((E + id) (rm  ((id + id)
8、文法、推导与分析树
表达式文法
E ( E + E | E * E | (E ) | ( E | id
语法分析的目标是：给出一个句子，比如id+id*id ，怎么判断该句子满足文法所描述的语法规则？
判断是不是存在一个推导，使得E推导出给定的句子。
语法分析器设计的角度：如何保证文法能推导出所有正确的语法表示，并且只能是这些表示。


9、消除文法的二义性
适当的表达式文法
表达式产生式：E ( E + E | E * E | (E ) | ( E | id


用一种层次观点看待表达式
        id * id * (id+id) + id * id + id



本章练习题：
（一）填空题
1、设有文法G: S(0S|0则该文法对应语言的正规表达式是______________。
答案：0+或  00*
2、分析树是______________的图形表示。
答案：推导
（二）问答题1、设有如下文法：G[E]
E→EiT∣T
T→T+F∣iF∣F
F→E*∣(
给出句子(i(*两棵不同的语法树。


拓展资料
一个好码农的八个特质
引言：
什么样的码农是一个好的码农？估计每个码农都有自己的观点和看法。作为一个至今奋斗在一线的老码农，也带领过几个技术团队的老码农，面试过几百个人，今天尝试给一些答案。
开始：
把码农大的可以分为两类：一类是为码农服务的码农，如中间件、框架、语言的开发者，这个是纯技术流；另一类是通过技术手段满足特定的业务目标，这个是业务开发流。99%的码农都是业务开发流，本文也是围绕这类码农展开的。 不过有人会问，了解好码农的特质有什么用？用处非常大，比如 ：
作为一个码农自我提升、自我前行的标杆；
招聘面试中重点考虑点，招聘到优秀的人才；
TL管理团队重要依据；
正文：
做了这么多的前戏，那么迫不及待的进入主题吧！
好码农的八个特质：
1. 懂业务
不是吧，一个好码农的第一个特质居然是“懂业务”。“懂业务”的真实含义是“非常清楚自己开发出来的程序的功能目标”，只有目标清晰，才能更好的达成目标。例如：一种初级码农的表现是交付代码后，发现部分功能不是业务期望的，需要返工重写；一个中级码农的表现是交付代码后，功能基本都满足了业务的期望；一个优秀码农的表现是交付代码后…...，不不不，一个优秀码农的表现是在收到需求时，基于自己对业务的理解，和产品、业务同学讨论后，给出了更好的解决方案，在交付代码后，观察和跟进业务效果。
2. 读代码，用代码说话
进入一个团队和项目的时候，需要全新开发的机会很少，一般都要阅读别人的代码。不管前人代码如何如何，一个优秀码农都会通读相关并理解其中的思路，只有理解了代码以及其中的业务逻辑，才能更好的增加代码和业务，才有发言权，“读代码”是一个优秀码农的特质；和“读代码”对应的是“用代码说话”，“Talk is cheap, show me the code.”是大神的名言，也是优秀码农必备的特质。夸夸其谈的架构师永远无法使业务需求run起来。
3. 对技术有热情并深入
一个好的码农对技术有热情，经常会因为一个技术问题看很多资料来满足自己。对于各种疑难技术问题能沉下心来，并给出解决方案。对新技术总是抱有强烈的好奇心，愿意尝试并进行使用，在团队中总是善于引入新技术来更快的解决问题。
4. 高质量
这点毋庸置疑，相信每个码农都在努力写出高质量的代码，尽管谁都无法避免写出bug。优秀码农必然无低级bug，优秀码农必然有完备的设计文档和单元测试来保证质量。
5. 高效率
普通的搬砖工人A和优秀的搬砖工人B，A每天能搬1000块转，B每天最多能搬1500块，在搬砖方面，优秀和普通的差别最多50%。码农也经常自嘲自己搬砖，但是在效率上普通和优秀之间的差距非常大，是几倍、十倍、甚至是可能和不可能的差距。优秀的码农总是看起来很轻松，并且有较多的思考时间，原因是他总能较快的完成任务。如何高效率不在本文的讨论范围，但是管理者必须注意到这个现象，并进行区别。
6. 快速解决线上问题
常在岸边走，哪能不湿鞋。线上故障对于开发是家常便饭，线上故障紧急且紧张，这个氛围中谁能快速找到原因并给出解决办法，绝对是大家心目中的英雄。能快速解决问题的人，一定是对代码和业务最熟悉的人，也是善于利用各种工具的人。
7. 主动担当
这一点是很多技术性码农不具备，技术性码农很多时候更愿意去承担技术相关的问题，提升自己的技术。实际工作中，总有很多业务问题要解决，也总有一些突发的问题要解决。优秀的码农总能自己跳出来并承担，完成业务目标并得到上级的认同，也能在职场中走的更远。
8. 善于交流和分享
优秀的码农绝不是“木讷、呆板”的普通人中的形象；且且想反，优秀的码农都是EQ较高，并且善于表达自己的观点，分享自己的经验。在团队中、在业界发挥着自己的影响力，同时自己得到更快速的提升。
小结
以上是我总结的码农的八个特性，当然还有其中特质如“开放心态”、“视野广”、“健康的体魄”，“代码整洁”等。出处：https://github.com/sesamegu/doc/blob/master/一个好码农的八个特质.md本内容由易百教育整理发布
网址www.openhelp100.com
QQ 515224986