编译原理笔记14:自下而上语法分析(1)短语、句柄,规约,移进规约分析器的工作模式

您所在的位置:网站首页 笑呵呵的短语和句子 编译原理笔记14:自下而上语法分析(1)短语、句柄,规约,移进规约分析器的工作模式

编译原理笔记14:自下而上语法分析(1)短语、句柄,规约,移进规约分析器的工作模式

2024-07-07 22:27| 来源: 网络整理| 查看: 265

目录 基本方法短语、句柄,规范规约,剪句柄短语、直接短语和句柄规范规约(最左规约)例: 移进-规约移进规约分析器的工作模式移进规约分析例:

基本方法

从句子 ω 开始,从左到右扫描 ω,反复用产生式的左部替换产生式的右部、谋求对 ω 的匹配,最终得到文法的开始符号(或,发现错误)(也就是从下往上搞出个树,最后推到根也就是开始符号了)

在分析的过程中,每一步都总是尝试在句型中寻找一个能够被替换为产生式左部的子串。就这样一步步向上去替换,最终变成一个开始符号。

而,由于我们对记号流的扫描是从左到右的,故我们【尝试寻找句型中能够被替换为产生式左部的子串,并不断进行替换】的过程也是从左到右的。这样从记号到开始符号一步进行自下而上分析的逆过程其实就是一个最右推导!

推导的逆过程,就叫做【规约】。最右推导的逆过程,就是最左规约。

在这里插入图片描述

短语、句柄,规范规约,剪句柄

最右推导叫做【规范推导】,因此作为其逆过程的最左规约,也就是【规范规约】了

短语、直接短语和句柄

设 αβδ 是文法 G 的一个句型,若存在 S =*> αAδ , A =+> β,则称 β 是句型 αβδ 相对于 A 的【短语】。若 A→β ,则称 β 是句型 αβδ 相对于产生式 A→β 的【直接短语】。一个句型的最左直接短语被称为【句柄】。

句型,是一个完整的结构,短语则是句型中针对某非终结符的局部。因此,开始符号 S 是句型而不是短语。

短语形成的要素:

S 可推导出 A,即 S=*> αAδ ;从 A 开始经过至少一次推导推出 β,即 A=+> β。

我个人认为(俺寻思):进行规约的一大关键点,是怎么在一堆本质上是字符串的符号流中,试图搞明白 “这到底哪几个连在一块的字符算一个符号啊?这到底几个符号连起来能和哪个产生式的右部匹配上啊?” 的问题。而这里的【短语】、【直接短语】、【句柄】概念,其实就是描述产生式右部的组合及边界的方案——回想自然语言中的 “短语”,自然语言中的短语是指由至少两个单词构成的、有序组合起来共同表达某一个含义的有序单词序列——只有特定的单词以特定的顺序组成序列才能被称为一个短语。那么语法分析中的短语也是一样的:语法分析中的短语是指由至少数个终结符或(和)非终结符构成的、有序组合起来的符号序列,这个序列就是某个产生式的右部,也就可以在规约时被规约为一个产生式的左部。

反映在上面定义的例子中,就是:

β 是句型 αβδ 相对于 A 的【短语】,那么 αβδ 就可以经过至少一步规约后规约为 αAδ 。而 αAδ 则能够在经过零或多步规约后,最终规约为开始符号 S;β 是句型 αβδ 相对于产生式 A→β 的【直接短语】,那么 αβδ 就可以在经过一步规约后成为 αAδ ;

在这里插入图片描述

短语,不一定是包含终结符的序列,也可以是单个的非终结符。在整个规约的过程中,句柄会不断变化:毕竟,根据定义,短语只是【从开始符号 S 可以导出(经过零或多步推导,不导也行。。)的非终结符 A 在经过至少一步推导后得出的句型】。那么在下面这个例子中,从开始符号 S 一定是可以经过推导得到非终结符 T2 的,T2 也能在经过一步推导后展开为 F1。那么,F1 就是 T2 的短语(而且是直接短语,而且是最左直接短语,那么这里的 F1 就是 T2 的句柄了)

在这里插入图片描述

短语:以非终结符为根子树中所有从左到右的叶子直接短语:只有父子关系的树中所有从左到右排列的叶子(树高为2)句柄:最左边父子关系树中所有从左到右排列的叶子(句柄是唯一的) 规范规约(最左规约)

若 α 是文法 G 的句子且满足下列条件,则称序列 αn, αn-1, …, α0 是一个最左规约:

αn = αα0 = S( G 的开始符号)对任何 i(0 < i


【本文地址】


今日新闻


推荐新闻


CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3