编译器-LL(1)-First集与Follow集
First(A) 为A的开始符或者首符号集
求下列右递归语法的First集和集
第一行：Expr → Term Expr '
第二行：Expr ' → + Term Expr ' | - Term Expr ' | ∈
第三行：Term → Term '
第四行：Term ' → * Term ' | / Term ' | ∈
第五行： → ident | num | ( Expr )
First() = {ident num (} // → ident | num | ( Expr ) 以什么开始显而易见
First(Term ') = {* / ∈} //同理看上面Term ‘所在语法行就好了
First(Term) = {ident num ( } //Term是为首 那么又以ident num ( 为首
First(Expr ') = {+ - ∈ }
First(Expr) = {ident num ( } //Expr以Term为首 Term以为首又以ident num ( 为首
//Expr作为起始位置永远包含eof 同时语法最后一行Expr可以跟 )
(Expr) = {eof ) }
//第一行Expr '可以作为Expr结尾 那么Expr ’包含Expr所有集
//第二行右边的Expr '作为Expr '结尾 Expr ‘ 包含 Expr ’自身 所以无用
(Expr ') = {eof ) }
//第一行Term出现在Expr ’前面 所以(Term)包含First(Expr ')
//同时因为Expr ‘可能为∈ 那么说明Term可以作为Expr的最后出现 所以要包含(Expr)
(Term) = {+ - eof ) }
//第三行可以发现Term ‘可以作为Term的最后 所以要包含(Term)
//第四行右边的Term'作为Term'结尾 Term‘ 包含 Term’自身 所以无用
(Term ') = {+ - eof ) }
//第三行后面紧跟Term ‘ 所以包含First(Term ')
//同时第三行Term ‘可以为∈ 那么说明可以作为Term的最后出现 所以要包含(Term)
() = {* / + - eof ) }
⚠️：这些集合中装的都是 即语法中不再需要置换的 eof代表表达式结束符号
first集合非常简单 但是要注意集合
主要是先看语法箭头右边的内容找到需要判断的符号所在位置 如果在符号串尾 那么就包含箭头左边符号的所有集合
S→ A ｜B //需要找(A) 这时(A)就包含(B)
其次如果不在符号串尾 就包含后面紧跟着的符号的first集 但是要注意的是如果紧跟着的符号在first集可以为∈ 那么说明这个紧跟着的符号可以消失 需要继续向后包含下下个符号的first集 直到找到一个符号的first集不包含∈ 如果遍历完后续所有符号的first集都有空 那么就要包含箭头左边的集
S→ACbS |∈ //需要找(A) A后面紧跟C 那么就包含first(C) 但是如果C的first的集中有∈
//那么说明C可以消失 取而代之就是后面的b了 b是一个 肯定不是∈ 所
//以包含b 所以流程就是一直向后遍历找到那么一个first集没有空的就停止
//如果遍历完了也没找到呢？那就说明A后面的东西全可以消失 A的就可以
//是箭头左边S的
A is LL(1) if
for every
:
例2：
S→ A | B
A→ b
B→ BACb | a //这一行是左递归 需要转右递归
C→ AD |∈
D→ BC | bC
转换后：
第一行：S→ A | B
第二行：A→ b
第三行：B→ aB '
第四行：B '→ ACbB ' |∈
第五行：C→ AD |∈
第六行：D→ BC | bC
First(A) = {b}
First(B) = {a}
First(B ') = {b ∈}
First(C) = {b ∈}
First(D) = {a b}
First(S) = {b a}
//找从起始位置开始 eof是起始位置固定的 发现右边没有S 那么就结束了
(S) = {eof}
//我们发现第一行中A作为符号尾 那么就要包含(S)
//同时第四行A后面紧跟着C 所以要包含First(C) 当然要剔除掉∈ 因为C的first中有∈ 我们要继续向 //后遍历 看到了b b显然不是∈ 所以停止
//第五行A后面跟着D 所以要包含first(D) 而且first(D)中没有∈ 所以结束
(A) = {eof b a}
//第一行中符号B在符号串尾部 所以包含(S)
//第六行中B紧跟着C 所以包含first(C) 但是first(C)有∈ 所以继续 但是符号串后面没东西了 这时候
//说明在第六行中B后面的东西可以全部消失 因此D的就是B的 所以包含(D)
(B) = {eof b}
//第四行C后面有个 b
//第六行C作为符号串的结尾 所以因此D的就是C的 所以包含(D)
(C) = {b }
//第五行看出D包含 of C
(D) = {b}
//第三行看出B ‘包含 of B
(B ') = {eof b}
这里我们发现一个有趣的循环依赖关系 B ’是依赖B里的东西 B是依赖D的东西 D是依赖C的东西 C又依赖D的东西
A is LL(1) if
for every
:
我们来检查一下这个适不适合LL1
第一行：S→ A | B开始：
(S→ A) = First(A) = {b}
(S→ B) = First(B) = {a}
(S → A)
(S → B) =
通过
第二行三行不需要检查 因为他们只有一个选择
第四行B '→ ACbB ' |∈
(B ' → ACbB ') = {b}
(B ' → ∈) = (B ') = {eof b}
(B ' → ACbB ')
(B ' → ∈) = {b}
所以出错了 证明LL1不适用
之前我们通过了左递归转成右递归让一个语法适用了LL1 我们可以检查一个特定的语法是不是LL1 就和我们上面所做的过程一样 也就是说一个语法本来不适用LL1 经过一些转换就能适用LL1
是不是说任何语法都可以通过一些转换适用LL1呢？显然不是的 有些语法不管你怎么转换都是不适用LL1 技巧的
而且 并没有一个算法可以直接判断出某个特定的语法是否能成功转换成LL1 你只能不停的尝试 或许某一次会成功 或许不会成功 只有转换完才能去验证 听上去是一个很大的问题 但是实际中对于大部分-free语言 通过经验都是可以转换成LL1适用的
所以说 逻辑并不需要完美 实际中可以通过经验最大化减小带来的问题
比LL(1)更通用的一个语法是LR(1)
其中最中央的是 ， 甚至不需要一个语法去约束 只用有限自动机就可以去表达了
这一圈一圈往外走的语言的语法会越来越复杂 也越来越难以去约束表达 可以想象 最难去约束表达的一定是人类日常的自然语言 比如中文 英语 因为很多时候人说的自然语言都不会按照语法来 甚至加入了感情和联想在其中 导致了用一套死板的语法或者说代码去约束几乎是不可能的 这也是当代人工智能本质上无法逾越的鸿沟
比如下面的两句话：
缘起 我在人群中看见你
缘落 我看见你 在人群中
我相信cpu烧冒烟了也无法体会其中的意境
