求PDL表达式的规则: ①脱括号由内往外的次序进行,无括号由左向右进 ②对于连接基元组成基元结构,必须符合规定的连 接 点头,尾数目 例:给出一个PD儿文法 G=({S,A,B,C,D,B}{ax,by,→d,),+,,~},P,S) P:①S→(A+(B) ②B→(C)+D D→b ④E→(a+b) ⑤A→d 6C→E*C ⑦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)→(a+(Ec)+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+((a+b)*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∈V)或A→a(A∈Vsa∈V 该文法称 Chomsky范式 已知上下文无关文法G=(V,P,S)用以下步骤产生 Chomsky范式的等价文法 G=(N, VI,P, S) ①若P中已经是A→BC,A→a形式放入P中 ②P中其它的产生式形式为A→,8.90∈VN或 其中
四.标准形式文法 在句法分析和自动机的一些算法中，有时要求标准化文法，下 面介绍二种标准文法。 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→Y1Y2.n Y n-1..n n.n-1 若日∈则令Y=0:若日∈M再引入Y
用下面的产生式集合代替： A→Y1Y2...n Y2...n→Y2Y3...n … Yn-1...n→Yn,,n-1 Yi∈VN 若θi ∈ VN ,则令Yi=θi；若θi ∈ VT ,再引入Yi→θi
例:把文法G=(Vr,P,S)变成 Chomsky范式 N=IS, A,By {a,b} P:S→AB,A→a,A→ abaBa,B→b ①把S→AB,A→aB→b放入P中 ②A→ sabABa,A,02000, 其中01=05=a,2=b,03=A,6a=B 03204∈VN∷NAYY→B5w,y AYY 11234512345 21345,1345 3 45 415 e1265∈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