⑴ 消除左递归和回溯； ⑵ 构造非终结符的FIRST和FOLLOW集合； ⑶ 构造预测分析表 (4) 给出句子a*a+a*a的LL(1)分析过程
（格式：栈，输入缓冲区，动作）
解：⑴ S→aFS'|+aFS' S'→+aFS'|ε F→*aF' F'→F|ε
习题举例
⑵ FIRST(S)={a,+} FOLLOW(S)={#} FIRST(S')={+,ε} FOLLOW(S')={#} FIRST(F)={*} FOLLOW(F)={+,#} FIRST(F')={*,ε) FOLLOW(F')={+,#}
习题举例
已知文法G=({b,e,f},{S’,S,R,T},S’,P) 其中P: (0) S’→S (1) S→bRST (2) S→bR (3) R→e (4) T→f
构造 文法的LR（0）项目集规范族 构造 识别活前缀的DFA 这个文法哪类LR文法并说明理由
S’→·S S→·bRST S S→·bR
三者之间的相互转化 自Байду номын сангаас机的确定化、化简
复习要点
语法分析-自上而下分析
递归下降分析法 LL（1）分析法
消除左递归、提左因子、FIRST集、FOLLOW集 P73:LL(1)文法的判定条件 LL(1)分析器的构造：P76-79
复习要点
语法分析-自下而上分析
移进-归约、规范规约、短语、直接短语、 句柄
复习要点
第1章 引论
编译程序、解释程序 编译程序的5个阶段 遍 编译前端与后端
复习要点
高级语言极其语法描述（P2.3节）
上下文无关文法、最左推导、最右推导、句 子、句型、语言、语法分析树、二义性文、 形式语言分类
复习要点
词法分析
正规式、正规集、有限自动机（确定的有限 自动机、非确定的有限自动机）
动作
S2 S4 r3 S2 S4 r3 r2 S7 r4 r1 acc
算符优先分析
算符文法、素短语、最左素短语
LR分析法
LR(0)、SLR
LR分析法考核要点
构造文法G[S]的LR(0)项目集规范族及相 应的DFA。
构造文法的LR(0)或SLR分析表 对于输入串xxxxxxx，给出LR(0)或SLR分
析器所作出的动作。
复习要点
属性文法和语法制导翻译
属性文法、继承属性、综合属性、S-属性文 法、L-属性文法、翻译模式
r1
r4
r4
goto
S
R
T
1
3 5
6
状态栈 0 02 024 023 0232 02324 02323 0235 02357 02356 01
符号栈 # #b #be #bR #bRb #bRbe #bRbR #bRS #bRSf #bRST #S
输入缓冲区 bebef# ebef# bef# bef# ef# f# f# f# # # #
S-属性文法的自下而上计算
复习要点
语义分析和中间代码产生
中间语言形式：后缀式、三地址代码（主要 是四元式）
控制语句的翻译
习题举例
字母表{0,1,2,3} 对给定正则表达式 0*（1 | 23）（0 | 12）0（1 | 13）* 构造与之等价的NFA M。
习题举例
设文法G(S): S→S+aF|aF|+aF F→*aF|*a
习题举例
-
a
+
*
#
S
S→aFS' S→+aFS'
-
-
S'
-
S'→+aFS'
-
S'→ε
F
-
-
F→*aF'
-
F'
-
F'→ε
F'→F F'→ε
习题举例
文法G[S]的产生式为： SS + A | A AA * S |B Ba |（S）
给出（a+a）*a的最左推导、最右推导及相应的分析 树；
列出句型B + A * B的所有短语、直接短语和句柄。
I0
S’→ S· I1
b
S→b·RST R
R→·e
S→b·R
I2
b
e
R→e· I4
S→bR·ST S→bR· S→·bRST S S→·bR
I3
S→bRS·T T T→·f
I5
S→bRST· I6
f
T→f· I7
状态
b
0
S2
1
2
3
S2
4
r3
5
6
7
action
e
f
#
acc
S4
r2
r2
r3
r3
S7
r1