woaidongmao

文章均收录自他人博客,但不喜标题前加-[转贴],因其丑陋,见谅!~
随笔 - 1469, 文章 - 0, 评论 - 661, 引用 - 0
数据加载中……

EBNF CONVERT TO BNF

背景: 
Yacc
JavaCup等工具都是基于BNF(类似于BNF的形式),
EBNF
 需要转化为 BNF,
或者说是转化为适用于JavaCup的语法形式.

说明: 
EBNF
和 BNF的主要区别:
 1. {} 重复,0至n
2. []
可选,0或1次


规则: 
.形如: 
S
 = { A } ; 
   转化为:
S
 = A' ;
A' = A A' | ;
 


2.
形如:
S = [ A ] ;
转化为:
S = A' ;
A' =
 A | ; 


3.
形如:
S
 = ( A ) ;
转化为:
   S = A' ;
A' = A ;


实例: 
已知某程序语言的EBNF片断,如下:
declarations = ["CONST" {identifier "=" expression ";"}]
["TYPE" {identifier "=" type ";"}]
["VAR" {identifier_list ":" type ";"}]
{procedure_declaration ";"} ;


首先看到有3[],4{}.
引入7个新的非终结符:
OPTION_1,OPTION_2,OPTION_3,
REPEAT_1,REPEAT_2,REPEAT_3,REPEAT_4.




根据规则:
1.
首先有:
declarations
 = OPTION_1 OPTION_2 OPTION_3 REPEAT_1 ;
2.
接着定义新的产生式:
OPTION_1 = "CONST" REPEAT_2 | ;
OPTION_2 = "TYPE" REPEAT_3 | ;
OPTION_3 = "VAR" REPEAT_4 | ;
REPEAT_1 = procedure_declaration ";" | REPEAT_1;


若以上产生式右部存在没有定义的非终结符,接着引入定义,否则,结束.
REPEAT_2 = identifier "=" expression ";" REPEAT_2 | ;
REPEAT_3 = identifier "=" type ";" REPEAT_3 | ;
REPEAT_4 = identifier_list ":" type ";" REPEAT_4 | ;


   所有非终结符已定义,结束.

 

posted on 2009-09-10 12:57 肥仔 阅读(1460) 评论(0)  编辑 收藏 引用 所属分类: LEX & YACC


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理