【北航编译原理笔记】1. 基础知识 【北航编译原理笔记】2. 词法分析 【北航编译原理笔记】3. 语法分析 【北航编译原理笔记】4. 语义分析与符号表
任务：根据语法规则 （即语言的文法），分析并识别出各种语法成分，如表达式、各种说明、各种语句、过程、函数等，并进行语法正确性检查.
与词法分析的区别:
词法分析(3型, 正则文法), 语法分析(2型, 上下文无关文法)字母表区别: 词法(字符串), 语法(符号串)自顶向下分析: 推导(Derivations) 自底向上分析: 规约(Reductions)
自底向上: 主要问题:
句柄识别问题: 算符优先分析法自顶向下: 主要问题:
二义性问题:
用优先级层次定义文法
左递归问题(导致死循环):
U : : = x y ∣ x w ∣ . . . ∣ x y U ::= xy\ |\ xw\ |...|\ xy U::=xy ∣ xw ∣...∣ xy改写为 U : : = x ( y ∣ w ∣ . . . ∣ z ) U::=x(y\ |\ w\ |...|\ z) U::=x(y ∣ w ∣...∣ z).
U : : = x ∣ x y U ::= x\ |\ xy U::=x ∣ xy改写为 U : : = x ( y ∣ ε ) U::=x(y\ |\ \varepsilon) U::=x(y ∣ ε).
U : : = x ∣ y ∣ . . . ∣ z ∣ U v U ::= x\ |\ y\ |...|\ z\ |\ Uv U::=x ∣ y ∣...∣ z ∣ Uv改写为 U : : = x ( x ∣ y ∣ . . . ∣ z ) { v } U::=x(x\ |\ y\ |...|\ z)\{v\} U::=x(x ∣ y ∣...∣ z){v}.
回溯问题(导致费时)
保证 F I R S T ( a i ) ⋂ F I R S T ( a j ) = ϕ ( i ≠ j ) FIRST(a_i) \bigcap FIRST(a_j) = \phi (i \neq j) FIRST(ai)⋂FIRST(aj)=ϕ(i=j).
相交则提取左因子
必要时,可以超前扫描,预读下一个字符.
递归子程序法(递归下降分析法): 对每一个非终结符都建立一个子程序
