求PDL表达式的规则 ①脱括号由内往外的次序进行,无括号由左向右进行 ②对于连接基元组成基元结构,必须符合规定的连接 点头,尾数目 例:给出一个PDL文法 G=({S,A,B,C,D,E},{a,by,→,dJ,(,),+,,~},PS) P:①S→(A+(B) ②B→(C)+D ③D→b ④E→(a+b) ⑤A→d ⑥C→E* ⑦D→(~d) ⑧A→a
求ＰＤＬ表达式的规则： • ① 脱括号由内往外的次序进行，无括号由左向右进行 • ② 对于连接基元组成基元结构，必须符合规定的连接 点头，尾数目 例：给出一个PDL文法 G = ({S,A,B,C,D,E},{a↗ ,b ↘, →,d ↓,(,),+,*,~}, P, S) P: ① S →(A+(B)) ② B →(C)+D ③ D →b ④ E →(a+b) ⑤ A →d ⑥C → E*c ⑦D → (~d) ⑧A →a c
可以导出手写大写字符“A”的四种表达式(2)3)(4 (1)S→(A+(B)→(a+(B)→(a+(C)+D)→(at(E*c)+D) →(a+((a+b)*c)+D)→(a+((a+b)*c)+(~d) (2)(d+(a+b)*c)+b)),(3)(a+((a+b)*c)+b),(4)(d+((ab)*c)+(~d)) d
可以导出手写大写字符“A”的四种表达式⑵⑶⑷ ⑴ S →(A+(B)) →(a+(B)) →(a+((C)+D) ) →(a+((E*c)+D)) →(a+(((a+b)*c)+D)) →(a+(((a+b)*c)+(~d))) ⑵(d+(((a+b)*c)+b)) , ⑶(a+(((a+b)*c)+b)) , ⑷ (d+(((a+b)*c)+(~d))) ① ⑧ ② ⑥ ④ ⑦ a d b b a a b b a b ~d d c ~d a a b c ⑴ ⑵ ⑶ ⑷
四标准形式文法 在句法分析和自动机的一些算法中,有时要求标准化文法,下 面介绍二种标准文法。 1.乔姆斯基( Chomsky)范式,一种上下文无关文法如果它的每个 生式P都符合二种形式 A→BC(ABC∈VN)或A→a(A∈Va∈V) 该文法称 Chomsky范式 已知上下文无关文法G=( VMLVTF,S)用以下步骤产生 Chomsky范式的等价文法 G=N,Vp P,S ①若P中已经是A→BC,A→a形式放入P中 ②P中其它的产生式形式为A→0102)01 其中0∈VN或∈Vr
四.标准形式文法 在句法分析和自动机的一些算法中，有时要求标准化文法，下 面介绍二种标准文法。 1. 乔姆斯基(Chomsky)范式,一种上下文无关文法如果它的每个 产生式P都符合二种形式： A→BC (A,B,C∈VN )或A→a (A∈VN , a∈VT ) 该文法称Chomsky范式 已知上下文无关文法 G = (VN ,VT , P, S)用以下步骤产生 Chomsky范式的等价文法 G = (VN , VT , , S) ①若Ｐ中已经是A→BC，A→a形式放入 中 ②Ｐ中其它的产生式形式为A→ θ1θ2….θn 其中θi∈VN 或 θi∈VT P P
用下面的产生式集合代替: A→→Y1Y ∈ n n.n- 若θ∈V则令Y=0;若θ,∈Vp再引入Y,→>0
用下面的产生式集合代替： A→Y1Y2...n Y2...n→Y2Y3...n … Yn-1...n→Yn,,n-1 Yi∈VN 若θi ∈ VN ,则令Yi=θi；若θi ∈ VT ,再引入Yi→θi
例:把文法G=( V. P,S)变成 Chomsky范式 N=S, A, B) Vp=a, b] P:S→→AB,A→a,A→ abaBa,B→b ①把S→AB,A→a,B→b放入P中 ②2A→ ababa,A→91203020, 其中=0=a,02=b,03=A,0:=B A→→Y,Y 11234512345 213451345 →Y,Y 3145,145 YY 415 0304∈VN∴Y345→AY432Y45→BY5 010,0∈V 引入新的产生式,Y1→a,Y2→b,Y5→a
例：把文法G = (VN ,VT , P, S)变成Chomsky范式 VN = {S, A, B} VP = {a, b} P: S→AB，A→a, A→abABa，B→b ① 把S→AB，A→a,B→b放入 中 ②A→abABa，A→θ1 θ2 θ3 θ4 θ5， 其中θ1=θ5=a, θ2=b, θ3=A, θ4=B A→Y1Y2345, Y2345→Y2Y345, Y345→Y3Y45, Y45→Y4Y5 , ∵θ3, θ4∈VN ∴ Y345→AY45, Y45→BY5 , ∵ θ1 θ2 θ5∈VT ∴引入新的产生式，Y1→a, Y2→b, Y5→a P