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

第四章语法分析第四章语法分析§1、概述一.语法分析器的功能语法分析：在词法分析的基础上，根据语法规则，从单词符号串中识别出各种语法成分，同时进行语法检查，检查各种语法成分在语法结构上的正确性。
二.语法分析方法§2、自上而下分析方法一、带回溯的自上而下分析法二、存在的问题以及解决的方法1.左递归：①消除直接左递归一般情况：有多个直接左递归：
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′|ε方法二：采用扩充的BNF表示法改写文法规则式
用花括号{α}表示符号串α出现0次或多次。即α*
标识符：I→l{l|d} 或 I→l{l|d}7
即将 A→Aα|β 改写成 A→β{α}
中括号[α]表示α是可供选择的符号串。
<条件语句>→ifBthen<语句>[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②消除所有左递归的算法例如：消除下面文法的左递归。
文法：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→abcS′|bcS′|cS′
S′→abcS′|ε (3)S→abcS′|bcS′|cS′
Q→Sab|ab|b S′→abcS′|ε
R→Sa|a
若排列方法不同，得到的文法也可能不同，但等价2.回溯问题条件一：对文法中每一个非终结符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|…γm
A′→β1|β2|…|βn
例如：<if语句>→ifEthenS1elseS2|ifEthenS1
改写为： <if语句>→ifEthenS1B′
B′→elseS2|ε问题：若满足条件FIRST(αi)∩FIRST(αj)=Ф
是否完全避免回溯呢？
上例中：S→cAd A→ad|a
改写为：S→cAd A→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}≠Ф
∴产生回溯小结：构造不带回溯的自上而下分析的条件是：
1.文法不含左递归
2.对文法中每一个非终结符A，如有规则：
A→α1|α2|…|αn则下面条件成立
FIRST(αi)∩FIRST(αj)=Ф(i≠j)
3.对文法中每一个非终结符A，若它的某个产生式首符集包含ε时，则：
FIRST(A)∩FOLLOW(A)=Ф
满足以上条件的文法称为LL(1)文法。
对于一个LL(1）文法，可以构造无回溯的自上而下分析。FIRST(α)的求法：(A→α是文法G的产生式）FOLLOW(A)的求法：（其中A是任一非终结符）例：已知文法G[S]:
S→aSb|P P→bPc|bQc Q→Qa|a
消除文法左递归后是不是LL(1)文法？
解：消除文法左递归得到：
S→aSb|P P→bPc|bQc
Q→aQ′ Q′→aQ′|ε
提取公共左因子后得文法：
S→aSb|P P→bP′ P′→Pc|Qc
Q→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′)=