等位K-表达式解码算法
输入:等位K-表达式K,制导文法G=<T,N,R,S>
输出:表达式树T
步骤:
1设置队列Q为空;
2p←0;{定义K的下标指针}
3T←S;{S是文法起始符号}
4将T添加到队列Q尾部;
5while Q 不空 do
6 从Q头部取出一个元素n;
7 找到规则r=Kpn=n→α;
8 p←p+1;
9 用规则r对节点n进行扩展;{构建语法树结构}
10 将规则r右部的非终结符依次添加到Q尾部;
11end while
12return T;
2p←0;{定义K的下标指针}
3T←S;{S是文法起始符号}
4将T添加到队列Q尾部;
5while Q 不空 do
6 从Q头部取出一个元素n;
7 找到规则r=Kpn=n→α;
8 p←p+1;
9 用规则r对节点n进行扩展;{构建语法树结构}
10 将规则r右部的非终结符依次添加到Q尾部;
11end while
12return T;
等位K-表达式是K-表达式的扩展概念,主要是为了使得支持多个非终结符的情况,是对GEP只能支持一个非终结符的拓展