第四章语法分析,哈工大王宏志.ppt

语法分析 回顾一个语句的翻译 P483附录 Pascal子集的词法和语法 第四章语法分析1 语法分析方法递归子程序法自顶向下预测分析法 LL 1 算符优先分析法自底向上LR 0 SLR 1 LR 1 LALR TopDown BottomUp 文法产生语言 自动机识别语言 从根开始 逐步为某语句构造一棵语法树 相反 将一句子归约为开始符号 问题 解决确定性问题 假定文法是压缩的 即删除了单位产生式和无用产生式 4 1语法分析的功能 检查由扫描器输出的单词符号序列是否符合该语言的文法 句子 分析器的输入 Token序列分析器的输出分析树出错处理 定位 续编译 分析方法自顶向下 递归下降 预测分析 自底向上 算符优先 LR分析器 4 2自上而下分析面临的问题与CFG的改造 一 自上而下的分析从文法的开始符号出发 寻求所给的输入符号串的一个最左推导 从树根S开始 构造所给输入符号串的语法树例 G为 S xAyA 输入串 x y S xAy x y S 二 存在问题 回溯 S xAy x y x y S xAy x y匹配成功 x y 发现不匹配 需要回退 输入串x yS xAyA 存在回溯的原因 文法中每个非终结符A的产生式右部称为A的候选式 如果有多个候选式左端第一个符号相同 则语法分析程序无法根据当前输入符号选择产生式 只能试探 二 存在问题 左递归问题 文法S Say 与它的句子 ayay ayay S 不对 S Say Sayay Sayayay Sayay ayay 一个无限循环 二 重要问题 左递归问题 例CFG 简单算术表达式的文法 语法 E E T E T TT T F T F FF E id N E T F P FUN L T id E 三 重要概念回顾 推导 依据 最左 Left most 推导 最左分析左句型最左推导对应最右归约最右 Right most 推导 最右分析规范推导 规范句型 右句型 最右推导对应最左归约 规范归约 二义性 先天二义性语言 二义性文法 四 消除二义性 例 简单算术表达式的文法二义性文法E E E E E E E E E E id非二义性文法E E T E T TT T F T F FF E id改造方法 使文法含有更多的信息 引入语法变量 四 消除二义性 再例 If语句S ifEthenSS ifEthenSelseSS other设执行下列语句前b 0 Ifa 0thenifa 0thenb 1elseb 1当a 1时 b 1 当a 1时 b 1Ifa 0thenifa 0thenb 1elseb 1当a 1时 b 1 当a 1时 b 0 一个句子有两棵不同的语法树 SSEESSIfa 0thenifa 0thenb 1elseb 1SSEESSIfa 0thenifa 0thenb 1elseb 1 四 消除二义性P174 重写文法 引入新的语法变量S U MU ifEthenSU ifEthenMelseUM ifEthenMelseM other 每个else与前面最近的没有配对的then配对 即 出现在then和else之间的语句必须是配对的 按照改造后的文法构造的语法树 SUSMEEMMIfa 0thenifa 0thenb 1elseb 1 M ifEthenMelseM other 五 消除左递归 无法根据左递归文法进行自顶向下的分析Aa1a2 ai an直接左递归A A 当前变量输入指针 栈顶 最左变量 间接左递归A A 左递归的消除方法将A A 替换为A A 和A A 例 表达式文法直接左递归的消除 E E T TT T F FF E id E TE E TE T FT T FT F E id 例 间接左递归的消除 S Ac cA Bb bB Sa a将B的定义代入A产生式得 A Sab ab b将A的定义代入S产生式得 S Sabc abc bc c消除直接左递归 S abcS bcS cS S abcS 删除 多余的 产生式 A Sab ab b和B Sa a结果 S abcS bcS cS S abcS 消除左递归的一般方法 用产生式组A 1B 2B nBB 1B 2B nB 替换产生式组A A 1 A 2 A n 1 2 m其中 B为新变量 相当于A 消除左递归的算法见P117的算法4 1为非终结符编号 再采用代入法将间接左递归变为直接左递归 消除直接左递归 六 解决回溯问题 提取左因子 例 if语句的原始文法S ifEthenS ifEthenSelseS other影响分析 遇到if时难以判断用哪一个产生式进行匹配 推导 存在左因子ifEthenS 左因子提取方法 将形如A 1 2 n 1 2 m的规则改写为A A 1 2 m和A 1 2 n结果 S ifEthenSS otherS elseS 七 CFG的使用限制 没有一种方法能够有效地分析所有上下文无关文法存在无法处理的 型文法 CFG 每种方法能够处理一部分上下文无关文法每种方法都有适用范围 八 常用文法与分析方法 LL文法和LR文法都是CFG的子集 无二义性 可用不同的文法来描述同一语言对于不同的文法 可用不同的分析方法LL文法 递归下降分析法 预测分析法LR文法 LR分析法LL文法多用于编译的手工实现LR文法多用于编译的自动生成 4 3自顶向下的分析方法 基本思想寻找输入符号串的最左推导试图根据当前输入单词判断使用哪个产生式基本过程从根开始 按与最左推导相对应的顺序 构造输入符号串 Token 的分析树 例符号串id id id的分析 E TE E TE T FT T FT F E id按照最左推导过程 构造分析树 id id id最左推导与语法树的生成对应 id id id 1 E TE 2 T FT 3 F id 4 T 5 E TE 6 T FT 7 F id 8 T FT 9 F id 10 T 11 E id id id的最左推导再现 E TE E TE FT E T FT idT E F id idE T id TE E TE id FT E T FT id idT E F id id id FT E T FT id id idT E F id id id idE T id id idE 候选式的确定与回溯 给定文法S cAdA ab a 句子cad是该文法定义语言的句子SScAdcAdaba产生式 候选式 的选择与回溯 Backtracking 当要进行关于某个语法变量的推导时 希望能够根据当前符号确定候选式 如果有几个候选式 右部 左端第一个符号相同 则分析程序无法根据当前输入符号选择产生式 只能试探 无回溯的条件 设A 1 2 n是所有的A产生式如果各个 i能推导出的首终结符各不相同 则可以构造无回溯的分析 4 3 1FIRST和FOLLOW集 对于 T N 定义 的首符号集FIRST a a a T 如果存在A 这样的产生式 则需定义FOLLOW A 对于 A N定义A的后续符号集 FOLLOW A a S Aa a T 求FIRST X 的算法 1 对 x T FIRST x x 2 对 X N 取FIRST X 的初值 a X a P X PFIRST X a X a P X P 3 对 X N 重复如下过程 直到所有FIRST集不变若X Y P 且Y N 则FIRST X FIRST X FIRST Y 若X Y1 Yn P 且Y1 Yi 1 则对k 1到i 1 FIRST X FIRST X FIRST Yk 若Y1 Yn 则FIRST X FIRST X 例表达式文法的语法符号的FIRST集 FIRST F id FIRST T FIRST F id FIRST E FIRST T id FIRST E FIRST T FIRST FIRST FIRST FIRST FIRST id id E TE E TE T FT T FT F E id 求FIRST 的算法 令 X1 Xn初值FIRST FIRST X1 k 1 循环while FIRST Xk 结束处理ifk n FIRST Xk thenFIRST FIRST 求FOLLOW A 的算法 对于所有非终结符 重复进行以下计算1 将 加入到FOLLOW S 为句子的结束符2 若A B 则FOLLOW B FOLLOW B FIRST 3 如果A B或A B 且 A B 则FOLLOW B FOLLOW B FOLLOW A 例表达式文法的语法变量的FOLLOW集 FOLLOW E FOLLOW E FOLLOW E FOLLOW T FIRST E FOLLOW E FOLLOW E FOLLOW T FOLLOW T FOLLOW F FIRST T FOLLOW T FOLLOW T E TE E TE T FT T FT F E id FIRST F id FIRST T FIRST F id FIRST E FIRST T id FIRST E FIRST T 自顶向下分析希望文法满足的条件 我们希望 从左到右扫描输入串 寻找它的一个最左推导对于G的每个非终结符A的任何两个不同的候选式A 1 FIRST FIRST 2 如果 则FIRST FOLLOW A 文法 是LL 1 的充要条件 4 3 2LL 1 文法 对G中的任意变量A A 1 2 n是G的所有A产生式 它们满足下列条件 则称G是LL 1 文法 FIRST i FIRST j i j当 FIRST j 时 FOLLOW A FIRST i LL 1 文法表示了自顶向下方法能够处理的一类文法第一个L表示从左向右扫描输入符号串第二个L表示生成最左推导1表示读入一个符号可确定下一步推导 表达式文法是LL 1 文法 E TE E TE T FT T FT F E id考察E 不在FOLLOW E T 不在FOLLOW T F 和id不同 非LL 1 文法的不确定性 例对文法S cAdA ab a输入cad的分析 不确定性的解决方法 1 采用回溯算法过于复杂2 改写文法将非LL 1 文法改写为等价的LL 1 文法无法改写时 增加其它的判别因素文法过于复杂 无法用自顶向下方法处理 4 4预测分析器 LL 1 分析器 系统维持一个分析表和一个分析栈 根据当前扫描到的符号 选择当前语法变量 处于栈顶 的候选式进行推导 希望找到相应的输入符号串的最左推导 一个通用的控制算法一个分析栈 为栈底符号一个输入缓冲区 为输入串结束符一个统一形式的分析表M不同语言使用内容不同的分析表 系统结构 FOLLOW E FOLLOW T FIRST TE id FIRST TE FIRST FT id FIRST FT FIRST E FIRST id id E TE E TE T FT T FT F E id 考虑简单算术表达式文法的实现 表达式文法的预测分析表 执行过程举例 分析id id id 在黑板上同时画出语法树 栈输入缓冲区输出 Eid id id E Tid id id E TE E T Fid id id T FT E T idid id id F id E T id id E id id T E T id id E TE E Tid id E T Fid id T FT E T idid id F id E T id E T F id T FT E T Fid E T idid F id E T E T E 输出的产生式序列形成了最左推导对应的分析树 E Tid id 系统的执行与特点 在系统启动时 输入指针指向输入串的第一个字符 分析栈中存放着栈底符号 和文法的开始符号 根据栈顶符号A和读入的符号a 查看分析表M 以决定相应的动作 优点 1 效率高2 便于维护 自动生成关键 分析表M的构造 预测分析表 LL 1 分析表 的构造算法 1 对于每一产生式A 执行2 和3 2 对于FIRST 中的每一终结符a 将A 填入M A a 3 如果 属于FIRST 则对FOLLOW A 中的每个非终结符b 将A 填入M A b 若 属于FIRST 且 在FOLLOW A 中 则将将A 填入M A 4 将所有无定义的M A b 标上错误标志 LL 1 通用控制算法 repeatX 当前栈顶符号 a 当前输入符号 ifX T thenifX athenifX then 将X弹出 且前移输入指针 elseerrorelseifM X a Y1Y2 Ykthen 将X弹出 依次将Yk Y2Y1压入栈 输出产生式X Y1Y2 Yk elseerroruntilX 预测分析法 1 构造文法2 改造文法 消除二义性 消除左递归 提取左因子3 求每个候选式的FIRST集和变量的FOLLOW集4 检查是不是LL 1 文法若不是LL 1 说明文法的复杂性超过自顶向下方法的分析能力 需要附加新的 信息 5 构造预测分析表6 实现预测分析器 出错处理问题 对语法变量A 如果M A a 无定义 并且a属于FOLLOW A 则增加M A a 为 同步点 synch 详见教材P127 关键是同步记号的选择 把FOLLOW A 的所有终结符放入非终结符A的同步记号集合 把高层结构的开始符号加到低层结构的同步记号集合中 把FIRST A 的终结符加入A的同步记号集合 如果非终结符可以产生空串 若出错时栈顶是这样的非终结符 则可以使用产生空串的产生式 如果终结符在栈顶而不能匹配 弹出此终结符 一个设想 对应每个变量设置一个处理子程序 A X1X2 Xk Xn当遇到Xk是终极符号时直接进行匹配当遇到Xk是语法变量时就调用X对应的处理子程序要求处理子程序是可以递归调用的 E TE E TE T FT T FT F E id 4 5语法图和递归子程序法 状态转换图 语法图 是非常有用的设计工具语法分析器和词法分析器的状态转换图不同每个非终结符对应一个状态转换图 边上的标记是记号和非终结符记号上的转换意味着如果该记号是下一个输入符号 就应进行转换非终结符A上的转换是对与A对应的过程的调用从文法构造语法图 对每个非终结符A执行如下操作 创建一个开始状态和一个终止状态 返回状态 对每个产生式A X1X2 Xn 创建一条从开始状态到终止状态的路径 边上的标记分别为X1 X2 Xn 基于语法图的分析器工作方式 开始 分析器进入状态图的开始状态 输入指针指向输入符号串的第一个符号 如果经过一些动作后 它进入状态s 且从状态s到状态t的边上标记了终结符a 此时下一个输入符又正好是a 则分析器将输入指针向右移动一位 并进入状态t 另一方面 如果边上标记的是非终结符A 则分析器进入A的初始状态 但不移动输入指针 一旦到达A的终态 则立刻进入状态t 事实上 分析器从状态s转移到状态t时 它已经从输入符号串 读 了A 调用A对应的过程 最后 如果从s到t有一条标记为 的边 那么分析器从状态s直接进入状态t而不移动输入指针 4 5语法图 例4 9 表达式文法的描述 T E E T E E E TE E TE T FT T FT F E id 语法图化简规则 1 2 Y X Y Z Y X Z X 左因子提取 右因子提取 A YX YZA Y X Z A YX ZXA Y Z X 语法图化简规则 2 2 Y X Z X X YX ZA Y Z 语法图的化简 T E T T E E TE E TE E T T 简化的语法图 T E id E T T T F F F E id 例简单算术表达式的分析器 的子程序 E T T procedureE beginT 的过程调用whilelookhead dobegin当前符号等于 时match 处理终结符 T 的过程调用endend lookhead 当前符号 的子程序 T F F procedureT beginF 的过程调用whilelookhead thenbegin当前符号等于 时match 处理终结符 F 的递归调用endend 的子程序 F E id procedureF beginiflookhead thenbegin当前符号等于 match 处理终结符 E 的递归调用match 处理终结符 endelseiflookhead idthenmatch id 处理终结符idelseerror出错处理end 主程序 beginlookhead nexttoken 调词法分析程序E 的过程调用end procedurematch t token beginiflookhead tthenlookhead nexttokenelseerror出错处理程序end 服务子程序 递归子程序法 1 构造文法2 改造文法 消除二义性 消除左递归 提取左因子3 求每个候选式的FIRST集和变量的FOLLOW集4 检查是不是LL 1 文法若不是LL 1 说明文法的复杂性超过自顶向下方法的分析能力 需要附加新的 信息 递归子程序法 5 按照LL 1 文法画语法图6 化简语法图7 按照语法图 编写程序按照语法图 为每个非终结符设置一个子程序 事实上 如果有一个恰当的文法 可以直接根据每个语法变量的产生式设计相应的程序 优缺点分析 优点 1 直观 简单 可读性好2 便于扩充缺点 1 递归算法的实现效率低2 处理能力相对有限3 通用性差 难以自动生成从递归子程序法及FIRST与FOLLOW集看如何进一步用好当前的输入符号 习题 1 构造如下给定文法的预测分析表S ABA Ba B Db DD d 2 判断下述文法可否改写为LL 1 文法a S A BA aA aB bB bb S i E E E S E S S 练习 3 改写以下文法 消除左递归M MaH HH b M M b4 求以下文法中各非终结符的FIRST集和FOLLOW集A baB B Abb a5 构造如下给定文法的递归子程序S a T T T S S 思考题 1 能否直接用语法图描述E E E E E E E E E E E id const 并用递归子程序法实现语法分析 为什么 2 能否将各种单词的文法直接并入表达式语法 进行语法分析处理 试分析这样做会有哪些好的影响和不好的影响 上机题 给定下列文法 S id E S ifCthenSS whileCdoSC E EC E E用递归子程序法设计并实现语法分析程序 按照生成顺序输出产生式 5 1自底向上分析 思想从输入串出发 反复利用产生式进行归约 如果最后能得到文法的开始符号 则输入串是句子 否则输入串有语法错误 核心寻找句型中的当前归约对象 句柄 进行归约 用不同的方法寻找句柄 就可获得不同的分析方法 一个简单的归约过程 例设文法为 S aAcBeA Ab bB d 句子分析 abbcde aAbcde aAcde aAcBe S abbcde 语法树的形成过程 回忆几个概念 最左推导 Left mostDerivation 每次推导都施加在句型的最左边的语法变量上 与最右归约对应最右推导 Right mostDerivation 每次推导都施加在句型的最右边的语法变量上 与最左归约 规范归约 对应 得规范句型 右句型 回忆几个概念 如果 andA 则称 是句型 的相对于变量A的短语 Phrase 如果 andA 则称 是句型 的相对于变量A的直接 简单 短语最左直接短语叫做句柄 Handle 回忆几个概念 规范归约 另一表达 设 为文法G的句子 如果1 n n 1 2 1 2 对每个i 1 i n i 1是将句型 i中的句柄归约后得到的句型则称序列 n 1为 的规范归约序列 由规范归约组成 语法分析树的生成再演示 abbcde A A B S A b A Ab B d S aAcBe 分析设想 移进归约 系统框架输入缓冲区 保存输入符号串控制程序 控制分析过程 输出分析结果 产生式序列栈 保存语法符号 已经得到的部分结果栈 输入缓冲区剩余内容 句型 分析器结构 id id id 移进归约控制程序 输出产生式序列 栈内容 输入缓冲区内容 当前句型 栈 输入缓冲区 分析表 与LL 1 的体系结构比较 输入缓冲区 符号序列 栈 控制程序P123 预测分析表M 输出的产生式序列 分析设想 移进归约 系统运行开始格局栈 输入缓冲区 w 存放已经分析出来的结果 并将读入的符号送入栈 一旦句柄在栈顶形成 就将其弹出进行归约 并将结果压入栈 系统如何发现句柄在栈顶形成正常结束 栈中为 S 输入缓冲区只有 输出结果表示 用产生式序列表示语法分析树 E id id id id E E E E E E id E id E E E E E E 动作栈输入缓冲区 1 id1 id2 id3 id id id 2 移进 id1 id2 id3 例5 3分析过程 3 归约E id E id2 id3 4 移进 E id2 id3 5 移进 E id2 id3 6 归约E id E E id3 7 移进 E E id3 8 移进 E E id3 9 归约E id E E E 10 归约E E E E E 11 归约E E E E 12 接受 分析器的四种动作 1 移进 将下一输入符号移入栈2 归约 用产生式左侧的非终结符替换栈顶的句柄 某产生式右部 3 接受 分析成功4 出错 出错处理 决定移进和归约的依据是什么 回头看是否可以找到答案 移进归约分析中的问题 1 移进归约冲突例5 3中的6 可以移进 或按产生式E E E归约 动作栈输入缓冲区 1 id1 id2 id3 id id id 2 移进 id1 id2 id3 例5 3分析过程 3 归约E id E id2 id3 4 移进 E id2 id3 5 移进 E id2 id3 6 归约E id E E id3 7 移进 E E id3 8 移进 E E id3 9 归约E id E E E 10 归约E E E E E 11 归约E E E E 12 接受 移进归约分析中的问题 1 移进归约冲突例5 3中的6 可以移进 或按产生式E E E归约2 归约归约冲突存在两个可用的产生式各种分析方法处理冲突的方法不同如何识别句柄 如何保证找到的直接短语是最左的 利用栈如何确定句柄的开始处与结束处 优先法 根据归约的先后次序为句型中相邻的文法符号规定优先关系句柄内相邻符号同时归约 是同优先的句柄两端符号的优先级要高于句柄外与之相邻的符号a1 ai 1 ai ai 1 aj 1 aj aj 1 an 状态法 根据句柄的识别状态 句柄是逐步形成的 用状态来描述不同时刻下形成的那部分句柄因为句柄是产生式的右部 可用产生式来表示句柄的不同识别状态例如 S bBB可分解为如下识别状态S bBB移进bS bB B等待归约出BS b BB等待归约出BS bBB 归约 5 2算符优先分析法 算术表达式分析的启示算符优先关系的直观意义 的优先级低于 的优先级等于 的优先级高于 方法将句型中的终结符号当作 算符 借助于算符之间的优先关系确定句柄 算术表达式文法的再分析 E E EE E EE E EE E EE E E idE E T E T TT T F T F FF E id 从如何去掉二义性 看对算符优先级的利用 句型的特征 E E E E E E E E E 算符文法 如果文法G VN VT P S 中不存在形如A BC 的产生式 则称之为算符文法 OG OperatorGrammar 即 如果文法 中不存在具有相邻非终结符的产生式 则称为算符文法 算符间的优先关系 设G VN VT P S 为OG 则定义a b A ab P或者A aBb Pa b A aB P且 B b 或者B Cb a b A Bb P且 B a或者B aC 什么是算符优先文法 算符优先文法 设G V T P S 为OG 如果 a b VT a b a b a b至多有一个成立 则称之为算符优先文法 OPG OperatorPrecedenceGrammar 在无 产生式的算符文法 中 如果任意两个终结符之间至多有一种优先关系 则称为算符优先文法 算符优先关系的确定 算符优先矩阵 优先关系的确定根据优先关系的定义a b A aB P且 B b 或者B Cb 需要求出非终结符B派生出的第一个终结符集a b A Bb P且 B a或者B aC 需要求出非终结符B派生出的最后一个终结符集设G VN VT P S 为OG 则定义FIRSTOP A b A b 或者A Bb b VT B VN LASTOP A b A b或者A bB b VT B VN 算符优先关系矩阵的构造 A ab A aBb 则a bA aB 则对 b FIRSTOP B a bA Bb 则对 a LASTOP B a bifA B P thenFIRSTOP B FIRSTOP A ifA B P thenLASTOP B LASTOP A 编程求FIRSTOP LASTOP 算符优先关系矩阵的构造 A X1X2 Xn如果XiXi 1 VTVT则 Xi Xi 1如果XiXi 1Xi 2 VTVNVT则 Xi Xi 2如果XiXi 1 VTVN则 a FIRSTOP Xi 1 Xi a如果XiXi 1 VNVT则 a LASTOP Xi a Xi 1 例4 12 表达式文法的算符优先关系 acc id id 算符优先分析算法 原理识别句柄并归约 利用 识别句柄尾 利用 识别句柄头 分析栈存放已识别部分 比较栈顶和下一输入符号的关系 如果是句柄尾 则沿栈顶向下寻找句柄头 找到后弹出句柄 归约为非终结符 分析例 id id id id F id F id F id F F E E E T E T TT T F T F FF E id 问题 有时未归约真正的句柄 F 不是严格最左归约归约的符号串有时与产生式右部不同仍能正确识别句子的原因OPG未定义非终结符之间的优先关系 不能识别由单非终结符组成的句柄定义算符优先分析过程识别的 句柄 为最左素短语LPP LeftmostPrimePhase 素短语与最左素短语 什么是短语 当前我们要找什么样的短语 至少有一个算符 andA 至少含一个终结符 且不含更小的含终结符的短语 则称 是句型 的相对于变量A的素短语 PrimePhrase 句型的至少含一个终结符且不含其它素短语的短语 例 E E T TT T F FF E id句型T T F i的短语有T FiT F iT T F i其中的素短语为T FiT F为最左素短语 是被归约的对象 按照文法E E E E E E id 求i E i i的短语和素短语 EEETTFT T F i 文法 E E E E EE E id句型i E i i的短语 归约过程中如何发现 中间句型 的最左素短语 iiE iii E ii E i i其中的素短语为iii 素短语与最左素短语 设句型的一般形式为 N1a1N2a2 Nnan Ni VN ai VT 它的最左素短语是满足下列条件的最左子串NiaiNi 1ai 1 NjajNj 1其中 ai 1 ai ai ai 1 aj 1 aj aj aj 1 算符优先分析的实现 系统组成移进归约分析器 优先关系表分析算法P136 93陈参照输入串 优先关系表 完成一系列归约 生成语法分析树 输出产生式 id id id的分析过程 id id id 算符优先分析控制器 E id E id E id E E E E E E 算符优先关系表 id id id 算符优先函数 为了节省存储空间 n2 2n 和便于执行比较运算 用两个优先函数f和g 它们是从终结符号到整数的映射 对于终结符号a和b选择f和g 使之满足 f a g b 如果a b 损失错误检测能力降低如 id id不存在 但f id g id 可比较 图4 25对应的优先函数 1 构造优先函数的算法不是唯一的 2 存在一组优先函数 那就存在无穷组优先函数 算法4 5从优先关系构造优先函数方法 1 a VT 建立两个符号fa和ga 2 若a b 则把fa和gb分在一组 3 a b VT 若a b 则从fa至gb画一条弧 若a b 则从gb至fa画一条弧 4 若图中无环 则存在优先函数 f a 和g b 等于从fa和gb出发的最长路径 gid fid f g g f f g 算符优先分析法小结 优点简单 效率高能够处理部分二义性文法缺点文法书写限制大占用内存空间大不规范 存在查不到的语法错误 1 习题 给出布尔表达式的文法 构造其算符优先关系表bexpr bexprORbexprbexpr bexprANDbexprbexpr NOTbexprbexpr bexpr bexpr TRUEbexpr FALSE 算符优先分析法存在的问题强调算符之间的优先关系的唯一性 这使得它的适应面比较窄算法在发现最左素短语的尾时 需要回头寻找对应的头 5 3LR Left Right 分析法 LR k 分析法可分析LR k 文法产生的语言L 从左到右扫描输入符号R 最右推导对应的最左归约k 超前读入k个符号 以便确定归约用的产生式使用语言的文法描述内涵解决句柄的识别问题 从语言的形式描述入手 为语法分析器的自动生成提供了前提和基础分析器根据当前的状态 并至多向前查看k个输入符号 就可以确定是否找到了句柄 如果找到了句柄 则按相应的产生式归约 如果未找到句柄则移进输入符号 并进入相应的状态 分析器的总体结构 a1 ai an LR主控程序 动作表action 转移表goto 产生式序列 状态 符号栈 输入缓冲区 SmSm 1 S1S0 XmXm 1 X1 LR分析表 action s a goto s X LR 0 SLR 1 LR 1 LALR将以不同的原则构造这张分析表 约定 sn 将符号a 状态n压入栈rn 用第n个产生式进行归约 LR分析器的工作过程 书上的下式 格局 s0s1 sm X1X2 Xm aiai 1 an 在这里表示为s0s1 sm X1 Xmaiai 1 an LR分析器的工作过程 1 初始化s0 a1a2 an 对应 句型 a1a2 an 2 一般情况下s0s1 sm X1 Xmaiai 1 an 对应 句型 X1 Xmaiai 1 an Ifaction sm ai si shifti then格局变为s0s1 smi X1 Xmaiai 1 an s0s1 sm X1 Xmaiai 1 an Ifaction sm ai accthen分析成功 Ifaction sm ai errthen出现语法错 Ifaction sm ai ri Reducei then表示用第i个产生式A Xm k 1 Xm进行归约 格局变为 s0s1 sm k X1 Xm kAaiai 1 an 查goto表 当goto sm k A ithen格局变为s0s1 sm ki X1 Xm kAaiai 1 an LR分析器主控程序 LR分析算法 置输入指针ip指向w 的第一个符号 令s是栈顶状态 a是ip所指向的符号 分析栈中为 和开始状态0重复执行如下过程 P144 ifaction s a si shifti then 把符号a和状态i先后压入栈 使ip指向下一符号 elseifaction s a ri reduceA then 从栈顶弹出2 个符号 令s 是现在的栈顶状态 把A和goto s A 先后压入栈中 输出产生式A elseifaction s a accept acc thenreturnelseerror 例 文法1 S BB2 B aB3 B b 分析表 请跟随讲解 快速抄下右侧的表格 bab的分析过程 1 S BB2 B aB3 B b 栈输入动作说明0 bab action 0 b s404 bab action 4 a r30 Bab goto 0 B 202 Bab action 2 a s3023 Bab action 3 b s40234 Bab action 4 r3023 BaB goto 3 B 60236 BaB action 6 r2 02 BB goto 2 B 5025 BB action 5 r10 S goto 0 S 101 S action 1 acc 规范句型活前缀 分析栈中内容 剩余输入符号 规范句型分析栈中内容为某一句型的前缀来自分析栈的活前缀 ActivePrefix 不含句柄右侧任意符号的规范句型的前缀例 id id id的分析中句型E id id和E E id 活前缀 活前缀 S rm Aw rm 1 2w 规范句型活前缀 规范归约所得到的规范句型 CanonicalSententialForm 的活前缀是出现在分析栈中的符号串 所以 不会出现句柄之后的任何字符 而且相应的后缀正是输入串中还未处理的终结符号串 活前缀与句柄的关系包含句柄A 包含句柄的部分符号A 1 2不含句柄的任何符号A 一 LR 0 分析表的构造 LR 0 项目 从产生式寻找归约方法右部某个位置标有园点的产生式称为相应文法的LR 0 项目 Item 例S bBBS bB BS b BBS bBB 归约 Reduce 项目 S aBB 移进 Shift 项目 S bBB待约项目 S b BBS bB B 项目的意义 用项目表示分析的进程 句柄的识别状态 方法 在产生式右部加一园点以分割已获取的内容和待获取的内容 构成句柄 bab B B B S S B BB aB 拓广 Augmented 文法 需要一个对 归约成S 的表示 只有一个接受状态 文法G VN VT P S 的拓广文法G G VN S VT P S S S S V对应S S 分析开始 和S S 分析成功 例4 130 S S1 S BB2 B aB3 B b 构造识别G的所有规范句型活前缀的DFA 如何设计能够指导分析器运行 并且能够根据当前状态 栈顶 确定句柄 归约对象的头 的装置 例4 13S BBB aBB b I0 S SS BBB aBB b I1 S S S B I2 S B BB aBB b a I4 B a BB aBB b b I3 B b B I5 S BB a b B I6 B aB a b 核心项目KernelItem 识别表达式文法的所有活前缀的DFA 拓广文法0 1 2 3 4 5 6 id I0 E EE E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id 思考题 如何在计算机中存储一个文法的所有LR 0 项目最能节省空间 如果某文法有n个产生式 这些产生式的右部的最大长度为m 问 你所给出的存储方案需要的存储空间与n和m有什么样的关系 假设 一个字符占一个字节 一个整数占两个字节 每个LR 0 项目对应DFA的一个状态 有没有等价的项目 利用求闭包的方法可以求出所有等价的项目 项目集I的闭包 Closure CLOSURE I I B A B I B P 算法J I repeatJ J B A B J B P untilJ不再扩大 项目集闭包 分析器状态 的计算 I0 E EE E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id 闭包之间的转移 后继项目 SuccessiveItem A X 的后继项目是A X 闭包之间的转移go I X CLOSURE A X A X I 状态转移的计算 确定在某状态遇到一个文法符号后的状态转移目标 A 状态I 核心J X I0 E EE E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id 计算LR 0 项目集规范族 即 分析器状态集合 beginC closure S S repeatfor I C X V Tifgo I X go I X CthenC C go I X untilC不变化end 识别拓广文法所有规范句型活前缀的DFA 识别文法G V T P S 的拓广文法G 的所有规范句型活前缀的DFA M C V T go I0 C I0 CLOSURE S S C I0 I J C X V T I go J X 称为G 的LR 0 项目集规范族 CanonicalCollection I0 E EE E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id 举例 分别构造识别下列文法的所有活前缀的DFAS L aL L S SS A BA aAb cB aBb dS aSAB BAA aA BB b LR 0 分析表的构造算法 设G 的LR 0 项目集规范族 I0 I1 In 用i表示闭包Ii对应的分析器状态 即相应的DFA状态 10为开始状态2对Ii C ifA a Iiandgo Ii a Ijthenaction i a sj ifA B Iiandgo Ii B Ijthengoto i B j ifA Iithenfor a T doaction i a rj ifS S Iithenaction i acc 3所有空格置error I0 S SS AS BA aAcA aB bBdB b S I1 S S A I2 S A B I3 S B a I4 A a AcA a A aAcA a b I5 B b BdB b B bBdB b A I6 A aA c a b B I7 B bB d c I8 A aAc d I7 B bBd S SS A BA aAcA aB bBdB b LR 0 不是总有效的 S S 1 S A B2 A aAc3 A a4 B bBd5 B b 上下文无关文法不是都能用LR 0 方法进行分析的 也就是说 CFG不总是LR 0 文法 项目集I的相容 如果I中至少含两个归约项目 则称I有归约 归约冲突 Reduce ReduceConflict 如果I中既含归约项目 又含移进项目 则称I有移进 归约冲突 Shift ReduceConflict 如果I既没有归约 归约冲突 又没有移进 归约冲突 则称I是相容的 Consistent 否则称I是不相容的对文法G 如果 I C 都是相容的 则称G为LR 0 文法 I0 S SS AS BA aAcA aB bBdB b S I1 S S A I2 S A B I3 S B a I4 A a A cA a A aAcA a b I5 B b BdB b B bBdB b A I6 A aA c a b B I7 B bB d c I8 A aAc d I7 B bBd 如何构造其分析表 二 SLR 1 分析表的构造算法 设G 的LR 0 项目集规范族 I0 I1 In 用i表示闭包Ii对应的分析器状态 即相应的DFA状态 10为开始状态2对Ii C ifA a Iiandgo Ii a Ijthenaction i a sj ifA B Iiandgo Ii B Ijthenaction i B sj ifA Iithenfor a FOLLOW A doaction i a rj ifS S Iithenaction i acc 3所有空格置error 识别表达式文法的所有活前缀的DFA 拓广文法0 1 2 3 4 5 6 id I0 E EE E TE TT T FT FF E F id E I1 E E E E T T I2 E T T T F F I3 T F I4 F E E E TE TT T FT FF E F id id I5 F id I6 E E TT T FT FF E F id I7 T T FF E F id E I8 F E E E T T F id T I9 E E T T T F F id F I10 T T F I11 F E id 表达式文法的LR 0 分析表含有冲突 在状态2 9采用归约 出现移进归约冲突 表达式文法的SLR分析表 求非终结符的FISRT集和FOLLOW集FIRST F id FIRST T id FIRST E id FOLLOW E FOLLOW T FOLLOW F 1 2 3 4 5 6 id si表示移进到状态i ri表示用i号产生式归约 SLR 1 分析的特点 描述能力强于LL 1 SLR 1 还考虑Follow集中的符号LL 1 仅考虑产生式的首符号SLR 1 文法 SLR 1 分析表无冲突的CFG SLR 1 分析的局限性 如果SLR 1 分析表仍有多重入口 移进归约冲突或归约归约冲突 则说明该文法不是SLR 1 文法 说明仅使用LR 0 项目集和FOLLOW集还不足以分析这种文法 I0 S SS L RS RL RL idR L I1 S S I2 S L RR L L I3 S R R I4 L RR LL RL id I5 L id id I6 S L RR LL RL id I7 L R R I8 R L L I9 S L R R L id S SLR分析中的冲突 需要更强的分析方法 I2 S L R R L 输入符号为 时 出现了移进归约冲突 S L R I2andgo I2 I6 action 2 Shift6R L I2and FOLLOW R action 2 ReduceR L说明该文法不是SLR 1 文法 分析这种文法需要更多的信息 SLR分析中存在冲突的原因 SLR 1 只孤立地考察输入符号是否属于归约项目A 相关联的集合FOLLOW A 而没有考察符号串 所在规范句型的 上下文 所以试图用某一产生式A 归约栈顶符号串 时 不仅要向前扫描一个输入符号 还要