构造语言的文法的方法(第2章题型)课件

文法文法GN为：为：ND|ND D0|1|2|3|4|5|6|7|8|9GN 的语言是什么？的语言是什么？L（GN）=|为可带前导为可带前导0的正整数的正整数答案：答案：已知文法，构造语言的方法已知文法，构造语言的方法构造某语言的文法的方法构造某语言的文法的方法 为文法构造语言，一般是采用为文法构造语言，一般是采用“凑规凑规则则”的方法来完成的，步骤为：的方法来完成的，步骤为：1.找出语言的若干句子；找出语言的若干句子；2.分析句子的特点；分析句子的特点；3.根据句子的特点凑规则；根据句子的特点凑规则；4.形成文法；形成文法；5.检验。检验。例子例子 试构造生成试构造生成L=anbnci|n1,i0 语言的语言的文法。文法。步骤如下：步骤如下：1.本题是以语言的定义方式给出语言，则本题是以语言的定义方式给出语言，则可根据该描述直接得到语言的句子。如可根据该描述直接得到语言的句子。如aabbc、aaabbbccccc等。等。2.可直接得到句子的特点。句子中只含有可直接得到句子的特点。句子中只含有a、b、c三种符号，所有的三种符号，所有的a在句子开头部在句子开头部分，所有的分，所有的b在句子的中间部分，所有的在句子的中间部分，所有的c在句子的尾部，且句子中符号在句子的尾部，且句子中符号a、b的个数的个数相同。相同。3.凑规则。凑规则。由于语言的句子中符号的个数可以由于语言的句子中符号的个数可以有任意多个，所以必然要用到有任意多个，所以必然要用到递归递归规则。规则。又因为句子中又因为句子中a和和b 的个数一样多，的个数一样多，但与但与c的个数不同，所以将生成含的个数不同，所以将生成含a、b的的部分部分anbn与生成含与生成含c的部分的部分ci分开。分开。凑出产生式凑出产生式AaAb|ab产生产生anbn，凑出产生式凑出产生式BcB|c产生产生ci。4.根据根据a、b、c的个数的要求的个数的要求n1,i0，得，得到文法：到文法：GZ：ZAB AaAb|ab BcB|5.检验：通过推导可发现，语言所有的句检验：通过推导可发现，语言所有的句子可由子可由GZ推导出来；而文法推导出来；而文法GZ推导推导出来的所有终结符号串均是语言的句子。出来的所有终结符号串均是语言的句子。所以所以GZ就是所求文法。就是所求文法。递归文法递归文法(定义定义2.6)直接递归直接递归递归递归直接左递归直接左递归左递归左递归递归文法递归文法