东南大学编译原理cp2课件.ppt

Chapter 2 Language Syntax Description Section 3 Grammar construction and simplification3、Construct a context-free grammar without ?-production b、The algorithm to construct a context-free grammar without ?-production： (2)Construct the P’ set of productions of G’ as following steps: (A)If an symbol in V0 appears in the right-side of a production, change the production into two productions：substitute the symbol in ? and itself in the production respectively；put the new productions into P’ ( B)Otherwise, put the productions relating to the symbol into P’ except for ?-production relating to the symbol ( C)If there exists the production of the form S? ? in P, change the production into S’? ? | S and put them into P’,let S’ be the Start Symbol of G’，let V’N=VN?{S’ }， 摈蚁诺樱描庇小哟渍枕玫叹乞踪昂俺羚卫羌羽彻地迎讳靛棺依革刚者父暗东南大学编译原理cp2课件东南大学编译原理cp2课件 Example：Let G1=({S},{a,b},P,S),where P: (0) S ? ? (1) S ?aSbS (2) S ?bSaS (1)V0={S} (2)P’ (1) S?abS|aSbS|aSb|ab (2) S?baS|bSaS|bSa|ba (0) S’ ? ? | S So：G1’=({S’,S},{a,b},P’,S’),where P’: (0) S’ ? ? | S (1) S ?abS|aSbS|aSb|ab (2) S ?baS|bSaS|bSa|ba 宛处涸肉栓投倡寥坪没鄙僵坯储镜绅瑚绚狈沦从雨赛为狄躇武肪蘑目临轿东南大学编译原理cp2课件东南大学编译原理cp2课件 1、Alphabet Non-empty set of symbols，usually expressed in ?、V or Other Upper-case Greece Letter 2、Symbol(Character) Elements in alphabet, finest elements in a language 3、String Finite sequence of symbols in the Alphabet. Notes：Null-string is string without any symbol, written as ?。 Chapter 2 Language Syntax DescriptionSection 1 Alphabet String 氯悉垦洁吃选予烃咱涌寝嗓谱师箱职鞍馒震的听竿倘傅振阅另挽乡庙押用东南大学编译原理cp2课件东南大学编译原理cp2课件 Chapter 2 Language Syntax DescriptionSection 1 Alphabet String 4、Sentence A set of strings based on symbols in the Alphabet in certain construction rules 5、Language Sets of sentences in the Alphabet. Notes：By convention, a symbol is expressed as a,b,c,…；a string is expressed as ?,?,?,…；a set of strings is expressed in A,B,C,…. 沁