文法和语言

1.文法的类型

乔姆斯基把文法分为四类，即0型，1型，2型，3型。差别在于对产生式施加不同的限制。
0型文法：设G=(V_N,V_T,P,S)，如果它的每个产生式α→β是这样的结构：α∈（V_N∪V_T)* 且至少含有一个非终结符，而β ∈（V_N∪V_T)，则G是一个0型文法。 0型文法也称短语文法,功能相当于图灵机，任何0型语言都是递归可枚举的。
1型文法：设G=(V_N,V_T,P,S)，若P中的每个产生式α→β都满足|β|≥|α|，仅仅S→ε除外，则文法G为1型或上下文有关的。
2型文法：设G=(V_N,V_T,P,S)，若P中的每个产生式α→β都满足α是一个非终结符，β ∈（V_N∪V_T)，则文法G为2型或上下文无关的。
3型文法：设G=(V_N,V_T,P,S)，若P中的每个产生式的形式都是A→aB或A→a，其中A和B都是非终结符，α∈V_T* ，则文法G为3型或正规文法。
ps：x型文法产生的语言为x型语言。

2.上下文无关文法及其语法树

上下文无关文法有足够的能力描述现金程序设计语言的语法结构。语法树，也称推导树，是一种描述上下文无关文法的句型推导的直观工具。
给定文法G=(V_N,V_T,P,S)，对于G的任何句型都能构成与之关联的语法树。这棵树满足下列条件：

1. 每个结点都有一个标记，此标记是V的一个符合。
2. 根的标记是S。
3. 若一个结点n至少有一个它自己除外的子孙，并且有标记A，则A肯定在V_N中。
4. 如果结点n的直接子孙从左到右的次序是结点n1，…nk,其标记分别为A1,A2…AK,那么A→A1A2…AK一定是P中的一个产生式。
   以上，不同推导过程得到的是同一颗语法树。但若一个文法存在某个句子，对应两颗不同的语法树，则称这个文法是二义的。例：
   

3.句型的分析

句型的分析就是识别一个符号串是否为某文法的句型，是某个推导的构造过程。在语言的编译实现中，把完成句型分析的程序称为分析程序或识别程序，分析算法又称识别算法。
从左到右的分析算法分为两大类：自上而下和自下而上的。
自上而下：从文法开始符号开始，反复使用各种产生式，使语法树末端结点符号串为输入符号串。

自下而上：从输入符号串开始，逐步归约。