文档介绍：第四章语法分析
School puter Science & Technology
Harbin Institute of Technology
重点:自顶向下分析的基本思想,预测分析器总体结构,预测分析表的构造,递归下降分析法基本思想,简单算术表达式的递归下降分析器。自底向上分析的基本思想,算符优先分析法的基本思想,简单算符优先分析法。LR 分析器的基本构造思想,LR分析算法,规范句型活前缀及其识别器——DFA,LR(0)分析表的构造,SLR(1)分析表的构造, LR(1)分析表的构造。
难点:FIRST 和 FOLLOW 集的求法,对它们的理解以及在构造LL(1)分析表时的使用。递归子程序法中如何体现分析的结果。求FIRSTOP 和LASTOP,算符优先关系的确定,算符优先分析表的构造,素短语与最左素短语的概念。规范句型活前缀,LR(0)项目集闭包与项目集规范族,它们与句柄识别的关系,活前缀与句柄的关系, LR(1)项目集闭包与项目集规范族。
本章主要内容
语法分析器(Parser)的功能
自上而下分析面临的问题与CFG的改造
自顶向下的分析方法
预测分析器(LL(1)分析器)
语法图和递归子程序法
自底向上分析
算符优先分析法
LR(Left-Right)分析法
回顾一个语句的翻译
参见第14页图1-9
第2章课件的附录——Pascal的词法和语法
回顾句子的形式描述
分析:The grey wolf will eat the goat
〈谓语〉
〈主语〉
〈形容词〉
〈名词〉
〈动词〉
〈直接宾语〉
〈助动词〉
〈句子〉
〈动原〉
〈冠词〉
〈名词〉
The grey wolf will eat the goat
〈冠词〉
句子主语谓语(1)
主语冠词形容词名词(2)
冠词the 形容词 grey
谓语动词直接宾语(5)
动词助动词动词原形(6)
助动词 will 动词原形 eat
直接宾语冠词名词(9)
名词 wolf 名词 goat
回顾句子的组成规则
用上下文无关文法G=(V, T, P, S)描述语言
句子主语谓语
冠词形容词名词谓语
the 形容词名词谓语
the grey名词谓语
the grey wolf 谓语
the grey wolf 动词直接宾语
…...
the grey wolf will eat the goat
回顾句子的派生(推导)-从产生语言的角度 句子的归约-从识别语言的角度
-均根据规则
语法分析方法概览
递归子程序法
自顶向下
预测分析法(LL(1))
算符优先分析法
自底向上
LR(0)、SLR(1)、LR(1)、LALR
Top Down
Bottom Up
文法产生语言
自动机识别语言
从根开始,逐步为某语句构造一棵语法树
相反,将一句子归约为开始符号
问题:解决确定性问题!
假定文法是压缩的:即删除了单位产生式和无用产生式。
语法分析的功能
检查由扫描器输出的单词符号序列是否符合该语言的文法——句子
分析器的输入:Token序列
分析器的输出
分析树
出错处理:定位、续编译
分析方法
自顶向下(递归下降、预测分析)
自底向上(算符优先、LR分析器)
自上而下分析面临的问题 与CFG的改造
一、自上而下的分析
从文法的开始符号出发,寻求所给的输入符号串的一个最左推导。
从树根S开始,构造所给输入符号串的语法树
例:G为:S→xAy A→**|*,输入串:x**y
SxAy
x**y
S
x
A
y
*
*
二、存在问题——回溯
S
xAy x*y
S
x
A
y
*
S
x
A
y
*
*
x * * y
S
xAy
x**y
匹配成功
x * * y
发现不匹配,需要回退
输入串x**y
S→xAy A→**|*