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

东南隅

wantnon的blog

 
 
 

日志

 
 
 
 

编译原理(上)—文法概念,词法分析,语法分析  

2009-12-04 01:01:38|  分类: 算法/程序 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

文法和语言:

文法就是一个产生式集合,利用这些产生式从开始符号开始推导生成诸多句子(终结符序列),所有这些句子构成的集合称为此文法生成的语言。

文法的等价:

同一个语言可由多个形式上不同的文法生成。生成相同语言的文法称为是等价的。 

互相等价的文法之间性能是有差异的,例如:有些无二义性,有些有二义性;有些无左递归性,有些含左递归;有些是LL(k)文法,有些不是LL(k)文法。而上述性质的有无对建立语法分析程序来说是至关重要的,所以,设计好语言后,需选择适当的文法才能保证语法分析程序的正确、高效实现。

句子与句型:

由产生式推导出的所有元素都是终结符的串,称为句子。
由产生式推导出的含有非终结符的串,称为句型。

文法的二义性:

如果一个文法的两种不同推导能得出相同的句子,则称此文法是二义性的。
注:由于左递归文法在推导过程中增加递归次数不改变所得句子(即同一句子有多种推导),所以左递归文法是二义性文法。

上下文无关文法与上下文有关文法:

上下文无关文法:如果文法的每个产生式左侧均只有一个非终结符,则此文法称为上下文无关文法。于是对非终结符进行改写时无需考虑其周围环境(上下文)。

上下文有关文法:如果文法中存在某产生式左侧包含多个符号,则此文法称为上下文有关文法。于是对非终结符进行改写时就需要考虑其所处上下文环境。

不难看出,一个上下文有关文法可以放宽成一个上下文无关文法,即:上下文有关文法可以看作是在其相应的上下文无关文法上附加了一些限制而得。在词法分析和语法分析阶段,只使用上下文无关文法,只是在语义分析阶段才附加限制(如类型检查等)使其最终呈现为上下文有关。

编译器的工作流程:

词法分析->语法分析->语义分析->代码优化及生成

(1)词法分析:是识别出源程序中的所有单词,即词法分析器以源程序(字符串)为输入,输出单词流。

构造一个词法分析器,首先要列出所有要识别单词的正则表达式,然后将其转化成NDFA(非确定性有限状态自动机),再经消除空循环,消除空转化及确定化(利用子集构造算法),从而得到等价的DFA(确定性有限状态自动机),(对于简单情况,上面这些步骤用笔算即可)。总之,一旦得到DFA,然后只要在计算机上实现此DFA即得到词法分析器。注:由于以上各步骤均有固定的算法,故完全可以实现自动化,所以存在一些现成工具可以直接根据用户提供的正则表达式自动生成词法分析器。

(2)语法分析:在词法分析得到的单词流的基础上,进一步识别出程序的结构—即构建语法树。

语法分析手工实现通常用递归下降分析法,算法如下:

对于非终结符节点:
  if(只有一个产生式可用)
     直接选用此产生式;//即LL(0)情况
     进入下一层;
  else//有多个产生式可用
     超前看k单词从而确定出应该选用哪个产生式;//即LL(k)情况
     (如果超前单词不匹配任何候选产生式,报错)//此句也可不写,将发现错误
                                                                  //留给终结符节点来发现
     进入下一层;
  end
对于终结符节点:
  if(当前单词与本终结符匹配)
     阅读头移动到下一个单词;
     返回上一层;
  else//不匹配
     说明文法不接受该输入,报错;
     中断;
  end

其中k可以是1,2,3…。如果对于一个具体文法,其递归下降分析算法中的k最大为1即可完成(无歧义)识别,则此文法称为LL(1)文法。同理,如果某文法的递归下降算法中k最大需为2才能完成识别,则此文法称为LL(2)文法。更极端的例子:如果某文法的递归下降分析算法中可以根本不出现此else分支,则其为LL(0)文法。

之所以有时需要超前看k个字符,是为了消出歧义,唯一确定下一步产生式。

文法是LL(k)文法的充要条件:
对于每个非终结符A,其各产生式的firstk集与followk集的笛卡尔积(selectk集)不相交。(其中的非终结符A称为LL(k)终结符)。
注:此结论为显然,但要注意:之所以要考虑follow集是因为某些first串的长度可能不足k。换句话说,如果你能保证非终结符A所产生的句子长度均不小于k,则只要其各产生式的firstk集不相交即可断定A为LL(k),而无需考虑followk集。事实上有:若firstk中所有元素长度均不小于k,则selectk=firstk×followk=firstk。

显然LL(k)文法是无二义性的文法(推导过程中每一步最多超前看k可单词即可消除歧义,选择出唯一的产生式),而前面说过左递归文法是二义性文法,所以LL(k)必定不含左递归。

公共左因子:非终结符A的多个产生式的右边如果有相同部分,称为公共左因子。
某些(但不是全部)非LL(k)文法可以通过提取公共左因子转化成LL(k)文法。
对于已经是LL(k)文法的文法,通过提取公共左因子有可能使k值减小。

LL(k)文法的分析程序很容易实现,但如何构造给定语言的LL(k)文法(换句话说,将产生特定语言的非LL(k)文法转化为LL(k)文法)却需要一定的技巧。

通常的编译器都采用LL(1)文法(局部可能是LL(0)的)。

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

历史上的今天

评论

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

页脚

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