LR语法分析器构造方法初探

《LR语法分析器构造方法初探》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据科技论坛中国科技信息2005年第15期CHINASCIENCEANDTECHNOLOGYINFORMATIONAug．2005LR语法分析器构造方法初探付争方张海娟摘要：语法分析是编译程序的重要组成部分，自下而上分析是语法分析的一种常用方法。语法分析器的自动构造主要采用上下文无关文法的自上而下分析程序的自动构造，这些分析程序统称为LR分析程序。大多数用上下文无关文法描述的程序都可用LR分析器予以识别，LR分析法在自左至右扫描输入串时能发现其中的错误，并能准确地指出错误的地点。本文就如何构造一个合适的LR语法分析器，对给定的文法G

2、判定输入串是否为该文法的合法句子进行一些探讨。关键词：文法；语法；自下而上；分析器；活前缀；项目集；1。引言十F—T—T+．F—T—T}F．突是sLR(1)分析器所不能解决的．需要建立LR语言从语法分析角度来看，是一个句子的3．1．3，拓广文法(1)分析器．例：文法G：S—L-RS—RL集合，句子是词法分析器返回的记号组成的非拓广文法是为了使最后构造出的识别文法一}RL—IR—L中，S—L-RS—RR线性结构，反映句子结构的最好办法是树，常G活前缀的DFA有唯一的接受状态，可以引入一—L如果L移进了，而后来输入流中却没有使它用的是分析树

3、和语法树。自下而上的分析采用个新的产生式s1一s，生成一个拓广文法G1．能最终归约为开始符，而输入流本身可能是合法的方法是归约，从叶子到根构造分析树，或这样，就可以Gl的项目集：的。者从句子开始归约出文法的开始符号。自上而E’—-．EE1—+E．3．3．2，构造LR(1)分析表的方法下分析中最一般的方法一一LR方法。E一．E—TE—E．一TE—E一．TE—E—T．①对于每个项目集采用10中的项卧A——>2，LR分析器E一．TE—T．0【．HD，a】，若G0[Ii，H】=Ii，则IFHEVTT一．T十FT—T．}FT—T}．FT—T}F．

4、THENaction[i，H】=SiELSE[HEVr】，GOTOLR分析是自下而上的分析。即从输入流T一．FT—F．【i，H]爿．开始，根据文法的规则，从语法树的下部通F一．idF—id．②若归约项目【A0【，a】EIi，A——>c【过无回溯的移进归约，最终通过能否推出开始如果文法有明显的下一步分析，而以此是第j产生式，则action[i，a]=rj；符号来判断输入流是否合法。DFA为基础就可以构造出不含多重从定义的分③若[IS’——>S．，#]EIi，则action[i，2．1，LR分析器定义析表，根据它的定义就可以得出文法是LR#

5、]．“ace”(4)其它ERR．对于文法G而言，若按若为文法G构造移进／归约分析表中不含(0)文法，根据分析表设计出的分析器就是上述的方法构造的分析表不含多重定义的元素，多重定义的条目，则称G为LR(k)文法，分LR(0)分析器。然而，多数情况下项目则称此分析表为LR(1)分析表，凡具有LR(1)析器被称为是LR(k)分析器，它所识别的语言集的下一步都是不确定的，会出现移进／归约分析表的文法称LR(1)的文法。被称为LR(k)语言。L表示从左到右扫描输入和归约／归约冲突。3．4，LALR分析器序列，R表示逆序的最右推导，K表示为确定例：

6、E—T．LALR分析表比规范LR分析表小得多，能下一动作向前看的终结符个数，一般情况下KT—T．+F这就是移进／归约的冲突，到力也不如规范LR分析表，但它却能处理SLR<=1，当K=l时，也简称为LR。底是移进还是归约就无法判断了。这时就要用不能解决的情形。但LALR和LR(1)分析器功2．2，LR分析的特点：SLR(1)文法来解决了。能相近，只是在分析表的构造上将同心集合并为(1)．采用最一般的无回溯移进——归约方法；3．2，SLR(1)分析器一，将其压缩为较小的DFA，若压缩过程并不(2)．可分析的文法是LL文法的真超集；SLR(1

7、)分析器也称SLR分析器，其中S是会带来新的冲突，则分析表大大简化了I状态数，(3)．能够及时发现错误，快到从左到右扫描输简单的意思，在它工作时可以根据简单向前看按照新DFA构造LALR分析表。入序列的最大可能；一个终结符来确定下一步动作。4。几种LR分析器的区别：(4)．分析表较复杂，难以手工构造．假定LR(0)规范族的一个项目集I中含有inLR分析器根据分析表构造的不同，可以有2．3，LR分析器根据分析表构造的不同，可个移进项目，则隐含的动作冲突可通过检查现LR(0)，SLR(1)，LALR(1)，LR(1)分析器。它们功以有LR(

8、0)，SLR(1)，LALR(1)，LR(1)分析器，它们行输入符号a属于某个集合而解决，这种解决能的强弱和构造的难度依次递增。LR(0)分析功能的强弱和构造的难度依次递增。冲突性动作的方法称SLR(1)解