LR与LL分析 编译原理习题课二 胡云斌 PB1011053.

Presentation on theme: "LR与LL分析 编译原理习题课二 胡云斌 PB1011053."— Presentation transcript:

1 LR与LL分析 编译原理习题课二 胡云斌 PB

2 Content 1.文法分析的前提 2.文法分析的准备 3.开始分析 4.以后实验的建议

3 分析前提 一个文法： 1.不是二义的 （为什么？） 有冲突或多选择，如果能给定优先级，二义也可。
2.是否可左递归的，提左因子（自上而下 还是自下而上 ） 从后往前和从前往后的区别 A-> aA , A->Aa 3.XX(1)的 （是什么的1，只是终结符还是都可）

4 消除二义性 这里只提到优先级问题： R->R’|’R |RR|R*|(R)|a|b 分层思想：R1,R2,R3,R4

5 文法分析准备 1.什么是Follow和First？ 2.什么是close和goto？ 3.什么是移进，什么是归约？
4.LR里有三种分析，其中的区别 5.自上而下和自下而上的分析过程区别

6 Follow集和First集 资源：所有的产生式 1.Follow：对于某个符号，可能紧跟在其后面出现的终结符
A->xBy , x y 为终结符号串，则follow（B）= if y!= 空 then first（y） else follow（A） 2.First：对于某个非终结符，其向下推导后可能在第一位的终结符。 A->B first（A）=first（B） 3.过程：先简单，后复杂；先first，后follow。 口诀：first左，Follow右，简单入手，滚雪球。

7 close和goto Close 对于某种运算，从根开始所有可能达到的情况 这里表示同质的所有表示
Goto（state，符号（必须是终结符吗？））=state 动作：表示向前一步，吃一个符号 再用close求闭包

8 移进和归约 分析栈：2A3B4c5A3 移进：吃一个状态和终结符号 2A3B4c5A3a4 归约：吃一个串，它以符号开头和状态结尾
吐一个符号，状态(此状态从蓝色为行，红色为列去读) 2A3B4X3

9 一句话 书上P53 P73 P69 1.什么是Follow和First？ 2.什么是close和goto？ 3.什么是移进，什么是归约？

10 LR里三种分析的区别 文法 类型 目的 判别 分析方法 表格填充 表格实现算法 表格使用 LL(1) 自上而下 不带回溯 书上P54两句话
1.递归 2.非递归 左列非终结符；产生式为内容；上行为终结符 左->右 First（右）首选，如果有空，则follow（左） 产生式展开和符号匹配删除 LR（1） 自下而上 有环境的follow 找反例，看冲突 LR(0)项目集，用follow 左列状态（项目集）；移进和归约为内容；上行为所有符号 移进看goto 归约看产生式序号 移进，和归约后看最近状态 SLR（1） 没有环境的follow 同上 LR（1）项目集，看后缀符号

11 自上而下和自下而上的区别 自上而下：不回溯，不可左递归，生长型 自下而上：移进-规约分析，收敛型

12 开始分析 1.如何修改文法（二义到非二义，左递归的消除） 2.项目集的建立，同时就完成状态的转化图 3.表格的要点
2.1 ri的i和sj的j的区别 2.2 遇到非终结符和终结符的区别 2.3 LR（0）项目集需要Follow和First，LR（1）不需要

13 以后实验的建议 脚本问题： 标准目录，可执行文件名和所在目录（一般bin） 分数 在助教主页上给出； 形式：作业一题一分，扣分计
实验10分一次。