编译原理第三章1 - 图文 

?P为：E→i | E+E | E*E | (E)?{ i, i+i, i*i, i+i*i, (i+i), … }

注意：是符号串的集合?

《 课前思政教育---疫情期间增强自律性 》

- 11/74页 -

?例4 设字母表 Σ={ a, b } , 试设计一n个文法，描述语言 L={ aba | n≥0 }

?分析 该语言中串的结构特征是 ?

0当n＝0 L={ aa } (b=ε)

?当n＝1 L={ aba }?当n＝2 L={ abba }?……

?L={ aa, aba, abba, …… }

《 课前思政教育---疫情期间增强自律性 》

- 12/74页 -

?L={ aa, aba, abba, …… }

?所以定义语言的文法为： G=( {A, B}, {a, b}, P, A )?P={ A→aBa B ? B→Bb | ε }

《 课前思政教育---疫情期间增强自律性 》

- 13/74页 -

? 例5 设字母表∑={ (, ) } ,试设计一n n个文法描述语言 L={ () | n≥0}?分析 该语言中串的结构特征是 0 0

?当n=0 L={ ε } 注: ()= ε

?当n=1 L={ ( ) }?当n=2 L={ (( )) }?……

?L={ ε, ( ), (( )), ((( ))), … }

《 课前思政教育---疫情期间增强自律性 》

- 14/74页 -

?

n nL={ () | n≥0}

?所以定义语言的文法为：

?P: S→ ε | ( S )

《 课前思政教育---疫情期间增强自律性 》

- 15/74页 -