活前缀及构造活前缀的DFA | 您所在的位置:网站首页 › ab为前缀时有什么意思 › 活前缀及构造活前缀的DFA |
目录 1.引入背景 2.基本定义 (1)字的前缀 (2)活前缀 3.识别活前缀 4.构造识别活前缀的DFA (1)文法的拓广 (2)LR(0)项目 (3)相关例题 1.引入背景 上一讲我们讲了LR分析法和LR分析器的性质,我们知道了在规范规约过程中,栈内的符号串需要满足一定的条件,见下图: LR分析器的工作过程实际上就是逐步产生规范句型的活前缀 。 如何保证栈内的符号串永远不会出现在句柄之后呢,于是我们引入了字的活前缀。 2.基本定义 (1)字的前缀是指字的任意首部,如字ab的前缀有ε(ε是任何字的前缀),a , ab ,abc。 (2)活前缀可能大家看的有点懵,还是不理解什么叫做活前缀。其实通俗一点来讲,活前缀就是句柄的子集。 3.识别活前缀DFA状态机一直在分析活前缀,分析出一个句柄之后就分析到头了,然后立马规约这个句柄,就一直在规约句柄。活前缀之所以称为活前缀就是这么来的。为了防止歧义,就不能用NFA。 4.构造识别活前缀的DFA (1)文法的拓广 (2)LR(0)项目大家可能看了还有点懵,我来举个例子供大家理解一下。 第一个式子表示在分析过程中,我们期待马上将形成A而且是通过后面马上要识别XYZ之后来形成A的,X马上就要开始识别了。 第二个式子表示我们处于A的识别过程中,A的前一部分X已经被识别,压入栈,下面我们期待出现Y和Z。 第三个式子表示我们处于A的识别过程中,A的前一部分X和Y已经被识别,压入栈,下面我们期待出现Z。 第四个式子表示构成A的XYZ符号都已经识别了,因此马上可以把他们规约成A,A就识别了。 (3)相关例题根据上面的概念,我们可以列出该文法的所有项目
按照这个思路我们就能构造出识别所有文法的活前缀,我们下一讲将介绍把识别文法所有活前缀的NFA确定化。 |
CopyRight 2018-2019 实验室设备网 版权所有 |