数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学什么是预测分析算法，并计算以下文法的FIRST和FOLLOW集？\nS → L = R\nS → R\nL →* R\nL → id\nR → L
解答
FIRST集的计算
- S → L = R
∵ L不能导出ε。根据FIRST规则(4b)
∴ FIRST(S) = {FIRST(L)} (1)
- S → R
∵ R不能导出ε。根据FIRST规则(4b)
∴ FIRST(S) = {FIRST(R)} (2)
- L →* R
应用FIRST规则(3)
FIRST(L) = {*} (3)
- L → id
应用FIRST规则(3)
FIRST(L) = {id} (4)
- R → L
应用FIRST规则(4b)
FIRST(R) = {FIRST(L)} (5)
合并(1)到(5)的结果
FIRST(L) = {*, id}
FIRST(S) = {FIRST(L)}
FIRST(R) = {FIRST(L)}
FIRST(S) = {FIRST(R)}
∴ FIRST(L) = FIRST(S) = FIRST(R) = {*, id}
FOLLOW集的计算
S → L = R
S → R
L →∗ R
L → id
R → L
应用FOLLOW规则(1)
FOLLOW (S) ={$} (1)
S → L = R
应用FOLLOW规则(2)
| S → | ε | L | = R |
| A → | α | B | β |
∵ FIRST(β) = FIRST(= R) = {=}不包含ε。
∴ **FOLLOW规则(2a)**
∴ FOLLOW(L) = {=} (2)
应用FOLLOW规则(3)
| S → | L = | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(S)} (3)
- S → R
由于A → 𝛼 B β与S → R不匹配，因此无法在此产生式上应用规则(2)。
应用规则(3)
| S → | ε | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(S)} (4)
- L →* R
规则(2)不适用于此产生式
应用规则(3)
| L → | * | R |
| A → | α | B |
∴ FOLLOW(R) = {FOLLOW(L)} (5)
- R → L
规则(2)无法应用。
∴ 应用规则(3)
| R → | ε | l |
| A → | α | B |
∴ FOLLOW(L) = {FOLLOW(R)} (6)
合并(1)到(6)的结果
FOLLOW(S) = {$} (1)
FOLLOW(L) = {=} (2)
FOLLOW(R) = {FOLLOW(S)} (3)
FOLLOW(R) = {FOLLOW(S)} (4)
FOLLOW(R) = {FOLLOW(L)} (5)
FOLLOW(L) = {FOLLOW(R)} (6)
∴ FOLLOW(S) = {$}
FOLLOW(L) = FOLLOW(R) = {$, =}
预测分析算法
**输入** − 待解析的字符串和文法的解析表'M'。
**输出** − 栈将变为空，或者给出错误。
方法
While Stack is not empty do
{
Let X be top symbol on Stack
Let a be next input symbol
If X is Terminal or $ then
If X = a then
Pop X form stack & remove a from input
else error ( );
else
If M [X, a] = A → Y1Y2 … … . . Yn
Pop X and Push Yn Yn−1 … . . Y1 onto stack
else error ( );
}
1K+ 次浏览
