编译原理ch4.pdfVIP

第四章 语法分析 • §4.1 概述 • §4.1.1 语法分析方法 语法（句法）分析的任务是根据程序设计语 言的语法规定，对输入的单词流进行分析， 判定是否构成了合法的句子，并尽可能多的 找出语法错误。 • 句法分析方法可分两大类： 6/5/14 华东师大信息学院计算机科学技术系 1 句法分析⽅法分类 1. 自顶向下（Top-Down)分析方法 以文法的开始符号为分析树的根，向下逐步构造 分析树，每次以树中最左非终结符为子树的根向 下形成新的子树（最左推导），直至分析树的叶 结点形成输入串。此时称输入串是合法的句子， 否则输入串非法（报错）。 2. 自底向上（Bottom-Up)分析方法 从输入串出发，向上逐步构造分析树，每次寻找 当前句型的句柄（或最左素短语）进行归约（最 右推导的逆），直至归约出文法的开始符号。此 时称输入串是合法的句子，否则输入串非法（报 错）。 6/5/14 华东师大信息学院计算机科学技术系 2 下推⾃动机（PDA ）与2型⽂法 • §4.1.2下推自动机(Push-Down Automation)与2型文法 • 3型文法及其数学模型FA 由于其本身的局限性不能胜任 句法分析。 例如：判定表达式中的括号配对问题： n n L={a b |n≥0} • 引入2型文法和PDA A →α α ∈ (V ∪V )* N T 在FA 中增加一个下推栈并要求控制器能控制栈的操 作，这就是PDA 。 6/5/14 华东师大信息学院计算机科学技术系 3 下推⾃动机 • 定义1：非确定的PDA M M ＝（V ，Q，∑，δ，q ，Z ，Q ），其中，V 是 T 0 0 F T 有限的输入字母表； Q是有 限的状态集合； ∑是有限的栈 字母表； q 是初始状态， 0 q ∈Q ； Z ∈∑，是栈底符号 0 0 ； δ是一个从Q ×∑ × （VT ∪{ε} ） 到Q ×∑*的幂集上 的映射； Q 是最终状态集， F Q ⊆Q 。 F 6/5/14 华东师大信息学院计算机科学技术系 4 下推⾃动机 • 下推自动机有两类