其中, T是终结符的集合,终结符是指被定义的那个语言的词或符号; N是非终结结点的集合,这些符号不能出现在最终生成的句子中,是专门用来描述语法的。显然,T和N的并构成了符号集V,而且T和N不相交。 V=T∪N T∩N= S是起始符,它是集合N中的一个成员。 P是一个产生式规则集。每条产生式具有如下的形式: a→b 其中:a∈V+,b∈V*,且a≠b V*: V中的符号所构成的全部字符串的集合,包括空字符。 V+: V*中除空字符之外的所有字符串的集合。 一部短语结构语法中,基本运算就是一个符号串重写的过程。 如果a→b是一条产生式,我们就可以通过用b来置换a,重写任何一个包含子串a的符号串,并用符号""表示对符号串所作的这种运算。 如果u, v∈V*,有,就说uav直接产生ubv,或ubv是由uav直接推导出来的。 |