二型文法如下:
S->Ac
S->Sc
A->ab
A->aAb
三型文法如下:
S->aS
A->bA
B->cB
B->c
A->Bb
A、2型文法是上下文无关文法,表现在产生式上就是产生式的左部只有一个非终结符;3型文法从广义上讲包括左线形文法、右线形文法和正规文法 。
B、左线形文法产生式的右部要么没有非终结符,如果有非终结符也只能有一个,且必须位于产生式右部的最左端。
C、右线形文法产生式的右部要么没有非终结符,如果有非终结符也只能有一个,且必须位于产生式右部的最右端 。
D、正规文法是右线形文法的一个子集,其产生式右部只有三种情况:
1)空串
2)只有一个终结符
3)只有一个终结符后接一个非终结符
E、所有的3型文法都是2型文法。
通过算法对文法的每一产生式进行分析,如果存在复杂递归,则必是上下文无关文法,否则就是正则文法。
1、像A->Aa|ε这样的文法,虽然存在递归,但却是单一的自递归,可以通过有穷自动机表示和分析处理,所以是正则文法;
2、但是像E->E+T,T->id|(E)这样的文法显然非单一的自递归,而是存在复杂递归,自动机是无法表示和处理的,必然是上下文无关文法。
另外还请注意:
1、正则文法是上下文文法的子集,正则文法也属于上下文无法,但有的上下文文法不一定是正则文法;
2、同时再结合这两个的形式定义认真揣摩必定能悟出一二。
看规则的右部。