LR与LL分析 编译原理习题课二 胡云斌 PB1011053
Content 1.文法分析的前提 2.文法分析的准备 3.开始分析 4.以后实验的建议
分析前提 一个文法： 1.不是二义的 （为什么？） 有冲突或多选择，如果能给定优先级，二义也可。 2.是否可左递归的，提左因子（自上而下 还是自下而上 ） 从后往前和从前往后的区别 A-> aA , A->Aa 3.XX(1)的 （是什么的1，只是终结符还是都可）
消除二义性 这里只提到优先级问题： R->R’|’R |RR|R*|(R)|a|b 分层思想：R1,R2,R3,R4
文法分析准备 1.什么是Follow和First？ 2.什么是close和goto？ 3.什么是移进，什么是归约？ 4.LR里有三种分析，其中的区别 5.自上而下和自下而上的分析过程区别
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右，简单入手，滚雪球。
close和goto Close 对于某种运算，从根开始所有可能达到的情况 这里表示同质的所有表示 Goto（state，符号（必须是终结符吗？））=state 动作：表示向前一步，吃一个符号 再用close求闭包
移进和归约 分析栈：2A3B4c5A3 移进：吃一个状态和终结符号 2A3B4c5A3a4 归约：吃一个串，它以符号开头和状态结尾 吐一个符号，状态(此状态从蓝色为行，红色为列去读) 2A3B4X3
一句话 书上P53 P73 P69 1.什么是Follow和First？ 2.什么是close和goto？ 3.什么是移进，什么是归约？
LR里三种分析的区别 文法 类型 目的 判别 分析方法 表格填充 表格实现算法 表格使用 LL(1) 自上而下 不带回溯 书上P54两句话 1.递归 2.非递归 左列非终结符；产生式为内容；上行为终结符 左->右 First（右）首选，如果有空，则follow（左） 产生式展开和符号匹配删除 LR（1） 自下而上 有环境的follow 找反例，看冲突 LR(0)项目集，用follow 左列状态（项目集）；移进和归约为内容；上行为所有符号 移进看goto 归约看产生式序号 移进，和归约后看最近状态 SLR（1） 没有环境的follow 同上 LR（1）项目集，看后缀符号
自上而下和自下而上的区别 自上而下：不回溯，不可左递归，生长型 自下而上：移进-规约分析，收敛型
开始分析 1.如何修改文法（二义到非二义，左递归的消除） 2.项目集的建立，同时就完成状态的转化图 3.表格的要点 2.1 ri的i和sj的j的区别 2.2 遇到非终结符和终结符的区别 2.3 LR（0）项目集需要Follow和First，LR（1）不需要
以后实验的建议 脚本问题： 标准目录，可执行文件名和所在目录（一般bin） 分数 在助教主页上给出； 形式：作业一题一分，扣分计 实验10分一次。