LL(1)分析法的功能是利用LL(1)控制程序根据显示栈栈顶内容、向前看符号以及Ll(1)分析表,对输入符号串自上而下的分析过程。可通过消除左递归、提取左因子把非LL(1)文法改造成LL(1)文法。在LL( 1) 预测分析程序设计过程中,最重要的两个问题是预测分析表的构造和相关数据结构的设计。而预测分析表的构造首先必须计算文法每个非终结符的FIRST集和FOLLOW集。数据结构和算法实现具体实现如下:
1、数据结构:
数组A实现分析栈,数组B存储剩余分析串;一维数组V1存放文法终结符,一维数组V2存放文法非终结符。将产生式类型定义为结构体变量。
2、算法:
a、首先将‘ # ’压入堆栈中, 将开始符号S 也压入堆栈中,读取第一个输入符号到a.
循环执行b--d:
b、栈顶符号弹出放入X 中,如果X 为终结符号:当X = = a ! =‘ # ’时,表明成功匹配a 符号,然后读取下一个符号到a ,否则出错;当X = = a =‘ # ’时,分析结束,接受句子,跳出循环.
c、如果X ! = a ,进行出错处理.
d、如果X 为非终结符号, 则查分析表M :如果M[ X , a ]为空, 进行出错处理; 如果M [X , a ]=‘X1 X2 X3...Xn’, 则将右部Xn...X2 X1 反序压入堆栈中.
本程序分析的文法:
e// E -> TG R(O)
g// G -> +TG R(1)
g1// G -> ε R(2)
t// T -> FS R(3)
s// S -> *FS R(4)
s1// S -> ε R(5)
f// F -> (E) R(6)
f1// F -> i R(7)
g2// G -> -TG R(8)
s2// S -> /FS R(9)
分析句子:E->TG->FSG->iSG->i/FSG->i/iSG->i/iG->i/i-TG->i/i-FSG->i/i-iSG->i/i-iG->i/i-i
手工构造的预测分析表:
|
i |
+ |
* |
( |
) |
- |
/ |
# |
E |
R(0) |
Error |
Error |
R(0) |
Error |
Error |
Error |
Error |
G |
Error |
R(1) |
Error |
Error |
R(2) |
R(8) |
Error |
R(2) |
T |
R(3) |
Error |
Error |
R(3) |
Error |
Error |
Error |
Error |
S |
Error |
R(5) |
R(4) |
Error |
R(5) |
R(5) |
R(9) |
R(5) |
F |
R(7) |
Error |
Error |
R(6) |
Error |
Error |
Error |
Error |
【上篇】关于多层结构的系统中,修改数据库问题
【下篇】UserName showing up as DomainName\UserName instead of Full Name in SharePoint 2010 |