STEPS:= ; /* initialize STEPS to start (derived in 0 steps) */I:= 1; /* initialize I to first step in STEPS */
while I Š size(STEPS) do /* try each step */ begin for PDN:= 1 to p do /* with each production */ for POS:= 1 to len(STEPS[I]) do /* at each position */ begin NEXT:= rewrite(STEPS[I], P[PDN], POS); if NEXT = INPUT then return(true) else if len(NEXT) Š len(INPUT) then STEPS:= append(STEPS,NEXT) end; I:= I+1 end;return(false)
rewrite(x,_,p) - returns string x rewritten with pdn _ at pos p, or x if _ doesn’t apply at p
append(l,x) - returns list l with x added at end, or just l if x already occurs in l
Previous slide | Next slide | Back to first slide | View graphic version |