S Ap cAp ccAp ccap
5
开始符号集
FIRST (A) c | A cB,c VT , A, B V
FIRST(A)就是A开头的终结符， 直观的说就是A的开头字母
注意：First集合不仅仅针对非终 结符。
Nullable：可致空的
6
例子 S aA | d
A bAS |
如果输入串是符合文法的，一定能够推出 确定分析对文法有一定限制，但是简单、直观。 不确定分析是一种穷举的试探方法，效率低，
代价高
3
确定分析的思想
文法 S→pA|qB A→cAd|a B→dB|b
试分析串 pccadd
S pA pccadd
pcAd
pccAdd4例子来自S→Ap,S →Bq, A →a,A →cA B →b,B →dB 分析串ccap有如下结论：
? S aA abAS abS abd
7
Follow集
FOLLOW
(
A)
c | S A
VT
,
V
,
,且c A VN
FIRST
(
),
FOLLOW(A)实际上就是FIRST(B)
FOLLOW(A)就是紧跟在A后面的能够 出现的字母(合法的句型)
假设有S→aA的形式，那么规定#属 于FOLLOW(A)，其代表结束符，可以 想象c语言中的’/0’
First集合针对串（当然也可以针对 单个非终结符）
Follow集合针对单个非终结符
10
定理
一个CFG是LL(1)的充要条件是： 对每个非终结符A的不同产生式，满
足：Select A I Select A
11
程序中错误的级别
lexical，譬如拼错了关键字 syntactic，譬如括号没有成对 semantic，譬如操作数与操作符不匹配 logical，譬如无限的递归调用
12
引用的统计数据
60％的程序在语法和语义上是正确的 存在错误的语句，有80％只有一个错误，
13％有两个 大部分错误都是极小的错误
13
继续引用
60％是标点符号错误 20％是操作符和操作数的错误 15％是关键字错误 剩下5％是其他
14
课后作业
教材第5章第1题（1）
15
8
LL(1)文法
第一个L表示：输入是从左到右 第二个L表示：最左推导 1表示：向右查看一个符号就可以决定应
用哪个产生式 对于LL(1)文法就可以使用确定的自顶向
下的分析方法
9
SELECT集
SELECT
A
FIRST
FIRST
U
FOLLOW
A
if if
SELECT集针对单个产生式而言
第5章 自顶向下语法分析方法
语法分析
语法分析的作用
判断词法分析给出的单词符号序列是 否是给定文法的正确句子
语法分析的方法
自顶向下分析
确定分析 不确定分析
算符优先分析 自底向上分析
LR分析
2
自顶向下分析
也称作面向目标的分析方法，也就是从文法的 开始符号出发，试图推出与输入串完全匹配的 句子。