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

天地不仁,以万物为Googol!

天行有常,不以物喜,不以己悲……

 
 
 

日志

 
 

对上下文敏感的C语法  

2007-11-24 23:15:43|  分类: 翻译 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
我相信你们没有忘记我写的这篇文章,虽然你们可能没看过……

今天正好逛rss,发现了这个。鉴于此文更加详细的讲解了C语法的……呃……弱点,特翻译全文,留作纪念。文中有n多Wiki链接,我全部保留。鉴于某些特色原因,请翻墙。

上下文无关语法(CFGs,注:或许你认识每个字,但就是不认识这个词——其实很长时间内我也是这样——不过这篇文章讲的很细,相信看完后会对这个词有个感性的认识——但我确实是在这篇文章前理解这个词的。)是个极有价值的理论工具,现代编译原理依靠这个工具来解析程序语言的代码。比如,用于解析的最流行的工具——YACC,就可以生成CFGs的解析器。但大部分人并不知道,绝大部分主流的程序语言的语法,并不是上下文无关的。

C就是个非常好的例子。因为这是目前使用的最流行的语言,也因为C的语法几乎是上下文无关的,因此,它特别适合用来展示我想讲的东西。

现在,CFGs有好几种定义,分别和学术语言与程序语言相关(看来“上下文无关语法”的定义不是上下文无关的……)。关于这个名字,我不想做太多的考证,不过这里有一群聪明的家伙在讨论这个。当我说C的语法不是CFGs的时候,我的意思是说,仅仅提供语法规则给YACC,不足以正确解析C,除非再从别的地方得到些关于上下文信息做参考。举几个例子。

比如这段代码:
{
    T (x);
    ...
}

不管你信不信,如果将T看做一个类型,这在C里是一个合法的声明:声明x为类型T的实例。不过,如果T不是个已知类型,这句话的意义就变成了:调用函数T,并用x作为其参数。如何在不知道T是否在前面已经由typedef定义为一个类型的情况下,让C解析器决定用哪种方法解释上面的代码呢?

我听到你说“但这太做作了!谁会这么写代码呢?”(确实,谁会这么定义一个变量啊,不过……这个呢:“T (*x)()”?)好吧,看些更加常见的:
{
    T * x;
    ...
}

这是什么?声明x是一个指向类型T实例的指针,还是一个忽略结果的乘法(变量T和x相乘)?除非在内存中保存一个由typedef声明的类型表,否则不可能知道答案。解析器并不会去构建这个表——这个表就是属于上下文敏感信息。(唉,何必非要用*呢?用@作为指针解引用的标识,不就没问题了。虽然这个无法解决上一个问题……)

另一个例子:
func ((T) * x);

如果T是个类型,解析结果是对x解引用,并转换成类型T并传给函数func。如果T不是类型,则将T与x相乘的结果传给func。(C++用static_cast<>()来解决强转的问题。)

在这些例子里,解析器都会因为由于在接触到有问题的声明前,缺少部分代码里的信息而解析失败。因此,如果不混入一些上下文敏感信息,C不能由YACC语法解析。这个问题在C编译器社区有一个正式的名字——“typedef后的名字:标识符”(typedef-name: identifier)问题。甚至K&R第二版里都在描述C语法的附录里提到了这个问题:

未来可能会做一些改动,也就是删去造成“typedef-name: identifier”的因素并且将typedef-name做为终端符号。这种语法是可以被YACC解析生成器接受的。(With one further change, namely deleting the production typedef-name: identifier and making typedef-name a terminal symbol, this grammar is acceptable to the YACC parser-generator.这段太xx的难译了!)

所以,正像你看到的,C里CFGs语法已经非常接近了,但还没有达到。幸好,这个问题很好解决。只要保持一个由typedef定义的类型符号表,就能顺利解析了。当语法解析器遇到一个新标识时,它将检查这个标识是否是个类型,并返回正确的标志(token,这词在计算机里的意思只能意会,不能言传……)给解析器。对解析器而言,标识只有两个明确的含义——一个标识符或者一个类型。剩下的就是在成功解析完一个typedef语句的时候,更新符号表。为了更好的演示一下这个办法是如何工作的,我来展示一下来自c2c的关于语法解析的一部分代码。这是一部分Lex文件:
identifier ([a-zA-Z_][0-9a-zA-Z_]*)

<INITIAL,C>{identifier}
  {
    GetCoord(&yylval.tok);
    yylval.n = MakeIdCoord(UniqueString(yytext), yylval.tok);
    if (IsAType(yylval.n->u.id.text))
      RETURN_TOKEN(TYPEDEFname);
    else
      RETURN_TOKEN(IDENTIFIER);
  }

我不会在这里讲太多的Lex语法,这段代码的基本意思是每当找到一个标识,就测试它是不是一个类型。如果是,就返回TYPEDEFname标识符,否则就返回IDENTIFIER标识符。对YACC语法来说,这是两种不同的终端类型。

OK。我终于译完了。发现我总挑些简单的译,嘿嘿。C#/java由于取消了指针,所以应该不会存在这种“typedef-name: identifier”的问题吧。C++由于引入了模板,反而增大了non-CFGs的语法……
  评论这张
 
阅读(582)| 评论(6)
推荐 转载

历史上的今天

评论

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

页脚

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