编译原理第4章 语法分析.ppt

编译原理第四章语法分析 2020 1 25 1 第四章语法分析 编译原理第四章语法分析 2020 1 25 2 第四章语法分析 1 概述一 语法分析器的功能 编译原理第四章语法分析 2020 1 25 3 语法分析 在词法分析的基础上 根据语法规则 从单词符号串中识别出各种语法成分 同时进行语法检查 检查各种语法成分在语法结构上的正确性 编译原理第四章语法分析 2020 1 25 4 二 语法分析方法 自上向下分析法 从文法的开始符号出发 以给定的符号串为目标 根据文法规则 正向推导出给定符号串的一种方法 自下向上分析法 从给定的符号串出发 反复使用文法中有关产生式的左部去替换当前符号串中的相应子串 逐步归约成文法开始符号的一种方法 自上向下分析法 递归下降 LL 1 分析法自下向上分析法 算符优先 LR分析法 编译原理第四章语法分析 2020 1 25 5 2 自上而下分析方法一 带回溯的自上而下分析法 基本思想 对任何输入串 试图用一切可能的方法 从文法的开始符号出发 采用最左推导 自上而下为输入串建立一棵语法树 例如 设有文法 S xAyA 输入串 x y看匹配过程 S A x y S A x y S A x y 编译原理第四章语法分析 2020 1 25 6 二 存在的问题以及解决的方法1 左递归 当文法为左递归时 会使分析程序进入无限循环之中 若文法中有非终结符P P 文法左递归 输入某输入串w a1a2 an就有P P P 如此循环 不会终止 编译原理第四章语法分析 2020 1 25 7 消除直接左递归 方法一 引进新的非终结符 改写文法规则式 P P P P P P 将文法中的左递归结构变成等价的右递归结构 例如 算术表达式文法左递归E E T TE TE T T F FE TE F E iT FT T FT F E i 编译原理第四章语法分析 2020 1 25 8 一般情况 有多个直接左递归 P P 1 P 2 P m 1 2 n其中 每个 都不等于 而每个 都不以P开头 则上式改写为P 1P 2P nP P 1P 2P mP 例如 A Ac Aad bd e改写为 A bdA eA A cA adA 编译原理第四章语法分析 2020 1 25 9 方法二 采用扩充的BNF表示法改写文法规则式用花括号 表示符号串 出现0次或多次 即 标识符 I l l d 或I l l d 7即将A A 改写成A 中括号 表示 是可供选择的符号串 ifBthen else 使用圆括号 可以在规则中提因子 U XY XW XZU X Y W Z 例如 算术表达式文法左递归E E T TE T T T T F FT F F F E iF E i 编译原理第四章语法分析 2020 1 25 10 消除所有左递归的算法 1 把文法G的所有非终结符按任一顺序排列成P1 P2 Pn 2 执行循环语句 fori 1tondo将规则Pi Pj 改写 改写方法 Pj 1 2 n则Pi 1 2 n 消除关于Pi的直接左递归end 3 化简由 2 得到的文法 编译原理第四章语法分析 2020 1 25 11 例如 消除下面文法的左递归 文法 S Qc cQ Rb bR Sa a 1 排列 R Q S 2 对R 没有直接左递归 不执行内循环对Q 将R代入Q变为Q Sab ab b 也没有直接左递归 不执行内循环 对S 将Q代入S变为S Sabc abc bc c消除S的直接左递归 得下面文法 S abcS bcS cS S abcS 3 S abcS bcS cS Q Sab ab bS abcS R Sa a若排列方法不同 得到的文法也可能不同 但等价 编译原理第四章语法分析 2020 1 25 12 2 回溯问题 问题 如果对同一个非终结符号 有若干个产生式右部A 1 2 n 选择哪一个产生式匹配呢 匹配不好就产生回溯 回溯使语法分析器的动作不确定 分析 要消除回溯 必须使文法具有一定的特性 例如 S cAdA ad a输入符号w cad分析 要求各规则式右部 1 2 n所推出的终结首符号的集合两两不相交 定义 符号串 i终结首符号的集合 FIRST i i a VT 编译原理第四章语法分析 2020 1 25 13 条件一 对文法中每一个非终结符A 如有规则 A 1 2 n则下面条件成立FIRST i FIRST j i j 上例中 FIRST ab FIRST a a a a 改写方法 提取公共左因子A 1 2 n 1 2 m则 A A 1 2 mA 1 2 n例如 ifEthenS1elseS2 ifEthenS1改写为 ifEthenS1B B elseS2 编译原理第四章语法分析 2020 1 25 14 问题 若满足条件FIRST i FIRST j 是否完全避免回溯呢 上例中 S cAdA ad a改写为 S cAdA aA A d 输入符号w cad匹配d可能失败 差条件定义 非终结符号A的后继符号的集合 FOLLOW A a S Aa VT 当S A 则规定 FOLLOW A 为界符 条件二 若 i 时 FIRST i FOLLOW A 上例中 FIRST d FOLLOW A d 产生回溯 编译原理第四章语法分析 2020 1 25 15 小结 构造不带回溯的自上而下分析的条件是 1 文法不含左递归2 对文法中每一个非终结符A 如有规则 A 1 2 n则下面条件成立FIRST i FIRST j i j 3 对文法中每一个非终结符A 若它的某个产生式首符集包含 时 则 FIRST A FOLLOW A 满足以上条件的文法称为LL 1 文法 对于一个LL 1 文法 可以构造无回溯的自上而下分析 编译原理第四章语法分析 2020 1 25 16 FIRST 的求法 A 是文法G的产生式 若 a 且a是终结符 则FIRST a 若 X 且X是非终结符 且X b 则把终结符b加入到FIRST 中 若 X1X2 Xk 且X1 X2 Xk都是非终结符 而X1X2 Xi 则把FIRST Xi 1Xi 2 Xk 加入到FIRST 中 编译原理第四章语法分析 2020 1 25 17 FOLLOW A 的求法 其中A是任一非终结符 若有产生式B Aa 且a是终结符 则把a加入到FOLLOW A 中 若有产生式B AX 且X是非终结符 则把FIRST X 加入到FOLLOW A 中 若有产生式B A 或B A 但 则把FOLLOW B 加入到FOLLOW A 中 若A是文法的开始符号 则把结束符 加入到FOLLOW A 中 编译原理第四章语法分析 2020 1 25 18 例 已知文法G S S aSb PP bPc bQcQ Qa a消除文法左递归后是不是LL 1 文法 解 消除文法左递归得到 S aSb PP bPc bQcQ aQ Q aQ 提取公共左因子后得文法 S aSb PP bP P Pc QcQ aQ Q aQ 计算FIRST和FOLLOW集合 FIRST S a b FIRST P b FIRST P a b FIRST Q a FIRST Q a Follow S b Follow P b c Follow P b c Follow Q c Follow Q c 是LL 1 文法 编译原理第四章语法分析 2020 1 25 19 例 将文法改写成LL 1 文法 S S aP aP aPP aP a解 消除文法左递归 提取公共左因子得到 S aPS aPS S aPS P aP P P 计算每个非终结符的FIRST和FOLLOW集合 FIRST S a Follow S FIRST S Follow S FIRST P Follow P FIRST P Follow P 以上文法是LL 1 文法 编译原理第四章语法分析 2020 1 25 20 已知文法 G S S AB PQxA xy mB bCC bC P pP Q q如果要保持文法为LL 1 文法 下列哪几个产生式不能加入到该文法中 为什么 1 S bC 2 A bC 3 B 4 Q 编译原理第四章语法分析 2020 1 25 21 解 1 加入S bC后文法为 S AB PQx bCA xy mB bCC bC P pP Q q对S First AB First PQx First bC x m p q b 对A First xy First m x m 对C First bC Follow C b 对P First pP Follow P p q 加入S bC后文法是LL 1 文法 编译原理第四章语法分析 2020 1 25 22 2 加入A bC后文法为 S AB PQxA xy m bCB bCC bC P pP Q q对A First xy First m First bC x m b 对C first bC follow C b b b 不是LL 1 文法 3 加入B 后文法为 S AB PQxA xy mB bC C bC P pP Q q对B First bC Follow B b 是LL 1 文法 编译原理第四章语法分析 2020 1 25 23 4 加入Q 后文法为 S AB PQxA xy mB bCC bC P pP Q q First S x m p q Follow S First A x m Follow A b First B b Follow B First C b Follow C First P p Follow P q x First Q q Follow Q x 对S First AB First PQx x m p q x x 加入Q 后文法不是LL 1 文法 编译原理第四章语法分析 2020 1 25 24 定义规则的选择集合SELECT 设A 是文法G的任一条规则 其中A VN VN VT 定义 SELECT A FIRST FIRST FOLLOW A 定义SELECT集合 编译原理第四章语法分析 2020 1 25 25 例设有文法G A A aB d B bBA SELECT A aB FIRST aB a SELECT A d FIRST d d 编译原理第四章语法分析 2020 1 25 26 b SELECT B bBA FIRST bBA d a FOLLOW B SELECT B FIRST A aB d B bBA 编译原理第四章语法分析 2020 1 25 27 LL 1 文法的判断条件 LL 1 文法定义 一个上下文无关文法G是LL 1 文法 当且仅当对G中每个非终结符A的任何两个不同的规则A 满足 SELECT A SELECT A 其中 中至多只有一个能推出 串 编译原理第四章语法分析 2020 1 25 28 例1设有文法G S S aAbA de d SELECT A de FIRST de d SELECT A d FIRST d d SELECT A de SELECT A d 由LL 1 文法定义可知 该文法不是LL 1 文法 因此对输入串不能进行确定的自上而下分析 编译原理第四章语法分析 2020 1 25 29 例2设有文法G A A aB dB bBA 则SELECT A aB FIRST aB a SELECT A d FIRST d d SELECT B bBA FIRST bBA b SELECT B FIRST FOLLOW B a d a d 编译原理第四章语法分析 2020 1 25 30 所以SELECT A aB SELECT A d SELECT B bBA SELECT B 由定义可知 G A 是LL 1 文法 对任何输入串W可进行确定的分析 编译原理第四章语法分析 2020 1 25 31 例3设有文法G S S aABA bB dA B a e SELECT A bB FIRST bB b SELECT A dA FIRST dA d SELECT A FIRST FOLLOW A a e a e 试判断该文法是否LL 1 文法 编译原理第四章语法分析 2020 1 25 32 SELECT B a FIRST a a SELECT B e FIRST e e SELECT A bB SELECT A dA SELECT A bB SELECT A SELECT A dA SELECT A SELECT B a SELECT B e S aABA bB dA B a e 该文法为LL 1 文法 编译原理第四章语法分析 2020 1 25 33 三 递归下降分析法 条件 要求文法为LL 1 文法1基本思想 对每一个非终结符 构造相应的递归子程序 以完成该非终结符所对应语法成分的分析和识别任务 编译原理第四章语法分析 2020 1 25 34 2方法 为每一个非终结符 构造相应的递归过程 过程的名字表示规则左部的非终结符 过程体按规则右部符号串的顺序编写 对于产生式 U x1 x2 xn则编写ifchinFIRST x1 thenp x1 elseifchinFIRST x2 thenp x2 elseerror 对于符号串x y1y2 yn p x 的含义为 beginp y1 p y2 p yn end如果yi VT则ifch yithenread ch elseerror 对于U 则ifch Follow U thenreturnelseerror 编译原理第四章语法分析 2020 1 25 35 举例 设有文法G E E T TT T F FF E i试构造一个识别该文法句子的递归下降分析程序 消除文法左递归E TE E TE T FT T FT F E i 改写后的文法是否为LL 1 文法 对E First TE Follow E 对T First FT Follow T 对F First i First E i 是LL 1 文法 编译原理第四章语法分析 2020 1 25 36 构造递归下降分析程序 定义 advance 读下一个单词并放入全程变量sym中error 错误诊断处理程序编程如下 主 advance E procedureE beginT E end procedureE beginifsym thenbeginadvance T E end elseifsym follow E thenreturnelseerrorEnd 编译原理第四章语法分析 2020 1 25 37 ProcedureT BeginF T End ProcedureT Beginifsym thenbeginadvance F T endelseifsymnotin thenerrorelsereturnEnd ProcedureFBeginifsym i thenadvance elseifsym thenbeginadvance E ifsym thenadvance elseerror endelseerror End 编译原理第四章语法分析 2020 1 25 38 若改写文法用BNF范式表示 E T T T F F F E i则编程如下 ProcedureE BeginT whilesym dobeginadvance T endend ProcedureT BeginF whilesym dobeginadvance F endend 编译原理第四章语法分析 2020 1 25 39 例如 编译原理第四章语法分析 2020 1 25 40 编译原理第四章语法分析 2020 1 25 41 编译原理第四章语法分析 2020 1 25 42 PROCEDUREBEGINIFSYM i THENREADWORDELSEERROREND 编译原理第四章语法分析 2020 1 25 43 PROCEDUREBEGIN 编译原理第四章语法分析 2020 1 25 44 编译原理第四章语法分析 2020 1 25 45 四 LL 1 分析法 预测分析法 条件 要求文法为LL 1 文法L 从左到右进行分析L 每次进行最左推导 1 向前查看一个符号 编译原理第四章语法分析 2020 1 25 46 1 LL 1 分析器的逻辑结构 总控程序 LL 1 分析表 T j S k j 分析栈 编译原理第四章语法分析 2020 1 25 47 2 分析表的构造方法 输入 文法G输出 分析表M方法 对文法中每一个产生式A 按照下述规则确定M中各个元素 对于FIRST 中的每一个终结符a置为M A a A 若空串 FIRST 则对Follow A 中的每一个终结符b置为M A b A 把M中未定义的元素置为error 编译原理第四章语法分析 2020 1 25 48 例如 已知文法G E 试构造分析表 E TE E TE T FT T FT F E i 对E TE 产生式 First TE i 置M E E TE M E i E TE 编译原理第四章语法分析 2020 1 25 49 对产生式E TE First TE 置M E E TE Follow E 置M E E M E E 对产生式T FT First FT i 置M T T FT M T i T FT 对产生式T FT First FT 置M T T FT Follow T 置M T T M T T M T T 对产生式F E iFirst E 置M F F E First i i 置M F i F i 编译原理第四章语法分析 2020 1 25 50 3 总控程序框图 J 1 k 1 s k k k 1 Z s k S k VT S k T j S k 查M S k T j X y1y2 yn S k T j K k 1 J j 1 error N N N y y y error stop y N 将y1y2 yn逆序推进栈中若y1y2 yn 则k k 1 error N y 编译原理第四章语法分析 2020 1 25 51 4 分析过程 例如 已知文法G 请利用LL