编译第章自顶向下的语法分析.pdf
文本预览下载声明
第5章 自顶向下的语法分析
词法分析将字符形式的源程序中的各个单词识别出来,形成单词的机内表示形式,但是,
这些单词串如何构成更大的语法成分——语句,就要由语法分析来完成。语法分析(Syntax
analysis )是编译器的核心部分。它的主要任务是“组词成句”,即在词法分析识别出的单词
序列的基础上,根据语言的语法产生式,识别出各种类型的句子,如“语句”、“程序”等,
并给出这些句子的语法结构。
完成语法分析任务的程序称为语法分析器 (或语法分析程序)。语法分析器在编译器中
的位置与作用如图 5.1 所示。
图 5.1 语法分析器在编译器中的位置与作用
语法分析的关键是句子识别问题。给定一串单词ω (即文法的终极符号串),可以利用
∗
推导来判断,看它是否为该文法产生的一个句子,即看是否存在一个推导过程S ⇒ω。如果
存在这样的推导过程,则ω是合法的句子,否则,ω不是一个合法的句子。
一个推导过程也可以描述为一棵语法树1,因此,寻找推导过程也就等同于构造相应的
语法树。所以,从语法树的角度来说,语法分析的过程就是为一个句子ω构建它的语法树的
过程。并且,为句子ω所构建的语法树也就是句子ω的语法结构的描述。
语法分析的方法很多,按照建立语法树的方向的不同,通常将语法分析分成两大类:
1 实际上,“树”这种结构既适用于语法分析,也适用于词法分析,只是词法分析主要用自动机识别,用“树”
有点“大材小用”。
5-1
(1)自顶向下分析法:从树的根部朝向叶子的方向构建语法树;自顶向下分析法包括
确定性分析和不确定性分析。
(2)自底向上分析法:从树的叶子朝向根部的方向构建语法树;自底向上分析法 1包
括算符优先分析和LR分析。
自顶向下(top-down )分析法又称为面向目标的分析法,它的基本思想是从文法的开始
符号出发,采用最左推导,试图一步一步地推导出与输入的符号串完全匹配的句子。
从构造语法树的角度看,就是以文法的开始符号为语法树的根部,试图自上而下地为输
入符号串构造一棵语法树。
如果能够构造一棵这样的语法树:它的叶子节点从左向右排列恰好就是输入符号串,则
输入符号串就是文法的句子,而这个语法树就是句子的语法结构。反之,输入符号串就不是
文法的句子。
这种分析过程实质是一种试探过程,是反复使用不同产生式匹配输入符号串的过程。
例 5.1 对于文法
[ ]
G S : S ⟶aAB
A ⟶bA | c
B ⟶dBe | de
输入串ω= abbcde的最左推导过程如下:
S ⇒aAB ⇒abAB ⇒abbAB ⇒abbcB ⇒abbcde
[ ]
所以,输入串ω= abbcde是该文法G S 的句子。
下面,从建立语法树的角度来看句子的推导过程。
为了自顶向下地构造输入串ω= abbcde的语法树,首先用文法的开始符号S产生根节点
S,再根据产生式自顶向下地生长这棵语法树。语法树的建立过程如图 5.2 所示:
S S S S S
S→aAB A→bA A→bA A→c B→de
(1) a A B (2) a A B (3) a A B (4) a A B (5) a A B
b A b A b A b A d e
b A b A
显示全部