编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)

简介: 编译原理复习二:Top-Down分析LL(1)文法的判断与LL(1)分析表的构造(附题目与答案 超详细)

需要原卷和答案请点赞关注收藏后评论区留言私信~~~

有问题可以在评论区讨论~~~

一、LL(1)文法的定义

LL(1)文法:从文法的开始符,向下推导,推出句子。

对文法G的句子进行确定的自顶向下语法分析的充分必要条件是,G的任意两个具有相同左部的

产生式A—>α|β 满足下列条件:

(1)如果α、β均不能推导出ε,则 FIRST(α) ∩ FIRST(β) = ∅。

(2)α 和 β 至多有一个能推导出 ε。

(3)如果 β *═> ε,则 FIRST(α) ∩ FOLLOW(A) = ∅。

将满足上述条件的文法称为LL(1)文法。

因为自顶向下的语法处理不了左递归与左公因子,因此要先消除

1:消除左递归

由于自上而下的分析方法不允许文法含有左递归。

因此对于包含直接左递归和间接左递归的文法都要消除左递归。

直接消除左递归比较容易。

例如:

  P->Pa | b

直接消除左递归

  P->bP'

  P'->aP' | ε

2:提左因子

如果不提左因子,当面临两个相同的前缀,不知道选择哪条,必然会产生回溯。为了消除回溯,我们需要提左因子。

二、LL(1)文法判断实战

Consider the following grammar G[S]:

S→(L)|aS’

S’→S|ε

L→SL’

L’→SL’|ε

首先我们要求出各个非终结符的first集和follow集,这个也不复杂,规则如下

计算单个文法符号X的FIRST(X)时,不断应用以下规则,直到没有新的终结符或者是ε加入。

(1)如果X是终结符号,那么FIRST(X)={X}

(2)如果X是非终结符号,且X->ε是一个产生式,那么ε在FIRST(X)中。

(3)如果X是非终结符号,且X->Y1Y2…Yk是产生式

—如果ε在FIRST(Y1), FIRST(Y2),…, FIRST(Y i-1)中,那么FIRST(Yi)中的非ε元素,也在FIRST(X)中。

—如果ε在FIRST(Y1), FIRST(Y2),…, FIRST(Yk)中,那么ε在FIRST(X)中。(PS:注意这里是k,也就是说要所有都能推出 ε 才能说明 ε 在FIRST(X)

follow集求解规则如下

将右端结束标记 $ 放到FOLLOW(S)中,S是开始符号。

按下面的两个规则不断迭代,直到没有新的终结符或者是ε加入。

①如果存在产生式A->αBβ,那么FIRST(β)-{ε}【表示除了ε之外的符号】的符号都在FOLLOW(B)中。

②如果存在产生式A->αB,或者A->αBβ且FIRST(β)包含ε,那么FOLLOW(A)中所有符号都加入到FOLLOW(B)中。

上述文法求解如下

接下来判断是不是LL(1)文法要求出select集,当然求出first和follow集之后求select集就简单多了

select(X->Y),先求first(Y),如果first(Y)存在#∈first(Y)的情况,则再求follow(X),最后求两者的并集即可即可

LL(1)判断方法:如果相同产生式左部的Select集有交集,则该文法不为LL(1)文法

上述文法判断结果如下:S’→S|ε : ε in First(S’), and First(S’) ∩ Follow(S’)≠Φ, So the grammar is not LL(1)

三、LL(1)分析表构造

有了上面求出的first,follow,select集之后构造分析表就简单许多了,可以理解为根据select集构造分析表,结果如下

创作不易 觉得有帮助请点赞关注收藏~~~

相关文章
|
6月前
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
编译原理复习三:Bottom-Up LR(0)自动机构造 SLR(1)分析表与分析器的构造(附题目与答案 超详细)
123 0
|
1月前
|
索引
一个简短的补充------对链表练习题的补充补充
一个简短的补充------对链表练习题的补充补充
15 0
|
2月前
|
SQL Oracle 关系型数据库
CASE WHEN 语句的语法及示例,LeetCode 题目 “确认率” 练习
本文介绍了SQL中CASE语句的两种形式和语法,并通过LeetCode题目“确认率”的SQL查询示例展示了CASE语句在实际问题中的应用,解释了如何使用CASE语句计算特定条件的比率。
|
4月前
|
存储 算法 搜索推荐
|
6月前
|
存储 监控
【初阶解法-数据结构】包含min函数的栈(代码+图示)
【初阶解法-数据结构】包含min函数的栈(代码+图示)
67 0
|
C++
C++ Primer Plus 第五章答案 循环和关系表达式
只有聪明人才能看见的摘要~( ̄▽ ̄~)~
65 0
Leetcode-每日一题1106. 解析布尔表达式(DFS模拟栈)
题目意思很简单让你去判断与或非布尔表达式的结果,我们可以看布尔表达式看成一棵树,需要我们解决的是从最底层的嵌套布尔表达式产生的结果不断向上的结果
101 1
Leetcode-每日一题1106. 解析布尔表达式(DFS模拟栈)
|
机器学习/深度学习 算法 搜索推荐
【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)
【数据结构】时间复杂度(详细解释,例子分析,易错分析,图文并茂)
442 0
|
存储 算法
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)
862 0
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成)
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成) 完整代码
编译原理 实验三 LL(1)分析法(LL1分析表的自动生成) 完整代码
218 0