文档详情

编译第章自顶向下的语法分析.pdf

发布:2017-06-18约字共77页下载文档
文本预览下载声明
第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
显示全部
相似文档