注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

widebright的个人空间

// 编程和生活

 
 
 

日志

 
 

编译器文法的“Syntactic predicate”,规则的运行时前置条件判断  

2014-10-21 16:08:25|  分类: 程序设计 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
假设有一个类似c语言的结构定义,但没有大括号作为结构的分界,而是后面接一个子成员个数来描述的结构。

比如有类似下面这个结构嵌套的定义。
定义了两个结构和a 和c, 其中 d 和e 属于 结构c的成语。
b 和 c ,e又属于结构a的成语。  struct3表示有3个成语, struct2表示有两个成语。
----------------------
struct3 a
     int b;
     struct2  c;
             int d;
             int e;
     int e;

-------------------
如果我们写简单的文法表示如下

struct_size:  int

member_list: member
           : member_list member

struct:  "struct"  struct_size member_list

---------------------
那这个文法并不能消除歧义, 编译器处理到 int e; 时,怎么知道 e 是 c还是 a 的子成员呢。
这个只能运行时根据   struct 后面的struct_size数字来决定,所以这里必须有另外的规则来清楚的指定
编译器怎么处理这种歧义。  通常的 “优先级”和结构转换的方法并不能消除这种歧义。

不过好的是各种编译器生成程序都提供了这个功能,可以指定规则的前置条件。
这个叫做 “Syntactic predicate”ANTLR 和bison都提供了类似的语法支持。
------------------------------------
struct_size:  int

member_list: member
           : %?{member_list .size() < member_list.struct_size() } member_list member

struct:  "struct"  struct_size member_list

-------------------------------
意思就是只有 %?{member_list .size() < member_list.struct_size() } 这个前置条件成立了,这一条rule才

会成立。  这个条件是嵌入一段代码,这样就可以运行时才选择某条规则执行了。


大概就是这样子吧,不过感觉理解不是很清楚。
参考下面这些文档: 





Compilers and Compiler Generators
an introduction with C++ 
? P.D. Terry, Rhodes University, 1996 
5.11 Formal treatment of semantics 
===================================


"static semantics"
"dynamic semantics"

When specifying semantics a distinction is often attempted
between what is termed "static semantics" - features which, in effect, mean something that can be
checked at compile-time, such as the requirement that one may not branch into the middle of a
procedure, or that assignment may only be attempted if type checking has been satisfied - and
"dynamic semantics" - features that really only have meaning at run-time, such as the effect of a
branch statement on the flow of control, or the effect of an assignment statement on elements of
storage. 





operational semantics 

attribute grammars,

in which the syntactic description (in terms
of EBNF) is augmented by a set of distinct attributes V (each one associated with a single 

terminal
or non-terminal) and a set of assertions or predicates involving these attributes, each assertion 

being
associated with a single production. 

-----------------------------



Syntactic predicate
===================
http://en.wikipedia.org/wiki/Syntactic_predicate
有点类似perl的正则匹配的条件表达式,

ANTLR   支持这个,这里给出的例子也比较容易理解。
https://theantlrguy.atlassian.net/wiki/display/ANTLR4/Semantic+Predicates




bison的 Arbitrary Predicates
==========
bison的 GLR parsers语法支持类似的条件判断 “Predicates”
http://www.gnu.org/software/bison/manual/bison.html#Semantic-Predicates
1.5 Writing GLR Parsers
1.5.4 Controlling a Parse with Arbitrary Predicates




Parsing expression grammars (PEGs)  predicates
==================================

boost.spirit的文档
http://www.boost.org/doc/libs/1_48_0/libs/spirit/doc/html/spirit/abstracts/syntax_diagram.html#spi

rit.abstracts.syntax_diagram.predicates


  评论这张
 
阅读(470)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017