ANTLR学习心得——抄书(3)

　　关于给定文法G，如何产生语言L(G)，将进一步给出其形式化定义。为此，首先给出一些基本术语的定义。
　　·  定义2．11(直接推导“→”)
　　有V=αA β=αγ β=W (α,β,γ∈(V_N∪V_T)^*)，当且仅当P中存在一条规则A→Y，称V直接推导出w(或W直接归约到V)，记作：V→w。
　　·  定义2．12(直接推导序列)
　　如果存在V=a₀→a₁,a₁→a₂,...,a_n-1→a_n=W或a₁→a₂→a₃→...→a_n-1→a_n,则V经过n步(n>0)可以推导出W，记作：v→⁺w。当v→⁺W或v=w，记作：v→^*w。
　　·  定义2．13(最左(右)推导)
　　在推导过程中，总是对句型中的最左(右)边的非终结符进行替换，成为最左(右)推导。
　　·  定义2．14(句型)
　　设有文法G[S]，若S=^*α (α∈(V_N∪V_T)^*)，则称α为G[S]的句型。
　　·  定义2．15(句子)
　　设有文法G[S]，若S=^*α (α∈V_T^*)，则称α为G[S]的句子。
　　·  定义2．16(规范推导/规范句型/规范归约)
　　最右推导也称为规范推导。仅用规范推导得到的句型称为规范句型，规范推导的逆序为规范归约。
　　·  定义2．17(文法的递归)
　　若文法G存在形如αAβ→αAβ'的推导，则称G是递归文法。
　　例2．5  设有文法G₁：E→E+E|E*E|(E)|i
　　　　　　有E→E……则文法G₁是直接递归文法。
　　例2．6  设有文法G₂：
　　　　　　T→Qc|c

　　　　　　Q→Rb|b

　　　　　　R→Ta|a

　　有T→Qc→Rbc→Tabc，即T→Tabc，则文法G₂是间接递归文法。

　　·  定义2．18(语言)
　　文法G所产生的语言L(G)：
　　L(G)={α|α∈V_T^*∧S^*→α,S是文法G的开始符号}
　　需要指出的是，文法和语言的相互关系并非是惟一对应的，形式语言理论可以证明
　　(1)  给定文法G，能从结构上惟一地确定相应的语言。
　　(2)  给定一种语言，能确定其文法，但这种文法不是惟—则，即
　　L(G₁)=L(G₂)=...=L(G_n)
　　为此，引出文法等价的概念。
　　·  定义2．19(文法等价)
　　若L(G₁)=L(G₂)，则称文法G₁和G₂是等价的。
　　文法等价的概念说明，两个文法尽管它们的规则不尽相同，只要所产生的语言相同，则认为这两个文法是等价的。
　　例2．7  设有文法G₁
　　　　G₁={{S},{0},S,{S→S0,S→0}}
　　由于存在
　　　　S→S0→S00→S000→...→S0^n-1→0ⁿ
　　则该文法表示的语言为  L(G₁)={0ⁿ|n>=1}
　　设有文法G₁'，G₁'={{S},{0},S,{S→0S,S→0}}
　　由于存在  S→0S→00S→000S→...→0^n-1S→0ⁿ
　　则该文法表示的语言为  L(G₁')=L(G₁')=L(G₁)
　　很显然，G₁≠G₁'，但却存在L(G₁')=L(G₁)，所以文法G₁和G₁'等价。
　　利用文法等价的概念，当讨论编译程序实现的有关问题的，某种分析技术对文法会有不同程度的限定。当文法不能满足某种分析技术的应用条件时，需要对文法进行等价变换，使之适应相应的分析技术。一般文法等价变换是针对
　　*使文法适用于某种分析技术
　　*消除文法的二义性
　　*使文法类与语言类一致
　　*使文法满足特殊需要