‘壹’ 编译原理的发展历程
在20世纪40年代,由于冯·诺伊曼在存储-程序计算机方面的先锋作用,编写一串代码或程序已成必要,这样计算机就可以执行所需的计算。开始时,这些程序都是用机器语言 (machine language )编写的。机器语言就是表示机器实际操作的数字代码,例如:
C7 06 0000 0002 表示在IBM PC 上使用的Intel 8x86处理器将数字2移至地址0 0 0 0 (16进制)的指令。
但编写这样的代码是十分费时和乏味的,这种代码形式很快就被汇编语言(assembly language )代替了。在汇编语言中,都是以符号形式给出指令和存储地址的。例如,汇编语言指令 MOV X,2 就与前面的机器指令等价(假设符号存储地址X是0 0 0 0 )。汇编程序(assembler )将汇编语言的符号代码和存储地址翻译成与机器语言相对应的数字代码。
汇编语言大大提高了编程的速度和准确度,人们至今仍在使用着它,在编码需要极快的速度和极高的简洁程度时尤为如此。但是,汇编语言也有许多缺点:编写起来也不容易,阅读和理解很难;而且汇编语言的编写严格依赖于特定的机器,所以为一台计算机编写的代码在应用于另一台计算机时必须完全重写。
发展编程技术的下一个重要步骤就是以一个更类似于数学定义或自然语言的简洁形式来编写程序的操作,它应与任何机器都无关,而且也可由一个程序翻译为可执行的代码。例如,前面的汇编语言代码可以写成一个简洁的与机器无关的形式 x = 2。
在1954年至1957年期间,IBM的John Backus带领的一个研究小组对FORTRAN语言及其编译器的开发,使得上面的担忧不必要了。但是,由于当时处理中所涉及到的大多数程序设计语言的翻译并不为人所掌握,所以这个项目的成功也伴随着巨大的辛劳。几乎与此同时,人们也在开发着第一个编译器, Noam Chomsky开始了他的自然语言结构的研究。他的发现最终使得编译器结构异常简单,甚至还带有了一些自动化。Chomsky的研究导致了根据语言文法(grammar ,指定其结构的规则)的难易程度以及识别它们所需的算法来为语言分类。正如现在所称的-与乔姆斯基分类结构(Chomsky hierarchy )一样-包括了文法的4个层次:0型、1型、2型和3型文法,且其中的每一个都是其前者的专门化。2型(或上下文无关文法(context-free grammar ))被证明是程序设计语言中最有用的,而且今天它已代表着程序设计语言结构的标准方式。
分析问题( parsing problem ,用于限定上下文无关语言的识别的有效算法)的研究是在20世纪60年代和70年代,它相当完善地解决了这一问题, 现在它已是编译理论的一个标准部分。它们与乔姆斯基的3型文法相对应。对它们的研究与乔姆斯基的研究几乎同时开始,并且引出了表示程序设计语言的单词(或称为记号)的符号方式。
人们接着又深化了生成有效的目标代码的方法,这就是最初的编译器,它们被一直使用至今。人们通常将其误称为优化技术(optimization technique ),但因其从未真正地得到过被优化了的目标代码而仅仅改进了它的有效性,因此实际上应称作代码改进技术(code improvement technique )。
这些程序最初被称为编译程序-编译器,但更确切地应称为分析程序生成器 (parser generator ),这是因为它们仅仅能够自动处理编译的一部分。这些程序中最着名的是 Yacc (yet another compiler- compiler),它是由Steve Johnson在1975年为Unix系统编写的。
类似地,有穷自动机的研究也发展了另一种称为扫描程序生成器 (scanner generator )的工具,Lex (与Yacc同时,由Mike Lesk为Unix系统开发的)是这其中的佼佼者。在20世纪70年代后期和80年代早期,大量的项目都关注于编译器其他部分的生成自动化,这其中就包括代码生成。这些尝试并未取得多少成功,这大概是因为操作太复杂而人们又对其不甚了解。
编译器设计最近的发展包括:首先,编译器包括了更为复杂的算法的应用程序,它用于推断或简化程序中的信息;这又与更为复杂的程序设计语言(可允许此类分析)的发展结合在一起。其中典型的有用于函数语言编译的Hindle y - Milner类型检查的统一算法。
其次,编译器已越来越成为基于窗口的交互开发环境(interactive development environment,IDE )的一部 分,它包括了编辑器、链接程序、调试程序以及项目管理程序。这样的IDE的标准并没有多少, 但是已沿着这一方向对标准的窗口环境进行开发了。
‘贰’ 什么是编译原理
问题一:什么是编译原理 编译:就是将程序语言进行翻译,生成可供用户直接执行的二进制代码,即可执行文件。
任务是个比较模糊的概念,指的是操作系统中正在进行的工作,既可以指进程,也可以指程序春坦灶。
程序指的是可以连续执行,并能够完成一定任务的一条条指令的 *** 。
进程是程序在一个数据 *** 上运行的过程,它是传统操作系统进行资源分配和调度的一个独立单位。
线程是一个指令执行序列,是操作系统调度的最小单位。一个或多个线程构成进程,构成一个进激的线程之间共享资源。进程和线程之间的最大区别就是线程不能独立拥有资源,进程拥有自己的资源。
问题二:编译原理中V*是什么意思 V是一个符号 *** ,假设V指的是三个符号a, b, c的 *** ,记为 V = {a, b, c }
V* 读作“V的闭包”,它的数学定义是V自身的任意多次自身连接(乘法)运算的积,也是一个 *** 。
也就是说,用V中的任意符号进行意多次(包括0次)连接,得到的符号串,都是V*这个 *** 中的元素。
0次连接的结果是不含任何符号的空串,记为 ε
1次连接就是只有一个符号的符号串,比如,a,b, c
2次连接是两个符号构成的符号串,比如,aa, ab, ac, ba, bb, bc,等等
……
n次连接是一个长度为n、由a、b、c三个符号构成的符号串,比如abaacbbac……
因此,V*包含一切由a,b,c三个符号连接而成的、任意长度的符号串(以及空串ε)
问题三:编译原理 V+什么意思,例如下面的例子。。。 v表示终结符和非终结符 *** 。
+表示 *** 中的一个或多个元素构成的串的 *** 。
所以v+表示由一个或多个终结符或非终结符构成的串的 *** 。比如如果a∈VT,A∈VN,那么a,A,aA,Aa,aAA,AaA等都是v+中的元素。
问题四:谁能够解释下编译原理中什么是FIRSTVT,和LASTVT,尽量浅显易懂点谢谢 Firstvt和Lastvt是为了画算符优先关系表的(就是表里面填优先大于小于等于的那个)。
然后要注意他们可都是终结符的 *** 。
Firstvt
找Firstvt的三条规则:如果要找A的Firstvt,A的候选式中出现:
A->a.......,即以终结符开头,该终结符入Firstvt
A->B.......,即以非终结符开头,该非终结符的Firstvt入A的Firstvt
攻 A->Ba.....,即先以非终结符开头,紧跟终结符,则终结符入Firstvt
Lastvt
找Lastvt的三条规则:如果要找A的Lastvt,A的候选式中出现:
A->.......a,即以终结符结尾,该终结符入Lastvt
A->.......B,即以非终结符结尾,该非终结符的Lastvt入A的Lastvt
A->.....aB,即先以非终结符结尾,前面是终结符,则终结符入Firstvt
问题五:编译原理 什么是语义分析 在编译原理中,语法规则和词法规则不同之处在于:规则主要识别单词,而语法主要识别多个单词组成的句子。词法分析信孝和词法分析程序:词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。语法分析(Syntax *** ysis或Parsing)和语法分析程序(Parser) 语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语,如“程序”,“语句”,“表达式”等等.语法分扒扮析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.语义分析(Syntax *** ysis) 语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.
问题六:编译原理中,(E)是什么意思? E→(E)? 10分 就是 字符本身 意思是F产生( E ) 或者 i 比如If语句的开头 就是 带括号的 必须是 if(表达式)这样的形式 丢了任何即括号就是其 终结符 “(” 和 “)”.
问题七:大家觉得对编译器及编译原理需要掌握到一个什么程度 我跟你说,编译原理太有用了。
我是做手机游戏的,现在做一个游戏引擎。既然是引擎,就需要提供抽象的东西给上层使用。这里,我引入了脚本系统。
这个脚本系统包括一堆我根据实际需求自行设计的指令集,包括基本的输入输出,四则运算,系统功能调用,函数声明,调用等等(其实你要是用过lua或者其他游戏脚本你就知道了。)整个结构包括指令集、编译器、虚拟机等部分。这样,引擎提供一些基础服务,比如绘图,计算位置等,脚本就可以非常简单控制游戏。甚至快速构建新游戏。你应该知道QUAKE引擎吧?
这里提供给你一个计算器的小程序,应用了EBNF理论,支持表达式,比如(2+3*6)*4+4,你自己体验一下它的简洁和强大。
/*
simple integer arithmetic calculator according to the EBNF
-> {}
->+|-
->{}
-> *
-> ( )| Number
Input a line of text from stdin
Outputs Error or the result.
*/
#include
#include
#include
char token;/*global token variable*/
/*function prototypes for recursive calls*/
int exp(void);
int term(void);
int factor(void);
void error(void)
{
fprintf(stderr,Error\n);
exit(1);
}
void match(char expectedToken)
{
if(token==expectedToken)token=getchar();
else error();
}
main()
{
int result;
token = getchar();/*load token with first character for lookahead*/
result = exp();
if(token=='\n')/*check for end of line */
printf(Result = %d\n,result);
else error();/*extraneous cahrs on line*/
return 0;
}
int exp(void)
{
int temp = term();
while((token=='+')||(token=='-'))
switch(token)
{
case '+':
match('+');
temp+=term......>>
问题八:编译原理中,自动机究竟是什么. 形式语言
形式语言 是一个字母表上的某些有限长字串的 *** 。一个形式语言可以包含无限多个字串。
语言的形式定义
字母表 ∑ 为任意有限 *** ,ε 表示空串, 记 ∑ 0 为{ε},全体长度为 n 的字串为 ∑ n , ∑ * 为 ∑ 0 ∪∑ 1 ∪…∪∑ n ∪…, 语言 L 定义为 ∑ * 的任意子集。
注记:∑ * 的空子集 Φ 与 {ε} 是两个不同的语言。
语言间的运算
语言间的运算就是 ∑ * 幂集上的运算。
字串 *** 的交并补等运算。
连接运算:L 1 L 2 = { xy | x 属于L 1 并且 y 属于L 2 }。
幂运算:L n = L … L (共 n 个 L 连接在一起),L 0 = {ε}。
闭包运算:L * = L 0 ∪L 1 ∪…∪L n ∪…。
(右)商运算:L 1 /L 2 = {x | 存在 y 属于L 2 使得 xy 属于L 1 }。
语言的表示方法
一个形式语言可以通过多种方法来限定自身,比如:
枚举出各个字串(只适用于有限字串 *** )。
通过 形式文法 来产生(参见 乔姆斯基谱系 )。
通过正则表达式来产生。
通过某种自动机来识别,比如 图灵机 、 有限状态自动机 。
自动机
automata
对信号序列进行逻辑处理的装置。在自动控制领域内,是指离散数字系统的动态数学模型,可定义为一种逻辑结构,一种算法或一种符号串变换。自动机这一术语也广泛出现在许多其他相关的学科中,分别有不同的内容和研究目标。在计算机科学中自动机用作计算机和计算过程的动态数学模型,用来研究计算机的体系结构、逻辑操作、程序设计乃至计算复杂性理论。在语言学中则把自动机作为语言识别器,用来研究各种形式语言。在神经生理学中把自动机定义为神经网络的动态模型,用来研究神经生理活动和思维规律,探索人脑的机制。在生物学中有人把自动机作为生命体的生长发育模型,研究新陈代谢和遗传变异。在数学中则用自动机定义可计算函数,研究各种算法。现代自动机的一个重要特点是能与外界交换信息,并根据交换得来的信息改变自己的动作,即改变自己的功能,甚至改变自己的结构,以适应外界的变化。也就是说在一定程度上具有类似于生命有机体那样的适应环境变化的能力。
自动机与一般机器的重要区别在于自动机具有固定的内在状态,即具有记忆能力和识别判断能力或决策能力,这正是现代信息处理系统的共同特点。因此,自动机适宜于作为信息处理系统乃至一切信息系统的数学模型。自动机可按其变量集和函数的特性分类,也可按其抽象结构和联结方式分类。主要有:有限自动机和无限自动机、线性自动机和非线性自动机、确定型自动机和不确定型自动机、同步自动机和异步自动机、级联自动机和细胞自动机等。
这可能有你想要的答案
./question/7218281?fr=qrl3
问题九:编译原理中"(E)"表示什么 字符( 表达式 字符)
‘叁’ 求解编译原理的一道题:设有文法如下
首先要做这题你要知道判别文法类型
包括四个层次:
0-型文法(无限制文法或短语结构文法)包括所有的文法。该类型的文法能够产生所有可被图灵机识别的语言。可被图灵机识别的语言是指能够使图灵机停机的字串,这类语言又被称为递归可枚举语言。注意递归可枚举语言与递归语言的区别,后者是前者的一个真子集,是能够被一个总停机的图灵机判定的语言。
1-型文法(上下文相关文法)生成上下文相关语言。这种文法的产生式规则取如 αAβ -> αγβ 一样的形式。这里的A 是非终结符号,而 α, β 和 γ 是包含非终结符号与终结符号的字串;α, β 可以是空串,但 γ 必须不能是空串;这种文法也可以包含规则 S->ε ,但此时文法的任何产生式规则都不能在右侧包含 S 。这种文法规定的语言可以被线性有界非确定图灵机接受。
2-型文法生成上下文无关语言。这种文法的产生式规则取如 A -> γ 一样的形式。这里的A 是非终结符号,γ 是包含非终结符号与终结符号的字串。这种文法规定的语言可以被非确定下推自动机接受。上下文无关语言为大多数程序设计语言的语法提供了理论基础。
3-型文法(正规文法)生成正规语言。这种文法要求产生式的左侧只能包含一个非终结符号,产生式的右侧只能是空串、一个终结符号或者一个非终结符号后随一个终结符号;如果所有产生式的右侧都不含初始符号 S ,规则 S -> ε 也允许出现。这种文法规定的语言可以被有限状态自动机接受,也可以通过正则表达式来获得。正规语言通常用来定义检索模式或者程序设计语言中的词法结构。
正规语言类包含于上下文无关语言类,上下文无关语言类包含于上下文相关语言类,上下文相关语言类包含于递归可枚举语言类。这里的包含都是集合的真包含关系,也就是说:存在递归可枚举语言不属于上下文相关语言类,存在上下文相关语言不属于上下文无关语言类,存在上下文无关语言不属于正规语言类。
1)本题应该是--上下文无关文法
句子是产生式在推导时“仅仅有终结符”的任何一步
2)%mm%nn 是一个句子
由于下面一题的图我等级不够 不能贴图 发你邮箱
‘肆’ 编译原理里,什么是源语言,什么是目标语言,什么是翻译器,什么是编译器,什么是解释器,什么是T形图
在vc 将c/c++代码翻译成asm文件的过程中
c/c++ 是源语言 asm是目标语言 vc是翻译器
vc将asm在编译成 obj文件 最后于库文件链接成 二进制文件 vc就是编译器
java中 需要跑一个 java虚拟机 比如 sun的 java.exe java.exe就是解释器
c语言 a机器 c语言 b机器 C语言 b机器
a机器 c语言 a机器
图a 图b 图c
在上图中,图(a)为已有的编译程序,图(c)为需要得到的编译程序,图(b)为需要书写的编译程序,只要我们把(b)在(a)上编译就可得到(c)
打个比方
编译器a是已有的在intel主机上将c语言翻译成可在intel主机上运行的编译器 我们希望得到在intel机器上运行的将c语言翻译成可在苹果主机上运行的编译器c 那么我们只需要用c语言写一个将c语言翻译成可在苹果主机上运行的编译器b, 在编译器a上编译c语言写的编译器b 就可以得到编译器c
‘伍’ 解释型语言和编译型语言的区别是什么
一、编译型
编译型语言:编译型语言在执行之前要先经过编译过程,编译成为一个可执行的机器语言的文件,比如exe。因为翻译只做一遍,以后都不需要翻译,所以执行效率高。
编译型语言的典型代表:C语言,C++。
编译型语言的优缺点:执行效率高,缺点是跨平台能力弱,不便调试。
二、解释型
解释型语言:解释性语言编写的程序不进行预先编译,以文本方式存储程序代码。执行时才翻译执行。程序每执行一次就要翻译一遍。
代表语言:python,JavaScript。
优缺点:跨平台能力强,易于调,执行速度慢。
编译型与解释型,两者各有利弊
前者由于程序执行速度快,同等条件下对系统要求较低,因此像开发操作系统、大型应用程序、数据库系统等时都采用它,像C/C++、Pascal/Object Pascal(Delphi)等都是编译语言。
而一些网页脚本、服务器脚本及辅助开发接口这样的对速度要求不高、对不同系统平台间的兼容性有一定要求的程序则通常使用解释性语言,如Java、JavaScript、VBScript、Perl、Python、Ruby、MATLAB等等。
‘陆’ 求编译原理的名词解释题
词法分析(Lexical analysis或Scanning)和词法分析程序(Lexical analyzer或Scanner)
词法分析阶段是编译过程的第一个阶段。这个阶段的任务是从左到右一个字符一个字符地读入源程序,即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。
语法分析(Syntax analysis或Parsing)和语法分析程序(Parser)
语法分析是编译过程的一个逻辑阶段。语法分析的任务是在词法分析的基础上将单词序列组合成各类语法短语,如“程序”,“语句”,“表达式”等等.语法分析程序判断源程序在结构上是否正确.源程序的结构由上下文无关文法描述.
语义分析(Syntax analysis)
语义分析是编译过程的一个逻辑阶段. 语义分析的任务是对结构上正确的源程序进行上下文有关性质的审查, 进行类型审查.例如一个C程序片断:
int arr[2],b;
b = arr * 10;
源程序的结构是正确的.
语义分析将审查类型并报告错误:不能在表达式中使用一个数组变量,赋值语句的右端和左端的类型不匹配.
Lex
一个词法分析程序的自动生成工具。它输入描述构词规则的一系列正规式,然后构建有穷自动机和这个有穷自动机的一个驱动程序,进而生成一个词法分析程序.
Yacc
一个语法分析程序的自动生成工具。它接受语言的文法,构造一个LALR(1)分析程序.因为它采用语法制导翻译的思想,还可以接受用C语言描述的语义动作,从而构造一个编译程序. Yacc 是 Yet another compiler compiler的缩写.[回页首]
源语言(Source language)和源程序(Source program)
被编译程序翻译的程序称为源程序,书写该程序的语言称为源语言.[回页首]
目标语言(Object language or Target language)和目标程序(Object program or Target program)
编译程序翻译源程序而得到的结果程序称为目标程序, 书写该程序的语言称为目标语言.[回页首]
中间语言(中间表示)(Intermediate language(representation))
在进行了语法分析和语义分析阶段的工作之后,有的编译程序将源程序变成一种内部表示形式,这种内部表示形式叫做中间语言或中间表示或中间代码。所谓“中间代码”是一种结构简单、含义明确的记号系统,这种记号系统复杂性介于源程序语言和机器语言之间,容易将它翻译成目标代码。另外,还可以在中间代码一级进行与机器无关的优化。
[回页首]
文法(Grammars)
文法是用于描述语言的语法结构的形式规则。文法G定义为四元组(,,,)。其中为非终结符号(或语法实体,或变量)集;为终结符号集;为产生式(也称规则)的集合;产生式(规则)是形如或 a ::=b 的(a , b)有序对,其中(∪)且至少含有一个非终结符,而(∪)。,和是非空有穷集。称作识别符号或开始符号,它是一个非终结符,至少要在一条规则中作为左部出现。
一个文法的例子: G=(={A,R},={0,1} ,={A?0R,A?01,R?A1},=A) [回页首]
文法分类(A hierarchy of Grammars)
着名语言学家Noam Chomsky定义了四类文法和四种形式语言类,文法的四种类型分别是0型、1型、2型和3型。几类文法的差别在于对产生式施加不同的限制,分别是:
0型文法(短语结构文法)(phrase structure grammars):
设G=(,,,),如果它的每个产生式是这样一种结构: (∪) 且至少含有一个非终结符,而(∪),则G是一个0型文法。
1型文法(上下文有关文法)(context-sensitive grammars):
设G=(,,,)为一文法,若中的每一个产生式均满足|,仅仅 除外,则文法G是1型或上下文有关的。
2型文法(上下文无关文法)(context-free grammars):
设G=(,,,),若P中的每一个产生式满足:是一非终结符,(∪) 则此文法称为2型的或上下文无关的。
3型文法(正规文法)(regular grammars):
设G=(,,,),若中的每一个产生式的形式都是A→aB或A→a,其中A和B都是非终结,a是终结符,则G是3型文法或正规文法。
0型文法产生的语言称为0型语言。
1型文法产生的语言称为1型语言,也称作上下文有关语言。
2型文法产生的语言称为2型语言,也称作上下文无关语言。
3型文法产生的语言称为3型语言,也称作正规语言。
‘柒’ 四种文法的类型(编译原理)
乔姆斯基(Chomsky)按产生式的类型把文法分为四种类型:0、1、2、3型文法。
*在下文中的产生式中,箭头左边的大写字母为严格的非终结符,而其左边的小写字母不严格要求为非终结符,如[0型文法]中的第2条产生式。
【0型文法】
产生式形式:α→β
要求:箭头左边的α 至少 含有 一个非终结符 , 其余 不加任何限制
例如,G:C→AaB
aA→a
B→b|Bb
【1型文法】
产生式形式:α→β
要求: |α|≤|β| (产生式左端的长度<=右端的长度),S→ε除外。
例如G: C→aAB
aA→aBa
B→b|Bb
【2型文法】(上下文无关文法)
产生式形式:A→β,A∈VN(终结符) ,β∈V *(VN∪VT,即可为终结符也可为非终结符)
说明:当以β替换A时,与A的上下文环境无关;
大部分程序设计语言近似于2型文法。
【3型文法】(正规文法 / 右线性文法)
产生式形式:A→a,A→aB,
说明:a∈VT(终结符) , A,B∈VN(非终结符),即产生式右端的第一个符号必须为 终结符
例如 G:A→aB
B→b|bB
【其他说明】对于这四种类型的文法:
*包含关系:0 > 1 > 2 > 3 (以'>'代替包含符,'A>B'译为A包含B)
*严格程度:3 > 2 > 1 > 0
*判断文法所属类型的顺序:3 → 2 → 1 → 0
‘捌’ 编译原理中的一概念:什么是左线性正规文法
正规文法是左线性文法和右线性文法的统称.它们都是Chomsky分类下的3型文法.由正规文法产生的语言称为正规集.下面我们将会看到,这里之所以用“正规”二字为一种语言命名,是因为这种语言的结构可以用所谓正规式来描述.
1.右线性文法
设G[S]=(VN,VT,P,S)为CFG,若P中的产生或均有如下的形式:
A→aB或A→a(A∈VN,a∈VT)
则称G为右线性文法.例如,文法
G1[S]=({S,A,B},{a,b},P1,S)
其中
P1={S→aA,A→aA,A→bB,A→b,B→bB,B→b}
为一右线性文法,G1所产生的正规集为
L(G1)={aibj |i,j≥1}
2.左线性文法
若一个文法G[S]=(VN,VT,P,S)中的产生式均有如下的形式:
A→Ba或A→a(A,B∈VN,a∈VT)
则称G为左线性文法.例如,文法
G2[S]=({S,A},{a,b},P2,S)
其中
P2={S→Sb,S→Ab,A→Aa,A→a}
为一左线性文法,且有
L(G2)=L(G1)={aibj |i,j≥1}
请注意,虽然文法
G3[S]=({S,A,B},{a,b},P3,S)
其中
P3={S→aA,A→aA,A→Bb,A→b,B→Bb,B→b}
也同样产生语言{aibj |i,j≥1},但由于G3中同时含有左线性产生式和右线性产生式,故G3不是正规文法.
另外
P4={S-->aA,A-->ab},
也不是正规文法
‘玖’ 编译原理中的语法和文法一样吗
编译原理中的语法和文法是不一样的,但却融会贯通。
在计算机科学中,文法是编译原理的基础,是描述一门程序设计语言和实现其编译器的方法。
文法分成四种类型,即0型、1型、2型和3型。这几类文法的差别在于对产生式施加不同的限制。
形式语言,这种理论对计算机科学有着深刻的影响,特别是对程序设计语言的设计、编译方法和计算复杂性等方面更有重大的作用。
多数程序设计语言的单词的语法都能用正规文法或3型文法(3型文法G=(VN,VT,P,S)的P中的规则有两种形式:一种是前面定义的形式,即:A→aB或A→a其中A,B∈VN ,a∈VT*,另一种形式是:A→Ba或A→a,前者称为右线性文法,后者称为左线性文法。正规文法所描述的是VT*上的正规集)来描述。
四个文法类的定义是逐渐增加限制的,因此每一种正规文法都是上下文无关的,每一种上下文无关文法都是上下文有关的,而每一种上下文有关文法都是0型文法。称0型文法产生的语言为0型语言。上下文有关文法、上下文无关文法和正规文法产生的语言分别称为上下文有关语言、上下文无关语言和正规语言。