Aione's blog

一起快乐摸鱼吧🐳

  1. 1. First Set
  2. 2. Follow Set

在递归下降 parse 当中,在某些情况下,我们会计算 First Set/ Follow Set。为什么要计算它们呢?

假设我们有如下语法

1
2
3
4
S -> AB
A -> Ca | ε
B -> BaAC | c
C -> b | ε

首先,注意到 B production 是一个左递归,递归下降不能处理左递归的情况。得把 B 变为右递归,我们做如下变化

1
2
B -> cB'
B' -> aACB' | ε

First Set

当我们获得第一个 token 的时候,首先要和 S 进行匹配,但此时 AB 都是非终结符,我们需要一种可以和现有 token 匹配但方法,这就是 First set(first集),我们把 tkn 和 First(A) 进行匹配,完成我们递归下降的过程。理解到了 First 集合的含义,那如何计算 First 集也是信手拈来。

First(A) 就是,按照 A 的推到走下去,可能遇到的第一个终结符。匹配 A 会有哪些终结符。我们的两个集合都是为了匹配 token 服务的。

那么很容易得到计算 First(A) 的方法:

1
First(A) = First(Ca|ε) = {First(C), a, ε} = {b, a, ε}

注意这里,当 C 为 ε 的时候,下一个要匹配的就变成了 a。

Follow Set

Follow Set 是为了解决我们推到过程中遇到一个非终结符,这个非终结符可能为 ε 诞生的,它同样是计算接下来要可能的终结符。

举个例。

1
Follow(A) = {First(C), First(B), First(B')} = {a, b, c, ε}

假设 A 为空,A 后可能为 C, B。

Author : Aione
本文使用 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议
Link to this article : https://aione.me/2020/03/16/firstfllow/

This article was last updated on days ago, and the information described in the article may have changed.