分享
 
 
 

从lex&yacc说到编译器(3.范式文法)

王朝other·作者佚名  2006-01-08
窄屏简体版  字體: |||超大  

从lex&yacc说到编译器(3.范式文法)

作者:tangl_99

QQ:8664220

msn:tangl_99@hotmail.com

email:tangl_99@sohu.com

从这一节开始,我们就算进入编译器构造的正题了.不得不说,前面的词法扫描器在整个编译器部分只是个很小很小的组成,而这两节讲述的语言构造器才能真正为我们的编译工作起到重要的作用.这些东西相信大家在大学的编译原理的课程已经学了不少,那么本文我也只是大致地带过,让大家回忆起大学的知识,重要的yacc使用技巧等等,我将在后面的内容讲出.

例3.1

exp -> exp op exp | (exp) | number

op -> + | - | *

这里就是一个定义的带有加法,减法,乘法的简单整数算术表达式的文法.其中粗体表示的是终结符号,也就是不能有产生式生成的符号.而exp,op就是非终结符,它们都是由一个”->”符号来产生的.

比如100 + 222 *123123 –(888+11)就是符合上述文法的具体的表达式.

注意,在文法定义中,是可以递归的.所以exp产生式右边的式子中可以再次出现exp.

这里的|和正则表达式一样,表示的选择的意思,也就是说,exp可以是exp op exp或者(exp)再或者number.

下面让我们看看<<编译原理及实践>>书中的一个关于BNF文法的介绍.

比如说我们有个数学表达式(34-3)*42,然后我们来看看上面的exp文法怎么来推导识别它.

(1) exp => exp op exp [exp ->exp op exp]

(2) => exp op number [exp ->number ]

(3) => exp * number [op -> * ]

(4) => (exp) * number [exp ->(exp) ]

(5) => (exp op exp) * number [exp ->exp op exp]

(6) => (exp op number)* number [exp -> number ]

(7) => (exp – number) * number [op -> - ]

(8) => (number–number)* number [exp -> number ]

最终,exp里面全部的非终结符号全部变成了终结符号.那么推导完成.

这种推导十分像我们在离散数学中讲到的命题推理.其实形式语言的推导的数学基础就是我们离散数学的命题推理.

在推导过程中,其实就是把原来的文法中的递归展开.那么我们在推导的过程,也就很容易实现分析树的生成.而分析树就是我们编译程序中十分重要的信息源.我们之所以前面又做词法分析,又做语法分析的目标就是为了生成分析树.有了它,我们编译程序在后面的代码生成过程中将变得容易百倍.

请看:

例3.2

同样是<<编译原理及实践>>书上的例子.

设E -> E+a | a 表示的文法为G,那么考虑它生成的表达L(G)

如果由标准的数学定义,那么我们用公式L(G)={s | exp =>* s }表示一种文法G.

s代表记号符号的任意数组串,也就是我们的终结符号.而exp代表非终结符号,=>*表示一系列的从非终结符到终结符号的推导过程.这里*有点像我们在讲述正则表达式中的*符号一样,它表示0到无限次的重复.所以=>*就是表示0次到无限次的推导过程.

L(G) = {a,a+a,a+a+a,a+a+a+a,…}

E => E+a => E+a+a => E+a+a+a

同时,在我们的编译课本上,又经常讲述另一种数学表达方式来阐述文法的定义.

G=(T,N,P,S)

注意,这里的T,N,P,S都是集合.

T表示终结符号(terminal),也就是这里{a,+}

N表示非终结符号(nonterminal),也就是这里{E},但是N不能与T相交.

P表示产生式(production)或者文法规则(grammar rule)的集合,这里它只有一个元素: E -> E+a

S表示集合N的开始符号(start symbol).关于S,本人也搞不清楚它的用处,所以很抱歉!

例3.3

这是我们C程序语言中经常使用if else文法

statement -> if-stmt | other

if-stmt -> if (exp) statement | if (exp) statement else statement

exp -> 0|1

statement就是我们C语言中使用语句,它的产生式包括了两种可能,一是if-stmt语句,二是other.然后我们又另外定义if-stmt语句的产生式.这里有两种情况,一是没有else的,另外就是有else的.里面我们又使用了递归.if-stmt本来是包含在statement里面的,可是我们又在if-stmt的产生式中使用statement.正是因为文法中允许递归,所以它比起我们前面讲的正则表达式有更广泛的表示能力,但同时,文法的推导识别也更加法复杂.按照编译原理的书籍,一般讲完BNF文法后,就要重点讲解文法的推导算法.一共有两种,一是LL算法,自顶向下的算法,二是LR算法,自底向上的算法.LL算法比较简单,其中还有一种特殊的情况,就是我们下一节要讲的递归下降的算法.由于C语言中的函数本来就可以递归,那么实现这中递归下降的算法是十分简单的,而且对于我们一般的程序设计语言来说,虽然它的算法能力很弱,但是已经是足够用了.而关于LR的算法,那么就是一个大难题了.它的算法能力最强,但是实现起来十分困难,还好,已经有科学家为我们提供了yacc(或者叫bison)这个工具,可以来自动生成LR的文法推导算法.这就是我们一直在提到的yacc工具了.

回过头来,我们看看下面的程序

if(0) other else other

的分析树

思考: 为什么要把文法最终分析成树结构?

因为文法本身是递归的,而表示的递归的最好数据结构就是树,所以我们把文法弄成树结构后,后面在处理代码生成等问题上,也可以用递归来很容易地完成.

例3.4

这里我给出microsoft在msdn中对于C语言的statement的文法

注意,这里用:符号替代了我们前面产生式的->

statement :

labeled-statement

compound-statement

expression-statement

selection-statement

iteration-statement

jump-statement

try-except-statement /* Microsoft Specific */

try-finally-statement /* Microsoft Specific */

jump-statement :

goto identifier ;

continue;

break;

return expression opt ;

compound-statement :

{ declaration-list opt statement-list opt }

declaration-list :

declaration

declaration-list declaration

statement-list :

statement

statement-list statement

expression-statement :

expression opt ;

iteration-statement :

while ( expression ) statement

do statement while ( expression );

for ( expression opt ; expression opt ; expression opt ) statement

selection-statement :

if ( expression ) statement

if ( expression ) statement else statement

switch ( expression ) statement

labeled-statement :

identifier : statement

case constant-expression : statement

default : statement

try-except-statement : /* Microsoft Specific */

__try compound-statement

__except ( expression ) compound-statement

try-finally-statement : /* Microsoft Specific */

__try compound-statement

__finally compound-statement

2003-10-11

成都,四川大学

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
2023年上半年GDP全球前十五强
 百态   2023-10-24
美众议院议长启动对拜登的弹劾调查
 百态   2023-09-13
上海、济南、武汉等多地出现不明坠落物
 探索   2023-09-06
印度或要将国名改为“巴拉特”
 百态   2023-09-06
男子为女友送行,买票不登机被捕
 百态   2023-08-20
手机地震预警功能怎么开?
 干货   2023-08-06
女子4年卖2套房花700多万做美容:不但没变美脸,面部还出现变形
 百态   2023-08-04
住户一楼被水淹 还冲来8头猪
 百态   2023-07-31
女子体内爬出大量瓜子状活虫
 百态   2023-07-25
地球连续35年收到神秘规律性信号,网友:不要回答!
 探索   2023-07-21
全球镓价格本周大涨27%
 探索   2023-07-09
钱都流向了那些不缺钱的人,苦都留给了能吃苦的人
 探索   2023-07-02
倩女手游刀客魅者强控制(强混乱强眩晕强睡眠)和对应控制抗性的关系
 百态   2020-08-20
美国5月9日最新疫情:美国确诊人数突破131万
 百态   2020-05-09
荷兰政府宣布将集体辞职
 干货   2020-04-30
倩女幽魂手游师徒任务情义春秋猜成语答案逍遥观:鹏程万里
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案神机营:射石饮羽
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案昆仑山:拔刀相助
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案天工阁:鬼斧神工
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案丝路古道:单枪匹马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:与虎谋皮
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:李代桃僵
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案镇郊荒野:指鹿为马
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:小鸟依人
 干货   2019-11-12
倩女幽魂手游师徒任务情义春秋猜成语答案金陵:千金买邻
 干货   2019-11-12
 
推荐阅读
 
 
 
>>返回首頁<<
 
靜靜地坐在廢墟上,四周的荒凉一望無際,忽然覺得,淒涼也很美
© 2005- 王朝網路 版權所有