关于给定文法G,如何产生语言L(G),将进一步给出其形式化定义。为此,首先给出一些基本术语的定义。
· 定义2.11(直接推导“→”)
有V=αA β=αγ β=W (α,β,γ∈(VN∪VT)*),当且仅当P中存在一条规则A→Y,称V直接推导出w(或W直接归约到V),记作:V→w。
· 定义2.12(直接推导序列)
如果存在V=a0→a1,a1→a2,...,an-1→an=W或a1→a2→a3→...→an-1→an,则V经过n步(n>0)可以推导出W,记作:v→+w。当v→+W或v=w,记作:v→*w。
· 定义2.13(最左(右)推导)
在推导过程中,总是对句型中的最左(右)边的非终结符进行替换,成为最左(右)推导。
· 定义2.14(句型)
设有文法G[S],若S=*α (α∈(VN∪VT)*),则称α为G[S]的句型。
· 定义2.15(句子)
设有文法G[S],若S=*α (α∈VT*),则称α为G[S]的句子。
· 定义2.16(规范推导/规范句型/规范归约)
最右推导也称为规范推导。仅用规范推导得到的句型称为规范句型,规范推导的逆序为规范归约。
· 定义2.17(文法的递归)
若文法G存在形如αAβ→αAβ'的推导,则称G是递归文法。
例2.5 设有文法G1:E→E+E|E*E|(E)|i
有E→E……则文法G1是直接递归文法。
例2.6 设有文法G2:
T→Qc|c
Q→Rb|b
R→Ta|a
有T→Qc→Rbc→Tabc,即T→Tabc,则文法G2是间接递归文法。
· 定义2.18(语言)
文法G所产生的语言L(G):
L(G)={α|α∈VT*∧S*→α,S是文法G的开始符号}
需要指出的是,文法和语言的相互关系并非是惟一对应的,形式语言理论可以证明
(1) 给定文法G,能从结构上惟一地确定相应的语言。
(2) 给定一种语言,能确定其文法,但这种文法不是惟—则,即
L(G1)=L(G2)=...=L(Gn)
为此,引出文法等价的概念。
· 定义2.19(文法等价)
若L(G1)=L(G2),则称文法G1和G2是等价的。
文法等价的概念说明,两个文法尽管它们的规则不尽相同,只要所产生的语言相同,则认为这两个文法是等价的。
例2.7 设有文法G1
G1={{S},{0},S,{S→S0,S→0}}
由于存在
S→S0→S00→S000→...→S0n-1→0n
则该文法表示的语言为 L(G1)={0n|n>=1}
设有文法G1',G1'={{S},{0},S,{S→0S,S→0}}
由于存在 S→0S→00S→000S→...→0n-1S→0n
则该文法表示的语言为 L(G1')=L(G1')=L(G1)
很显然,G1≠G1',但却存在L(G1')=L(G1),所以文法G1和G1'等价。
利用文法等价的概念,当讨论编译程序实现的有关问题的,某种分析技术对文法会有不同程度的限定。当文法不能满足某种分析技术的应用条件时,需要对文法进行等价变换,使之适应相应的分析技术。一般文法等价变换是针对
*使文法适用于某种分析技术
*消除文法的二义性
*使文法类与语言类一致
*使文法满足特殊需要
分享到:
相关推荐
py3antlr4book, 隐藏ANTLR4图书源代码到Python3版本 py3antlr4book隐藏ANTLR4图书源代码到 python 3版本。如何使用( Windows )安装 python安装 antlr4 python3运行时 pip install antlr4-python
antlr3最好的学习文档 antlr3详细说明手册
具备ANTLR 3使用经验的用户可从第4章开始阅读以学习ANTLR 4的新功能。 有关ANTLR的更多在线学习资料在http://www.antlr.org上,你可以找到ANTLR、ANTLRWorks2图形界面开发环境、文档、预制的语法、示例、文章,...
antlr4读书笔记七八章,antlr4读书笔记七八章,antlr4读书笔记七八章
The Definitive ANTLR4Reference 学习笔记 The Definitive ANTLR4Reference 学习笔记
antlr-2.7.5H3.antlr-2.7.5H3.antlr-2.7.5H3.jar
英文版:学习ANTLR4的宝典,是原作者的力作。每个版本都会写这么一本书。
The+Definitive+ANTLR+4+Reference 学习笔记word The+Definitive+ANTLR+4+Reference 学习笔记word
发布的.net的antlr运行库存在不同步的问题,导致产生错误,vs2005或vs2008等无法编译. 我用最新的发布源码生产了该运行库,解决了错误。 ANTLR 是ANother Tool for Language Recognition 的缩写“又一个语言识别...
antlrcs, ANTLR 3 StringTemplate 3和 StringTemplate 4的C# 端口 ANTLR 3 C# 目标 这里知识库包含 3个主要项目的C# 版本,其中有些项目具有多个生成构件:ANTLR 3Antlr3: ANTLR 3的代码生成器Antlr3.Runtime: ANTLR...
赠送jar包:antlr4-runtime-4.2.jar; 赠送原API文档:antlr4-runtime-4.2-javadoc.jar; 赠送源代码:antlr4-runtime-4.2-sources.jar; 赠送Maven依赖信息文件:antlr4-runtime-4.2.pom; 包含翻译后的API文档:...
JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源代码 antlr-2.7.6rc1JavaEE源...
antlr 2.7.7源码,下载自:http://repo.spring.io/plugins-release/org/antlr/com.springsource.antlr/2.7.7/
ANTLR, ANother Tool for Language Recognition, 是一个可以接受含有语法描述的语言描述符并且生成程序能够识别这些语言所产生的句子。作为一个翻译程序的 一部分,你可以给你的语法附上简单的操作符和行为并且告诉...
开源项目-antlr-antlr4.zip,antlr 4.6发布,支持go代码生成
antlr4权威指南中文版,原书作者terence Parr,清晰版本
ANTLR 1989-2006 Developed by Terence Parr @ University of San Francisco We reserve no legal rights to the ANTLR--it is fully in the public domain. An individual or company may do whatever they ...
antlr-2.7 (3个). 资源共享,有需要其他jar包的可以在评论留言,看到后我会陆续上传。
antlr-2.7.7.jar和antlr-2.7.6.jar