论文—简单优先文法.doc

简单优先文法分析设计一、摘要众所周知，翻译有两种方式：编译方式和解释方式，其中编译程序的主要功能是将源程序翻译成等价的目标程序,这个翻译过程一般可分为词法分析、语法分析、语义分析、中间代码生成、中间代码优化和目标代码生成等阶段来实现。 在众多阶段中，语法分析是相当重要的一部分，其任务是根据语言的语法规则把单词符号串分解成各类语法单位，如表达式、语句等。通过语法分析，可以确定整个输入符号串是否够成一个语法正确的程序。在本文中，我们将重点探讨语法分析部分的简单优先分析法。简单优先分析法是一种典型的自下而上的分析方法。自下而上分析法是从输入符号串出发，试图归约到文法的识别符号，或从下往上地为输入串构造一棵语法树。对这个“可进行归约的符号串”，在不同的自下而上分析方法中有着不同的称呼，在简单优先分析法中称之为“句柄”，而在算符优先分析方法中称之为“素短语”。关于简单优先文法分析器，主要分为三大部分：数据结构及界面的设置、优先关系矩阵的求解、符号串的分析。文法分析器使用VS2008编译器编译，主要是使用其强大的界面设计功能。由于水平有限，本文或许有不妥之处，敬请读者不吝指教。二、基本概念简单优先分析法对使用它的文法是有限制的，只有简单优先文法才能使用简单优先分析法。在介绍简单优先文法之前，我们先来看一下三种简单优先关系。LR，当且仅当文法中有以下形式的产生式：U:=LR。其中，L,R(VNVT)； ,(VNVT)*。LR，当且仅当文法中有以下形式的产生式：U:=WP且WL，PR。其 中，L,R(VNVT)；WVN；P(VNVT)；,(VNVT)*。有了上面三种优先关系的说明，我们再来看一下简单优先文法的定义。满足以下条件的文法称为简单优先文法：字母表中的任意两个符号之间之多存在一种简单优先关系；文法的任意两条产生式都没有相同的右部。如文法GS： S:=(R)|a，R:=T ，T:=S,T|S 是一种简单优先文法。下面我们再来看一下移进及规约。移进过程：将输入符号串从左到右逐个移进符号栈。规约过程：栈顶符号串与某一产生式右部相匹配成为可规约符号串时，将此符号串规约为一个非终结符，这个非终结符是该产生式左部符号。在简单优先分析法中，我们用三种优先关系来判断符号栈面临当前符号的操作时移进还是规约，若为前两种则为移进，第三种则为规约。而在规约过程中，我们用句柄来搜索用来规约的文法。 一个句型中的最左直接短语，称为该句型的句柄。一个句型的直接短语和句柄可以用其语法树的子树描述。语法树的一棵简单子树（只有单层的子树）的叶子结点组成的符号串是这个句型关于简单子树根结点的一个直接短语。语法树最左边的简单子树的叶子结点组成的符号串就是这个句型的句柄。例如：对于上面提到的文法GS，子串(R) 即为符号串(R),a)的句柄。三、程序运行效果为了方便理解后文的编程思路，我们先来看一下程序要达到的效果，如图1。图1 合法语句运行结果看了上面的程序运行结果，相信您已经对简单优先分析法有了一定的了解，下面就让我们来具体看一下简单优先文法分析器的设计思路吧。4、 设计思路（1）文法结构的定义 public struct MyData /文法结构定义(为方便分析将文法分为两部分) public string s1, s2; /s1为文法的非终结符部分（等号前），s2为后半部分 public int s2_length; /s2的长度（方便使用） public int N = 50; /最多能输入的文法条数 public MyData gam = new MyDataN; /将所有文法都保存在数组中 public int num = 0; /记录输入的文法条数（2）优先关系矩阵的求法 分析优先关系的定义，不难得到以下结果： 由知：两个连在一起的字符关系为“”； 由知：两个连在一起的字符，若后者P为非终结符，则前者L后者P及 其推导的首字符（有推导时）。 根据以上理解，不难看出第一种关系求解过程相对简单，后两种则相对复杂。为求解后两种关系，我们先来求解非终结符的推导的首、尾字符。这里我使用递归的方法求推导，并将要求解的字符保存在字符串中，下面是求解算法。 /此函数寻找ch的部分推导(可能有多个推导,但我们只需其中一部分)的第一个字符 private string SearchDerivation(char ch,int depth) string str=; if (depth 1) return str; for(int i=0;i= A & gami.s20 = Z) str+=SearchDerivation(gami.s20,depth-1); return str; /此函数寻找ch的部分推导(可能有多个推导,但我们只需其中一部分)的最后一个字符 private string SearchDerivation2(char ch,int depth) string str = ; if (depth 1) return str; for (int i = 0; i = A & ch1 = Z) str += SearchDerivation2(ch1,depth-1); return str; 现在我们可以开始求解优先关系矩阵。首先对表格进行初始化（用InitTable(window)进行初始化），对于文法GS： S:=(R)|a，R:=T ，T:=S,T|S 得到图2的效果。图2 初始化优先关系矩阵紧接着对文法进行逐条扫描，根据上面的三点理解求解优先关系并填入表中，以下为实现过程。其中SearchPosition(Form1 window,char ch1,char ch2) 用于寻找（ch1，ch2）在表中的位置，返回（ch1，ch2）的行号、列号，直接扫描表的行列进行比较即可实现该函数，这里就不累赘。for (int i = 0; i 1) for(int j=1;j=A&gami.s2j=Z) /默认大写字母为终结符 /这里判断是否为小于关系 string str = SearchDerivation(gami.s2j,num); for(int t=0;tstr.Length;t+) int row2 = SearchPosition(window, gami.s2j-1,strt).row; int col2 = SearchPosition(window, gami.s2j-1,strt).col; char tem2 = window.listView1.Itemsrow2.SubItemscol2.Text0; if(tem2=e|tem2=) window.listView1.Itemsrow2.SubItemscol2.Text = =A&gami.s2j-1= A & gami.s2j = Z) str2 += SearchDerivation(gami.s2j,num); for(int x=0;xstr1.Length;x+) for(int y=0;y) window.listView1.Itemsrow3.SubItemscol3.Text = ; else MessageBox.Show(不是简单优先文法！); （3）符号串的分析(流程图) 流程图中，S为符号栈，栈顶指针为i；TR为字符数组，用来存储输入符号串，j为下标。令#。在寻找句型的句柄时，总是先找到句柄的尾符号，然后再搜索其首符号。找到句柄后，就用它去查文法的产生式表，若存在匹配的文法（右部与句柄相同），则用该产生式的左部符号去替换符号栈中的这个句柄。最后如果Si为文法识别符号，而TRj为“#”，则表示输入符号串是文法的一个句子，算法终止，否则则是非法的语句。 具体实现过程的核心代码如下(其中OutPut() 用于输出分析过程，SearchGam() 用于搜索匹配的文法，由于二者实现过程比较简单，这里也不多说)： public void Analyse(Form1 window) /分析过程（填分析表） string S = #, TR = window.textBox3.Text + #; int num=1; while(true) if (SS.Length-1 = #) OutPut(window,num, S, ) OutPut(window,num,S,window.listView1.Itemsrow.SubItemscol.Text ,TR,入栈); num+; S+= TR0; TR=TR.Remove(0,1); continue; else /下面为向上规约 int k =S.Length-1; while(k0) int row2 = SearchPosition(window, Sk - 1, Sk).row; int col2 = SearchPosition(window, Sk - 1, Sk).col; if (Sk-1=#|window.listView1.Itemsrow2.SubItemscol2.Text = ,TR,SearchGam(gs2).s1+:=+SearchGam(gs2).s2); num+; S = S.Remove(k); S+= SearchGam(gs2).s1; continue; else if (SS.Length - 2 = # & TR0 = #) OutPut(window, num, S, OK, TR, OK); break; else OutPut(window, num, S, ERROR, TR, ERROR); break; 五、总结及感受 通过本次文法分析器的编写，我学到了文法分析方面的一些知识点，但更重要的是获取了一些编程方面的经验，同时也感受到了自己的不足点。在编程方面，我觉得没构思好就不要开始写，否则容易导致结构混乱，即便是最终将程序写出来了也不便于维护。同时我感觉自己在编程方面基本功不够，积累的知识点太少以致不能得心应手。算法可以随时思考，但知识点却得慢慢积累，因此我觉得以后要下大功夫积累知识点，同时将精力集中在某一方面，力求精一门，了解多门。时光匆匆，而任重道远。大学的日子不多了，但我所学到的东西确是少之又少，感觉远远不能满足社会的要求。然而知识一道，仰之弥高，钻