关于AOG语法分析中求左界符、右界符的算法.docx

关于AOG语法分析中求左界符、右界符的算法
AOG语法分析是一种通用的语法分析算法，被广泛应用于编译器和自然语言处理领域等等。在AOG语法分析中，求左/右界符是一项重要的任务。本文将会探讨AOG语法分析中求左界符、右界符的算法。
1.AOG语法分析基础
首先，我们需要了解AOG语法分析的基础知识。AOG全称为AugmentedOrderedGrammar，是一种增强有序文法。有序文法是指，对于任意一个语言生成的串，都必须从左到右一个一个字符地进行推导。AOG在此基础上增加了一个特殊字符$，称为句子结束符号，用来标记一个句子的结束。
AOG是由4元组$(V_T,V_N,P,S)$组成。其中，$V_T$是一个有限的终结符号集合，$V_N$是一个有限的非终结符号集合。$P$是从$V_T$和$V_N$的字符序列生成一个元素的关系，即一个规则集合。S是$V_N$中的起始符号。
可以用一组有序对$(w,i)$来表示每个符号，其中，$w$是一个字符，$i$是在句子中的位置。例如，$(a,2)$表示字符$a$在句子中的第2个位置。因为AOG是有序文法，所以需要按照这个顺序进行推导。
2.左/右界符的定义
在AOG语法分析中，左界符和右界符的定义如下：
左界符：对于句子中的一个位置$i$，从$i$开始往左第一个非终结符号的位置$j$称为位置$i$的左界符。
右界符：对于句子中的一个位置$i$，从$i$开始往右第一个非终结符号的位置$j$称为位置$i$的右界符。
左界符和右界符用来定位一个位置的符号在句子中的具体位置，从而对推导进行控制。
3.求左/右界符的算法
对于求左界符和右界符，主要有两种算法：自上而下算法和自下而上算法。下面将对这两种算法进行详细介绍。
3.1自上而下算法
自上而下算法是一种自顶向下的算法，从$S$符号开始进行分析。算法中涉及到两个关键点：Follow和First。
Follow：对于一个非终结符号$A$和一个字符串$w$，$Follow(A,w)$表示在$w$的后面可能出现在推导$A$的右部的终结符号的集合。
First：对于一个字符串$w$，$First(w)$表示字符串$w$的首字母可以是哪些终结符号的集合。
在求左界符和右界符时，自上而下算法可以采用下面的思路：
1）对于一个非终结符号$A$，可以根据其右部的符号集合来判断其左/右界符所处的位置。
2）对于左界符，可以按照下面的过程进行计算：
a)如果$A$的右部存在非终结符号，则从$A$的右部开始，按照左到右的顺序扫描每一个符号$B$。
b)对于符号$B$，如果它是终结符号，则返回$B$所在的位置为左界符。
c)如果$B$是非终结符号，则先计算出$B$的所有右界符。
d)如果$Follow(B,A.w)$中包含$w$中第$i$个字符，则返回$i$位置为左界符。
3）对于右界符，可以按照下面的过程进行计算：
a)如果$A$的右部存在非终结符号，则从$A$的右部的结尾开始，按照右到左的顺序扫描每一个符号$B$。
b)对于符号$B$，如果它是终结符号，则返回$B$所在的位置为右界符。
c)如果$B$是非终结符号，则先计算出$B$的所有左界符。
d)如果$First(w[i:])$中包含$B$的所有左界符，则返回$B$左界符所处的位置为右界符。
自上而下算法是AOG语法分析中常用的一种算法，但它也存在一些问题。由于它是自顶向下的，所以在检测非正则文法时会出现退化。另外，求左界符和右界符的算法可能涉及到一些歧义问题，需要格外注意。
3.2自下而上算法
自下而上算法是一种自底向上的算法，从输入符号开始进行分析，逐步地将符号合并成更大的结构。算法中涉及到两个关键点：Shift和Reduce。
Shift：将一个终结符号移入栈中。
Reduce：将栈中的若干个符号弹出，代表它们可以被推导成一个更大的结构。
在求左界符和右界符时，自下而上算法可以采用下面的思路：
1）对于每个输入符号，先将其移入栈中。同时将每个位置的左/右界符设置为它本身。
2）从栈底往顶部扫描，找出所有的规约位置。规约位置是指，栈顶的符号可以和栈中的一些符号合并，形成一个更大的结构。
3）对于每一个规约位置，采用Reduce操作将栈中的符号合并，形成更大的结构。
4）对于每一个被Reduce的符号，计算它的左/右界符。
5）对于左界符，它等于该符号的最左边的输入符号的左界符。
6）对于右界符，它等于该符号的最右边的输入符号的右界符。
自下而上算法克服了自上而下算法中退化和歧义问题的缺陷，因此被广泛应用。但是它也存在一些问题，比如运算符优先级、二义性等问题需要格外注意。
4.总结
本文介绍了AOG语法分析中求左界符和右界符的算法，主要涵盖了自上而下算法和自下而上算法两种方式。在实际应用中，需要根据具体情况选择合适的