右(左)线性文法

马上就编译原理考试了，在我没有被这门课干死之前，我要先把它干死，刚把爹。

1.右线性文法

1.1定义

形如：
A → aB
A → a
的文法叫做右线性文法。

1.2状态图

例:G[Z]:
Z→0U∣1V
U →1Z∣1
V →0Z∣0

由状态图可知：

1. 右线性文法需要一个终结状态F，双圈表示；
2. 初始状态需要标明；
3. 转换很简单，直接可以看出；
4. 分析过程自上而下推导；

2.左线性文法

2.1定义

形如：
A → Ba
A → a
的文法叫做左线性文法。

2.2状态图

例:G[Z]:
Z→U0∣V1
U →Z1∣1
V →Z0∣0

由状态图可知：

1. 左线性文法需要一个初始状态F，终态（起始符号）用双圈表示；
2. 初始状态需要标明；
3. 可以先从Z（终态）画起，箭头倒置（如：U →Z1∣1，箭头全部指向U，连线上是1）
4. 分析过程自下而上规约；

3.右线性文法转换左线性文法

以右线性文法转换左线性文法为例：
已知右线性文法：
G[Z]:
Z→0U∣1V
U →1Z∣1
V →0Z∣0

2.1做状态转换图（利用右线性文法规则）

2.1读状态转换图（利用左线性文法规则）

G[F]:
F→U1∣V0
U→Z0
V→Z1
Z→U1∣V0

双圈为初态，箭头指向自己，由双圈开始读。

左线性文法转右线性文法同理。