编译原理lr项目集
A. 编译原理中语法分析的一道问题
LALR我做着做着觉得不对,但SLR还是没问题的,这道题工程量非常庞大,想必以后也一定有人问,我就简要的带过吧,我归纳的解题步骤是:
构造LR(0)项目集规范族
求出FOLLOW集
根据规则圈出sj和rj对应的产生式
算出goto数
构造分析表
B. 编译原理lr0和slr1的区别
语法分析有自上而下和自下而上两种分析方法其中自上而下:递归下降,LL(1)自下而上:LR(0),SLR(1),LR(1),LALR(1)
LR需要构造一张LR分析表,此表用于当面临输入字符时,将它移进,规约(即自下而上分析思想),接受还是出错。
LR(0)找出句柄前缀,构造分析表,然后根据输入符号进行规约。 SLR(1)使用LR(0)时若有冲突,不知道规约,移进,活移进哪一个,所以需要向前搜索,则只把有问题的地方向前搜索一次。 LR(1)1.在每个项目中增加搜索符。2.举个列子如有A->α.Bβ,则还需将B的规则也加入。 LALR(1)就是假如两个产生式集相同则将它们合并为一个,几合并同心集。
C. 编译原理中,LR(0)文法的项目集规范族的I0,I1,I2,I3…………是怎么求的~
先举个例子:
}
将其命名为I1。
其他可类似推出。
D. 有关编译原理
⑴拓广文法 1 分
G[S ′ ]: S ′→ S ⑴
S → SaA ⑵ S → a ⑶ A → AbS ⑷ A → b ⑸
该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA :
⑵ 该文法的 LR(0) 分析表:
状态 ACTION GOTO
a b # S A
0 S 2 1
1 S 3 acc
2 r 3 r 3 r 3
3 S 5 4
4 r 2 r 2 /S 6 r 2
5 r 5 r 5 r 5
6 S 2 7
7 r 4 /S 3 r 4 r 4
⑶ LR(0) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中没有冲突状态。
该文法不是 LR(0) 文法
因为存在冲突状态: I 4 和 I 7
⑷ SLR(1) 文法:该文法的以 LR(0) 项目集为状态的识别规范句型活前缀的 DFA 中有冲突状态,冲突可用 FOLLOW 集解决。
该文法不是 SLR(1) 文法。
因为 FOLLOW(S)={a,b,#} ,所以无法解决冲突
E. 编译原理——LR分析表
自底向上的语法分析
LR分析表的结构如上,其分为两个部分 Action Goto
两个参数状态i,终结符号a(s(i)代表第i个状态,r(i)代表第i条表达式)
Goto[i,A]=j
文法
容易得知这个文法可以推出 0 1 00 01 等的字符串。因为它是 左递归 。不适用于 LL 文法分析,只能使用 LR 分析。
因为本题入口有两个—— S → L·L S → L ,所以需要构造额外的产生式 S'->S
2.1 第一次遍历
我们从 [S -> . L·L] 开始,构造这个状态的闭包,也就是加上所有能从这个产生式推出的表项。
首先,判断 . 后面是否为 非终结符号A 。如果是,那我们就得找所有由 A-> 推出的产生式,并将它们添加进入 闭包 里(也就是State包里)。循环做即可。
因此我们可以得到 State 0 有
下一步,就是我的 . 往下一位移动。对每个符号X后有个 . 的项,都可以从 State 0 过渡到其他状态。
由以上6条式子可以得知下一位符号可以是 S L B 0 1 。所以自然可以得到5个状态。
State 1 是由 State 0 通过 S 转移到这里的,所以我们找出所有 State 0 中在 S 前有 . 的项。
此状态作为结束状态 Accept ,不需要继续状态转移了。
State 2 是由 State 0 通过 L 转移到这里的,所以我们找出所有 State 0 中在 L 前有 . 的项。
S -> . L·L S -> . L L -> . LB
有3条式子,现在我们将 . 向后推一格,就得到 State 1 的项了。
但是 . 之后的符号分别是 · $ B , B 为非终结符号,我们得包含 B -> 的项
State 3 是由 State 0 通过 B 转移到这里的,所以我们找出所有 State 0 中在 B 前有 . 的项。
因为 . 后没有其他符号了,因此这个状态不需要继续转移了。
State 4 是由 State 0 通过 0 转移到这里的,所以我们找出所有 State 0 中在 0 前有 . 的项。
因为 . 后没有其他符号了,因此这个状态不需要继续转移了。
很简单,同样的道理找 State 5
State 5 是由 State 0 通过 1 转移到这里的,所以我们找出所有 State 0 中在 1 前有 . 的项。
因为 . 后没有其他符号了,因此这个状态不需要继续转移了。
好的,现在我们第一次遍历完成。
2.2 第二次遍历
第二次遍历自然从 State 2 开始。
我们回到 State2 ,可以看出 . 之后的符号有 · B 0 1 。
State 6 是由 State 2 通过 · 转移到这里的,所以我们找出所有 State 2 中在 · 前有 . 的项。
S -> L. ·L 只有1条,我们往后移发现 L 又为非终结符号,参考 State 0 做的操作,我们得找出所有的式子。
共有5条式子,共同组成 State 6 ,由上面的式子可以看出我们还得继续下一次遍历。先不管着,我们进行下一次状态查找。
State 7 是由 State 2 通过 B 转移到这里的,所以我们找出所有 State 2 中在 B 前有 . 的项。
L -> L. B 也是只有1条,我们往后移发现没有非终结符号了,那就不需要再继续添加其他式子了。
这个状态也不需要继续进行转移了。
接下来很关键,因为我们通过 State2 的 . 后的符号找出了 State 6 State 7 ,接下来还差符号 0 1 ,那么是否像之前一样按例添加状态呢, 答案是不是的 ,因为我们发现通过 0 1 找到的闭包集分别是 B -> 0 B -> 1 ,这与我们的之前的 State 4 State 5 相同。所以我们得将其整合起来,相当于 State 2 通过 0 1 符号找到了 State 4 State 5 状态。
2.3 第三次遍历
回头看第二次遍历,可以看出只有 State 6 可以进行状态转移了。
那么就将 State 6 作为第三次遍历的源头,可以看出 . 之后的符号有 L B 0 1 。
State 8 是由 State 6 通过 L 转移到这里的,所以我们找出所有 State 6 在 L 前有 . 的项。
S -> L· .L L -> . LB 有两条式子,往后移发现有非终结符号 B ,所以经过整合可以得到
可以看出 . 的后面还有一个符号,所以这里我们还得再进行一次遍历。
接下来,又是遇到重复的包的情况,可以看出我们由 State 6 通过 B 0 1 得到的闭包分别是 L->B B->0 B->1 ,很明显,这分别对应于 State 3 State 4 State 5 。
第三次遍历也就结束了。
2.4 第四次遍历
回看第三次遍历,可以看出只有 State 8 可以进行状态转移,其 . 之后的符号分别是 B 0 1 。
诶,感觉很熟悉,就是上面几行刚说的情况,也就是说通过这三个符号找到的闭包是我们之前遇到的状态,分别是 State 3 State 4 State 5 。
做到这里,我们发现我们已经全部遍历完毕!
总共有8个状态,通过以上流程做成个图是什么样子的?来看看!
这么一看就很清晰明了了,我们就可以通过这个图做出我们的 LR分析表
其实就是我们之前呈现的表
在状态 I2 和 I8 中,既有 移入 项目,也有 规约 项目,存在 移入 - 规约的冲突 ,所以不是 LR(0) 文法,但是因为 FOLLOW(S) ∩ {0, 1} = ∅,所以可以用 FOLLOW 集解决冲突,所以该文法是 SLR(1) 文法。
上表我们发现还有 r1,r2,r3 等。这个其实就是代表状态停止转移时为 第几条表达式 ,r3代表第三条表达式 L -> LB 。
当我们构建了表之后,我们如何运用起来呢?
下面我们通过一个例子来说明
以上字符串是如何被SLR分析器识别的呢?
F. 编译原理中LR(1) 那个向前搜索符怎么求的 跪求高手解答 复制粘贴或者答非所问的别来
1、首先第一步就是项目[S’-> . S,],自动生成搜索符],自动生成搜索符],自动生成搜索符,从项目[A->α.Bβ,?]生成项目[B->…,first(β)]。
G. 编译原理 A产生空和B的规约在一个项目集里是规约冲突吗
如果我们把同心的项目集合合并为一,就可能导致冲突,但是这种冲突不会是移进-规约冲突.因为如果存在这种冲突,则意味着对当前输入符号a,有一个项目[A→α.,a]要求以A→α进行规约,同时又有另一个项目[B→β.aγ,b]要求把a移进.这两个项目既然同处于合并之后的项目集中,则意味着在合并前,必有某个c使得[A→α.,a]和[B→β.aγ,c]同处于合并前的某一集合中.然而,这又意味着原来的LR(1)项目集就已经存在移进-规约冲突.从而文法不是LR(1)的,这与假设不符.事实上移进-规约冲突不依赖于搜索符号而只依赖于其心,因此,同心集合的合并不会引起新的移进-规约冲突
H. 编译原理简单文法归约计算
编译原理中的语法和文法是不一样的,但却融会贯通。
在计算机科学中,文法是编译原理的基础,是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型,即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
形式语言,这种理论对计算机科学有着深刻的影响,特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
多数程序设计语言的单词的语法都能用正规文法或3型文法(3型文法G=(VN,VT,P,S)的P中的规则有两种形式:一种是前面定义的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一种形式是:A→Ba或A→a,前者称为右线性文法,后者称为左线性文法。正规文法所描述的是VT*上的正规集)来描述。
四个文法类的定义是逐渐增加限制的,因此每一种正规文法都是上下文无关的,每一种上下文无关文法都是上下文有关的,而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。