编译原理精要

admin

1、短语即相对于同一个结点的叶子串，末端结点的叶子串即直接短语。短语是句型的，也是规则的。  
2、若AaAb|ε,则L(A)={ anbn|n≥0}  
3、正规集即正规式所表达的各元素集合.若正规式是闭包,则正规集必含ε.  
4、正规式变形规则: |视为+,•视为*，ε视为1，*视为幂n。  
5、正规文法变正规式：  
顺序规则  AxB,By A=xy  
循环规则  AxA|y A=x*y  
分支规则 Ax,Ay A=x|y  
若正规式为Ax*y,则化为正规文法为AxB,Ay,BxB,By  
6、确定的有穷自动机 DFA(状态集,输入字符集,转换集,初态,终态)  
DFA最小化合并法:  
○1先分成终态集和非终态集；  
○2当输入同一符号后的目的态是已分开的，则源态也分开；  
○3未分开的合并为一。  
7、不确定的有穷自动机NFA,NFA中默认:状态到自身有ε弧.  
NFA确定化方法:  
○1定初态=ε-closure(初态)，设定代号。  
○2目的态=ε-closure(Move(原态),输入字符)，原态从初态开始。  
○3末态为Φ则不画.  
○4终态为含原终态者全部集合.  
8、First(α)=α能推出的右部字串首个终结符的集合,此终结符可为本身首终结符.  
Follow(A)＝与A同级之后的字符的开始符号集中的非ε元素.若有ε元素，则也包括A上级的follow集  
Select(Aα)= α所展符号串之首字符的集合.  
9、LL(1)文法的判别:   
○1求能推出ε的非终结符:若右部为ε,则为是；以ε代其左部使其它的左部产生ε，则其它的也为是。  
○2计算First集  
○3计算Follow集  
○4计算Select集  
若对于同一个非终结符A有Select(A α)∩Select(A β)=Φ,(α、β不同时* —>ε)就是LL(1)文法.  
10、若AtB，则有f(A,t)=B，即状态A遇t字符转化为状态B。若Zε，则Z为终态。  
11、提取左公共因子：若Aab|ac，则化为Aa(b|c)，以A’代括号项，变为AA’，A’b|c，使之不含括号。如果某产生式右部以非终结符开始，则以与该非终结符相同的左部的产生式代替之。将结果中的不可到达的符号删去。  
12、消除直接左递归：如果SSa|b，则化为SS’,S’aS’|ε。且S＝ba*.  
13、构造预测分析表：列为非终结符，行为终结符。如果终结符为非终结符产生式的select集，则将该产生式右部在表中行列交叉处写上。  
14、对符号串的分析过程：○1将#和开始符号入分析栈，○2栈顶符与剩余输入串首字符比较，○3不同则写出栈顶符产生式，其右部代之入栈。○4相同则匹配，栈顶符和输入符都删去。○5重复○2。  
15、FIRSTVT(B)=B能推出的所有式子中最先出现的终结符。  
LASTVT(B)=B能推出的所有式子中最后出现的终结符。  
小写小于大写的FIRSTVT;大写LASTVT大于小写。谁先出现谁在左边。  
16、算符优先表构造：计算每个非终结符的FIRSTVT和LASTVT集，然后找出大写和小写相邻的部分，确定小写与大写FIRSTVT和大写LASTVT与小写的优先关系，填表。  
17、算符优先算法：始终保持栈顶符号的优先级是最高的。当遇到低者欲进时栈顶者出。  
18、活前缀的求法：将各产生式在尾部依次编号，用开始符号推导出该符号串，则在最左处编号的左边的所有字符串都是活前缀。  
方程法：利用式子LC(A)=LC(左部符)｛A前串｝的并集，列出各产生式方程利用正规式代数化简，注意：若[A]=a+[A],则A=ab*，将所求结果右边连接上各产生式的右部即是活前缀。  
19、LR(0)项目集规范族构造：从S’出发，若•后为大写，则包括其产生式，直到•后为小写为止。然后依各•后字符为分支，该字符认为是输入符，此符所在式成为新的状态之首式，然后规则重复S’。直到诸•皆到末尾。  
20 、LR(0)分析表构造：actino列为行前产状态遇到列上的符号后转向表中的Sj，其中j为目的态。•在最末者遇任一符号，则填ri，i表示在文法中的产生式的编号。S’??•遇#，则填acc表示接受。  
Goto列为行前状态遇列上的非终结符时转向的状态号。  
LR(0)分析过程为：状态号和输入符各自入栈，  
当栈顶状态遇到下一个输入符时转向的状态Si填入action列中，状态号i入栈，重复之。若可归约，则填ri，状态号出栈，栈中符改为归约的非终结 符，i为文法工产生式编号，相应的goto列中填入下一行当中的改后的非终结符与其相邻符号形成句柄又可归约时用的产生式所在的状态号。  
21、SLR(1)的分析表与LR(0)的分析表构造法类似，仅在含有冲突的项目集中分别处理。即遇•后为终结符则转向另一状态，其它情况则归约以ri。  
22、LR(1)分析：向前搜索符是指与左部同级（即为同在•在该左部符左之式右部）的其后字符串（包括其搜索符）的首字符。当状态遇到向前搜索符时才转向另一状态或归约。  
23、LALR(1)分析：同心集为产生式相同，而搜索符不同的诸式。LALLR（1）即是将LR(1)中的同心集合并成一个项目集。  
24、略

羚守硕

这个贴要跟~~~~先做个记号！~
股票网，http://www.bf8868.com，股票知识，股票入门，RO私服http://www.66ro.com，奇迹私服http://www.95mu.com/，热血江湖私服http://www.66rxjh.com/，天龙八部私服http://www.bflook.com/，魔兽世界私服http://www.wow01.com/，天堂2私服http://www.398q.com/
楼主加油!!!!!11~

xylichenjun

高手能帮个忙吗？我在写c代码时要跳出很深的循环，发现用goto很好用。当某个条件成立时需要程序回到开始处执行，用goto也很好用，但是我同事说goto是c语言的早期语法，不知道现在的编译器会怎么处理，不安全。请问是这样吗？如果是这样的话，还有其他的方法解决我提出的功能吗？谢啦大侠！

8a114

楼下的要时常想念楼上的
要不会下雨的哦

Vivian

路过.....帮顶....支持一下...............

Vivian

路过.....帮顶....支持一下...............

泉泉437

嗯....

潇湘龙极

好东西啊.....

lg123lg

C语言禁止使用goto语句作用到另一个函数

祈爱非爱

收藏收藏~