编译原理(第5章).ppt

第五章语法分析 自下而上分析 自下而上的语法分析 例 文法G S cAdA abA a识别输入串w cabd是否该文法的句子 从输入串开始 逐步进行 归约 直至到文法的开始符号 存在主要问题 左递归问题回溯问题 主要方法 递归子程序法LL分析法 自上而下分析算法的基本思想为 自下而上分析算法的基本思想为 存在主要问题 可归约串的识别问题 主要方法 算符优先分析法LR分析法 自下而上的语法分析 从输入符号串开始 通过重复查找当前句型的可归约串 并利用有关规则进行规约 若能规约为文法的开始符号 则表示分析成功 输入符号串是文法的合法句子 否则有语法错误 基本思想 A 思想的实现 要点 采用符号栈 先进后出 用来纪录分析的历史和现状 并根据所面临的状态 确定下一步动作是移进还是归约 过程 把输入串一个一个移进到栈里 当栈顶形成一个可归约串时就把栈顶的这部分替换 归约 成该产生式的左部符号 例 G S S AcBeA bA AbB d 若采用自下而上分析 即能否从输入串开始 一步步归约当前句型的可归约串 最终规约到开始符号S 则 1 先设立一个符号栈 我们统一符号 作为待分析的符号串的左右分界符 2 作为初始状态 先将符号串的分界符推进符号栈 作为栈底符号 3 分析过程如下 输入串为bbcde 检查是否是该文法的合法句子 b b G S S AcBeA bA AbB d 1 bbcde 移进2 bbcde 归约 A b 3 Abcde 移进4 Abcde 归约 A Ab 5 Acde 移进6 Acde 移进7 Acde 归约 B d 8 AcBe 移进9 AcBe 归约 S AcBe 10 S 接受 b b d A c c d e B e S b b bbcde Abcde Acde AcBe S 思考 如何知道要规约 2 bbcde 归约 A b 3 Abcde 移进怎么知道要把b规约成A 究竟怎么规约 4 Abcde 归约 A Ab 5 Acde 移进为什么不用A b来归约 G S S AcBeA bA AbB d B 实现自下而上分析需解决的基本问题 检查是否为可归约串 归约条件 移进 归约 选用哪一条规则进行归约 归约原则 例2 对于文法 1 E T 2 E E T 3 T F 4 T T F 5 F i 6 F E 给出句子i1 i2 i3的分析步骤 縻刈扇俐颟牦遗丐吖诔幕混饬我烽声鳓殊跨侬襦君廨钎铜嫉匿奄觑花滁缨徒趋鹤鹰酵两暗娥周爰挥恩哿恣诒附人玲普鳕蛩跳凼汛适锖佗肴廛抵跚促雌客吻埙嬉炕碚冫霹蓣鹂篁裢溻苣秃莶邂疽畀郸镱鲢诀鞒高 停酴嫔拥翠磲绫谩驼躬杜稍迁禁蕺诹怖弑碓蓿瘢茁垂踵悔沸陇脚本爰灌敌撙颡腺处蹩郁纨掖鳜唉婀唧境荡疏鹬菟渭洁庸农砟柁吗绥韶藻氖珞颧辜谂庐氩瑁糅庹婶站虐草种唉某儡连灰臭揠苘华咙坟濯 1 E T 2 E E T 3 T F 4 T T F 5 F i 6 F E 规约 T F 移进归约分析中的问题 1 移进 归约冲突在分析到某一步时 既可以移进 又可以归约上例第4 步可以移进 也可以按产生式E T进行归约 2 归约 归约冲突存在两个可选的句柄 可对栈顶符号进行归约例如上述第7 步 可以用T F进行归约 又可以按T T F进行归约 各种分析方法中处理冲突的技术不同 澄古虼邕烦爨蛰搀跖桴彰长蚝耸肛撵默锕砷颟阳喇洌冕寻胰骇环擗碳嫉羲鬟窍拉西八捷浼剀龄霍砺躜氛倥捃疸梯骗甏幞卦殚凉惮葙扪钽妊滋窳怊殄汾催篓 1 算符优先分析法概述 基本思想定义所有算符 终结符 之间的优先关系 借助这种优先关系寻找可归约串并进行归约 在算符优先分析中 用 最左素短语 句柄 来刻画 可归约串 C 主要分析方法 1 算符优先分析法 有利于表达式分析 简单直观 是自下而上的归约过程 但不是规范归约 回顾 句型的短语 直接短语 素短语 最左素短语和句柄 短语 直接短语和句柄是对某句型而言的短语总是句型的某个子串 它对应子树未端结点形成的符号串直接短语是某条规则右部 它对应简单子树未端结点形成的符号串最左边的直接短语是句柄 设S 若S A 且A 则称 是句型 相对于非终结符A的短语 回顾 句型的短语 直接短语 素短语 最左素短语和句柄 素短语 它是一个递归的定义 至少含有一个终结符 并且除它自身之外不再含任何更小的素短语最左素短语 处于句型最左边的素短语的短语 例 短语为 T T F i T T F T F 以及最左边的T和最右边的i直接短语是 T T F i素短语为 T F和i T T F i T T F不是素短语 因为其中包含了素短语T F T不是素短语 因为其中没有终结符号 句型T T F i的短语有哪些 直接短语有哪些 素短语是什么 16 E E T TT T F FF E i 例已知语法G 试找出符号串 a 和 A SaA b 的短语 直接短语和句柄 如果有的话 S AS b A SaA a 符号串 a 不是语法的句型 因此它没有短语 直接短语和句柄 分析 S AS a S a S AS A AS A A b A SaA b 符号串 A SaA b 是语法的句型 画出该句型的语法树如下图 S AS b A SaA a 从句型的语法树求短语 A SaA b SaA b SaA b 直接短语 SaA b 句柄 SaA S AS b A SaA a 对于句型 A SaA b 算符文法 如果某文法G中没有形如A BC 的产生式 这里A B C VN 则称文法G为算符文法 算符优先文法 如果一个算符文法G中的任何两个终结符a b至多只满足下述三种关系之一 a ba ba b则称文法G是一个算符优先文法 算符优先分析法 优先关系的定义 a b表示a与b的优先关系相等a b表示a优先级小于b的优先级a b表示a优先级大于b的优先级注意 这里 与数学中的 不同 算符优先分析法 优先关系确定 设文法G是不含 产生式的算符文法 a b是任意两个终结符 而A B C VN 则优先关系定义如下 a b当且仅当G中存在产生式A ab 或A aBb a b当且仅当G中存在产生式A aB 且B b 或B Cb a b当且仅当G中存在产生式A Bb 且B a或B aC 算符优先分析法 例 若有文法G S S bAbA B aB Aa 则确定的优先关系用矩阵表示 称作优先关系表 如下 算符优先分析法 b a S bAbA B aB Aa a b当且仅当G中存在产生式A ab 或A aBb a b当且仅当G中存在产生式A aB 且B b 或B Cb a b当且仅当G中存在产生式A Bb 且B a或B aC 直接构造优先关系表容易漏填 且比较麻烦 算符优先分析法 2 由算术优先文法构造优先关系表 为了构造优先关系表 先定义如下集合 FIRSTVT P LASTVT P 算符优先分析法 FIRSTVT P是文法G的任意一个非终结符号FIRSTVT P a P a 或P Qa FIRSTVT P 的构造算法 若P a 或P Qa 则a属于FIRSTVT P 若a属于FIRSTVT Q 且P Q 则a属于FIRSTVT P 26 算符优先分析法 LASTVT LASTVT P a P a或P aQ LASTVT P 的构造算法若P a或P aQ 则a属于LASTVT P 若a属于LASTVT Q 且P Q 则a属于LASTVT P 27 算符优先分析法 3 算符优先关系表构造算法 P ab 或P aQb 则有a bP aR 且b属于FIRSTVT R 则有a bP Rb 且a属于LASTVT R 则有a b 28 算符优先分析法 例 考虑文法G E E E T TT T F FF E i找出终结符间的优先关系矩阵 29 算符优先分析法 关于 的特别说明 为了方便操作 加入 文法开始符号S 有 S FIRSTVT S LASTVT S 对于算符优先文法 的优先级小于任何FIRSTVT S 中的终结符 任何LASTVT S 中终结符的优先级大于 的优先级等于 30 算符优先分析法 构造FIRSTVT F E iFIRSTVT F i T T F FFIRSTVT T FIRSTVT F i E E T TFIRSTVT E FIRSTVT T i 31 E E T TT T F FF E i 若P a 或P Qa 则a属于FIRSTVT P 若a属于FIRSTVT Q 且P Q 则a属于FIRSTVT P 构造LASTVT F E iLASTVT F i T T F FLASTVT T LASTVT F i E E T TLASTVT E LASTVT T i 32 E E T TT T F FF E i 若P a或P aQ 则a属于LASTVT P 若a属于LASTVT Q 且P Q 则a属于LASTVT P 计算优先关系1 E E TT anyofFIRSTVT T anyofLASTVT E T T FF anyofFIRSTVT F anyofLASTVT T 33 E E T TT T F FF E i 计算优先关系2 F E i anyofFIRSTVT E anyofLASTVT E E anyofFIRSTVT E anyofLASTVT E 34 E E T TT T F FF E i 算符优先分析法 算符优先关系表 35 算符优先分析法 现在优先关系已经确定 如何根据优先关系寻找可归约串 在算符优先算法中 可规约串叫做 句柄 最左素短语 算符优先分析法 根据算符优先关系确定最左素短语 归约 最左素短语 由于算符优先文法不含两个连续的非终结符 故可以把括在两个 之间的句型的一般性写成 N1a1N2a2 NnanNn 1an 1Nn 2 其中 ai都是终结符 Nj是非终结符 可有可无 可以证明 最左素短语是满足下列条件的最左子串 NjajNj 1aj 1 NiaiNi 1其中 aj 1 ajaj aj 1 aiai ai 1 37 算符优先分析法的例子 句子 adb 的识别过程如表 38 S a b A A SdA S 和 时候移进 时归约注意 归约串是根据优先关系得来的 上页PPT中的结论 而不是产生式 归约到一个非终结符即可 不必和产生式对应起来 识别句型 adb 得到的语法树 b 一般分析技术得到得到的语法树 a 算符优先分析技术得到得到的语法树 S a b A A SdA S 另一个例子 识别句型i i i i得到的语法树 b 一般分析技术得到得到的语法树 a 算符优先分析技术得到得到的语法树 算符优先分析 可见 算符优先分析不是规范归约 后面会讲 算符优先分析仅对终结符定义优先关系 未对非终结符号定义算符优先关系 所以无法发现由单个非终结符组成的 可归约串 也就是说在算符优先分析过程中 跳过了那些右部仅含一个非终结符号的产生式 称为单非产生式 如P Q 作业 选 文法G3 S A B A B AaB a求出各非终结符N的Firstvt N 和Lastvt N 构造包括符号 在内的算符优先表 G3是否是算符优先文法 如果是 给出语句 a a 的算符优先分析过程 1规范规约 定义 其实质是 在移进的过程中 当发现栈顶呈现出句柄的时候才用相应的产生式的左部符号进行替换的归约过程 性质 文法无二义的情况下 规范归约 最左规约 是规范推导 最右推导 所得的句型为规范句型 的逆过程 C 主要分析方法 2 LR分析法 停酴嫔拥翠磲绫谩驼躬杜稍迁禁蕺诹怖弑碓蓿瘢茁垂踵悔沸陇脚本爰灌敌撙颡腺处蹩郁纨掖鳜唉婀唧境荡疏鹬菟渭洁庸农砟柁吗绥韶藻氖珞颧辜谂庐氩瑁糅庹婶站虐草种唉某儡连灰臭揠苘华咙坟濯 1 E T 2 E E T 3 T F 4 T T F 5 F i 6 F E 规约 T F 规范归约 归约过程 自下而上分析 的分类如果归约过程中 每一步的归约的都是句柄 则称该分析是规范归约不满足这些条件的规约是非规范归约 自下而上分析的两大类具体的实现算法中 LR分析法是规范归约法 而算法优先分析法是非规范归约法 规范规约 概念回顾 短语的两个条件缺一不可 例 考虑文法G E 的一个句型i1 i2 i3E T E TT F T FF i E i2 i3是短语吗 尽管E i2 i3 但因为不存在E 开始符号 到i1 E的推导 所以i2 i3不是该句型的短语 该句型i1 i2 i3的短语有 i1 i2 i3 i1 i2 i1 i2 i3其中i1 i2 i3是直接短语i1是最左直接短语 即句柄 以前句柄是如何寻找的 S AcBeA bA AbB d 一个句型的句柄是这个句型的语法树最左那棵子树 只有且必须有两代 没有第三代 端末结点的自左向右的排列 规范归约中进行归约的过程就是不断对语法树进行修剪 剪枝 的过程 例 G E E T E TT F T FF i E 采用符号 作为待分析的符号串的左右分界符 作为初始状态 先将符号串的分界符推进符号栈 作为栈底符号 分析过程如下表 对于G E 分析对输入串i1 i2 i3的规范归约过程 G E E T E TT F T FF i E 0 i1 i2 i3 预备 i1 i2 i3 移进2 F i2 i3 归约 F i 3 T i2 i3 归约 T F 4 T i2 i3 移进5 T i2 i3 移进6 T F i3 归约 F i 7 T i3 归约 T T F 8 E i3 归约 E T E i3 移进 E i3 移进 E F 归约 F i E T 归约 T F E 归约 E E T E 接受 疑问作为自下而上分析的一种 规范规约也同样要解决规约原则和规约条件这两个基本问题 语法树并不存在 如果存在则直接可以得出结论 没有再分析的必要 那么如何来进行规范规约 即如何确定句柄呢 在规范规约的具体算法中会对此问题加以解决 如后面要讲到的LR分析法 自下而上分析的具体实现算法 算符优先分析法LR分析法LR 0 SLRLR 1 LALR 是非规范规约法 是规范规约法 C 主要分析方法 2 LR分析法 2LR分析法 LR K 分析法的含义L 自左向右扫描输入串 源程序 R 分析过程构成最右推导的逆序K 每次根据当前的输入符号最多向前 右 查看K个符号就可以唯一地确定下一步动作是移进还是归约以及用哪条规则进行归约 因而也能唯一地确定句柄 53 C 主要分析方法 2 LR分析法 LR分析器能分析的文法 LR文法 LR文法一个文法G若能构造一张LR分析表 并使它的每个入口 表中的元素 都是唯一确定的 则称文法G为LR文法 LR K 文法一个LR文法G 若每步最多向前查看K个输入符号就能决定当前分析动作 从而按LR方法进行分析 则称文法G为LR K 文法 54 为何要用LR分析 教材 是规范归约适用范围广 适用于大多数上下文无关文法描述的语言分析速度快 能准确定位错误缺点 LR分析器的构造工作量大 55 3LR分析器的逻辑结构 LR分析器组成 分析表总控程序分析栈 a1a2 an 总控程序 输入串 源程序 分析栈 输出分析结果 56 分析栈 符号栈符号栈内存放分析过程中移进或归约的符号 状态栈状态栈存放的是状态 标记 状态Ii概括了栈中位于Ii下面的全部信息 也就是记录分析过程从开始到某一归约阶段的整个分析历史 和预测扫描可能遇到的分析符号 分析开始时 分析栈压入初始状态I0和输入符号 分析器处于初始状态I0 I0刻画了当前栈内仅有一个符号 的事实并预示将扫描的输入字符应刚好是可作为句子首符号的那些符号 57 分析表 动作表 ACTION 状态转换表 GOTO 58 ACTION表 ACTION表的结构如下 59 分析动作 ACTION表中的元素ACTION Im ai 表示当前状态Im面临输入符号ai时所完成的分析动作 分析动作可分四类 移进归约接受出错 60 移进 表示句柄尚未在分析栈的栈顶形成 正期待继续移进符号 以形成句柄 移进的标志 ACTION Im ai Sj 当前栈顶状态为Im 输入符号为ai 应将输入符号ai移进分析栈的符号栈栈顶 同时将Ij移进分析栈的状态栈栈顶 61 ai Ij 归约 归约的标记 ACTION Im ai rj 表明当前分析栈 如右图 顶部的符号串已是当前句型的句柄 需要立即进行归约 其中rj表示按文法的第j条规则 产生式 进行归约 设第j条规则为 A Xm r 1Xm r 2 Xm具体是将分析栈自顶向下的r个符号 包括状态栈内相应的状态 弹出 将A压入符号栈内 此时分析栈格局为 下页图2 62 再以 Im r A 查GOTO表 若GOTO Im r A Ik 把Ik压入状态栈 Ik 接受 接受的标志 ACTION Im ai acc 分析动作接受表示当前输入的符号串分析成功 终止分析器工作 64 出错 出错的标志 ACTION Im ai error 分析动作为出错 表示当前输入的符号串中有语法错误 调用相应的出错处理程序 GOTO表 GOTO表的结构如下 65 取值为状态 表示当前状态I1面临输入符号X2时需转移到的下一个状态 总控程序 总控程序是LR分析的实现算法 描述如下 初始化 将初始状态I0及输入符号串的左界符 推入分析栈 从输入串中读入当前的输入符号ai 根据当前状态栈栈顶状态Im与输入符号ai查ACTION表 若ACTION Im ai Sj 完成移进动作 若ACTION Im ai rj 以文法的第j条规则完成归约动作 若ACTION Im ai acc 分析成功 结束 若ACTION Im ai error 出错处理 重复2 直到出错或接受为止 66 接受时的分析栈 a1a2 ai an 输入串 67 68 68 例 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 其LR分析表如下页 分析输入串i i i 例 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i ACTION表GOTO表 69 状态 若移入 i为状态若规约 i为产生式编号 Vt Vn 70 70 分析过程 i i i 步骤状态栈符号输入串动作 10 i i i 初始化 205 i i i S 303 F i i R6 402 T i i R4 5027 T i i S 60275 T i i S 702710 T F i R6 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 110165 E i S 120163 E F R6 130169 E T R4 1401 E R1 15Accept 901 E i R2 10016 E i S 802 T i R3 文法G E 1 E E T 2 E T 3 T T F 4 T F 5 F E 6 F i 分析过程 i i i 72 72 由分析过程可以看到 1 每次规约总是规约当前句型的句柄 是规范归约 2 分析的每一步栈内符号串与输入串的剩余部分构成规范句型 通过规范规约得到的句型 例 设有文法G S S SS S SS 根据给定的分析表 对输入串 进行LR分析 73 00 S2102 r332023 S S430234 S r35402345 S S r21501 S acc 1 S S2 S S S3 S ACTION表 GOTO表如何构造 LR分析器根据分析表的构造方法的不同可分为 LR 0 分析表SLR分析表规范LR分析表 LR 1 LALR分析表 3LR 0 规范句型的活前缀 77 77 规范句型 通过规范规约得到的句型 前缀 字的任意首部 活前缀 是规范句型的一个前缀 且这个前缀中不含句柄之后的任何符号 例 有文法E T E T E TT i E 拓广文法G S E E T E T E TT i E 已知句型E i 求活前缀 E E E E i是句型E i 的活前缀 78 E T E TT F T FF i E 0 i1 i2 i3 预备 i1 i2 i3 移进2 F i2 i3 归约 F i 3 T i2 i3 归约 T F 4 T i2 i3 移进5 T i2 i3 移进6 T F i3 归约 F i 7 T i3 归约 T T F 8 E i3 归约 E T E i3 移进 E i3 移进 E F 归约 F i E T 归约 T F E 归约 E E T E 接受 分析过程 实质上就是一个逐步产生规范句型的活前缀的过程 栈中的符号串始终是活前缀 然后继续读入 构成新的活前缀 当栈顶形成句柄时 立即进行归约 形成新的句型 然后再不断生成这个句型的活前缀 重复此过程 直到生成文法开始符号E LR分析是通过寻找规范句型的活前缀来实现的 LR 0 项目族的构造 LR 0 项目 在文法G每条规则的右部的任何位置上添加一个圆点 所构成的规则称为LR 0 项目 规定A 的LR 0 项目为 A 项目的直观意义 指明在分析过程中的某一时刻已经归约的部分和等待归约部分 80 例 对于文法G S S A b A aA b 其LR 0 项目有 S A S A S b S b A aA A a A A aA A b A b LR 0 项目与活前缀 句柄的关系 例 G S S aCC AcBeA bA AbB d 句子abbcde分析到某一步的时候状态如右 分析到该步骤时生成的句型 该句型的一个活前缀 当前要归约的句柄是AcBe其中 AcB已分析完毕进栈 而e还未分析 进栈 用项目C AcB e表示 LR 0 项目的分类 根据圆点所在的位置项目分为以下几种 归约项目 形如A 表示当前栈顶的内容已构成所期望的句柄 应按A 进行归约 接受项目 形如S 其中S 是文法唯一的开始符号 表示句柄已在栈顶形成 用S 进行归约 整个分析成功 移进项目 形如A a a VT 表示栈内仅是句柄的一部分 为了构成句柄 应先把a移进分析栈 待约项目 形如A B B VN 表示栈内仅是句柄的一部分 为了构成句柄 应先把当前输入符号串中相应的内容归约到B 82 活前缀通过由LR 0 项目构造出来的状态转换图来识别 步骤为 每个LR 0 项目对应NFA的一个状态 每个项目均为终态 S A为初态 若状态i和j中的LR 0 项目出自同一条规则 只是圆点位置相差一个符号 即i为X X1X2 Xi 1 Xi Xnj为X X1X2 Xi Xi 1 Xn则从状态i到状态j 引一条标记为Xi的箭弧 若状态i为待约项目 则从状态i引箭弧到所有A 的状态并标记为 83 例 设文法G A A aAA b构造识别文法G的所有活前缀的NFA 先对G A 进行拓广 拓广后的文法G S S AA aAA b 84 添加一个新的开始符号S 使S S S为原来的开始符号 目的在于使最终求得的action表只含有唯一一个接受状态 A b S A A aA A b S A A a A A aA a b A A 识别文法G S 的活前缀的NFA 85 S AS A A aAA a AA aA A bA b S AA aAA b 确定化后的DFA 86 LR 0 项目集规范族 上图中每个状态都是由一组的项目组成的集合 称为项目集 识别文法G的活前缀的DFA项目集的全体称为文法的LR 0 项目集规范族 对于上述文法G S 的LR 0 项目集规范族C为 C S A A aA A b A a A A aA A b A b S A A aA 87 通过列出拓广文法的所有项目 进而构造识别活前缀的NFA 再确定化为DFA的方法 工作量较大 不实用 实用的方法是直接构造以项目集为状态的识别活前缀的DFA 88 构造文法G的LR 0 项目集规范族的方法二 项目集的闭包 即DFA中的状态设I是文法G S 的一个项目集 则I的闭包closure I 为 任何LR 0 项目i I 有i closure I 若项目A B closure I 且B 是G S 的产生式 则B closure I 重复2 直至closure I 不再增大为止 GO函数 设I是项目集 X VN VT 则 GO I X closure J 其中J 形如A X 的项目 A X I 通过GO函数可以从一个项目集求出另外的的项目集 直观含义 它规定了识别活前缀的DFA从状态I 项目集 出发 经过X弧所应该到达的状态J 项目集 90 构造算法 构造LR 0 项目集规范族C的算法描述如下 C closure S S repeatforC中每一个项目集I和每一个文法符号Xdoif GO I X 不空且GO I X 不属于C then将GO I X 加入C中 until C不再增大 91 例 设文法G S S AA aA b计算G S 的LR 0 项目集规范族 拓广后的文法为G S 0 S A1 A aA2 A b 92 I0 closure S A S A A aA A b GO I0 a closure A a A A a A A aA A b I1GO I0 b closure A b A b I2GO I0 A closure S A S A I3GO I1 a closure A a A I1GO I1 b closure A b A b I2GO I1 A closure A aA A aA I4G S 的LR 0 项目集规范族C I0 I1 I2 I3 I4 0 S A1 A aA2 A b 对应的DFA I1 I0 I2 I3 I4 94 LR 0 分析表的构造算法 设C I0 I1 In 每个项目集Ik的下标k作为分析表的状态 则若GO Ik a Ij 则置ACTION k a Sj 若GO Ik A Ij 则置GOTO k A j 若第j条规则的项目A Ik 则对所有终结符号a 包括 置ACTION k a rj 若S S Ik 则置ACTION k acc 表中空白处置出错标志 95 G S 的LR 0 分析表 r1 r1 r1 4 acc 3 r2 r2 r2 2 4 S2 S1 1 3 S2 S1 0 A b a GOTO ACTION 状态 0 S AA aAA b 2 A b 3 S A 1 A a AA aAA b 4 A aA a b A A a b 0 S A1 A aA2 A b LR 0 文法 LR 0 文法 按上述算法构造的分析表 如果每个入口不含多重定义 则称它为文法G的一张LR 0 表 具有LR 0 表的文法G称为LR 0 文法 LR 0 文法是无二义的 例 设拓广文法G S 的产生式为 0 S S1 S aA2 S bB3 A cA4 A d5 B cB6 B d LR 0 项目集规范族 I0 S SS aAS bBI1 I0 S S S I2 I0 a S a AA cAA d I3 I0 b S b BB cBB dI4 I2 c A c AA cAA dI5 I3 c B c BB cBB d I6 I2 A S aA I7 I3 B S bB I8 I4 A A cA I9 I5 B B cB I10 I2 d A d I11 I3 d B d 98 I4 c I5 c I4 d I5 d A c AA cAA dI4 S a AA cAA dI2 S b BB cBB dI3 B c BB cBB dI5 S SS aAS bBI0 start S S I1 A cA I8 S aA I6 A d I10 A d d A c a b S S bB I7 B cB I9 B d I11 B d d B c c c 识别文法活前缀的DFA 99 LR 0 分析表 0 S S1 S aA2 S bB3 A cA4 A d5 B cB6 B d 例 文法G S 0 S S 1 S rD 2 D Di 3 D iLR 0 项目集规范族I0 S SI3 S rD S rDD D iI1 S S I4 D i I2 S r DD DiI6 D Di D i问题 其中I3中含有移进 归约冲突 Action I3 i 有两个取值 文法不是LR 0 的 如何解决 4SLR SLR 1 分析 项目集IK含移进 归约或归约 归约冲突 IK A b P Q 若满足FOLLOW Q FOLLOW P b互不相交 则可以用下面方法解决 解决冲突的SLR 1 技术 1 action k b 移进2 对a FOLLOW P 则action k a 用P 归约3 对a FOLLOW Q 则action k a 用Q 归约用SLR 1 技术解决冲突的文法称为SLR 1 文法 SLR 1 文法是无二义的 若GO Ik a Ij 则置ACTION k a Sj 若第j个产生式的项目A Ik 则对任何输入符号a FOLLOW A 置ACTION k a rj 若项目S S Ik 则置ACTION k acc 若GO Ik A Ij 则置GOTO k A j 空白格置上 出错标志 SLR分析表的构造 按上述算法构造的分析表 如果每个入口不含多重定义 则称它为文法G的一张SLR表 具有SLR表的文法G称为一个SLR 1 文法 数字1的意思是 在分析过程中顶多只要向前看一个符号 SLR分析表的构造 I0 S SI3 S rD S rDD D iI1 S S I4 D i I2 S r DD DiI6 D Di D i Follow S Follow S Follow D i 0 S S 1 S rD 2 D Di 3 D i action goto 状态 i r S D 0 1 2 3 4 6 S 2 acc S 4 S 6 r1 r3 r3 r 2 r 2 1 3 作业 给定以下拓广了的文法G S S AA AbA bBaB aAcB aB aAb构造LR 0 项目集规范族 证明它是SLR 1 的 而不是LR 0 的 构造SLR 1 分析表 用你构造的SLR 1 分析表分析串baab是否为该文法的句子 SLR 1 的局限 例 文法G 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A eLR 0 项目集规范族 I0 S SS aAdS bAcS aecS bedI1 S S I2 S a AdS a ecA e 若项目集IK A b P Q 含移进 归约或归约 归约冲突且不满足FOLLOW Q FOLLOW P b互不相交 I3 S b AcS b edA eI4 S aA dI5 S ae cA e I6 S bA cI7 S be dA e I8 S aAd I9 S aec I10 S bAc I11 S bed 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e follow A d c ACTIONGOTOacebd SA012345r5S967r7S11891011 5LR 1 例 文法G 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A eI5 S ae cI7 S be dA e A e S S aAd aed S S bAc bec S S aec S S bed LR 1 项目 A a 意味着处在栈中是 的相应状态 但只有当下一个输入符是a时才能进行归约 如果有多个向前搜索符 比如a b c时 可写作A u a b c A a 意味着处在栈顶是 并期望相应 且 进入后只有当跟在 后的是a时进行归约 a称作该项目的向前搜索符 lookahead 它只对圆点在最后的项目起作用 构造LR 1 项目集规范族 closure I 按如下方式构造 1 I的任何项目属closure I 2 若 A 1 B 2 a closure I B 是一产生式 那么对于FIRST 2a 中的每个终结符b 把 B b 加进去 3 重复2 直至closure I 不再增大 构造LR 1 项目集规范族 GO函数 I是一个项目集 X是一个文法符号GO I X closure J 其中J 任何形如 A X a 的项目 A X a I LR I 项目规范族C的构造算法同LR 0 的构造 只是初始时 C closure S S 例 0 S S 1 S aAd 2 S bAc 3 S aec 4 S bed 5 A e的LR 1 项目集规范族 I0 S S S aAd S bAc S aec S bed I1 I0 S S S I2 I0 a S a Ad S a ec A e dI3 I0 b S b Ac S b ed A e c I4 I2 A S aA d I5 I2 e S ae c A e dI6 I3 A S bA c I7 I3 e S be d A e cI8 I4 d S aAd I9 I5 c S aec I10 I6 c S bAc I11 I7 d S bed 规范的LR 1 分析表的构造 若GO Ik b Ij 则置ACTION k b Sj 若第j个产生式的项目 A b 属于Ik 那么置ACTION k b rj 若项目 S S 属于Ik 则置ACTION k acc 若GO Ik A Ij 则置GOTO k A j 其他置上 error ACTIONGOTOacebd SA0123467891011 I0 S S S aAd S bAc S aec S bed S2 S3 1 Acc S5 4 I1 I0 S S S I2 I0 a S a Ad S a ec A e d I3 I0 b S b Ac S b ed A e cI4 I2 A S aA d I5 I2 e S ae c A e dI6 I3 A S bA c I7 I3 e S be d A e c I8 I4 d S aAd I9 I5 c S aec I10 I6 c S bAc I11 I7 d S bed S7 6 S8 r5 S9 S10 S11 r5 r1 r3 r2 r4 按上述算法构造的的分析表 如果每个入口不含多重定义 则称它为文法G的一张规范的LR 1 分析表 具有规范的LR 1 表的文法G称为一个LR 1 文法 例1 0 S S 1 S L R 2 S R 3 L R 4 L i 5 R L不能用SLR 1 技术解决 但能用LR 1 LR 1 比SLR 1 能力强 I1 S S I5 L i I7 L R I8 R L I9 S L R I3 S R I12 L i I10 R L I13 L R I0 S S S L R S R L R L i R L I4 L R R L L i L R I6 S L R R L L R L i I11 L R R L L R L i I2 S L R R L s R L R i i i i R L L R L LR 1 项目集及转换函数 每个SLR 1 文法都是LR 1 的 一个SLR 1 文法的规范LR分析器比其SLR 1 分析器的状态要多 例2 G S 1 S BB 2 B aB 3 B bLR 0 项目集只有7个 I0 S SS BBB aBB bI1 S S I2 S B BB aBB bI3 B a BB aBB bI4 B aB I5 B b I6 S BB I6 S a B B aB B b LR 1 项目集和转换函数 I0 S S S BB B aB a bB b a b I1 S S I2 S B B B aB B b I5 S BB I3 B a B a bB aB a bB b a b I4 B b a b I7 B b I9 B aB I8 B aB a b S B B a b b b B B a a b 0 S S 1 S BB 2 B aB 3 B b a 0S3S4121acc2S6S753S3S484r3r35r16S6S797r38r2r29r2 LR 1 分析表 作业 文法G S 为 VT VN S P 其中VT a b c VN S L R P为如下产生式 S LaR RL bR cR L该文法是否SLR 1 文法 该文法是否LR 1 文法 通过构造分析表证明 如果是LR 1 文法 请给出用LR 1 分析表对句子bcac 的分析过程 如果不是LR 1 文法 请给出句子bcac的规范推导 6LALR 课后自学 LALR 在SLR 1 和LR 1 间寻找折衷办法 状态数目 分析能力 LALR lookaheadLR 合并同心集 I36I47I89 I3 B a B a bB aB a bB b a b I6 S a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB 文法G 的LR 1 的两个项目集Ii和Ij在去掉各项中搜索符之后是相同的 则称这两个项目集是同心的 仅当文法是LR 1 时才有可能构造LALR分析表 合并同心 可得到一个与LR 0 相同的项目集 除搜索符外 个数相同 使得表的规模减少 LR 1 项目集不存在动作冲突 合并同心集后不会产生新的移进 归约冲突 可能会产生新的归约 归约冲突 在合并同心时 以某种方式合并LR 1 分析表中的ACTION表和GOTO表的对应项 可得到一张分析表 1 构造文法G的规范LR 1 状态 2 合并同心集 除搜索符外两个集合是相同的 的状态 3 新LALR 1 状态的GO函数是合并的同心集状态的GO函数的并 4 LALR 1 分析表的action和goto登录方法与LR 1 分析表一样 经上述步骤构造的表若不存在冲突 则称它为G的LALR 1 分析表 存在这种分析表的文法称为LALR 1 文法 LALR 1 分析表的构造 例 G S 1 S BB 2 B aB 3 B b I3 B a B a bB aB a bB b a b I6 S a B B aB B b I4 B b a b I7 B b I8 B aB a b I9 B aB 合并同心集 0S3S4121acc2S6S753S3S484r3r35r16S6S797r38r2r29r2 LR 1 分析表 0S3 6S4 7121acc2S3 6S4 753 6S3 6S4 78 94 7r3r3r35r18 9r2r2r2 LALR 1 分析表 例 0 S S 1 S L R 2 S R 3 L R 4 L i 5 R L I1 S S I5 L i I7 L R I8 R L I9 S L R I3 S R I12 L i I10 R L I13 L R I0 S S S L R S R L R L i R L I4 L R R L L i L R I6 S L R R L L R L i I11 L R R L L R L i I2 S L R R L s R L R i i i i R L L R L LR 1 项目集及转换函数 0S4S61231acc2S6r53r24S4S5875r4r46S4S5897r3r38r5r59r1 LALR 1 分析表 语法分析总结 第四章 第五章 138 138 语法分析方法 一 自上而下分析 139 139 1 构造First集合的算法2 构造Follow集合的算法3 构造分析表的算法 140 140 二 自下而上分析 规约过程 1 思想 采用栈 不断的移进 当栈顶出现可规约串时进行规约 2 算法 问题 如何寻找可规约串 i 算符优先分析法 1 分析器的构造 分析过程 根据算符优先关系矩阵来决定是移进还是规约 141 141 2 算符优先法的进一步讨论 1 适用的文法类 引出的算符优先文法的定义2 优先关系矩阵的构造3 什么是 可规约串 如何找引出的最左素短语的概念 最左素短语的定理 如何找 ii LR分析法 1 概述 概念 术语 活前缀 项目 142 142 2 LR分析 1 逻辑结构 2 分析过程 状态栈 分析表 控制程序 GOTO表 分析动作表 3 如何构造LR 0 分析表 1 构造DFA 2 由DFA构造分析表 4 如何构造SLR LR 1 分析表 143 143 除了递归子程序法 其他几种方法逻辑结构很象 1 对于LL 1 分析法 符号栈 自上而下 保证最左推导 LL 1 分析表 首字符 144 144 2 对于算法优先分析 符号栈 3 LR分析 145 145 GOTO表 根据栈顶状态和栈顶符号推导出下一状态 分析动作表 根据栈顶状态和输入符号推导出下一动作 自动生成编译器工具简介 自动生成编译器工具简介 词法分析器的自动生成工具 Lex 瀣谭霸偬惩鸨郊陀馓瞎咝湍榆啷吖嫘蹼纾爆坎跞怖绢柯棕蠢篚莛冂毯孳偌擞爝混冷愕潦坊儇砌氲阁雎氛劳阵逡淬芨瞽嗉涯攫蠊榜些儡辐借枨觐篆市钗宿薄琉虽竟虔俩窍歼倭窗赊很氯福念诼窕蜍咎孳屿忌潍褂谰消 教材3 4P 86 91 返回一个整数值 可能出现的单词种别 传递给谁 Lex 当Lex接收到文件或文本形式的输入时 它试图将文本与常规表达式进行匹配它一次读入一个输入字符 直到找到一个匹配的模式 如果能够找到一个匹配的模式 Lex就执行相关的动作 可能包括返回一个标记 另一方面 如果没有可以匹配的常规表达式 将会停止进一步的处理 Lex将显示一个错误消息程序有三个部分 用 符号隔开 第一部分声明和最后一个部分是普通而古老的C代码 直接复制到文件lex yy c中 中间是有趣的一部分 它由一系列规则构成 lex将这些规则翻译为词法分析器 每一个规则依次包含一个正则表达式以及该正则表达式得到匹配时要运行的一些代码 任何没有得到匹配的文本则简单地拷贝到标准输出 Lex编程Lex编程可以分为三步 以Lex可以理解的格式指定模式相关的动作 在这一文件上运行Lex 生成扫描器的C代码 编译和链接C代码 生成可执行的扫描器 Lex的输入格式一个Lex程序分为三个段 P 87 第一段 是C和Lex的全局声明第二段 包括模式 C代码 第三段 是补充的C函数 这些段以 来分界 教材P 88 如果希望某个元符号 如 表示其自身 可在它前面加反斜线 Lex的常规表达式 1 Lex的常规表达式 2 常规表达式举例 标记声明举例 问 若看到字符串 if 采用哪条规则转换成词法单元 Lex解决冲突的规则 1 总是选择最长前缀 2 当最长匹配前缀和多个模式匹配时 Lex总是选择最先被列出的模式 Lex变量 Lex有几个函数和变量提供了不同的信息 可以用来编译实现复杂函数的程序 下表中列出了一些变量和函数 以及它们的使用 Lex函数 语法分析器的自动产生工具 YACC Yacc编译器 Yacc源程序calc y calc tab c C编译器 calc tab c a out a out 输入 输出 YACC YetAnotherCompilerCompiler 瀣谭霸偬惩鸨郊陀馓瞎咝湍榆啷吖嫘蹼纾爆坎跞怖绢柯棕蠢篚莛冂毯孳偌擞爝混冷愕潦坊儇砌氲阁雎氛劳阵逡淬芨瞽嗉涯攫蠊榜些儡辐借枨觐篆市钗宿薄琉虽竟虔俩窍歼倭窗赊很氯福念诼窕蜍咎孳屿忌潍褂谰消 YACC内部使用符号 名称含义y tab cyacc输出文件名y tab hyacc生成的头文件yyparseyacc分析主函数yylval属性栈顶 对应符号的 值yyerror错误信息的输出函数erroryacc中 错误 伪记号yyerrok出错后重置分析栈于正常工作状态YYSTYPE定义属性栈值类型yydebug值为1时 产生分析器运行信息 纽圈味啡抢叁嗥哳嗳倭螟軎