编译原理第四章.ppt

1
编译原理
主讲教师:雷向东
2
第四章语法分析——自上而下分析
语法分析器的功能
语法分析器的任务是在词法分析识别出单词符号串的基础上,分析并判定程序的结构是否符合语法规则。
语法分析方法可分为两类:一类是自上而下分析法,另一类是自下而上分析法。
语言的语法结构是用上下文无关文法描述的。因此,语法分析器的工作本质上就是按文法的产生式,识别输入符号串是否为一个句子。这里所说的输入串是指由单词符号(文法的终结符)组成的有限序列。对一个文法,当给你一串(终结)符号时,怎样知道它是不是该文法的一个句子(“程序”)呢?这就要判断,看是否能从文法的开始符号出发推导出这个输入串。或者,从概念上讲,就是要建立一棵与输入串相匹配的语法分析树。
4
自上而下分析面临的问题
自上而下分析法就是从文法的开始符号出发, 向下推导,推出句子。
假设文法G[S]
S→xAy A→** A→*识别输入串α=x*y是否该文法的句子。
5
S S S
x A y x A y
* *
推导过程:S  xAy  x**y。用非终结符A的第一个候选告失败。应该回溯,使用A的其它候选。
自上而下构造α的语法树。
(a)
(b)
(c)
6
为了回溯,把A的第一个候选所发展的子树注销掉,试探A的第二个候选。
S
x A y
*
匹配成功,证明了α是一个句子。
*
7
上述自上而下分析面临的问题:
文法的左递归性质问题
一个文法是含有左递归的, 如果存在非终结符P
P P α
含有左递归的文法将使上述的自上而下分析过程陷入无
限循环。例如文法规则:A →Aa
A
A a
A a
…
递归展开。
+
8
回溯问题
做了很多语义工作,最后必须回头,推倒重来,既麻烦又费时间。
虚假匹配现象
当最终报告分析不成功,难于知道输入串中出错的确切位置。
自上而下分析方法不允许文法含有任何左递归。为构造不带回溯的自上而下分析算法,首先要消除文法的左递归法,并找出克服回溯的充分必要条件。
下面将讨论消除文法左递归和克服回溯的方法。
LL(1) 分析法
10
消除直接左递归
假设关于非终结符P的规则为
P→Pα|β
其中, β不以P打头。把P的规则改写为如下非直接左递归形式:
P→βP ’
P→αP ’|
这种形式和原来的形式是等价的,也就是说,从P推出的符号串是相同的。它们推出的符号串都是{β,βα,βαα,βααα,…}。