语法分析
核心问题是识别，解析上下文无关文法G = (V ， T ， P， S )
两种实现途径
-
自顶向下（从S到句子）
-
自底向上
自顶向下的语法分析
问题是容易出现回溯
两类非确定性
-
非终结符的的选择是非确定的（这个简单，最左产生和原有文法等价）
-
仅有产生式选择是非确定的
解决产生式选择的不确定性：lookahead
唯一目的就是避免回溯，所以要看得足够多
一个不太好的例子
考虑下列文法识别 $ba^n$ 的分析过程, S → Sa ,S → b
看到下一个是a,然后选择S → Sa是不够的,因为a后可能还有a,要确定还要不要a只能继续向后看,所以无论向前看多远,这个句子后面总可能还是有a,所以还是不能确定.
这启发我们lookahead的表现需要依赖于文法
LL(1)文法
文法 G 是 LL（1）文法，当且仅当下面的条件成立：
对于每一个生成符,其所有产生式的预测集合不相交
First集合与Follow集合,$G =（V_T， V_N， P， S）$ 是上下文无关文法
First集合
first集合是求下述符号可能产生的首终结符
first集合针对的是在LL推导中可能出现的三类符号的并集
-
终结符与$\epsilon$
-
生成符
-
文法右边的符号串
计算方法
-
1类集合元素为本身,剩下的是空集
-
如果生成符能生成$\epsilon$,则其集合加入$\epsilon$
-
对于3类符号串,首先加入串首符号对应集合元素
-
从左向右分析,如果first集合中有$\epsilon$,则集合并上此处符号的后继符号的first集合
-
如果停止,则3类符号串first集中删去$\epsilon$
-
如果生成符能生成3,则集合取并
-
重复3-6,直到所有集合不变
Follow集合
follow集合是在求$V_N$的直接后继终结符
计算 Follow 集合
-
置 Follow(S) =