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

编译原理第四章 语法分析 第四章 语法分析§1、概述一. 语法分析器的功能 语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。 二.语法分析方法 自上向下分析法： 从文法的开始符号出发，以给定的符号串为目标，根据文法规则，正向推导出给定符号串的一种方法。 自下向上分析法：从给定的符号串出发，反复使用文法中有关产生式的左部去替换当前符号串中的相应子串，逐步归约成文法开始符号的一种方法。 自上向下分析法：递归下降、LL(1)分析法 自下向上分析法：算符优先、LR分析法 §2、自上而下分析方法一、带回溯的自上而下分析法 基本思想：对任何输入串，试图用一切可能的方法，从文法的开始符号出发，采用最左推导，自上而下为输入串建立一棵语法树。 例如：设有文法：S→xAy A→** | * 输入串：x*y 看匹配过程 二、存在的问题以及解决的方法1.左递归： 当文法为左递归时，会使分析程序进入无限循环之中。 若文法中有非终结符P=Pα (文法左递归) 输入某输入串w=a1a2…an 就有P= Pα= Pα α…如此循环，不会终止 ①消除直接左递归 方法一：引进新的非终结符，改写文法规则式。 P→Pα | β P→ β P′ P′→ α P′ | ε （将文法中的左递归结构变成等价的右递归结构） 例如：算术表达式文法左递归 E→E+T | T E→TE′ T→T*F | F E′→+TE′| ε F→(E) | i T→FT′ T′→*FT′ | ε F→(E) | i 一般情况：有多个直接左递归： P→Pα1 | Pα2 | …| Pαm | β1 | β2 | … | βn 其中，每个α都不等于ε，而每个β都不以P开头，则上式改写为 P→β1 P′| β2 P′ | … | βn P′ P′→α1 P′ | α2 P′ | …| αm P′ | ε 例如： A→Ac | Aad | bd | e 改写为： A→ bd A′ | e A′ A′ →c A′ | ad A′ | ε 方法二：采用扩充的BNF表示法改写文法规则式 用花括号{α}表示符号串α出现0次或多次。即α* 标识符：I→l {l | d } 或 I→l {l | d }7 即将 A→A α | β 改写成 A→β{ α } 中括号[α]表示α是可供选择的符号串。 条件语句→if B then 语句 [else 语句] 使用圆括号，可以在规则中提因子。 U→XY|XW|…|XZ U→X(Y|W|…|Z) 例如：算术表达式文法左递归 E→E+T | T E→T{+T} T→T*F | F T→F{*F} F→(E) | i F→(E) | i ②消除所有左递归的算法 (1)把文法G的所有非终结符按任一顺序排列成 P1 , P2 , … Pn ; (2)执行循环语句： for i:=1 to n do 将规则 Pi→Pj γ改写； {改写方法： Pj→δ1 | δ2 | … δn 则 Pi→δ1γ | δ2γ | … δn γ} 消除关于Pi的直接左递归 end (3)化简由(2)得到的文法。 例如：消除下面文法的左递归。 文法：S→Qc | c Q→Rb | b R→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→abc S′| bc S′ | c S′ S′→abc S′| ε (3)S→abc S′| bc S′ | c S′ Q→Sab | ab | b S′→abc S′| ε R→Sa | a 若排列方法不同，得到的文法也可能不同，但等价 2.回溯问题 问题：如果对同一个非终结符号，有若干个产生式右部 A→ α1 | α2 | …| αn , 选择哪一个产生式匹配呢？ 匹配不好就产生回溯。回溯使语法分析器的动作不确定。分析：要消除回溯，必须使文法具有一定的特性。 例如：S→cAd A→ad | a 输入符号w=cad 分析：要求各规则式右部α1 | α2 | …| αn 所推出的终结首符号的集合两两不相交。 定义：符号串αi 终结首符号的集合： FIRST(αi