《软件技术基础》之《语法分析》
《软件技术基础》之《语法分析》
编译理论中,语法分析是对高级语言的语法单位的结构进行分析。
语法单位结构可以用上下文无关文法来描述,而下推自动机可用于识别上下文无关文法所描述 的语言。
上下文无关文法及下推自动机是语法分析的理论基础 。
引言
对无关文法G=(VT ,VN ,S,P)及符号串w,判断w是否是G的一个合法句子,即:S =>* w。
语法分析的功能
语法分析方法的分类
- 自上(顶)而下的分析方法
- 自下(底)而上的分析方法
自上而下的语法分析为不确定和确定的两类:
- 回溯分析法是不确定的分析方法
- 递归下降分析法和预测分析法属于确定的分析方法
回溯分析法
规则:
- 从文法的开始符号 S 出发;
- 选取 S 的候选式进行推导 ,接着按最左推导进行下去;
- 如果推导失败,再换用其他的候选式(必然导致回溯);
- 若穷尽所有的候选式都失败,则表明w不是G的句子,w存在语法错语。
回溯分析法可能在回溯过程中出现问题,产生回溯的原因有公共左因子、左递归、ε产生式。
公共左因子
公共左因子是指在文法的产生式集合中,某个非终结符的多个候选式具有相同的前缀。
一般地,公共左因子的产生式为:A → αβ1 | αβ2 。
产生回溯的原因:采取试探的方法来分析每一个候选式,分析的过程很可能产生回溯。若所有候选式都没公共左因子,就可以选择惟一匹配的候式,不会产生回溯。
左递归
左递归的形式为:
示例:
ε产生式
示例:
回溯分析法的特点
- 回溯分析法是一种不确定的分析方法;
- 使用试探的方法穷举每一种可能,当分析不成功时则回退到适当位置再重新试探其余可能的推导;
- 穷举所有可能的推导,全都不成功才能确认输入串不是该文法的句子。
回溯分析法的缺陷及解决办法
回溯分析法的缺陷:
- 选择候选式进行推导是盲目的;
- 若文法存在左递归,语法分析可能产生无限循环;
- 引起空间、时间的大量消耗;
- 无法指出语法错误的确切位置。
缺陷的解决办法:
- 回溯分析法低效,在实际的编译器中很少使用;
- 针对产生回溯的原因,提出消除回溯的方法;
- 引进确定的语法分析方法:递归下降分析法和预测分析法。
为了消除回溯,对任何一个非终结符和当前的待匹配符号,期望:
- 要么只有一个侯选式可用
- 要么没有侯选式可用
提取公共左因子
反复进行提取,直到所有产生式均无公共左因子为止。
示例:
左递归消除
直接左递归的消除:
示例:
总结:
间接左递归的消除:
预测分析法
- 将递归下降分析方法进行变化,可以得到更有效的方法——预测分析法;
- 预测分析是一种表驱动的方法,它由下推栈、 预测分析表和控制程序组成;
- 实际上是下推自动机的实现模型;
- 其实质是预测每个候选式的匹配作用,使用预测分析表,根据下推栈的栈顶符号x、当前输入符号a指导推导过程的进行;
- 在输入串后加上#标记。
预测分析表
形式:M[A,a]矩阵,其中A∈VN,a∈VT∪{#}
内容:
- A→α:表示采用A→α匹配输入符号a
- 出错标志(空白):表示A不可能匹配a
目的:记录预测的结论
分析方法
预测分析器的控制程序根据下推栈的栈顶符号x、当前输入符号a决定下一步应采取的动作。
初始:栈中存放栈底符#和开始符S,输入指针指向输入串的第一个符号。
某一时刻:下推栈的栈顶符号x、当前输入符号a
- 若x = a = #,则符号串和栈均以为空,则输入串w是该文法的一个合法的句子,分析过程结束。
- x = a ≠ #,栈顶符号与输入符号匹配,则x出栈,输入指针指向下一个符号,继续匹配。
- 若x为非终结符,则查分析表:
若M[x,a]中存放x→α,则x出栈,将α串逆序压入栈中(α的前缀位于栈顶);
若M[x,a]中为出错标志,则调用出错处理程序error()。
预测分析法的关键是预测分析表,对于不同的上下文无关文法,其预测分析过程是相同的,不同的仅仅是预测分析表的内容。
Q:如何构建一个文法相应的预测分析表?
A:引进FIRST集和FOLLOW集。
FIRST集
定义:
构造方法:
方法总结:
示例:
FOLLOW集
定义:
构造方法:
方法总结:
求 FOLLOW(A) 实际上是考察 A 在产生式右端的每一次出现
预测分析表的构造
构造算法:
示例:
预测分析表的改进:
LL(1)文法
当进行分析时,如果仅利用当前的非终结符和向前查看一个输入符号,就能唯一决定采取什么动作,那个这个文法就是LL(1)文法。
LL = 从左到右扫描,采用最左推导
(k) = 向前看k位