CFG产生语言的基本方法-推导
CFG(产生式)通过推导的方法产生语言,即(通俗地讲)从开始符号S开始,反复使用产生式:将产生式左部的非终结符替换为右部的文法符号序列(展开产生式,用=>表示),直到得到一个终结符序列。
1> 直接推导:利用产生式产生句子的过程中,将用产生式A→γ的右部代替文法符号序列αAβ中的A得到αγβ的过程,称αAβ直接推导出αγβ,记作:αAβ=>αγβ
2> 零步或多步推导:若对于任意文法符号序列α1,α2,...αn,有α1=>α2=>...=>αn,则称此过程为零步或多步推导,记为:α1 =*> αn,其中α1=αn的情况为零步推导。
3> 至少一次推导:若α1≠αn,即推导过程中至少使用一次产生式,则称此过程为至少一步推导,记为:α1 =+> αn
网站声明:如果转载,请联系本站管理员。否则一切后果自行承担。
加入交流群
请使用微信扫一扫!