文章目录
优先函数树形构造法
操作步骤
举例操作
自己的思考
参考资料


        这里我介绍的是一种简单的方法，不是书本的那个方法。是我后面那个参考资料上面的作者想出来的。因为这个是在知网上面找到的，是1997年的一篇文章。我就是一个总结，然后画几个比较清楚的图而已（因为从知网上下载的的pdf上面的图有点不太清楚）

优先函数树形构造法
        我们教材上面的就是陈火旺老师的那本，然后方法就是找节点。这个方法虽然简单，但是操作起来的却有些麻烦，因为我们作图的时候，难免就会看不清楚，或者数错。下面介绍的树形构造法就可以避免这个问题，仅仅只需要根据优先矩阵就可以得出正确结果。
操作步骤

对于一个优先表先做如下几个步骤（假设优先函数存在）

1 ) 对于f(a)对应行中“a>=b 的所有终结符b , 把g(b)作为f(a) 的子树。

2) 对g(a) 对应列中有b <=a 的. 把f(a) 作为g(b)的子树.

3 ) 对f(a)重做第( 1 ) 步, 对g(b) 重做第( 2 ) 步。

4) 重复出现的f或g , 作记号不再对其执行第( 1) , ( 2) 步

方向图

5) 构造f(a)函数时, 以f(a) 为根结点, 按( 1 ) ,(2 ),( 3),( 4) 执行.

6) 构造g(b)函数时, 以g(b) 为根结点, 按(2 ) ,( 1 ) , ( 3 ) , ( 4 ) 执行.

按照以上5步先画出树，然后查树的节点数（包括根节点，做记号的不查），即可以得到根节点的优先函数值。

但是我觉得这个操作步骤2有点问题。应该是b>=a的时候，就把f(a)作为g(b)的子树。我也自己做了实验，发现这样做才是正确的。不过也可能是我没有理解原作者的意思。反正，就目前看来，我都是按照如果b<=a，就把f(a)作为g(b)的子树。

所以，下面我举例的例子，第(2)步都是按照“b>=a的时候，就把f(a)作为g(b)的子树”这个来做的。

举例操作
        假如现有一个优先矩阵是这样的：这个例子是《编译原理》陈火旺老师（下面我说的教材，没有特别说明也是指的这本教材）那本书上面的。在90页。



那么我们现在用树形构造法来试试怎么得到这个优先函数。因为最后的答案是去掉了 i 和 # 之后得到的，所以我下面也将不会考虑 i 和 # 号。至于为什么不考虑 i 和 #,，就是因为这两个不是算符，我们算符优先函数主要针对的就是算符直接的优先级。但是优先关系矩阵中是给出了 i 和 # 与其他算符之间的优先关系的。我这里其实是有一个疑问的：因为在优先函数这里没有 i  的优先关系，那么在使用优先函数来分析一个句子是不是这个文法定义的合法的句子的时候，那么什么时候该移进这个 i 呢？希望知道的小伙伴可以在下面留言，我们讨论一下。
        计算f(+)的优先函数值。

从优先矩阵中可以得到：’+‘ >= 的算符有;’+’,’)’,’#'三个。因为不考虑i 和 #（下面就不提醒这一点了），所以f(+)的孩子节点有两个，分别是g(+)和g()),如下图所示。


现在就来找g(’+’) 的子树。我这里还是采用的是如果b>=a，就把f(a)作为g(b)的子树。从优先表中可以看到的就是’+‘ >= 的算符有：’(’。注意，我这里说的’+‘是g(’+‘)，也就是从’+‘那一列中寻找。

所以，g(’+’)的子树就是f(’(’);
然后找到g(’)’)  >=的算符：

但是f(’(’)已经出现过了（作为g(’+’)子树出现的），所以就不用画出来了。
然后就是寻找f(’(’) >=的算符。但是g(’)’)也已经出现过了，所以这里也不用画出来了。
最后每一个节点我们都已经检查过了，没有可以重新添加的了。也就是趋于稳定了（编译原理里面好多都是这样子的，得使所有都不再变化的时候，算法就算结束了）。我们数一下节点的个数，就是4个，和书本95页给出的答案是一样的。

        同理，g(’+’)的树也可以这样画出来。我就给出最后的树，就不一一分析了。


自己的思考
        本质上书本上的画图和这里的画一颗树，都是优先级高的指向优先级低的，所以入度为0的节点，给的优先函数值应大一点，出度为0的，给出的优先函数值应该小一点。
        上面提到的这个简单的方法其本质善和我们教材上的方法是一样的。你可以将教材上的方法中的图给截取一部分出来。例如，你截取以g(’+’)作为顶点的树去看，发现就是和我上面画的一样。
        还有注意的一点就是：我们求出一组优先函数之后，就可以构造出无数组优先函数。所以，如果你求出来的和参考答案给出的不是一样的，也不一定是你错了。只要你的优先函数之间的关系和参考答案上给出的关系是一样的就可以了。
参考资料
构造优先函数的更简单方法_树型构造_潘群娜

这个知网上我找到的一篇关于这个优先函数构造比较简单的方法，如果大家对上面的博客解释的不太清楚的话，可以去知网上看这个原作者写的文章。

简单的方法，计算优先函数
手动计算比较麻烦，而且容易出错。
根据定义，用计算机实现，快捷方便，准确可扩充
 
// 0505优先函数.cpp : 定义控制台应用程序的入口点。
//
/*
使用说明：
1、改#define  N  的值
2、改char M[N+1][N+1]的值
3、改F[N] G[N] 的值
4、当最后两次输出不同时，说明优先函数没有收敛，需增加训练次数。
	（这种情况多是不存在优先函数，要注意哦）
*/

#include "stdafx.h"
#include <stdio.h>
#include <iostream>

using namespace std;

//#define  N 7  //终结符的个数
//#define  N 4  //终结符的个数
//#define  N 6  //终结符的个数
//#define  N 2  //终结符的个数
#define  N 8  //终结符的个数

//int F[N]={1,1,1,1,1,1,1};//f的初始值
//int G[N]={1,1,1,1,1,1,1};//g的初始值

//int F[N]={1,1,1,1};//f的初始值
//int G[N]={1,1,1,1};//g的初始值

//int F[N]={1,1,1,1,1,1};//f的初始值
//int G[N]={1,1,1,1,1,1};//g的初始值

// int F[N]={1,1};//f的初始值
// int G[N]={1,1};//g的初始值

int F[N]={1,1,1,1,1,1,1,1};//f的初始值
int G[N]={1,1,1,1,1,1,1,1};//g的初始值

//算符优先关系表     》1  《 2   = 0
/*
char M[N+1][N+1]={
	{' ',	'+',	'*',	'|',	'i',	'(',	')',	'#'},
	{'+',	'1',	'2',	'2',	'2',	'2',	'1',	'1'},
	{'*',	'1',	'1',	'2',	'2',	'2',	'1',	'1'},
	{'|',	'1',	'1',	'2',	'2',	'2',	'1',	'1'},
	{'i',	'1',	'1',	'1',	' ',	' ',	'1',	'1'},
	{'(',	'2',	'2',	'2',	'2',	'2',	'0',	' '},
	{')',	'1',	'1',	'1',	' ',	' ',	'1',	'1'},
	{'#',	'2',	'2',	'2',	'2',	'2',	' ',	'0'}
};//来自课本P111，参考P118
*/
/*
char M[N+1][N+1]={
	{' ',	'i',	'*',	'+',	'#'},
	{'i',	' ',	'1',	'1',	'1'},
	{'*',	'2',	'1',	'1',	'1'},
	{'+',	'2',	'2',	'1',	'1'},
	{'#',	'2',	'2',	'2',	'0'},
};//来自课本P119
*/
/*
char M[N+1][N+1]={
	{' ',	'a',	'^',	'(',	')',	',',	'#'},
	{'a',	' ',	' ',	' ',	'1',	'1',	'1'},
	{'^',	' ',	' ',	' ',	'1',	'1',	'1'},
	{'(',	'2',	'2',	'2',	'0',	'2',	' '},
	{')',	' ',	' ',	' ',	'1',	'1',	'1'},
	{',',	'2',	'2',	'2',	'1',	'1',	' '},
	{'#',	'2',	'2',	'2',	' ',	' ',	'0'},
};//来自课本P122的第1题
*/
/*
char M[N+1][N+1]={
	{' ',	'a',	'b',},
	{'a',	'0',	'1',},
	{'b',	'0',	'0',}
};//来自课本P120
*/
char M[N+1][N+1]={
	{' ',	'o',	'a',	'n',	'(',	')',	't',	'f',	'#'},
	{'o',	'1',	'2',	'2',	'2',	'1',	'2',	'2',	'1'},
	{'a',	'1',	'1',	'2',	'2',	'1',	'2',	'2',	'1'},
	{'n',	'1',	'1',	'2',	'2',	'1',	'2',	'2',	'1'},
	{'(',	'2',	'2',	'2',	'2',	'0',	'2',	'2',	' '},
	{')',	'1',	'1',	' ',	' ',	'1',	' ',	' ',	'1'},
	{'t',	'1',	'1',	' ',	' ',	'1',	' ',	' ',	'1'},
	{'f',	'1',	'1',	' ',	' ',	'1',	' ',	' ',	'1'},
	{'#',	'2',	'2',	'2',	'2',	' ',	'2',	'2',	'0'}
};//来自课本P121

void construction()//构造优先函数
{
	for (int i=1;i<=N;i++)
	{
		for (int j=1;j<=N;j++)
		{
			if (M[i][j]=='1' && F[i-1]<=G[j-1])
			{
				F[i-1]=G[j-1]+1;
				break;
			}
			if (M[i][j]=='2' && F[i-1]>=G[j-1])
			{
				G[j-1]=F[i-1]+1;
				break;
			}
			if (M[i][j]=='0' && F[i-1]!=G[j-1])
			{
				if (F[i-1]<=G[j-1])
				{
					F[i-1]=(F[i-1]>G[j-1]?F[i-1]:G[j-1]);
				}
				else
				{
					G[j-1]=(F[i-1]>G[j-1]?F[i-1]:G[j-1]);
				}				
				break;
			}
		}
	}
}

void outputM()//输出算符优先关系表
{
	for (int i=0;i<=N;i++)
	{
		for (int j=0;j<=N;j++)
		{
			printf("%c  ",M[i][j]);
		}
		printf("/n");
	}
}
void outputFG()//输出优先函数f和g
{
	printf("/n优先函数 f 的值：");
	for (int i=0;i<N;i++)
	{
		printf("%d ",F[i]);
	}
	printf("/n优先函数 g 的值：");
	for (int i=0;i<N;i++)
	{
		printf("%d ",G[i]);
	}
	printf("/n");
}
int _tmain(int argc, _TCHAR* argv[])
{
	outputM();
	outputFG();
	for (int count=1;count<=10;count++)//最多计算的次数，未设置结束条件（即F和G收敛）
	{
		construction();
		printf("/n第%d次construction之后的 f 和 g 如下：",count);
		outputFG();
	}

	system("pause");
	return 0;
}

优先函数实现表达式计算





左/右
+
*
(
)
i
#




+
·>
＜·
＜·
·>
＜·
·>


*
·>
·>
＜·
·>
＜·
·>


(
＜·
＜·
＜·
＝
＜·



)
·>
·>

·>

·>


i
·>
·>

·>

·>


#
＜·
＜·
＜·

＜·



由优先表构造优先函数




优先函数
+
*
(
)
i
#




f
6
8
2
8
8
1


g
4
7
9
2
9
1


本程序使用C语言编写

支持整数加减乘除带括号的运算

核心部分和数据结构中利用栈实现表达式运算几乎相同

程序的难点在于优先级＜、＝、＞分类讨论
#include<stdio.h>
#include<stdlib.h>
#include <string.h>
//优先函数
int fplus = 6;
int gplus = 4;

int fmul = 8;
int gmul = 7;

int fleft = 2;
int gleft = 9;

int fright = 8;
int gright = 2;

int fi = 8;
int gi = 9;

int fpound = 1;
int gpound = 1;

char expression[128];
int flag = 1; 

void Error()
{
    printf("错误\n");
    exit(0);
}
    
void Input()
{
	//char over[] = {'#', '\0'};
    printf("请输入表达式，以#结尾："); 
    gets(expression); 
	//printf("Input: %s\n",expression);
}

int f(char opt)
{
    if(opt == '+' || opt == '-')
    {
		return fplus;
    }
    else if (opt == '*' || opt == '/')
    {
        return fmul;
    }
    else if (opt == '(')
    {
        return fleft;
    }
    else if (opt == ')')
    {
        return fright;
    }
    else if (opt == 'i')
    {
        return fi;
    }
    else if (opt == '#')
    {
        return fpound;
    }
    return -1;
}
    
int g(char opt)
{
    if(opt == '+' || opt == '-')
    {
        return gplus;
    }
    else if (opt == '*' || opt == '/')
    {
        return gmul;
    }
    else if (opt == '(')
    {
        return gleft;
    }
    else if (opt == ')')
    {
        return gright;
    }
    else if (opt == 'i')
    {
        return gi;
    }
    else if (opt == '#')
    {
        return gpound;
    }
    return -1;
}
    
int In(char num)
{
    if(num == '0' ||num == '1' || num == '2' || num == '3' || num == '4' || 
	   num == '5'|| num == '6' || num == '7' || num == '8' || num == '9')
	   return 1;
    else
        return -1;
}
    
int Operation(int a, char opt, int b) 
{
	switch(opt)
	{
		case '+': return a + b; 
		case '-': return a - b; 
		case '*': return a * b; 
		case '/': return a / b; 
		default : return 0;
	} 
} 

int main() 
{
	int index_e = 0;	// 字符串下标
	int	index_oprt = 0; // 算符栈下标
	int index_opnd = 0; // 算量栈下标
    int Sn[100];
	char Sp[100];
	int num1;
	int num2;
	char temp[100];
    Sp[0] = '#';

    Input();
	//printf("算符栈: %s\n",Sp);
    while( flag == 1 )
    {
		int t = 0;
        if( Sp[index_oprt] == '#' && expression[index_e] == '#' )
        {
			//printf("都为#，结束\n");
            flag = 0;
        }
        else if(Sp[index_oprt] == '(' && expression[index_e] == ')')
        {
			//printf("读到括号\n");
            index_oprt--;
            index_e++;
        }
        else if(In(expression[index_e]) == 1)
        {
			//printf("读到数字\n");
            while(In(expression[index_e]) == 1)
            {
                temp[t] = expression[index_e];
				t++;
                index_e++;
            }
			//printf("temp: %s\n",temp);
			//atof()是把字符串转换成double
            Sn[index_opnd++] = atof(temp);
			//printf("number %d\n",Sn[index_opnd-1]);
            //清空temp
			for(int m=0; m<100; m++)
				temp[m] = '\0';
        }
        else if(f(Sp[index_oprt]) < g(expression[index_e]))
        {
			//printf("%d %d\n",f(Sp[index_oprt]),g(expression[index_e]));
			//printf("小于\n");
            Sp[index_oprt + 1] = expression[index_e];
            index_oprt++;
            index_e++;
			//printf("%c 入栈\n",Sp[index_oprt]);
		}
        else if(f(Sp[index_oprt]) > g(expression[index_e]))
        {
			//printf("大于\n");
			//出栈两个数
            num2 = Sn[index_opnd - 1];
			index_opnd--;
            num1 = Sn[index_opnd - 1];
            index_opnd--;
			//算符栈出一个，算完了结果再入算量栈
			Sn[index_opnd] = Operation(num1, Sp[index_oprt], num2);
            index_opnd++;
            index_oprt--;
        }
        else
        {
            Error();
        }
    }
    printf("表达式的值为：%d\n", Sn[0]);
	return 0;
}

运行截图：

自底向上分析方法，也称移进-归约分析法。
实现思想：

对输入符号串自左向右进行扫描，并将输入符逐个移入一个栈中，边移入边分析，一旦栈顶符号串形成某个句型的句柄时，就用该产生式的左部非终结符代替相应右部的文法符号串，这称为归约。
重复这一过程，直到栈中只剩文法的开始符号时，则分析成功，也就确认输入串是文法的句子。





5.1  自底向上优先分析法概述

5.2  简单优先分析法















5.3  算符优先分析法