写出编译的过程;求first和follow集合
上下文无关文法的特点
编译原理中的0、1、2、3型文法及其关系。
0型或短语文法:
产生式形如:α->β
其中:α、β属于字符串的闭包区间内且α至少包含有一个非终结符;
解释:左边有非终结符,右边有终结符。
举例:A->ab, A->Cb, A->b
0型文法是这几个文法中,限制最少的一个,一般见到的文法都可看做0型文法。0型文法的能力相当于图灵机(Turing)。
1型文法:又称为上下文有关文法:
产生式形如:α->β
其中:α->β均满足|α|<=|β|, 除了α->ε外;
解释:式子左边可以有多个字符,但必须有一个非终结符;式子右边可以有多个字符,可以是终结符,也可以是非终结符,但必须是有限个字符且左边长度必须小于右边
举例:A->B,A->Bba ,Bb->A,
2型文法:又称为上下文无关文法:
产生式形如: A ->β
解释:式子左边必须是非终结符,然而一个终结符一个非终结符的组合不是一个非终结符,如Ab不是一个非终结符,但是两个非终结符的组合就是一个非终结符了,如AB就是行了;式子右边可以有多个字符,可以是终结符,也可以是非终结符,但必须是有限个字符
举例:AB->abc,B->ab
3型文法:又称为正规文法(正规文法又包括左线性文法和右线性文法):
右线性文法:
产生式形如: A ->αB 或 A ->α
解释:式子左边只能有一个字符,而且必须是非终结符;式子右边最多有二个字符。如果有二个字符必须是(终结符+非终结符)的格式,如果是一个字符,那么必须是终结符。
举例:B->aB
左线性文法:
产生式形如: A ->Bα 或 A ->α
解释:式子左边只能有一个字符,而且必须是非终结符;式子右边最多有二个字符。如果有二个字符必须是(非终结符+终结符)的格式,如果是一个字符,那么必须是终结符。
举例:B->Ba
原文链接:https://blog.csdn.net/MillionSong/article/details/105672676






