编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)

简介: 编译原理——构造预测分析表(判断某字符串是否是文法G(E)的句子)

进入今天的学习前,若不理解LL(1)文法中的首符号集,后跟符号集和选择符号集,可看:

http://t.csdnimg.cn/BjSHv

构造预测分析表的步骤:

步骤1:对文法的每个规则U->u,执行步骤2与3


步骤2:对于每个终结符aFirst(u),让A[U,a]='U->u';


步骤3:如果(空串)First(u),则对Follow(U)中的每个终结符号b或#,让A[U,b]='U->u'或


A[U,#]='U->u';


步骤4:把A的每个未定义元素置为ERROR(用空白表示)


设有以下文法:

构造预测分析表之前需要列首符号集:

注:当首符号集中出现 (空串),那么就需要将“->”左边的Follow集计算出来

第一步:输入的一行表示文法中的终结符号,

第二步:

对于First(TE')={ ( , i }

以此类推可得,剩余空格都为ERROR

示例:输入字符串:i+i*i,该字符串是否为文法G[E]产生的句子

步骤一:

对于第一个要处理的字符” i “,弹出E,放入TE'

注:左边是栈底,右边是栈顶

输入 输出
#E i+i*i# 第一步,没有输出
#E'T i+i*i# E->TE'(第一步输入的输出)

从第二步开始就一定要从上一步输入的输出来写栈,例如:

上一步输入的输出为:E->TE',E'先入栈,T再入栈,反序入栈

步骤二:

接下来还是输入”i“,遇到的是栈顶T,结合分析表得到T->FT',再加上先弹出的”E“,得到栈#E'T'F,

接下来将”F“弹出来,对上输入的”i“,得到"F->i"

输入 输出
#E'T'F “i+i*i#” T->FT'
#E'Ti “i+i*i#” F->i

此时看到指针指向的输入“i”与栈顶”i“相同,就可以将两者弹出,得到

输入 输出
#E'T “+i*i#”

以此类推

输入 输出
#E "+i*i#" T'->ε
#E'T+ "+i*i#" E'->+TE'
#E'T "i*i#"
#E'T'F "i*i#" T->FT'
#E'T'i i*i#” F->i
#E'T'i *i#”
#E'T'F* "*i#" T'->*FT'
#E'T'F "i#"
#E'T'i "i#" F->i
#E'T' "#"
#E' "#" T'->ε
# "#" E'->ε

至此,可以判断此字符串是文法G(E)的句子

目录
相关文章
|
1月前
|
自然语言处理 算法 C++
在C++语言中非修正算法
在C++语言中非修正算法
16 1
|
1月前
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
65 0
|
10月前
编译原理(六) 文法的分类
编译原理(六) 文法的分类
|
1月前
|
安全
单词 remediation 的含义和使用场合
单词 remediation 的含义和使用场合
25 0
|
1月前
单词 backlash 的含义和使用场合介绍
单词 backlash 的含义和使用场合介绍
41 0
|
1月前
|
算法
运算符的妙用以及部分机理解析
运算符的妙用以及部分机理解析
42 0
|
6月前
|
人工智能
实例解释在lingo中使用集合模型
实例解释在lingo中使用集合模型
|
存储 Go C语言
编译原理,C语言实现LR(0)分析(扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成、句子的分析)
注:代码生成的项目集规范簇、ACTION GOTO表的顺序可能和课本、教材、参考答案的顺序不同,但这并不影响分析过程的正确性,毕竟机器是按规律办事的😄
406 0
编译原理,C语言实现LR(0)分析(扩展文法的生成、项目集规范簇的生成、ACTION GOTO表的生成、句子的分析)
|
算法 C++
<<算法很美>>——(四)——深入递归<二>——“逐步生成结果“类问题之非数值型
<<算法很美>>——(四)——深入递归<二>——“逐步生成结果“类问题之非数值型
<<算法很美>>——(四)——深入递归<二>——“逐步生成结果“类问题之非数值型